CS
Алгоритмы
Задачник Базовый курс EN

Что решает

выборка

Статьи

NUM~ Алгоритм Метод Монте-Карло Оценка числа случайным опытом: ошибка 1/√n в любой размерности, честный доверительный интервал. O(n) испытаний, ошибка ~ σ/√n 2 задачи SYS Алгоритм Резервуарная выборка k случайных элементов из потока неизвестной длины за один проход и O(k) памяти. O(n) 2 задачи

Задачи

Выборка по энергии Честный интервал для озера Сколько раз перепишется резервуар

Часто рядом

случайность 1 оценка 1 симуляция 1 интегрирование 1 приближение 1 изображения 1 финансы 1 классика 1 потоковая обработка 1 случайные числа 1 куча 1 журнал 1

Учебник пишет Вячеслав Легостин. Всё бесплатно; код читателей не сохраняется.

Computer Science Каталог алгоритмов Задачник Базовый курс Математика legost.in

Каталог алгоритмов

Задачник

SRT Поиск и сортировка

  1. Двоичный поиск
  2. Двоичный поиск по ответу
  3. Экспоненциальный поиск
  4. Интерполяционный поиск
  5. Троичный поиск
  6. Простые сортировки
  7. Сортировка слиянием
  8. Timsort
  9. Внешняя сортировка
  10. Быстрая сортировка
  11. Пирамидальная сортировка
  12. Сортировка подсчётом и поразрядная
  13. Нижние границы сравнений
  14. Быстрый выбор
  15. Top-k: k лучших
  16. Перемешивание Фишера — Йетса

DS Структуры данных

  1. Динамический массив
  2. Связный список
  3. Стек и очередь
  4. Монотонный стек
  5. Хеш-таблица
  6. Хеширование кукушки
  7. Фильтр Блума
  8. Корневая декомпозиция
  9. Персистентные структуры
  10. Верёвка
  11. Двоичная куча
  12. Двоичное дерево поиска
  13. АВЛ-дерево
  14. Красно-чёрное дерево
  15. Декартово дерево
  16. Список с пропусками
  17. B-дерево
  18. Косое дерево
  19. Бор (префиксное дерево)
  20. Система непересекающихся множеств
  21. Дерево отрезков
  22. Дерево Фенвика
  23. Разреженная таблица
  24. LRU-кэш

GRA Графы

  1. Как хранить граф
  2. Поиск в ширину
  3. Поиск в глубину
  4. Топологическая сортировка
  5. Компоненты сильной связности
  6. 2-SAT
  7. Мосты и точки сочленения
  8. Алгоритм Дейкстры
  9. A*
  10. Двунаправленный поиск
  11. Алгоритм Беллмана — Форда
  12. Алгоритм Флойда — Уоршелла
  13. Алгоритм Джонсона
  14. Иерархии сжатия
  15. Минимальное остовное дерево
  16. Максимальный поток
  17. Алгоритм Диница
  18. Минимальный разрез
  19. Раскраска графа
  20. Паросочетания в двудольном графе
  21. Венгерский алгоритм
  22. Поток наименьшей стоимости
  23. Эйлеров путь
  24. Наименьший общий предок
  25. Тяжёлые пути
  26. Центроидная декомпозиция
  27. Задача коммивояжёра
  28. PageRank

STR Строки и тексты

  1. Наивный поиск подстроки
  2. Префикс-функция и КМП
  3. Z-функция
  4. Полиномиальный хеш
  5. Алгоритм Рабина — Карпа
  6. Алгоритм Ахо — Корасик
  7. Бойер — Мур
  8. Суффиксный массив
  9. Суффиксный автомат
  10. Преобразование Барроуза — Уилера
  11. Алгоритм Манакера
  12. Редакционное расстояние
  13. BK-дерево
  14. Diff Майерса
  15. Код Хаффмана
  16. LZ77 и LZW

DP Динамическое программирование

  1. Динамическое программирование
  2. Задача о рюкзаке
  3. Наибольшая возрастающая подпоследовательность
  4. Наибольшая общая подпоследовательность
  5. Динамика на отрезках
  6. Динамика на деревьях
  7. Динамика по маскам
  8. Динамика по цифрам
  9. Convex hull trick
  10. Оптимизации Кнута и «разделяй и властвуй»
  11. Seam carving
  12. Алгоритм Витерби
  13. Выравнивание последовательностей
  14. Красивый перенос строк

PAR Парадигмы

  1. Жадные алгоритмы
  2. Перебор с возвратом
  3. Ветви и границы
  4. Разделяй и властвуй
  5. Ближайшая пара точек
  6. Встреча посередине

NUM Числа и алгебра

  1. Алгоритм Евклида
  2. Быстрое возведение в степень
  3. Решето Эратосфена
  4. Тест Миллера — Рабина
  5. ρ-алгоритм Полларда
  6. Китайская теорема об остатках
  7. Длинная арифметика
  8. Умножение Карацубы
  9. Быстрое преобразование Фурье
  10. Теоретико-числовое преобразование
  11. Матрицы и рекуррентности
  12. Метод Гаусса
  13. Генераторы псевдослучайных чисел

GEO Геометрия

  1. Векторы и ориентация
  2. Пересечение отрезков
  3. Выпуклая оболочка
  4. Точка в многоугольнике
  5. Площадь многоугольника
  6. Заметающая прямая
  7. Триангуляция Делоне и диаграмма Вороного
  8. k-d дерево
  9. R-дерево
  10. Вращающиеся калиперы
  11. Упрощение линий Рамера — Дугласа — Пекера
  12. Кривые Гильберта и geohash

NUM~ Численные методы

  1. Бисекция и метод Ньютона
  2. Градиентный спуск
  3. Численное интегрирование
  4. Метод Монте-Карло
  5. Методы Эйлера и Рунге — Кутты
  6. Суммирование Кэхэна
  7. Симплекс-метод

SYS Системы и большие данные

  1. Консистентное хеширование
  2. Рандеву-хеширование
  3. Count-Min Sketch
  4. HyperLogLog
  5. Резервуарная выборка
  6. Дерево Меркла
  7. Ограничение частоты запросов
  8. Инвертированный индекс и BM25
  9. MinHash и LSH
  10. LSM-дерево
  11. Повтор с джиттером
  12. Raft
  13. Часы Лэмпорта и векторные часы
  14. CRDT
  15. Два случайных выбора
  16. Планирование задач
  17. Алгоритм rsync
  18. LFU и ARC

ML Данные и машинное обучение

  1. k-средних
  2. DBSCAN
  3. k ближайших соседей
  4. Решающее дерево
  5. Наивный Байес
  6. Линейная регрессия
  7. Логистическая регрессия
  8. Метод главных компонент
  9. Рекомендации через разложение матрицы
  10. Перцептрон и обратное распространение

RND Случайность

  1. Лас-Вегас и Монте-Карло
  2. Случайные блуждания
  3. Имитация отжига
  4. Генетический алгоритм

TEC Приёмы

  1. O-большое
  2. Быстрый ввод и вывод
  3. Как честно измерить скорость
  4. Префиксные суммы
  5. Данные, удобные кэшу
  6. Два указателя
  7. Сколько операций в секунду
  8. Сложность по замерам
  9. Векторизация
  10. Скользящее окно
  11. Мемоизация
  12. Профилировщики
  13. Числа, которые стоит знать
  14. Амортизационный анализ
  15. Как выбрать структуру данных
  16. Сколько займёт в памяти
  17. Сжатие координат
  18. Битовые трюки
  19. Предподсчёт и таблицы
  20. Отсечения