Разработка программ повышенной сложности

Программа учебного курса РАЗРАБОТКА ПРОГРАММ ПОВЫШЕННОЙ СЛОЖНОСТИ I. Организационно-методический раздел. Курс реализуется в рамках специальности 220400 «Программное обеспечение вычислительной техники и автоматизированных систем», относится к циклу специальных дисциплин. 1.1.Цели и задачи курса Цели курса - знакомство с типовыми задачами программирования и основными моделями и методами их решения; - освоение алгоритмов и методов разработки программ для решения задач повышенной сложности в разных направлениях информатики; - cовершенствование владения языками программирования и техникой программирования.

Задачи курса - дать представление информации в ЭВМ и различных структур данных, способы кодирования информации; - рассмотреть основные классические алгоритмы из теории графов, поиска, сортировки, используемые при решении задач повышенной сложности; - представить методы: итерационный, рекурсивный, полного перебора и с отсечением, метод ветвей и границ, “разделяй и властвуй”, динамического программировния; - рассмотреть задачи минимизации, поиска оптимальных стратегий, теории расписаний, задачи, решаемые с использованием жадных алгоритмов и метода динамического программирования; классическим и - дать представление о сведении задач к известным эвристический подход; - научить оценивать объем требуемой для реализации памяти и быстродействие программ. 1.2.Требования к уровню освоения содержания курса По окончании изучения указанной дисциплины студент должен иметь представление - о различных стилях программирования; - о способах оценки (объема памяти и быстродействия) методов решения задачи; - о приближенных алгоритмах; - об оптимальных стратегиях игр.

знать - основные классические алгоритмы теории графов, расписаний, поиска, сортировки; - классические и типовые задачи, перечень NP-полных задач; - основные структуры данных и способы их реализации; - способы кодирования информации в ЭВМ.

уметь - реализовать представленные методы (итерационный, рекурсивный, динамического программирования) и алгоритмы; - корректно поставить задачу на основании формулировки проблемы и ее контекста; - доказательно выбрать самый оптимальный способ решения на основе анализа вариантов решения и различных критериев эффективности; - реализовать решение задачи в крайне ограниченное и строго определенное время. 1.3.Формы контроля Итоговый контроль. Для контроля усвоения дисциплины учебным планом предусмотрен экзамен по теоретической части и зачет по практической части. Текущий контроль. В течение семестра каждую неделю выполняются практические работы, по решению задач, либо взятых с международных серверов, либо предложенных преподавателями данного курса. Выполнение указанных задач является обязательным для всех студентов, а результаты текущего контроля служат основанием для выставления оценок в ведомость контрольной недели на факультете. 2. Содержание дисциплины. 2.1.Новизна и актуальность курса В данном курсе осуществляется знакомство как с типовыми задачами программирования и основными моделями и методами их решения, на примере которых дается представление об искусстве программирования, так и с современными, постоянно развивающимися, используемыми в ведущих международных чемпионатах по информатике и программированию. 2.2.Тематический план курса (распределение часов).

Наименование разделов и тем Лекции Раздел 1 Представление данных в ЭВМ, способы реализации, оценка сложности алгоритмов Способы кодирования.

10

Количество ЛабораторСеминар ные работы ы

часов Самостоятельная работа

Всего часов

6

16

Раздел 2. Перестановки, поиск, сортировки, хеширование Раздел 3 Классические задачи на графах и деревьях Раздел 4. Обзор NP-полных задач, метод ветвей и границ, динамическое программирование Раздел 5. Стратегии игр, геометрические задачи Раздел 6. Задачи теории расписаний, приближенные алгоритмы Раздел 7. Потоки в сетях, паросочетания.

Итого по курсу

8

4

10

22

14

6

20

40

6

4

10

20

4

2

4

10

4

2

4

10

6

2

6

14

52

24

60

132

2.3.Содержание отдельных разделов и тем. А) Теоретическая часть 1. Представление данных в ЭВМ, способы реализации, оценка сложности алгоритмов 1.1.

1.2. 1.3. 1.4.

2. 2.1. 2.2.

2.3.

2.4.

