по мотивам: Д. Кнут, Т. Кормен, Р. Седжвик, Н. Вирт, А. Степановafter: D. Knuth, T. Cormen, R. Sedgewick, N. Wirth, A. Stepanov

Фундамент Алгоритмов и Структур ДанныхAlgorithm & Data Structure Foundations

Математический анализ алгоритмов, сортировка и поиск, элементарные и продвинутые структуры данных, парадигмы проектирования алгоритмов, алгебраические основы (Степанов). Каркас: 5 подразделов, 15 пунктов; заполнение начато — 12 из 15 страниц написаны; 2.2.1, 2.2.2, 2.2.3, 2.2.4, 2.3.1, 2.3.2, 2.3.3, 2.4.1 и 2.4.2 дополнительно разложены на 64 отдельные статьи, все с анимированными интерактивными демонстрациями.Mathematical analysis of algorithms, sorting & searching, elementary and advanced data structures, algorithm-design paradigms, algebraic foundations (Stepanov). Skeleton: 5 subsections, 15 items; filling in has started — 12 of 15 pages written; 2.2.1, 2.2.2, 2.2.3, 2.2.4, 2.3.1, 2.3.2, 2.3.3, 2.4.1, and 2.4.2 are further broken out into 64 standalone articles, all with animated interactive demos.

2.1 Математический Анализ Алгоритмов2.1 Mathematical analysis of algorithms

2.1.1 Асимптотический анализAsymptotic analysisO, Ω, Θ нотации, о-малое, амортизационный анализ (метод потенциалов, метод группировки).O, Ω, Θ notation, little-o, amortized analysis (the potential method, aggregate method).interview 2.1.2 Рекуррентные соотношенияRecurrence relationsОсновная теорема о рекуррентных соотношениях (Master Theorem), дерево рекурсии, метод подстановки.The Master Theorem, recursion trees, the substitution method.interview 2.1.3 Комбинаторные алгоритмыCombinatorial algorithmsГенерация перестановок, сочетаний, разбиений, фундаментальная арифметика больших чисел (Кнут, TAOCP Vol 2).Generating permutations, combinations, partitions; big-number arithmetic fundamentals (Knuth, TAOCP Vol 2).

2.2 Сортировка и Поиск2.2 Sorting & searching

2.2.1 Сортировки сравнениемComparison-based sortsПузырьковая, сортировка вставками и выбором как база; быстрая сортировка, сортировка слиянием, пирамидальная сортировка (heapsort) — нижняя граница Ω(n log n) для сортировки сравнением и почему её нельзя обойти.Bubble, insertion, and selection sort as the baseline; quicksort, merge sort, heapsort — the Ω(n log n) lower bound for comparison-based sorting and why it can't be beaten.interview 2.2.2 Сортировки без сравненияNon-comparison sortsCounting sort, radix sort, bucket sort — как выйти за пределы Ω(n log n), используя структуру самих значений, а не только их сравнение.Counting sort, radix sort, bucket sort — beating Ω(n log n) by exploiting the structure of the values themselves, not just comparing them. 2.2.3 Поиск в отсортированных данныхSearching sorted dataБинарный поиск и его вариации (lower_bound/upper_bound, поиск в повёрнутом отсортированном массиве), тернарный поиск для унимодальных функций, экспоненциальный поиск.Binary search and its variants (lower_bound/upper_bound, searching a rotated sorted array), ternary search for unimodal functions, exponential search.interview 2.2.4 Порядковые статистикиOrder statisticsПоиск k-го наименьшего элемента (quickselect), алгоритм медианы медиан с гарантированным линейным временем.Finding the k-th smallest element (quickselect), the median-of-medians algorithm with guaranteed linear time.

2.3 Элементарные и Продвинутые Структуры Данных2.3 Elementary & advanced data structures

