Дата: 2 сентября 2004 г.
Тема: Повторение материала предыдущего семестра. Поиск, сортировки.
Материалы: Пятиминутка (PDF,
PostScript,
OO Writer).
Дата: 9 сентября 2004 г.
Тема: Подробно об указателях. Связь массивов и указателей.
Передача массивов в функции. Арифметика указателей.
Выделение памяти (malloc(), free()).
Материалы: Пятиминутка (PDF,
PostScript,
OO Writer).
Дата: 16 сентября 2004 г.
Тема: Связанные списки. Структура, выделение памяти, добавление и удаление
элементов. Проход по списку (while (p) p = p->next;).
Кратко о двусвязных списках. Стеки, очереди, деки. Примеры использования.
Задача о скобках, перевод выражения из инфиксной формы в постфиксную
(«обратная польская запись») и вычисление значения выражения в
постфиксной записи.
Материалы: Пятиминутка (PDF,
PostScript,
OO Writer).
Информация об односвязных
списках и об алгоритмах вычисления на стеке
в разделе практики.
Дата: 23 сентября 2004 г.
Тема: Задачи на списках. «Разворот» списка, слияние двух отсортированных
списков, задача Иосифа. Хэш-таблицы с разрешением коллизий при помощи списков.
Материалы: Пятиминутка (PDF,
PostScript,
OO Writer).
Информация о хэш-таблицах в разделе практики.
Дата: 30 сентября 2004 г.
Тема: Самостоятельная работа по спискам. Бинарные деревья. Инфиксный, префиксный, постфиксный обходы.
Дата: 7 октября 2004 г.
Тема: Разбор самостоятельной работы. Группа 1: Задачи на обходы деревьев. Группа 2: Деревья двоичного
поиска, добавление узлов в дерево двоичного поиска.
Материалы: Информация о двоичных деревьях
в разделе практики.
Дата: 14 октября 2004 г.
Тема: Группа 1: Повторение темы практического задания 2. Деревья двоичного поиска.
Группа 2: Удаление узлов из дерева двоичного поиска. Сбалансированные деревья. Правая и левая скобочные записи
деревьев.
Дата: 21 октября 2004 г.
Тема: Графы. Способы представления графов: матрица смежности, список ребер, списки смежности. Топологическая
сортировка на матрицах смежности.
Материалы: Информация о топологической сортировке
в разделе практики.
Дата: 28 октября 2004 г.
Тема: Контрольная работа. Топологическая сортировка на иерархических списках.
Дата: 4 ноября 2004 г.
Тема: Транзитивное замыкание. Обходы графа в глубину и в ширину.
Материалы: Информация о способах обхода графа
в разделе практики.
Дата: 11 ноября 2004 г.
Тема: Алгоритмы Флойда и Дейкстры для поиска кратчайших путей в графе..
Материалы: Информация об алгоритмах Флойда и Дейкстры
в разделе практики.
Дата: 18 ноября 2004 г.
Тема: Каркас графа. Задачи на каркас. Алгоритмы Прима и Краскала для поиска каркаса
минимальной стоимости.
Материалы: Информация об алгоритмах Прима и Краскала
в разделе практики.
Дата: 25 ноября 2004 г.
Тема: Двусвязность. Алгоритм поиска двусвязных компонент и точек сочленения.
Дата: 2 декабря 2004 г.
Тема: Эйлеровы и гамильтоновы циклы. Критерий существования эйлерова пути, эйлерова цикла.
Алгоритм Флери, алгоритм со стеком. Раскраска графа в два цвета, двудольные графы, паросочетания.
Задача о кубиках с буквами. Алгоритм поиска максимального паросочетания через чередующиеся пути.
Дата: 9 декабря 2004 г.
Тема: Контрольная работа по теории графов. [Группа 1: качественные задачи, проверка связности
двух вершин графа, подсчет количества различных путей между двумя вершинами графа. Группа 2:
качественные задачи, подсчет длины кратчайшего пути между двумя вершинами в неориентированном
графе, подсчет диаметра графа.] Динамическое программирование. Задача о максимальном подпалиндроме,
задача о максимальной общей подпоследовательности (алгоритм Ахо).
Дата: 16 декабря 2004 г.
Тема: Задачи на динамическое программирование: лыжники, скобки, гангстеры. Краткий обзор
курса методов программирования за год.