Ўвядзенне ў аналіз алгарытмаў

Original: http://aofa.cs.princeton.edu/home/

Людзі, якія аналізуюць алгарытмы маюць падвойнае шчасце. Перш за ўсё яны адчуваюць відавочную прыгажосць элегантных матэматычных мадэляў, якія атачаюць элегантныя вылічальныя працэдуры. Затым яны атрымліваюць практычны выйгрыш, калі іх тэорыі дазваляюць атрымаць іншыя работы, выкананыя больш хутка і больш эканамічна. Д. Е. Пуга

Гэта кніга сайт будуецца.:

Лекцыя горкі. Прачытайце гэтыя слайды для ўвядзення ў аналіз алгарытмаў.
Вэб-кантэнт (Матчы другое выданне тэксту: асноўнае адрозненне ад першага выдання з’яўляецца тое, што Кіраўнік 5 з’яўляецца новай для другога выдання).
Інтэрнэт, вядома. Прапанаваная верасня па лістапад і са студзеня па май на Coursera.

Вучэбны дапаможнік. Падручнік Уводзіны ў аналіз алгарытмаў Роберт Сэджвік і Філіп Flajolet [Амазон · Паведаміць IT] прыводзіцца агляд асноўных метадаў, якія выкарыстоўваюцца ў матэматычным аналізе алгарытмаў. Матэрыял пакрыты цягне з класічных матэматычных тэмы, у тым ліку дыскрэтнай матэматыкі, элементарнай рэальнага аналізу, камбінаторыкі і, а таксама ад класічных тым, кампутарныя навукі, у тым ліку алгарытмаў і структур дадзеных.

Кіраўнік 1: Аналіз алгарытмаў лічыць агульныя матывы для аналізу алгарытмаў і адносін паміж рознымі падыходамі да вывучэння характарыстыкі алгарытмаў.
Кіраўнік 2: Рэкурэнтная суадносін канцэнтруецца на фундаментальных матэматычных уласцівасцяў розных тыпаў Рэкурэнтная адносін, якія ўзнікаюць часта пры аналізе алгарытму шляхам прамога адлюстравання з рэкурсіўнага прадстаўлення праграмы рэкурсіўнага прадстаўлення функцыі, якая апісвае яго ўласцівасці.
Кіраўнік 3: Стварэнне функцыі ўводзіць цэнтральнае паняцце ў сярэднім выпадку аналізу алгарытмаў: вырабляюць функцыі – неабходны і натуральны сувязь паміж алгарытмамі, якія нашы аб’екты даследаванні і аналітычныя метады, якія неабходныя, каб выявіць іх ўласцівасці.
Кіраўнік 4: асімптатычна набліжэння разглядае метады атрымання набліжаных рашэнняў да праблем або апраксімацыі дакладных рашэнняў, якія дазваляюць нам распрацоўваць кароткія і дакладныя ацэнкі велічынь, якія ўяўляюць цікавасць пры аналізе алгарытмаў.
Кіраўнік 5: Аналітычная камбінаторыкі ўводзіць сучасны падыход да вывучэння камбінаторныя структур, дзе вырабляюць функцыі з’яўляюцца цэнтральным аб’ектам даследавання. Гэты падыход з’яўляецца асновай для вывучэння канкрэтных структур праз астатняй часткі кнігі.
Кіраўнік 6: Дрэвы даследуе ўласцівасці розных тыпаў дрэў, асноўных структур, якія ўзнікаюць відавочна і няяўна ў многіх практычных алгарытмаў. Наша мэта заключаецца ў прадастаўленні доступу да вынікаў з шырокай літаратуры па камбінаторнай аналізу дрэў, у той жа час забяспечваючы аснову для цэлага шэрагу алгарытмічных прыкладаннях.
Кіраўнік 7: Перастаноўкі апытанні камбінаторныя ўласцівасці перастановак (парадкі лікаў ад 1 да N) і паказвае, як яны ставяцца натуральным чынам да фундаментальных і шырока выкарыстоўваюцца алгарытмаў сартавання.
Кіраўнік 8: String і спрабуе даследаванні асноўныя камбінаторныя ўласцівасці радкоў, паслядоўнасці знакаў або літар, узятых з фіксаванага алфавіту, і ўводзіць алгарытмы, якія апрацоўваюць радкі, пачынаючы ад фундаментальных метадаў у самым сэрцы тэорыі вылічэнняў у практычных метадаў апрацоўкі тэксту з гаспадар важных прыкладанняў.
Кіраўнік 9: Словы і Карты ахоплівае глабальныя ўласцівасці слоў (N-літарных радкоў з М-літары алфавіту), якія добра вывучаных ў класічных камбінаторыкі (таму што яны мадэлююць паслядоўнасці незалежных выпрабаванняў Бярнулі) і ў класічных прыкладных алгарытмікі (таму што яны мадэлі ўваходных паслядоўнасцяў для алгарытмаў хэшавання). У гэтым раздзеле таксама ахоплівае выпадковыя карты (N-ліст слоў з N-літарнага алфавіту) і абмяркоўвае адносіны з дрэвамі і перастаноўкамі.

