Введение в анализ алгоритмов 20866

Завдання даної книги проста: розібрати «ідеї», що лежать в основі програм, і показати, як доводити їх правильність.

Як математично довести, що заданий алгоритм робить те, що він повинен робити? І чому це так важливо?

Доводиться правильність класичних алгоритмів: цілочисельного ділення, алгоритм Евкліда, ранжирування, ін. Крім традиційних алгоритмів, таких як жадібні алгоритми, алгоритми динамічного програмування і алгоритми «розділяй і володарюй», книга досліджує також рандомізовані і онлайнові алгоритми. Перші стали повсюдними через появу криптографії, а другі необхідні в багатьох областях, починаючи з операційних систем і закінчуючи фондовим ринком.

Книга всіяна завданнями. Більшість завдань теоретичні, але багато хто вимагає реалізації алгоритму; для таких завдань використовується мова програмування Python 3. Незважаючи на свою стислість, видання є математично строгим. Бажано попереднє знайомство з дискретною математикою.

Видання призначене для студентів вузів, фахівців в галузі інформатики та математики, а також широкого кола програмістів і розробників.