Наверх


Р.Уилсон, 1977 (Rus)
Введение в теорию графов

ПРЕДИСЛОВИЕ

1. ВВЕДЕНИЕ
   1.1
Что такое граф?

2. ОПРЕДЕЛЕНИЯ И ПРИМЕРЫ
   2.1 Определения
   2.2 Примеры графов
   2.3 Укладки графов

3.  ЦЕПИ И ЦИКЛЫ
  
3.1 Новые определения
   3.2 Эйлеровы графы
   3.3 Гамильтоновы графы
   3.4 Бесконечные графы

4.  ДЕРЕВЬЯ
   4.1 Элементарные свойства деревьев
   4.2 Перечисление деревьев
   4.3 Некоторые приложения теории графов

5.  ПЛАНАРНОСТЬ И ДВОЙСТВЕННОСТЬ
   5.1 Планарные графы
   5.2 Теорема Эйлера о плоских графах
   5.3 Графы на других поверхностях
   5.4 Двойственные графы
   5.5 Двойственность по Уитни

6.  РАСКРАШИВАНИЕ ГРАФОВ
   6.1 Хроматическое число
   6.2 Два доказательства
   6.3 Раскрашивание карт
   6.4 Реберная раскраска
   6.5 Хроматические многочлены

7.  ОРГРАФЫ
   7.1 Определения
   7.2 Эйлеровы орграфы и турниры
   7.3 Цепи Маркова

8.  ПАРОСОЧЕТАНИЯ, СВАДЬБЫ И ТЕОРЕМА МЕНГЕРА
  
8.1 Теорема Холла о свадьбах
   8.2 Теория трансверсалей
   8.3 Приложения теоремы Холла
   8.4 Теорема Менгера
   8.5 Потоки в сетях

9.  ТЕОРИЯ МАТРОИДОВ
   9.1 Введение в теорию матроидов
   9.2 Примеры матроидов
   9.3 Матроиды и теория графов
   9.4 Матроиды и теория трансверсалей

ПОСЛЕСЛОВИЕ
ПРИЛОЖЕНИЕ
СПИСОК ЛИТЕРАТУРЫ
ПРЕДМЕТНЫЙ УКАЗАТЕЛЬ





Наверх

Е.В.Андреева, Ю.Е. Егоров, 2002 (Rus)
Вычислительная геометрия на плоскости


ВВЕДЕНИЕ
ВЕКТОРЫ И КООРДИНАТЫ
УГОЛ МЕЖДУ ВЕКТОРАМИ
ОРИЕНТИРОВАННАЯ ПЛОЩАДЬ

1. УРАВНЕНИЯ ЛИНИЙ
  
1.1 Уравнение прямой, проходящей через две различные точки, заданные своими координатами
   1.2 Уравнение прямой, заданной одной из ее точек и вектором нормали к ней
   1.3 Уравнение прямой, перпендикулярной данной и проходящей через заданную точку
   1.4 Уравнение прямой, параллельной данной и находящейся от нее на заданном расстоянии r
   1.5 Уравнение биссектрисы угла
   1.6 Уравнение окружности
   1.7 Касательная к окружности



2. ВЗАИМНОЕ РАСПОЛОЖЕНИЕ ТОЧЕК И ФИГУР
   2.1 Расположение точки относительно прямой, луча или отрезка
   2.2 Взаимное расположение двух точек относительно прямой
   2.3 Взаимное расположение двух прямых или прямой и отрезка
   2.4 Определение взаимного расположения двух отрезков или лучей
   2.5 Взаимное расположение окружности и прямой
   2.6 Взаимное расположение двух окружностей
   2.7 Проверка принадлежности точки внутренней области многоугольника


3. ОСОБЫЕ ТОЧКИ МНОГОУГОЛЬНИКОВ И МНОЖЕСТВ N ТОЧЕК ПЛОСКОСТИ
   3.1 Построение окружности, описанной около треугольника или правильного N-угольника
   3.2 Построение окружности, вписанной в треугольник или правильный N-угольник
   3.3 Окружность, "охватывающая" N точек плоскости
   3.4 Наибольшая "пустая" окружность с центром внутри многоугольника, содержащего N точек
   3.5 Задача о покрытии
   3.6 Кратчайшая сеть дорог
   3.7 Центр масс


