Программа по курсу информатика и применение компьютеров в научных исследованиях (Алгоритмы и структуры данных) по направлению



Скачать 85.63 Kb.
Дата01.01.2013
Размер85.63 Kb.
ТипПрограмма
УТВЕРЖДАЮ

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

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

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, присутствуют на сайте http://su5.mipt.ru/judge и позволяют осуществить автоматическую проверку решения. Для сдачи задания необходимо послать их на проверку и получить подтверждение об успешной проверке, но это не достаточное условие сдачи задачи.

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

ЗАДАЧИ


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

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


  2. Задача «Стабильный коллектив» (EJ-106). http://acm.mipt.ru/twiki/bin/view/Algorithms/HarmoniousGroup

  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. Реализуйте суффиксный массив согласно описанию, данному на http://acm.mipt.ru/twiki/view/Algorithms/SuffixArray. Напишите библиотеку, которая позволяет после препроцессинга теста быстро находить все места, где встречается заданная строка. Интерфейс библиотеки может быть таким:

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

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 упорядоченных точек ai. При этом a0 = 0, aN = 1, i < j→ ai < aj. На всех парах точек определена функция f задающая вес wij=f(i,j). Путем назовем последовательности K точек ap, a0 = ap1 < ap2 <…< apK = aN, при этом вес пути W = f(p1, p2) + f(p2, p3) +…+ f(pK-1, pK). Написать программу для нахождения пути максимального веса.

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

3.3. Задача «Minimal Range Query» (EJ-105). При решении создайте таблицу, в ячейке (i, j) которой находится ответ на запрос поиска минимума среди чисел a(i),… a(i+2j). Время препроцессинга должно оцениваться как 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

Начальное состояние головоломки.

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

Вход. Строка с числами a1, a2, ...., a16, которые описывают начальное состояние головоломки.

Выход. Выведите 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). Напишите модуль для визуализации решения.

Похожие:

Программа по курсу информатика и применение компьютеров в научных исследованиях (Алгоритмы и структуры данных) по направлению iconПрограмма по курсу информатика и применение компьютеров в научных исследованиях
Процесс написания программ. Оформление текстов, требования к текстам и комментариям. Сопровождение программ. Документация на по,...
Программа по курсу информатика и применение компьютеров в научных исследованиях (Алгоритмы и структуры данных) по направлению iconПроект по курсу «Информатика и применение компьютеров в научных исследованиях» Моделирование оптических систем методом трассировки луча
В рамках изучения основ объектно-ориентированного программирования было принято решение применить полученные знания в разработке...
Программа по курсу информатика и применение компьютеров в научных исследованиях (Алгоритмы и структуры данных) по направлению iconСписок вопросов к экзамену по курсу “Информатика и программирование”
Информатика. Этапы решения задач. Алгоритм. Программа. Языки программирования, их характеристика. Синтаксис, семантика, прагматика....
Программа по курсу информатика и применение компьютеров в научных исследованиях (Алгоритмы и структуры данных) по направлению iconВопросы к экзамену по курсу «Структуры и алгоритмы обработки данных»
Вопросы к экзамену по курсу «Структуры и алгоритмы обработки данных» в 2009-2010 уч году
Программа по курсу информатика и применение компьютеров в научных исследованиях (Алгоритмы и структуры данных) по направлению iconПрограмма дисциплины Алгоритмы и структуры данных для направления 010400. 62 «Прикладная математика и информатика» подготовки бакалавров

Программа по курсу информатика и применение компьютеров в научных исследованиях (Алгоритмы и структуры данных) по направлению iconРабочая программа дисциплины "структуры и алгоритмы обработки данных"
Рабочая программа составлена в соответствии с государственным образовательным стандартом по направлению
Программа по курсу информатика и применение компьютеров в научных исследованиях (Алгоритмы и структуры данных) по направлению iconПрограмма дисциплины Алгоритмы и структуры данных для поиска для направления 010400. 68 «Прикладная математика и информатика»

Программа по курсу информатика и применение компьютеров в научных исследованиях (Алгоритмы и структуры данных) по направлению iconУчебное пособие по дисциплине «Структуры и алгоритмы обработки данных» для специальностей «Программное обеспечение информационных технологий»
Структуры и алгоритмы обработки данных: Учеб пособие. – Мн: бнту, 2010. – 151 с.: ил
Программа по курсу информатика и применение компьютеров в научных исследованиях (Алгоритмы и структуры данных) по направлению iconПрактикума по курсу «Алгоритмы и структуры данных»
Приводится примерный список задач для разбора на практических занятиях
Программа по курсу информатика и применение компьютеров в научных исследованиях (Алгоритмы и структуры данных) по направлению iconУчебная программа Дисциплины б4 «Алгоритмы и анализ сложности»
Дисциплина «Алгоритмы и анализ сложности» относится к дисциплинам базовой части профессионального цикла основной образовательной...
Разместите кнопку на своём сайте:
ru.convdocs.org


База данных защищена авторским правом ©ru.convdocs.org 2016
обратиться к администрации
ru.convdocs.org