Представление данных в ЭВМ: представление символов, целых чисел со знаком и без знака, вещественных чисел с фиксированной точкой и плавающей, представление массивов, структур. Системы счисления. Алгоритмы перевода из систем счисления с различными основаниями.. Длинная арифметика, способы реализации в Си и Паскале. Маски, решение задач с их использованием. Понятие сложности алгоритмов, классификация алгоритмов по сложности. Модель информационной системы Шеннона. Кодирование. Типы кодирования. Проблемы однозначного декодирования. Формулы Шеннона и Хартли для удельной емкости на символ. Избыточность кодирования. Метод Хаффмана построения кода с минимальной избыточностью. Перестановки, поиск, сортировки, хеширование Понятие перестановки и таблицы инверсии. Алгоритмы генерации перестановок: инверсионный, Дейкстры, рекурсивный, Кнута. Постановка задач поиска и сортировки записей в произвольном наборе данных, внешняя и внутренняя постановка задачи (при не/доступности всего набора). Алгоритмы поиска: прямой, бинарный, подстроки в строке, Бойера-Мура, КнутаМорриса-Пратта, Рабина-Карпа. Алгоритмы сортировки: метод простых вставок, простого выбора, обмена, быстрая сортировка, сортировка по методу Шелла, ирамидальная сортировка. Алгоритмы сортировки файлов. Достоинства организации исходного набора в виде древовидной структуры для совместного решения задач поиска и сортировки Хэш-функции, расширяемое хеширование.

3. 3.1 3.2 3.3

3.4 4. 4.1 4.2

5. 5.1 5.2

Классические задачи на графах и деревьях Основные определения и способы представления графов и деревьев. Обходы графов и деревьев в глубину и в ширину. Классические задачи на деревьях, алгоритм построения сбалансированного дерева двоичного поиска. Б-деревья, способы реализации. Классические задачи на графах: транзитивное замыкание, кратчайшие пути, достижимость вершин, топологическая сортировка. Поиск двусвязных компонент в графе Алгоритмы построения минимальных остовных деревьев Прима, Краскала. Задачи о лабиринтах. Эйлеровы циклы: алгоритм Флери. Гамильтоновы циклы. Раскраска графа. Автоматы и грамматики, регулярные выражения. Обзор NP-полных задач, метод ветвей и границ, динамическое программирование Обзор NP-полных задач, способы сведения задачи к известной. Способы реализации: полный перебор, перебор с отсечением, метод метод ветвей и границ. Метод “Разделяй и властвуй”, метод динамического программирования. Классические задачи об умножении матриц, о рюкзаке. Задачи с международных чемпионатов, решаемые с помощью динамического программирования. Оценка быстродействия. Стратегии игр, геометрические задачи Определение стратегии игры, поиск оптимальных стратегий. Определение неподвижной точки. Приемы решения геометрических задач. Построение выпуклой оболочки, определение местоположения точки, отрезка и т.д.

6.

Задачи теории расписаний, приближенные алгоритмы для NP-полных задач, оценка ошибки, быстродействие программы.

7.

Потоки в сетях, паросочетания

7.1 7.2

Потоки в сетях, понятие остаточной сети. Теорема о максимальном потоке и минимальном разрезе. Метод Форда-Фалкерсона и алгоритм Эдмодса-Карпа. Алгоритм поиска максимального потока методом проталкивания предпотока. Паросочетания, поиск максимальных паросочетаний в двудольном графе. Б) Практические занятия

Каждый студент должен выполнить серию практических заданий по реализации классических алгоритмов и разработать и реализовать несколько задач повышенной сложности, взятых либо с о сторонних серверов, либо предложенных преподавателями этого курса. 2.4. Перечень примерных контрольных вопросов и заданий для самостоятельной работы: - стек, преобразование инфиксной формы записи выражения в постфиксную и вычисление значения полученного выражения;

