ГЛАВНАЯ ФОРУМ CСЫЛКИ ТЕОРИЯ В ИЗБРАННОЕ ENGLISH VERSION
Учебно-тренировочные сборы г. Минска
к республиканской олимпиаде 2004 года
План сборов

13 февраля 2004 года


Лекция на тему: "Техника безопасности в компьютерных классах Лицея БГУ"
Лектор : Шалатонина И.Ю.
Тур на простые задачи:
  • Rland
  • Лестница
  • Анаграммы


17 февраля 2004 года


Лекция на тему: "Введение в теорию конечных автоматов"
Лектор : Кашкевич С.И.
Тур на тему "Конечные автоматы":
  • PASCAL
  • AT-последовательность


20 февраля 2004 года


Тур на разные задачи:
  • Рисунки
  • Сумма
  • Поле


24 февраля 2004 года


Лекция на тему: "Структуры данных"
Лектор : Метельский И.С.

  1. Простые структуры

    • Очереди и стеки
    • Списки
    • Способы хранения графов

  2. Приоритетные очереди

    • Бинарные кучи
    • Примеры использования

  3. Системы непересекающихся множеств

    • Реализация на основе массива
    • Реализация на основе списков с весовой эвристикой
    • Реализация на основе леса с объединением по рангам и сжатием путей
    • Примеры использования

  4. Структуры с одиночной модификацией

    • Дерево Фенвика для сумм (табличная реализация)
    • Дерево Фенвика для минимумов (табличная реализация)
    • Дерево Фенвика для двумерной таблицы
    • Применение для ускорения алгоритмов динамического программирования

  5. Структуры с интервальной модификацией

    • Дерево максимумов
    • Дерево отрезков
    • Примеры использования



27 февраля 2004 года


Тур на тему: "Структуры данных":


2 марта 2004 года


Лекция на тему: "Вычислительная геометрия"
Лектор : Кашкевич С.И.
Тур на тему "Вычислительная геометрия":
  • Convex
  • Polygon
  • Trap


5 марта 2004 года


Тур на разные задачи:
  • Многоугольник
  • Ребус
  • Лабиринт


9 марта 2004 года


Лекция на тему: "Введение в теорию графов"
Лектор : Хусаинов Д.Р.

  1. Терминология, основные теоремы

    • Определение графа, виды графа, способы хранения
    • Лемма о рукопажатиях
    • Планарные графы и их свойства, теорема Эйлера, теорема Понтрягина-Куратовского

  2. Обходы графов

    • Поиск в ширину
    • Поиск в глубину
      • Проверка на двудольность, теорема Кенига
      • Нахождение мостов, точек сочленения
      • Поиск эйлерова цикла, O(V3) и O(V+E) реализации
      • Топологическая сортировка
      • Нахождение компонент сильной связаности, граф Герца

  3. Кратчайшие пути в графах

    • Алгоритм Дейкстры
    • Алгоритм Беллмана-Форда
    • Алгоритм Флойда
    • Алгортим Джонсона
    • Нахождение циклов отрицательной длины, O(V3) и O(V*E) реализации

  4. Паросочетания

    • Теорема об увеличивающей цепочке
    • Нахождение максимального паросочетания за O(V3)




12 марта 2004 года


Тур на разные задачи:
  • Галактика
  • Пиво

Rambler's Top100
Copyright © 2003 BYOI.Narod.Ru
Создание сайта: Хусаинов Дмитрий, Метельский Иван