2.3.1 Линейные структуры и хешированиеLinear structures & hashingСвязные списки, кольцевые буферы, хеш-таблицы (Open Addressing, Robin Hood, Cuckoo Hashing, идеальный хеширование).Linked lists, ring buffers, hash tables (open addressing, Robin Hood, cuckoo hashing, perfect hashing).interview 2.3.2 Деревья поискаSearch treesОт наивного BST через AVL, красно-чёрные и splay-деревья к B-Trees/B+ Trees, Segment Trees и дереву Фенвика (BIT) — как поиск (2.2.3) специализируется под структуру дерева: O(log n) с гарантией баланса вместо O(n) в худшем случае несбалансированного BST. Разложено на 7 отдельных статей.From the naive BST through AVL, red-black, and splay trees to B-trees/B+ trees, segment trees, and the Fenwick tree (BIT) — how searching (2.2.3) specializes to a tree's structure: O(log n) with a balance guarantee instead of O(n) worst case in an unbalanced BST. Broken out into 7 standalone articles.interview 2.3.3 Кучи и очереди с приоритетомHeaps & priority queuesОт бинарной кучи в массиве через d-арное обобщение к структурам с дешёвым слиянием — биномиальной куче, куче Фибоначчи (каскадные вырезания, амортизированный O(1) decrease-key) и парной куче. Разложено на 5 отдельных статей.From an array-based binary heap through a d-ary generalization to structures with cheap merging — binomial heap, Fibonacci heap (cascading cuts, amortized O(1) decrease-key), and pairing heap. Broken out into 5 standalone articles.interview

2.4 Парадигмы Проектирования Алгоритмов2.4 Algorithm-design paradigms

2.4.1 Разделяй и властвуйDivide & conquerОбщий приём как таковой (в отличие от 2.2.1, где quicksort/mergesort разобраны как конкретные сортировки): умножение Карацубы, алгоритм Штрассена, БПФ, поиск ближайшей пары точек, выпуклая оболочка — задачи, где рекурсивное разбиение не про сортировку, а самостоятельная техника. Разложено на 5 отдельных статей.The general technique itself (as opposed to 2.2.1, where quicksort/mergesort are covered as concrete sorts): Karatsuba multiplication, Strassen's algorithm, the FFT, closest pair of points, convex hull — problems where recursive splitting isn't about sorting but a standalone technique. Broken out into 5 standalone articles. 2.4.2 Динамическое программированиеDynamic programmingМемоизация и табуляция, оптимальная подструктура и перекрывающиеся подзадачи; рюкзак, LCS, LIS, размен монет, редакционное расстояние, ДП по битовой маске (TSP) и оптимизация ДП (Convex Hull Trick, D&C Optimization). Разложено на 7 отдельных статей.Memoization vs tabulation, optimal substructure and overlapping subproblems; knapsack, LCS, LIS, coin change, edit distance, bitmask DP (TSP), and DP optimization (the convex hull trick, divide-and-conquer optimization). Broken out into 7 standalone articles.interview 2.4.3 Жадные алгоритмыGreedy algorithmsАлгоритм Хаффмана, задача о покрытии множества, теория матроидов и их связь с жадными стратегиями.Huffman coding, the set-cover problem, matroid theory and its connection to greedy strategies.

2.5 Алгебраические Основы Алгоритмов (Степанов)2.5 Algebraic foundations of algorithms (Stepanov)

2.5.1 Алгебраические структурыAlgebraic structuresПолугруппы, моноиды, группы, кольца, поля и их выражение в коде.Semigroups, monoids, groups, rings, fields, and how to express them in code. 2.5.2 Итераторы и диапазоныIterators & rangesАксиоматика итераторов, категории итераторов, обход структур данных без раскрытия внутреннего устройства.Iterator axioms, iterator categories, traversing data structures without exposing internal layout.

статусstatus