4.
МНОГОУГОЛЬНИКИ
   4.1 Определение вида треугольника
   4.2 Проверка выпуклости многоугольника
   4.3 Вычисление площади простого многоугольника
   4.4 Построение выпуклой оболочки для множества из N точек плоскости






Наверх

Е.В.Андреева, 2002 (Rus)
Лекции спецкурса "Подготовка и проведение олимпиад по информатике. Решение олимпиадных задач" в СУНЦ МГУ


1. ПРАВИЛА ПРОВЕДЕНИЯ ОЛИМПИАД
2. ПОРЯДОК РЕШЕНИЯ ОЛИМПИАДНЫХ ЗАДАЧ

3. ТЕХНИКА ПРОГРАММИРОВАНИЯ ОЛИМПИАДНЫХ ЗАДАЧ
   3.1 Директивы компилятора
   3.2 Ввод и вывод данных
   3.3 Инициализация данных и создание динамических переменных
   3.4 Подсчет времени работы программы


4. АЛГОРИТМЫ ПОИСКА В ОЛИМПИАДНЫХ ЗАДАЧАХ
   4.1 Алгоритмы поиска в неупорядоченных одномерных массивах
   4.2 Поиск в упорядоченных массивах
   4.3 Алгоритмы поиска и задачи на взвешивания
   4.4 Поиск подстроки в строке


5. ОЛИМПИАДНЫЕ ЗАДАЧИ И СОРТИРОВКА
   5.1 Использование "стандартных" алгоритмов сортировки одномерных массивов.
   5.2 Оптимальная сортировка
   5.3 Сортировка данных специального вида
   5.4 Обратные сортировке задачи

6.
КОМБИНАТОРНЫЕ ЗАДАЧИ
  
6.1 Генерация всех подмножеств данного множества
   6.2 Генерация всех перестановок n-элементного множества
   6.3 Разбиения множества
   6.4 Олимпиадные задачи, использующие комбинаторные конфигурации

7. ДИНАМИЧЕСКОЕ ПРОГРАММИРОВАНИЕ
   7.1 Основные определения
   7.2 Условия применимости динамического программирования
   7.3 Классические задачи динамического программирования
   7.4 Волновые алгоритмы

8. ДИНАМИЧЕСКОЕ ПРОГРАММИРОВАНИЕ, АЛГОРИТМЫ НА ГРАФАХ
  
8.1 Алгоритмы, использующие решение дополнительных подзадач
   8.2 Основные определения теории графов
   8.3 Поиск пути между парой вершин невзвешенного графа
   8.4 Пути минимальной длины во взвешенном графе

9.
ЭФФЕКТИВНЫЕ АЛГОРИТМЫ НА ГРАФАХ
   9.1 Обход вершин графа
   9.2 Поиск эйлерова пути в графе
   9.3 Построение минимального остова во взвешенном неориентированном графе
   9.4 Построение максимального паросочетания в двудольном графе

10.
КОНЕЧНЫЕ АВТОМАТЫ. РАЗБОР ВЫРАЖЕНИЙ
   10.1 Определение конечного автомата
   10.2 Проверка арифметического выражения на корректность
   10.3 Стековый конечный автомат
   10.4 "Палочный" способ разбора арифметических выражений
   10.5 Подсчет арифметических выражений с помощью постфиксной нотации
   10.6 Метод рекурсивного спуска

11.
ГРАФИЧЕСКИЕ ЗАДАЧИ НА ОЛИМПИАДАХ ПО ИНФОРМАТИКЕ
   11.1 Основные формулы и алгоритмы, которые необходимо знать
   11.2 Косое произведение в задачах вычислительной геометрии
   11.3 Выпуклая оболочка множества N точек плоскости

12.
NP-ПОЛНЫЕ ЗАДАЧИ. ПРИБЛИЖЕННЫЕ МЕТОДЫ РЕШЕНИЯ ЗАДАЧ
   12.1 NP-полнота
   12.2 Задача коммивояжера
   12.3 Программирование игр и головоломок.