Contents

• Переменные, выражения, присваивания
  • Задачи без массивов
  • Массивы
  • Индуктивные функции
    (по А.Г. Кушниренко)
• Порождение комбинаторных объектов
  • Размещения с повторениями
  • Перестановки
  • Подмножества
  • Разбиения
  • Коды Грея и аналогичные задачи
  • Несколько замечаний
  • Подсчет количеств
• Обход дерева. Перебор с возвратами
  • Ферзи, не бьющие друг друга:
    обход дерева позиций
  • Обход дерева в других задачах
• Сортировка
  • Квадратичные алгоритмы
  • Алгоритмы порядка
  • Применения сортировки
  • Нижние оценки для числа
    сравнений при сортировке
  • Родственные сортировке задачи
• Конечные автоматы и обработка текстов
  • Составные символы,
    комментарии и т.п.
  • Ввод чисел
• Типы данных
  • Стеки
  • Очереди
  • Множества
  • Разные задачи
• Рекурсия
  • Примеры рекурсивных программ
  • Рекурсивная обработка деревьев
  • Порождение комбинаторных
    объектов, перебор     width0pt
  • Другие применения рекурсии
• Как обойтись без рекурсии
  • Таблица значений
    (динамическое программирование)
  • Стек отложенных заданий
  • Более сложные случаи рекурсии
• Разные алгоритмы на графах
  • Кратчайшие пути
  • Связные компоненты,
    поиск в глубину и ширину     width0pt
• Сопоставление с образцом
  • Простейший пример
  • Повторения в образце --
    источник проблем
  • Вспомогательные утверждения
  • Алгоритм
    Кнута-Морриса-Пратта
  • Алгоритм Бойера-Мура
  • Алгоритм Рабина
  • Более сложные образцы
    и автоматы
• Представление множеств. Хеширование
  • Хеширование
    с открытой адресацией
  • Хеширование со списками
• Представление множеств. Деревья. Сбалансированные деревья
  • Представление множеств
    с помощью деревьев
  • Сбалансированные деревья
• Контекстно-свободные грамматики
  • Общий алгоритм разбора
  • Метод рекурсивного спуска
  • Алгоритм разбора
    для LL(1)-грамматик
• Синтаксический разбор слева направо (LR)
  • LR-процессы
  • LR(0)-грамматики
  • SLR(1)-грамматики
  • LR(1)-грамматики,
    LALR(1)-грамматики
  • Общие замечания
    о разных методах разбора
• Contents