Грокаємо алгоритми. Ілюстрований посібник для програмістів і допитливих

Оглавление Грокаємо алгоритми. Ілюстрований посібник для програмістів і допитливих

Передмова Вдячність Про книгу
 
1| Знайомство з алгоритмами 
Вступ 
Що ти дізнаєшся про ефективність програмування 
Що ти дізнаєшся про розв’язання задач 
Бінарний пошук 
Кращий спосіб пошуку 
Час виконання 
Нотація О-велике (Big O notation) 
Час виконання алгоритмів зростає з різним темпом 
Візуалізація різного часу виконання О-велике 
Час виконання О-велике для найгіршого випадку 
Поширені приклади нотації 
Задача комівояжера Конспект
 
2| Сортування вибором 
Як працює пам’ять 
Масиви та зв’язані списки 
Зв’язані списки 
Масиви 
Термінологія Вставлення в середину списку 
Видалення 
Алгоритм сортування вибором 
Конспект
 
3| Рекурсія 
Базовий та рекурсивний випадки 
Стек 
Стек викликів 
Стек викликів із рекурсивною функцією 
Конспект
 
4| Швидке сортування 
Розділяй і володарюй 
Алгоритм швидкого сортування 
Повторення нотації О-велике 
Сортування злиттям проти швидкого сортування 
Середній проти найгіршого випадку 
Конспект
 
5| Хеш-таблиці 
Хеш-функції 
Варіанти використання 
Використання хеш-таблиці для пошуку 
Запобігання дублюванню записів 
Використання хеш-таблиці як кешу 
Конспект 
Колізії 
Продуктивність 
Коефіцієнт заповнення 
Хороша хеш-функція 
Конспект
 
6| Пошук у ширину (BFS) 
Знайомство з графами 
Що таке граф? 
Пошуку в ширину 
Знаходження найкоротшого шляху 
Черги 
Реалізація графа 
Реалізація алгоритму 
Час виконання 
Конспект
 
7| Алгоритм Дейкстри 
Працюємо з алгоритмом Дейкстри 
Термінологія 
Виміняти піаніно 
Ребра з від’ємною вагою 
Реалізація 
Конспект
 
8| Жадібні алгоритми 
Проблема з розкладом занять для аудиторії 
Задача пакування рюкзака 
Задача про покриття множини 
Алгоритми апроксимації 
NP-повна задача (NP-complete) 
Задача комівояжера покроково 
Як ти визначиш, що задача належить до NP-повних? 
Конспект
 
9| Динамічне програмування 
Задача пакування рюкзака 
Просте рішення 
Динамічне програмування ЧаПи: задача пакування рюкзака 
Що станеться, коли додати предмет? 
Що станеться, коли змінити порядок рядків? 
Чи можна заповнювати таблицю по стовпчиках, а не по рядках? 
Що станеться, якщо додати менший предмет? 
Чи можна вкрасти частинки предмета? 
Оптимізація маршруту подорожі 
Поводження зі взаємозалежними предметами 
Чи може рішення вимагати більше, ніж два «підрюкзаки»? 
Чи завжди найкраще рішення заповнює рюкзак повністю? 
Найдовший спільний підрядок 
Створення таблиці 
Заповнення таблиці 
Рішення 
Найдовша спільна підпослідовність 
Найдовша спільна підпослідовність — рішення 
Конспект
 
10| Алгоритм k-найближчих сусідів 
Класифікація апельсинів і грейпфрутів 
Побудова системи рекомендацій 
Виділення ознак 
Регресія 
Вибір правильних ознак 
Введення до машинного навчання 
Оптичне розпізнавання символів (OCR) 
Побудова спам-фільтра 
Прогнозування на фондовій біржі 
Конспект
 
11| Наступні кроки 
Дерева 
Інвертований індекс 
Перетворення Фур’є 
Паралельні алгоритми 
MapReduce 
Чому розподілені алгоритми корисні? 
Функція map 
Функція reduce 
Фільтри Блума та HyperLogLog Фільтри Блума HyperLogLog 
Алгоритми безпечного хешування (SHA) 
Порівняння файлів 
Перевірка паролів 
Локально-чутливе хешування 
Протокол Діффі–Геллмана 
Лінійне програмування
 
Епілог Відповіді до вправ Абетковий покажчик