Программирование:
ТЕОРЕМЫ
И ЗАДАЧИ

---

 

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

---

pvv
1/8/1999