МЕТОДЫ ПРОГРАММИРОВАНИЯ

План семинаров и практических занятий

1 семестр

Примерный план семинаров

Тема 1.  Введение в язык C

Переменные, функции.  Условные инструкции.  Рекурсия: простейшие рекурсивные
алгоритмы.  Логические операции.  Указатели и  массивы,  строки.  Ввод и вывод
(stdio.h).  Структуры.

Тема 2.  Системы счисления и представление чисел в ЭВМ

Позиционные системы счисления.  Перевод целых и дробных чисел из 10-й системы в
систему по основанию b и наоборот.  Особенности умножения и деления на основание
системы счисления.  Кратные системы счисления.  Двоичная система, представление
натуральных чисел в ЭВМ.  Способы представления отрицательных чисел: прямой,
обратный и дополнительный коды.  Способы представления дробных чисел:
фиксированная и плавающая точка.

Контрольная работа

Тема 3.  Перестановки

Обзор алгоритмов генерации всех перестановок элементов N-элементного множества. 
Рекурсивный метод.  Беспорядки, таблица инверсий, инверсионный метод.  Метод
Кнута.  Понятие лексикографического порядка, алгоритм Дейкстры генерации
следующей по алфавиту перестановки.

Тема 4.  Поиск в массиве

Линейный поиск элемента в массиве, поиск с барьером.  Бинарный поиск элемента в
упорядоченном массиве.  Интерполяционный поиск.  Хэш-таблицы (реализация на
массивах, разрешение коллизий линейным исследованием).

Тема 5.  Поиск подстроки в строке

Прямой поиск.  Алгоритм Бойера-Мура.

Тема 6.  Сортировки

Постановка задачи внутренней сортировки.  Сортировка простыми вставками и метод
Шелла.  Обменная сортировка: метод пузырька, "шейкер", быстрая сортировка. 
Сортировка простым выбором и пирамидальная сортировка.  Оценки сложности в
среднем и наихудшем случаях.

Тема 7.  Слияние

Слияние двух и более упорядоченных последовательностей.  Методы сортировки
больших файлов.

Тема 8.  Архиватор Хаффмана

Бинарные операции в C.  Частота встречаемости символов, дерево Хаффмана
(реализация на массиве),  алгоритм Хаффмана.

Контрольная работа

Темы практических заданий

1.  Треугольник Паскаля
	а.  Через C_n^k
	b.  При помощи одномерного массива
2.  Простые числа
	a.  По определению
	b.  Решето Эратосфена
3.  Задача на строки в C
4.  Системы счисления
5.  Перестановки
	a.  Рекурсивный метод
	b.  Алгоритм Дейкстры
	c.  Инверсионный метод (*)
6.  Поиск
	a.  Бинарный поиск
	b.  Хэш-таблицы (*)
	c.  "Бредогенератор" (**)
7.  Сортировки
	a.  Любая сортировка сложности O(N^2)
	b.  Сортировка Шелла
	c.  Быстрая сортировка
	d.  Пирамидальная сортировка
8.  Сортировка большого файла (*)
9.  Архиватор Хаффмана (**)

2 семестр

Примерный план семинаров

Тема 1.  Связанные списки

Повторение указателей в C.  Структура связанного списка.  Добавление элементов в
начало, середину, конец списка, удаление элементов.  Двунаправленные и
циклические списки.  Задачи на списки. 

Тема 2.  Стеки, очереди, деки

Определение и способы реализации стека, очереди, дека.  Примеры применения
структур, задачи.

Тема 3.  Обратная польская запись

Определение инфиксной, префиксной и постфиксной записи арифметического
выражения.  Алгоритм Дейкстры перевода выражения из инфиксной записи в
постфиксную (обратную польскую).  Вычисление значения выражения в обратной
польской записи.

Тема 4.  Деревья

Определение бинарного дерева,  способы представления.  Поиск, добавление и
удаление элементов.  Обходы в глубину (префиксный, инфиксный, постфиксный) и в
ширину.  Задачи на деревья.  Деревья двоичного поиска.  Поиск, добавление и
удаление элементов.  Сбалансированные деревья двоичного поиска.

Контрольная работа

Тема 5.  Графы

Определения, способы представления графов.  Представление бинарного отношения в
виде графа, топологическая сортировка.  Транзитивное замыкание.  Поиск
кратчайшего пути во взвешенном графе, алгоритмы Флойда и Дейкстры.  Обходы
графов в ширину и глубину.  Остовное дерево, минимальный каркас, алгоритмы Прима
и Краскала.    Поиск двусвязных компонент и точек сочленения.  Мосты.  Эйлеровы
и гамильтоновы циклы.  Труднорешаемые задачи на графах.

Тема 6.  Динамическое программирование

Определение, область применения.  Примеры задач, решаемых этим методом.

Контрольная работа

Темы практических заданий

1.  Работа со списками
	a.  Сортировка чисел вставкой в упорядоченный список
	b.  Реализация хэш-таблицы, разрешение коллизий при помощи списков (*)
2.  Обратная польская запись
	a.  Преобразование выражения из инфиксной записи в обратную польскую.
	b.  Вычисление значения выражения в обратной польской записи.
	b.  Простейший интерпретатор
3.  Деревья двоичного поиска
	a.  Реализация добавления элементов в дерево двоичного поиска
	b.  Реализация сбалансированного дерева (**)
4.  Топологическая сортировка
	а.  Реализация на матрицах смежности
	b.  Реализация на иерархических списках
5.  Поиск кратчайшего пути во взвешенном графе
	а.  Алгоритм Флойда
	b.  Алгоритм Дейкстры
6.  Обходы графа
	a.  Поиск в глубину
	b.  Поиск в ширину
7.  Построение каркаса минимальной стоимости
	a.  Алгоритм Прима
	b.  Алгоритм Краскала
8.  Поиск двусвязных компонент и точек сочленения (*)
9.  Задание на динамическое программирование

Примечания

(*)	-- сдача задания необходима для получения оценки "отлично"
(**)	-- задание не является обязательным