Booksite. Чытанне кнігі і вэб-сёрфінг два розных мерапрыемстваў: Гэта booksite прызначаны для выкарыстання ў той час як на сайце (напрыклад, пры праграмаванні і пры працы ў Інтэрнэце); падручнік для выкарыстання пры першапачатковым вывучэння новага матэрыялу і пры армавання ваша разуменне гэтага матэрыялу (напрыклад, пры разглядзе на экзамен). Booksite складаецца з наступных элементаў:

Вытрымкі. Скарочаны варыянт тэкставага аповеду, для даведкі, а ў Інтэрнэце.

Практыкаванне рашэння. Вырашэння асобных практыкаванняў.

Java, шалфей, і Python код. Валідацыю аналітычных вынікаў.

Кніга была ўпершыню апублікаваная ў 1995 годзе booksite імкнецца дапоўніць матэрыял у тэксце, усё яшчэ паважаючы цэласнасць арыгіналу.

Іншыя рэсурсы. Каб у поўнай меры супрацоўнічаць з гэтым матэрыялам, вы ў канчатковым выніку хочаце, каб загрузіць і выкарыстоўваць па меншай меры наступныя прылады:

StdJava код. Базавая мадэль праграмавання, мы распрацавалі для нашых кніг Уводзіны ў праграмаванне (у Java) і алгарытмаў, 4-е выданне. Даступны ў booksite Algs4.

TEX. Класічная праграма па матэматыцы typsetting. Пачніце на сайце гурта карыстальніка Тэкс.

MathJax. Механізм для ўбудавання матэматыку ў вэб-старонках. Няма неабходнасці запампоўваць, проста спасылаюцца на іх сайце. Глядзіце хатнюю старонку MathJax. MathJax тэст: Калі ≠ 0, існуюць два рашэнні ах2 + BX + C = 0, і яны

Калі вы карыстаецеся Mac OS X Lion і Safari / Chrome ў пачатку 2012 года, і гэта матэматыка выглядае дрэнна, паспрабуйце адключыць Стыкс шрыфтоў у FontBook.

Мудрэц. З адкрытым зыходным кодам праграмнае забеспячэнне для сімвалічнага матэматыцы, чарчэння, і спецыяльных функцый (на аснове Python). Спампаваць з хатняй старонкі Sage.

Мы стараемся устрымлівацца ад пашыранага выкарыстання гэтых інструментаў. Калі вы не знаёмыя з імі, гэта можа быць добры час, каб вучыцца. Большасць людзей лічаць, што не цяжка навучыцца эфектыўна іх выкарыстоўваць.

Псеўда-дадатак іконы. Выканайце наступныя спасылкі і “Дадаць у галоўным экране“, каб атрымаць псеўда-прыкладанняў з прамымі спасылкамі на нашых booksites на вашым мабільным прыладзе.

Comments are closed.