Ю. А. Самарский 10 июня 2008 г. Программа

Вид материала

Программа

Содержание Введение в разработку и анализ алгоритмов. Поисковые и индексные структуры. Жадные алгоритмы. Динамическое программирование. Переборные методы решения задач. Алгоритмы на графах. Потоки в сетях. Поисковые структуры в многомерных пространствах. Список литературы STL). Задачи, отмеченные меткой EJ Поиск максимальной общей подпоследовательности двух строк (EJ-042). Восстановление сигнала по Витерби. Топологическая сортировка вершин графа. Сильно связные компоненты. 2. Жадные алгоритмы. Указание по реализации 3. Динамическое программирования. 4. Переборные задачи. Эвристики.

Подобный материал:

• Ю. А. Самарский 10 июня 2008 г. Программа, 163kb.
• Приказ 17 июня 2009 №529 Об утверждении Стратегии обеспечения единства измерений, 1213.66kb.
• Министерство образования и науки самарской области самарский государственный университет, 78.11kb.
• Ю. А. Самарский 10 июня 2011 г. Программа, 140.09kb.
• Технический регламент на молоко и закон РФ от 12 июня 2008 г. №88-фз // Вестник технического, 41.94kb.
• Королевские прокламации Тюдоров как источник по истории английского абсолютизма, 126.61kb.
• Программа курса "Методика дипломного исследования по отечественной истории" для студентов, 100.26kb.
• Муниципального образовательного учреждения, 410.2kb.
• Информационный бюллетень местного самоуправления Издается асдг по с окмо с февраля, 1775.64kb.
• Информационный бюллетень местного самоуправления Издается асдг по с окмо с февраля, 2146.28kb.

УТВЕРЖДАЮ

Проректор по учебной работе

Ю.А. Самарский

10 июня 2008 г.

ПРОГРАММА

по курсу ИНФОРМАТИКА И ПРИМЕНЕНИЕ КОМПЬЮТЕРОВ В НАУЧНЫХ ИССЛЕДОВАНИЯХ (Алгоритмы и структуры данных)

по направлению 511600

факультеты ФИВТ

кафедра ИНФОРМАТИКИ

курс II

семестр 3 Два задания

лекции – 34 часа Две контрольные работы

практические Зачет дифференцированный

занятия – 51 часов


ВСЕГО ЧАСОВ – 85


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

к.т.н. Д.В.Полевой


Программа обсуждена

на заседании кафедры

информатики

28 августа 2008 г.


Заведующий кафедрой И.Б. Петров

Введение в разработку и анализ алгоритмов. Понятие алгоритмической сложности. Критерии качества алгоритма. Амортизационный анализ. Задачи полиномиальной сложности и NP-сложные задачи. Использование приближенных решений.

Поисковые и индексные структуры. Сбалансированные деревья и задачи поиска. АВЛ–дерево и красно-чёрное дерево. B-деревья. Реализации абстрактной структуры данных «ассоциативный массив» и их сравнительный анализ: хэш-таблицы (с открытой адресацией и без), различные деревья поиска. Суффиксное дерево. Суффиксный массив.

Жадные алгоритмы.

Общий принцип и границы применимости. Задачи о выборе заявок. Кодирование и алгоритм Хаффмана построения оптимального префиксного дерева. Сравнение динамического программирования и жадных алгоритмов (задача заполнения рюкзака).

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

Общий принцип динамического программирования и границы применимости. Динамическое программирование сверху. Задача поиска наибольшей общей подпоследовательности и дуальная задача. Задача поиска наибольшей общей подпоследовательности. Задача декодирования сигнала, схема Витерби.

Переборные методы решения задач.

Переборная схема и функция оценки, поиск с возвратом. Альфа-бета отсечение. Метод ветвей и границ. Техника узкого окна. Использование эвристик (наискорейший подъем, частичный путь минимальной стоимости).

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

Потоки в сетях. Метод Форда-Уоршола. Алгоритм Джонсона для разреженных графов.

Метаэвристики в примерах.

Стратегии жадности и локальности. Макро-объекты. Метод отжига. Метод огрубления. «Разделяй и властвуй». Генетические алгоритмы. Метасистемные переходы на уровне алгоритмов. Задача о коммивояжере. Задача кластеризации.