Это каркас: 5 подразделов и 15 пунктов зафиксированы. Заполнение начато с 2.1.1 (Асимптотический анализ), 2.1.2 (Рекуррентные соотношения) и 2.1.3 (Комбинаторные алгоритмы), 2.2.1 (Сортировки сравнением), 2.2.2 (Сортировки без сравнения), 2.2.3 (Поиск в отсортированных данных), 2.2.4 (Порядковые статистики), 2.3.1 (Линейные структуры и хеширование), 2.3.2 (Деревья поиска), 2.3.3 (Кучи и очереди с приоритетом), 2.4.1 (Разделяй и властвуй) и 2.4.2 (Динамическое программирование) — полные страницы с терминологией с нуля, диаграммами, кодом и примерами из жизни, по формату раздела 03 (графы). 2.2.1, 2.2.2, 2.2.3, 2.2.4, 2.3.1, 2.3.2, 2.3.3, 2.4.1 и 2.4.2 устроены как хабы-классификаторы (плитки + минимальное описание каждой темы) со ссылками на 64 отдельные статьи: 15 по сортировкам сравнением, 4 по сортировкам без сравнения, 8 по поиску в отсортированных данных, 4 по порядковым статистикам, 9 по линейным структурам и хешированию (связные списки, кольцевой буфер, хеш-таблица с цепочками, открытая адресация, Robin Hood hashing, cuckoo hashing, идеальное хеширование, Bloom filter, skip list), 7 по деревьям поиска (бинарное дерево поиска, AVL, красно-чёрное дерево, splay-дерево, B-дерево/B+Tree, дерево отрезков, дерево Фенвика), 5 по кучам и очередям с приоритетом (бинарная куча, d-арная куча, биномиальная куча, куча Фибоначчи, парная куча), 5 по разделяй-и-властвуй (умножение Карацубы, алгоритм Штрассена, быстрое преобразование Фурье, ближайшая пара точек, выпуклая оболочка) и 7 по динамическому программированию (задача о рюкзаке, наибольшая общая подпоследовательность, наибольшая возрастающая подпоследовательность, размен монет, редакционное расстояние, ДП по битовой маске, оптимизация ДП) — все 64 статьи содержат анимированные интерактивные демонстрации: атомарные операции выполняются мгновенно по клику, многошаговые алгоритмы — через автопроигрывание шагов. 2.4.1 и 2.4.2 — первые два заполненных пункта раздела 2.4 (Парадигмы проектирования алгоритмов); 2.4.3 остаётся плейсхолдером. Остальные пункты верхнего уровня будут добавляться поэтапно. Метка interview отмечает темы, которые встречаются на технических собеседованиях чаще всего. Сортировка и поиск (2.2) выделены в отдельный подраздел, чтобы не растворяться внутри «разделяй и властвуй» (2.4.1) и структур данных (2.3) — важное разграничение теперь видно на практике: 2.4.1 разбирает рекурсивное разбиение как самостоятельную технику на задачах, не связанных с сортировкой, а 2.4.2 показывает ту же идею разбиения на подзадачи, но с перекрывающимися подзадачами и мемоизацией вместо независимых половин.This is a skeleton: 5 subsections and 15 items are locked in. Filling in has started with 2.1.1 (Asymptotic analysis), 2.1.2 (Recurrence relations), 2.1.3 (Combinatorial algorithms), 2.2.1 (Comparison-based sorts), 2.2.2 (Non-comparison sorts), 2.2.3 (Searching sorted data), 2.2.4 (Order statistics), 2.3.1 (Linear structures & hashing), 2.3.2 (Search trees), 2.3.3 (Heaps & priority queues), 2.4.1 (Divide & conquer), and 2.4.2 (Dynamic programming) — full pages with terminology from scratch, diagrams, code, and real-world examples, matching the format of section 03 (graphs). 2.2.1, 2.2.2, 2.2.3, 2.2.4, 2.3.1, 2.3.2, 2.3.3, 2.4.1, and 2.4.2 are built as hub/classifier pages (tiles plus a minimal description of each topic) linking to 64 standalone articles: 15 on comparison sorts, 4 on non-comparison sorts, 8 on searching sorted data, 4 on order statistics, 9 on linear structures & hashing (linked lists, ring buffer, hash table with chaining, open addressing, Robin Hood hashing, cuckoo hashing, perfect hashing, Bloom filter, skip list), 7 on search trees (binary search tree, AVL, red-black tree, splay tree, B-tree/B+Tree, segment tree, Fenwick tree), 5 on heaps & priority queues (binary heap, d-ary heap, binomial heap, Fibonacci heap, pairing heap), 5 on divide & conquer (Karatsuba multiplication, Strassen's algorithm, the fast Fourier transform, closest pair of points, convex hull), and 7 on dynamic programming (0/1 knapsack, longest common subsequence, longest increasing subsequence, coin change, edit distance, bitmask DP, DP optimization) — all 64 articles include animated interactive demos: atomic operations execute instantly on click, multi-step algorithms auto-play their steps. 2.4.1 and 2.4.2 are the first two filled-in items of section 2.4 (Algorithm-design paradigms); 2.4.3 remains a placeholder. The remaining top-level items will be added incrementally. The interview tag marks the topics that come up most often in technical interviews. Sorting & searching (2.2) is broken out into its own subsection so it doesn't dissolve inside divide-and-conquer (2.4.1) and data structures (2.3) — a distinction now visible in practice: 2.4.1 treats recursive splitting as a standalone technique on problems unrelated to sorting, while 2.4.2 shows the same idea of splitting into subproblems but with overlapping subproblems and memoization instead of independent halves.