'

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

Понравилась презентация – покажи это...





Слайд 0

Комбинаторные алгоритмы 1 ©Павловская Т.А. (СПбГУ ИТМО) Павловская Татьяна Александровна профессор кафедры информатики и прикладной математики (ауд. 378, тел.: (812)233-4690) e-mail: pta-ipm@yandex.ru Материалы на сайте: http://pta-ipm.narod.ru


Слайд 1

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


Слайд 2

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


Слайд 3

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


Слайд 4

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


Слайд 5

Интернет-источники 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 - курс С. Е. Столяра «Введение в алгоритмику» … ©Павловская Т.А. (СПбГУ ИТМО) 6


Слайд 6

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


Слайд 7

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


Слайд 8

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


Слайд 9

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


×

HTML:





Ссылка: