ФЭНДОМ


Номер Название Ссылка Статус
1 Грамматика, основные определения. Бесконтекстные грамматики. Грамматика для арифметических выражений. Грамматика Написано
2 Алгоритм рекурсивного спуска. Разбор арифметических выражений. Рекурсивный спуск Бред
3 Лево- и правоассоциативные операции. Разбор лево- и правоассоциативных операций с помощью алгоритма рекурсивного спуска. Разбор $ \lambda $-термов. Рекурсивный спуск Бред
4 Прямая и обратная польская запись. Алгоритм разбора выражения с использованием стека и приоритета операций. Польская запись Написано
5 Массивы, основные операции с массивами. Массивы в Окамле: создание, основные операции, функции высшего порядка. Циклы for и while. Массивы Написано
6 Поиск элемента в массиве. Двоичный поиск. Оценка сложности двоичного поиска. Двоичный поиск для вычисления значений обратной функции. Массивы Написано
7 Сортировка. Сравнение основных алгоритмов. Оценка количества сравнений в сортировке, доказательство оценки. Сортировка Не всё
8 Сортировки: быстрая и слиянием. Устойчивость сортировок. Оценки сложности с обоснованием. Сортировка Не всё
9 Пирамидальная сортировка. Устойчивость, оценка сложности с обоснованием. Поразрядная сортировка, сортировка подсчётом. Сортировка Не всё
10 Сортировка простыми вставками, сортировка Шелла. Оценка сложности. Сортировка Не всё
11 Число $ S(n) $, методика вычисления $ S(n) $ с помощью компьютера. Сортировка Не всё
12 Поиск подстроки. Общая постановка задачи. "Наивный" алгоритм. Оценка сложности. Хэш-функции. Алгоритм Рабина-Карпа. Поиск подстроки Написано
13 Конечный автомат (детерминированный). Алгоритм Кнута-Морриса-Пратта (автоматный вариант и классический вариант). Оценка сложности. Поиск подстроки, Автоматы Не всё
14 Недетерминированный конечный автомат. НКА с $ \varepsilon $-переходами. Реализация НКА. Преобразование НКА в ДКА. Автоматы Написано
15 Регулярные выражения, синтаксис. Преобразование регулярного выражения в НКА. Автоматы Написано
16 Построение регулярного выражения по данному НКА. Автоматы Не всё