Алгоритми

Извор: Викикњиге
Иди на навигацију Иди на претрагу
Наслов

Увод[уреди]

Ова књига има за циљ прихватљив увод у пројектовање и анализу ефикасних алгоритама. Кроз књигу ћемо представити само најосновније технике и описати ригорозне математичке методе које су потребне за анализу тих техника. Теме које су обрађене укључују:

  • Технику "подели, па владај"
  • Употреба рандомизације у алгоритмима
  • Општа, али неефикасна "бектрекинг" техника
  • Динамичко програмирање као ефикасна оптимизација за неке "бектрекинг" алгоритме
  • "Похлепни" алгоритми као опримизација других врсти "бектрекинг" алгоритама
  • Технике претраживања успоном, укључујући проток мреже.

Сврха књиге је да вам покаже како можете методично применити различите технике за своје алгоритме да би алгоритми постали ефикаснији. Док књига већином има акценат на опште технике, неки познати алгоритми су такође детаљно истражени. Ова књига је написана како бисте могли од "корице до корице" да је прочитате током једног семестра, при чему делови који су означени са * се могу прескочити.

Ова књига није водич кроз технике, нити је препорука. Топло препоручујемо томове Кнута и [CLRS]. Осим тога, понекад најбоље увиди долазе из самих примарних извора (на пример [Хоаре]).

Табела поглавља[уреди]

  1. Увод 100% завршен  Feb 20, 2016
  2. Математичке основе 50% завршен  Feb 20, 2016
  3. "Подели, па владај" 75% завршен  Feb 20, 2016
  4. Рандомизација 50% завршен  Feb 20, 2016
  5. "Бектрекинг" 50% завршен  Feb 20, 2016
  6. Динамичко програмирање50% завршен  Feb 20, 2016
  7. "Похлепни" алгоритми50% завршен  Feb 20, 2016
  8. Претраживање успоном50% завршен  Feb 20, 2016
  9. Алгоритми код неусмерених графова0% завршен  Feb 20, 2016
  10. Апроксимација раздаљине
Додатак А: Ада Имплементација 25% завршен  Feb 20, 2016


Постоји такође преглед свих поглавља за штампање.

Зашто Викикњига о алгоритмима?[уреди]

Викикњиге су подухват сличан пројекту отвореног софтвера: Обвезник доприноса ствара садржај за пројекат да помогне другима, за лично богаћење, или како би постигли нешто за сопствени рад (на пример, припреме за предавање).

Отворена књига, исто као и отворени програм, захтева време да се заврши, али могу имати велике користи чак и од скромних доприноса читалаца. На пример, можете поправити такозване "багове" у тексту (где "баг" може бити типографски, естетски, технички или неког другог типа) како би књига била што боља. Ако пронађете прилику да поправите "баг", једноставно притиснете дугме "Уреди", направите промене и потом притиснете дугме "Сачувај измене". Остали сарадници могу прегледати измене да би били сигурни да су прикладне за књигу. Ако нисте сигурни, можете да посетите страницу за разговор и тамо питати. Користите здрав разум.

Уколико желите више да допринесете, можете погледати поглавља која су превише кратка или је потребно више рада на њему и почнете писати! Будите сигурни да прегледате остатак књиге како не би дошло до дуплирања садржаја. Осим тога, требало би да прочитате упутство за сараднике за доследне савете.

Имајте на уму да не морате да допринесете све одједном. Можете обележити секције "TODO", са описом шта остаје да се уради, или ће можда неко други то да заврши уместо вас. Онда када су све "TODO" ставке готове, достићи ћемо наше прво издање!

Ова књига намерно држи уско-у-фокусу, како би допринос био лакши (јер тада је крајњи циљ је јаснији). Ова књига је други део серије од три књиге из области рачуарских наука о алгоритмима, почевши од Структура Података и завршно са Напредним Структурама Података и Алгоритмима. Уколико желите да допринесете тако што бисте додали неку тему која се не налази већ у листи ни у једној од три књига, пробајте да у Напредну књигу, што је више електрично у природи.

Осим тога, имплементација алгоритама као додатак је увек добродошла.

Додатна литература[уреди]

Следећа листа књига Алгоритама је као предуслов:


Извори[уреди]

Следећи извори су коришћени уз дозволу од оригиналних аутора. Неки од извора су уређени (понекад поприлично) од почетне верзије и тако су све грешке наше.

[Impagliazzo] Расел Импаглиацо. Белешке са предавања са курсева о алгоритмима 101 (Spring 2004; основне студије), and 202 (Spring 2004, Fall 2004; graduate). Калифорнијски Универзитет, Сан Дијего. Коришћена скоро свуда.
[Lippert] Eрик Липерт. "Рекурзија и Динамичко Програмирање," из Сјајних авантура у кодирању. 21 Јули 2004. Коришћено уз дозволу. https://blogs.msdn.microsoft.com/ericlippert/2004/07/21/recursion-and-dynamic-programming/ Коришћено у поглављима: "бектрекинг" и "динамичко програмирање".
[Википедија] Википедија https://sr.wikipedia.org/wiki/%D0%93%D0%BB%D0%B0%D0%B2%D0%BD%D0%B0_%D1%81%D1%82%D1%80%D0%B0%D0%BD%D0%B0, слободна енциклопедија. Цитати / одговарајуће продорно.

Референце[уреди]

Аутори топло препоручују следеће материјале:

[Aho] Алфред В. Ахо, Џефри Д. Улман, Џон Е. Хопкрофт. Структуре Података и Алгоритми. Addison-Wesley, 1983.
[CLRS] Томац Х. Кормен, Чарлс Е. Леисерон, Роналд Л. Ривест, Клифорд Стајн. Увод у Алгоритме. McGraw-Hill, 2001.
[Hoare] Ц. А. Р. Хоаре. "Алгоритам 63: Подела", "Алгоритам 64: Quicksort", "Алгоритам 65: Пронаћи", од Комуникације од ACM. Обим 4, Проблем 7 (Јули 1961). Страна 321. ISSN:0001-0782. http://doi.acm.org/10.1145/366622.366642.
[Knuth] Доналд E. Кнут. Уметност програмирања, Обими 1-3. Addison-Wesley Professional, 1998.

Сарадници[уреди]

Мајкл Шонле: "Велики део моје сарадње долази од Имплагиазових лекција у UCSD. Волим овај пројекат, јер ми даје шансу да објасним алгоритме на начин на који сам их коначно разумео. "

Метју Вилсон: "Откуцао сам отлајн након што сам дипломирао курс о алгоритмима. М. Шонле је од ове књиге заиста направио нешто што је сјајно. "

Мартин Крисчик: "Ја сам испоручио Ада примере за алгоритме. Никад не знате да ли вам алгоритам ради, док га не имплементирате. "

Спољашње везе[уреди]

http://www.algorito.com/

http://www.cs.berkeley.edu/~vazirani/algorithms/all.pdf

http://videolectures.net/mit6046jf05_introduction_algorithms/