ДСо18-07-Основы-анализа-алгоритмов (1238946)
Текст из файла
Carnegie MellonОсновы анализаалгоритмовАлгоритмыи алгоритмические языкиgoo.gl/c8pyqxЛекция 7, 19 октября, 2018Лектор:Дмитрий Северов, кафедра информатики 608 КПМdseverov@mail.mipt.ruhttp://cs.mipt.ru/wp/?page_id=60771ДЛИННЫЙ ФАКТОРИАЛn! = n10! = 10(n − 1)9......332211 = 3628800,сумма цифр числа 10! есть …3 + 6 + 2 + 8 + 8 + 0 + 0 = 27.Найдите сумму цифр числа N!20k2*dm-1dm-1…d3d2d1k1*dm-1…k1*d3k1*d2k1*d1…k2*d3k2*d2k2*d1k2*dm-1 + k1*dm…0k2*d0 + k1*d130k2*dm-1dm-1…d3d2d1k1*dm-1…k1*d3k1*d2k1*d1…k2*d3k2*d2k2*d1k2*dm-1 + k1*dm…0k2*d0 + k1*d14ДЛИННОЕ 2NКакова сумма цифр числа 2n?0 £ n £ 10001000k2 ≈10k ≈ 1000*lg2 k ≈ 3025Конкретно6Конкретно7Абстрактно8Абстрактно910АСТЕРОИДЫ11Три астероида летят в космическом пространстве. Каждый изних движется с постоянной скоростью и в постоянномнаправлении.
На всех трех астероидах существуют разумныеформы жизни. В обычное время обитатели астероидов понемногуразвиваются, осваивают новые технологии и готовятся выйти вкосмическое пространство. Но все радикально меняется, когда всетри космических тела находятся на одной прямой. Когдапроисходят такие "затмения", жители астероидов начинаютчувствовать себя неуютно. Они видят только одно из двухпривычных тел на небосводе, и это порождает чувство какой-тонеуверенности. Гуманоиды не могут заниматься привычнымиделами, некоторые даже начинают поговаривать оприближающемся конце света. О полетах в космос в такиемоменты можно забыть: на всех трех астероидах разом случаетсяэкономический кризис. Ваша задача - определить, сколько ещетаких кризисов случится в будущем.
Именно во время такихкризисов и приходится допускать к управлению биржами системытипа "SkyNet"12Замечание 1. Астероиды настолько малы, что их можно считатьточками. Чтобы слишком не усложнять анализ, будем считать, чтоастероиды вполне могут оказываться одновременно в одной и тойже точке пространства. При этом они не сталкиваются, а пролетаютсквозь друг друга. Если угодно, можно думать, что на самом делеони просто проходят друг от друга на незначительном расстоянии.Замечание 2.
Под "будущим" понимаются все моментывремени начиная с начала наблюдения. Само начало наблюдениятоже считаем частью "будущего".Вход. Входной файл содержит три строки, по одной на каждыйастероид. Каждая строка содержит 6 чисел X, Y, Z, Vx, Vy, Vz.Первые три числа задают координаты астероида в момент началанаблюдения, следующие три числа - координаты его вектораскорости. Все числа целые и не больше 20.Выход.
Одно целое число, равное количеству экономическихкризисов начиная с момента наблюдения. Если количество"кризисных моментов" бесконечно, выведите число -1.13(rC-rA)(rB-rA) + t*[(rC-rA)(vB-vA)+(vC-vA)(rB-rA)] + t2*(vC-vA)(vB-vA)=0X + t * Y + t2 * Z = 0Ri = ri + t* viAC = RC – RAAB = RB – RAAC ´ AB = 014151617Основы анализа алгоритмов18Алгоритм - точное предписание,задающее процесс преобразованияисходных данных в результаты.Свойства:1. Результативность2. Конечность3. Однозначность4. Массовость5. Детерминированность6. Эффективность19ОбозначенияM – набор машинных инструкций,составляющих программу;S – память для хранения промежуточныхрезультатов;d(n) – набор входных данных;D(n) = {d(n)} – множество всевозможныхнаборов входных данных;Т = {t} – время выполнения программы;20Допущениякаждая машинная команда выполняетсяне более чем за фиксированное время;¢рассматриваем правильные и финитныеалгоритмы, т.е.
алгоритмы, дающиеединственное решение общей проблемы¢21В силу сделанных допущенийДля любого начального набора данныхалгоритм выполняет не более, чем конечноеколичество «элементарных» операцийабстрактной машины.¢ Под трудоемкостью Fd алгоритма для данногонабора начальных данных – d(n), будемпонимать количество «элементарных»операций (ºвремя их выполнения),совершаемых алгоритмом для решенияконкретной задачи, в данной формальнойсистеме.¢22Цена выполнения программыt = c1* d(n) + c2 * M + c3 * S,здесь ci(d(n)) – «веса» ресурсовT^ = maxdÎD T – наихудший случайvT = mindÎD T – наилучший случайŤ = Σ t / |T| – средний случай23Классификация алгоритмов по видуфункции трудоёмкостиПараметрически-зависимые(порядко-независимые)vFd = f(n); T^ = T = Ť¢Порядко-зависимыеFd = f(d,n); Tv(d,n) £ Ť(n) £ T^(d,n)¢24Асимптотически точные оценки¢Q (тета)c2g(n)f,gf(n)c1g(n)f(n) и g(n): $c1,c2,n0:"n>n0c2*g(n)£f(n)£c1*g(n) àf(n) = Q( g(n) )nn0Пример: F(x) = 4x2+ sin(x) = Q(x2)25Асимптотические оценки снизу¢Ω (Омега)F(n)cg(n)f(n) и g(n): $c,n0:"n>n0f(n) £ c*g(n) £ 0 àf(n) = Ω( g(n) )Ex: Ω( x*ln(x) ) – класс функций, которыерастут не медленнее, чем x*ln(x)26Асимптотические оценки сверху¢O (О большое)cg(n)f(n) и g(n): $c,n0:"n>n0c*g(n)≥f(n)>0 àf(n) = O( g(n) )f(n)Пример: F(x) = 4x2+ x = O(x2)27Сравнение времен выполненияалгоритмовn=10n=103n= 106Log2 n0,2 сек0,6 сек1,2 секn0,6 сек1 мин16,6 часn26 сек16,6 час1902 года2n1 мин10295 лет10300000 лет28Задача ИосифаПусть n человек, стоящие по кругу, считаются(начиная с первого) считалкой из m слов.Человек, на котором считалка заканчивается, выбывает, круг смыкается, а счет продолжается счеловека, следующего за выбывшим.Напишите программу, выводящую номера трехчеловек, выбывших последними, в порядке ихвыбывания.29Результаты для m=3nпоследнийпредпоследнийПред предпоследний11221321341425425615274158748917210410511728121051130Задача Иосифаm= 3453530201714118414038361302214220228475181851414124104021022857167261032131017141124152522191613103420312829262320256Номер последнего выбывшего40nF(1)=1F(1)=1; F(n)=( F(n-1) + m )mod n31РЕШЕНИЕ 1:АНАЛИЗ ЗНАЧЕНИЙ ЭЛЕМЕНТОВМАССИВА3233РЕШЕНИЕ 2:УДАЛЕНИЕ ИЗ МАССИВАВЫБЫВШИХ ЭЛЕМЕНТОВ34Число сравнений: ~ m * n * ln n35РЕШЕНИЕ 3:ХРАНЕНИЕ В МАССИВЕ ИНДЕКСОВСОСЕДНИХ ЭЛЕМЕНТОВ36Число сдвигов: ~ n * n / 437РЕШЕНИЕ 4:ДИНАМИЧЕСКИ СОЗДАВАЕМЫЕСТРУКТУРЫ383940РЕШЕНИЕ НА ОСНОВЕПОСТРОЕНИЯ РЕКУРРЕНТНОГОСООТНОШЕНИЯ4142.
Характеристики
Тип файла PDF
PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.
Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
