Комбинаторные алгоритмы

Содержание курса
Общие комбинаторные алгоритмы
Алгоритмы сортировки и поиска
Алгоритмы на строках
Лабораторные работы:
Исследование алгоритмов сортировки
Исследование алгоритмов поиска
©Павловская Т.А. (СПбГУ ИТМО)
«Самое ценное в научном или техническом образовании — это развитие
универсального мыслительного аппарата, который будет служить вам
на протяжении всей жизни.»
Джордж Форсайт
«Часто говорят, что человек ничего не понимает, пока не объяснит это кому-то другому. Я бы перефразировал это так: человек глубоко не понимает предмет до тех пор, пока не научит этому компьютер, т.е. выразит что-либо в виде алгоритма... Попытка формализовать нечто в виде набора алгоритмов приводит к более глубокому пониманию сути вещей.»
Дональд Кнут

Виды учебной нагрузки
Лекции – 17 ч.
Лабораторные работы – 17 ч.
Лаб № 1 (Сортировка) – 20-33 б.
Лаб № 2 (Поиск) – 16–25 б.
Домашнее задание – 6-10 б.
Рубежный контроль – (6-10 б. в каждом модуле)
Личностные качества (3-5 б. в каждом модуле)
Зачет – при успешном выполнении всех видов контроля
©Павловская Т.А. (СПбГУ ИТМО)

Литература
а) основная литература:
Кукушкин Б.А. Описания комбинаторных алгоритмов (эл. вид).
Кнут Д. Искусство программирования, т.3. Сортировка и поиск. — М.: Вильямс, 2011. — 824 с.
Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. – М.: Вильямс, 2011. — 1296 с.
Макконнелл Дж. Основы современных алгоритмов. — М. : Техносфера, 2004. — 368с.
б) дополнительная литература:
Вирт Н. Алгоритмы и структуры данных. — М., ДМК_Пресс, 2011. — 272 с.
Ахо А., Дж. Хопкрофт, Дж. Ульман. Структуры данных и алгоритмы. — М., : Вильямс, 2010. — 384 с.
Левитин А.В. Алгоритмы: введение в разработку и анализ. : Пер. с англ. — М. : Издательский дом "Вильямс", 2006. — 576 с.
©Павловская Т.А. (СПбГУ ИТМО)

Литература - продолжение
Седжвик Р. Фундаментальные алгоритмы на C++. ч. 1-5. Анализ/Структуры данных/Сортировка/Поиск: Пер. с англ./Роберт Седжвик. - К.: Издательство «ДиаСофт», 2003.- 688 с.
Окулов С. М. Программирование в алгоритмах. — М.: БИНОМ, Лаборатория знаний, 2002. — 341 с.
Гудман С., С. Хидетниеми. Введение в разработку и анализ алгоритмов. М., Мир, 1981.
Рейнгольд Э., Ю.Нивергельт, М.Део. Комбинаторные алгоритмы – теория и практика. М, Мир, 1980.
Липский В. Комбинаторика для программистов. М., Мир. 1988.
Электронные версии большинства учебников – на сайте
©Павловская Т.А. (СПбГУ ИТМО)

Интернет-источники
www.intuit.ru/department/algorithms/algocombi/ - Комбинаторные алгоритмы для программистов – учебный курс.
pta-ipm.narod.ru — презентации лекций, задания, учебники, ссылки.
rain.ifmo.ru/cat/view.php/vis — визуализаторы алгоритмов
neerc.ifmo.ru/mediawiki — определения, материалы
alglib.sources.ru - описание аппроксимации МНК
ips.ifmo.ru/courses/coursesinfo/index.html - курс С. Е. Столяра «Введение в алгоритмику»
…
©Павловская Т.А. (СПбГУ ИТМО)

Лабораторная работа 1:
Исследование алгоритмов сортировки
Цель работы:
Реализация алгоритмов сортировки и исследование их характеристик:
быстродействие
требуемый объем памяти
естественность поведения
устойчивость
область применимости
©Павловская Т.А. (СПбГУ ИТМО)

Этапы выполнения работы
Реализовать алгоритмы сортировки, заданные в варианте задания. Отладить их на последовательности, приведенной в методичке (этап 1: 7-11 баллов).
Изучить средства измерения интервалов времени.
Измерить время сортировки для всех файлов из каталога F_SORT.
Файлы (около 80) имеют разную длину и степень упорядоченности. Имена файлов сформированы так:
4-значное число - длина файла в байтах
символ подчеркивания
3-значное число, задающее процент инверсий.
Расширение файла (1,2,3) определяет случайный вариант файла с одними и теми же параметрами
Например, файл 0256_075.2 соответствует последовательности из 256 чисел с количеством инверсий I=75%=24384 от максимального, вариант 2.
©Павловская Т.А. (СПбГУ ИТМО)

Построить аппроксимирующие графики зависимостей времени сортировки от длины файла (этап 2: 10-17 баллов).
©Павловская Т.А. (СПбГУ ИТМО)
Экспериментальные данные представить точками (маркерами).
Линии – аппроксимирующие зависимости (получить вручную МНК или средствами любых пакетов).
Вывести коэффициенты зависимостей.
Написать выводы по работе (этап 3: 3-5 баллов).