Комбинаторные алгоритмы 1 ©Павловская Т.А. (СПбГУ ИТМО) Павловская Татьяна Александровна профессор кафедры информатики и прикладной математики (ауд. 378, тел.: (812) ) Материалы на сайте:

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

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

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

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

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

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

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

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

Содержание отчета 1. Титульный лист (фамилия, группа, дисциплина, название задания, текст конкретного варианта, дата). 2. Описание алгоритма (словесная форма, схема алгоритма). // Методичку и учебники не копировать. Описать своими словами. 3. Текст программы. 4. Таблицы результатов замеров времени. 5. Графики зависимостей с коэффициентами аппроксимирующих функций. // Графики должны наглядно представлять исследуемые зависимости и сравнение алгоритмов. Аппроксимирующие коэффициенты выводятся для 2-3 графиков 6. Выводы по работе (словесное описание исследованных характеристик каждого алгоритма, сравнение алгоритмов по этим характеристикам, достоинства, недостатки и области применимости). ©Павловская Т.А. (СПбГУ ИТМО) 10