ДС17о07-Основы-анализа-алгоритмов (1238902)
Текст из файла
Carnegie MellonОсновы анализаалгоритмовАлгоритмыи алгоритмические языкиgoo.gl/c8pyqxЛекция7,17 октября,2017Лектор:ДмитрийСеверов,кафедраинформатики608КПМdseverov@mail.mipt.ruhttp://cs.mipt.ru/wp/?page_id=60771ДЛИННЫЙФАКТОРИАЛn!=n(n −1) ... 3 2 110!=10 9 ... 3 2 1=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Алгоритм - точноепредписание,задающеепроцесспреобразованияисходныхданныхврезультаты.¢Свойства:§§§§§§РезультативностьКонечностьОднозначностьМассовостьДетерминированностьЭффективность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– наихудшийслучайTv =mindÎD T– наилучшийслучайŤ = Σ t / |T| – среднийслучай23КлассификацияалгоритмовповидуфункциитрудоёмкостиПараметрически-зависимые(порядко-независимые)Fd =f(n);T^=Tv =Ť¢Порядко-зависимые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)f(n)иg(n):$c,n0:"n>n0c*g(n)≥f(n)>0àf(n)=O(g(n))Пример: F(x) = 4x2+ x = O(x2)27Сравнениевременвыполненияалгоритмовn=10n=103n= 106Log2 n0,2 сек0,6 сек1,2 секn0,6 сек11минмин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}