Поисковые структуры в многомерных пространствах.

Многомерные бинарные деревья (k-d trees), интервальные деревья (range trees). Задача поиска подмножества точек в заданной области многомерного пространства. Задача кластеризации точек.

Разработка программных систем. Проектирование, прототипирование, тестирование, верификация и документирование. Критерии качества кода.

СПИСОК ЛИТЕРАТУРЫ

1. Керниган Б.У., Пайк Р. Практика программирования, – М.: Издательский дом «Вильямс», 2004.
   
2. Кормен Т.Х., Лейзерсон Ч.И., Ривест Р.Л., Штайн К. Алгоритмы: построение и анализ, 2-е изд. – М.: Издательский дом «Вильямс», 2006.
   
3. Ахо А., Хопкрофт Дж., Ульман Дж. Структуры данных и алгоритмы. – М.: Издательский дом «Вильямс», 2000.
   
4. про computational geometry
   
5. Бентли Дж. Жемчужины программирования, 2-е изд. – СПб.: Питер, 2002.
   
6. Ласло М. Вычислительная геометрия и компьютерная графика на С++, пер. с англ. – М.: ”Издательство БИНОМ”, 1997.
   
7. Мейерс Скотт, Эффективное использование STL, – М.: Питер, 2002.
   
8. Ворожцов А.В., Винокуров Н.А. Практика и теория программирования. – М.: Физ-Мат., 2008 г.
   

Рекомендации к проведению практических занятий.

Цель курса – освоение ряда методов, которые позволяют решать алгоритмические задачи, знакомство с идеями и терминами, которые являются инструментарием при разработке технологических и программных решений.

Для решения задач использовать C++ со стандартной библиотекой (в т.ч. STL).

Задачи, отмеченные меткой EJ, присутствуют на сайте ссылка скрыта и позволяют осуществить автоматическую проверку решения. Для сдачи задания необходимо послать их на проверку и получить подтверждение об успешной проверке, но это не достаточное условие сдачи задачи.

Семинарист может пометить некоторые задачи как необязательные и дополнить список задач.

ЗАДАЧИ

(для совместного разбора)

Данные задачи будут разбираться на лекциях примерно в той последовательности, в которой здесь приведены.

1. Различные реализации интерфейса «ассоциативный массив»: дерево поиска, сбалансированное дерево поиска (АВЛ или красно-чёрное), хэш-таблица с открытой и закрытой адресацией.

2. Задача «Стабильный коллектив» (EJ-106). ссылка скрыта
   
3. Суффиксное дерево. Суффиксный массив.
   
4. Задачи о выборе заявок: максимизация числа заявок, минимизация числа аудиторий.
   
5. Кодирование Хаффмана и арифметическое кодирование.
   

6. Непрерывная задача о рюкзаке. Дискретная задача о рюкзаке. Применение метода динамического программирования при ограничении на общую массу предметов.

7. Наибольшая возрастающая подпоследовательность и дуальная к ней задача о разбиении последовательности на минимальное число убывающих (EJ-118).

8. Поиск максимальной общей подпоследовательности двух строк (EJ-042).

9. Задача «Minimal Range Query» (EJ-105). Связь с задачей «LCA» (EJ-123).
   

10. Восстановление сигнала по Витерби.

11. Топологическая сортировка вершин графа. Сильно связные компоненты.

12. Построение остовного дерева. Структура для непересекающихся множеств. Техника сжатия путей.
    
13. Поиск кратчайшего пути в графе. Поиск кратчайших путей для всех пар вершин графа.
    
14. Нахождение максимального потока в сети.
    
15. Range-trees.
    

ЗАДАНИЕ 1

(срок сдачи 25–29 октября)

1. Поисковые и индексные структуры.

1.1. Напишите реализации абстрактных структур данных «ассоциативный массив» и «очередь с приоритетом», либо используйте существующие контейнеры в библиотеке STL. Решите задачу «Радио»
(EJ-130). Поясните, как при решении этой задачи ограничиться только контейнером map.

1.2. Реализуйте суффиксный массив согласно описанию, данному на ссылка скрыта. Напишите библиотеку, которая позволяет после препроцессинга теста быстро находить все места, где встречается заданная строка. Интерфейс библиотеки может быть таким:

// создает индекс для заданного текста

index* create_index(const char *text);

// возвращает массив ссылок на места, где встречается слово;

// за освобождение этого массива отвечает вызывающая сторона

char** lookup(index *idx, const char *word);

Вы можете дополнить этот интерфейс и сделать его объектно-ориентированным. Протестируйте свою библиотеку. Напишите к ней документацию.

2. Жадные алгоритмы.

2.1. Задача “Атлеты” (EJ-004).

2.2. Задача “Алиса и Базилио” (EJ-058).

2.3. Написать программу для кодирования и декодирования файлов с использованием кодов Хаффмана. Провести эксперименты для разных типов файлов (txt, bmp, jpg), разных размеров ‘символов’ (1, 2, 4 байта) и сделать выводы об эффективности алгоритма.

Указание по реализации: самостоятельно реализовать одну из возможных специальных структур данных для сбора частотных характеристик, самостоятельно реализовать очередь с приоритетами.

3. Динамическое программирования.

3.1. На отрезке [0,1] размещено N+1 упорядоченных точек a_i. При этом a₀ = 0, a_N = 1, i < j→ a_i < a_j. На всех парах точек определена функция f задающая вес w_ij=f(i,j). Путем назовем последовательности K точек a_p, a₀ = a_p1 < a_p2 <…< a_pK = a_N, при этом вес пути W = f(p₁, p₂) + f(p₂, p₃) +…+ f(p_K-1, p_K). Написать программу для нахождения пути максимального веса.

3.2. Задача «LCS» (EJ-042).

3.3. Задача «Minimal Range Query» (EJ-105). При решении создайте таблицу, в ячейке (i, j) которой находится ответ на запрос поиска минимума среди чисел a(i),… a(i+2^j). Время препроцессинга должно оцениваться как O(n log n), а время выполнения отдельного запроса – O(1).

ЗАДАНИЕ 2

(срок сдачи 13–18 декабря)

4. Переборные задачи. Эвристики.

4.1. Задача “Восьминашки” (EJ-089).

4.2. Задача “Эндшпиль” (EJ-048).

4.3. Задача “Пятнашки” (EJ-091). Головоломка "пятнашки" заключается в следующем. Даны квадратные фишки с номерами 1, 2, 3, ..., 15, которые уложены в плоскую коробочку размера 4x4. Коробочка разделена на 16 ячеек, и каждая фишка лежит точно в одной ячейке. Одна из ячеек пустая. Разрешено за один ход одну из фишек, соседних с пустой ячейкой, передвинуть в эту ячейку.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15   Целевое состояние головоломки.

a1 a2 a3 a4 a5 a6 a7 a8 a9 a10 a11 a12 a13 a14 a15 a16 Начальное состояние головоломки.

На вход даётся начальное состояние головоломки пятнашки. Необходимо определить, можно ли её решить, и если можно, то вывести последовательность ходов, которые её решают.

Вход. Строка с числами a₁, a₂, ...., a₁₆, которые описывают начальное состояние головоломки.

Выход. Выведите NO, если головоломку нельзя решить. Если головоломку можно решить, то выведите YES, а в следующей строке выведите последовательность ходов, которые нужно сделать, чтобы достичь целевого состояния. Ход — обозначается одним из четырех символов: "r", "l", "u", "d" (right, left, up, down), и оно соответствует направлению перемещения пустой ячейки (вправо, влево, вверх и вниз, соответственно). Число ходов должно быть меньше 1000. Пробелы между буквами ставить не нужно. Примеры входа/выхода:

Вход#1 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 0

Выход#1 YES

Вход#2 1 2 3 4 5 6 7 8 9 10 0 11 13 14 15 12

Выход#2 YES rd

5. Алгоритмы и структуры данных. Алгоритмы на графах.

5.1. Задача «Пожарные станции» (EJ-092).

5.2. Задача «Минимальное дополнение до сильно связного графа» (EJ-098).

5.3. Задача «2D-Range Query» (EJ-120). Напишите модуль для визуализации решения.

5.4. Задача «Лучшая кластеризация» (EJ-046). Напишите модуль для визуализации решения.