- cписок, как универсальная модель линейно упорядоченных структур данных последовательного доступа, разновидности списков; - рекурсия как общий метод сведения задачи к самой себе, ветвящаяся рекурсия; - динамическое программирование как решение задач с помощью табличной техники, задача о ганстерах, о делимости (http://neerc.ifmo.ru); - изучить и реализовать задачу о стабильных браках; - рассмотреть алгоритмы с возвратом на примере шахматных задач; - Символьные формализмы для описания синтаксиса языков (БНФ, РБНФ). 3. Учебно-методическое обеспечение дисциплины 3.1.Образцы вопросов для подготовки к экзамену Раздел 1. 1) Привести примеры программ из различных классов вычислительной сложности. Привести нижние и верхние оценки для изученных классов задач. 2) Построить дерево Хаффмана с минимальной избыточностью для определенного текста. Раздел 2 1) Реализовать быструю сортировку Хоара, привести оценки сложности. 2) Определить таблицы инверсий и представить алгоритм восстановления перестановки по таблице инверсий. 3) Итерационный алгоритм генерации всех таблиц инверсий. 3) Описать алгоритм Бойера-Мура и дать оценки сложности. 4) Представить методы сортировки массива, имеющие оценку O(n2). Раздел 3. 1) Определить граф как наиболее общую модель данных последовательного доступа, пути и маршруты по графу, модели представления в ЭВМ. 2) Левое и правое скобочное представление деревьев. 3) Реализация обхода дерева методом в ширину с использованием очереди. 4) Найти кратчайший путь в лабиринте, тупик, цикл. 5) Построить транзитивное замыкание графа по алгоритму Флойда. 6) Представить алгоритм Декстры для определения кратчайших путей от источника до всех остальных вершин графа. Раздел 4. 1) Представить схему полного перебора на примере предложенной задачи. 2) Рассмотреть задачу обхода конем шахматной доски, дать понятие алгоритма с возвратом. 3) Описать метод ветвей и границ на примере задачи о рюкзаке. 4) Сравнить метод “Разделяй и властвуй” с методом динамического программирования, определить, в чем их различие. 5) Решить задачу обхода матрицы с максимальной суммой с помощью метода методом динамического программирования, оценить быстродействие программы. Раздел 5. 1) Построить оптимальную стратегию для предложенной игры. 2) Построить выпуклую оболочку для предложенных фигур. 3) Определить находится точка внутри многоуголька или снаружи.

Раздел 6. Реализовать приближенный алгоритм для задачи коммивояжера, определить быстродействие программы. Раздел 7. 1) Построить остаточную сеть для заданного потока, определить максимальный разрез.. Реализовать алгоритм Эдмодса-Карпа. 2) Определить максимальное паросочетание в заданном двудольном графе.

3.2.Список основной и дополнительной литературы 1) А.Ахо, Д.Хопкрофт, Д. Ульман. Структуры Издательский дом “Вильямс”, 2000 - 384 с..

данных

и

алгоритмы.

М.:

2) А.Ахо, Д.Хопкрофт, Д. Ульман. Построение и анализ вычислительных алгоритмов(пер. с англ. под ред. Матиясевича Ю.А. ) М: Мир - 1979 г. - 536 с. 3) Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: Построение и анализ (пер. с англ. под ред. Шеня А. ) - 960 с. {Классические учебники: Computer science} М: МЦНМО 01-99 4) Вирт Н. Алгоритмы и структуры данных. М.: Мир, 1989.-360с. 5) Хэзфилд Р., Кирби Л. Искусство программирования на C: Фундаментальные алгоритмы, структуры данных и примеры приложений (пер. с англ.) {Энциклопедия программиста} К: ДиаСофт 01- 736 с. 6) Д. Кнут. Искусство программирования. Т. 1,2,3.М.:Мир,1977. 7) В.А.Цикоза, Т.Г.Чурина. Методическое пособие к курсу программирования” (часть первая). Новосибирск: ВКИ НГУ, 1999.

Программу подготовила: к.ф.-м.н., доцент

“Методы

Чурина Т. Г.

Программа утверждена на заседании Ученого совета факультета информационных технологий Новосибирского государственного университета 18 декабря 2003 г., протокол заседания №16. Декан ФИТ НГУ, д.ф.-м.н.

М.М.Лаврентьев