МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ

Петрозаводский государственный университет

Математический факультет

Кафедра прикладной математики и кибернетики

УТВЕРЖДАЮ

Декан математического факультета

_______________

"_____"__________________2011 г.

Рабочая программа дисциплины

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

Направление подготовки

Информационные системы и технологии

230400

Профиль подготовки

Общий

Квалификация выпускника

Бакалавр

Форма обучения

очная

Петрозаводск

2012

Общие сведения о дисциплине


Название дисциплины – Алгоритмы и структуры данных

Факультет, на котором преподается данная дисциплина - математический

Направление подготовки – Информационные системы и технологии

Квалификация (степень) выпускника - Бакалавр

Цикл дисциплин –  Математический и естественнонаучный

Часть цикла – Базовая

Курс - 2

Семестры - 3

Всего зачетных единиц – 3

Всего часов – 108

Аудиторные занятия 54 часов (лекции 36 часов, практические занятия 18 часов)

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

Экзамен - 2 семестр

Зачет – нет

Составитель рабочей программы – Доцент, к. т.н.

1. Цели освоения дисциплины

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

Задачи дисциплины:

    познакомить студентов с процессом создания алгоритмов решения математических задач; познакомить студентов с основными структурами данных, применяемых для решения математических задач; научить реализовывать известные алгоритмы с помощью языков высокого уровня.

2.Место дисциплины в структуре ООП бакалавриата

НЕ нашли? Не то? Что вы ищете?

Связана с дисциплинами: «Криптография», «Вычислительная математика», «Прикладные методы оптимизации».

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

Информатика:

    типы данных; основные операторы языка программирования высокого уровня (Паскаль, Си); массивы; процедуры и функции; работа с файлами.

Дискретная математика:

    множества, операции над множествами; отношения, функции; отношения порядка, эквивалентности; булевы функции; комбинаторные конфигурации; подстановки, разбиения; производящие функции; алфавитное кодирование, сжатие данных; графы, виды графов, операции над графами; представление графов; связность, компоненты связности; деревья, циклы; эйлеровы, гамильтоновы циклы и графы; независимость и покрытия; раскраска графа.

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

3 Компетенции обучающегося, формируемые в результате освоения дисциплины:

    владение культурой мышления, способность к обобщению, анализу, восприятию информации, постановке цели и выбору путей ее достижения, умение логически верно, аргументированно и ясно строить устную и письменную речь (ОК-1); владение широкой общей подготовкой (базовыми знаниями) для решения практических задач в области информационных систем и технологий (ОК-6); готовность использовать основные законы естественно-научных дисциплин в профессиональной деятельности, применять методы математического анализа и моделирования, теоретического и экспериментального исследования (ОК-10); способность проводить предпроектное обследование объекта проектирования, системный анализ предметной области, их взаимосвязей (ПК-1); способность проводить моделирование процессов и систем (ПК-5); способность разрабатывать средства реализации информационных технологий (методические, информационные, математические, алгоритмические, технические и программные) (ПК-12); способность разрабатывать средства автоматизированного проектирования информационных технологий (ПК-13).

4. Структура и содержание дисциплины

Общая трудоемкость дисциплины составляет 3 зачетные единицы 108 часов (54 аудиторных и 54 самостоятельная работа).



№

Раздел дисциплины

Семестр

Номер семестра

Виды учебной работы

и трудоемкость в час.

Формы текущего контроля успеваемости.

Форма промежуточной аттестации.

Лек

Сем

Сам

Всего

1

Цель и задачи дисциплины. Примеры задачи и методов их решения.

3

1

2

1

4

7

2

Рекуррентные соотношения.

3

2

2

1

4

7

3

Метод ветвей и границ.

3

3

2

1

4

7

4

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

3

4

2

1

4

7

5

Жадные алгоритмы. Приближенные методы решения комбинаторных задач.

3

5

2

1

4

7

6

Абстрактные типы данных. Примеры. АТД множество, АТД словарь. АТД набор компонент.

3

6

2

1

4

7

7

АТД очередь с приоритетом. АТД корневое дерево.

3

6

2

1

4

7

Контрольная

работа

8

Сортировка. Пирамидальная сортировка. Сортировка за линейное время.

3

8

2

1

4

7

9

Прямой поиск строки в тексте. Алгоритм Рабина-Карпа. Поиск подстроки с помощью конечных автоматов.

3

9

2

1

4

7

10

Алгоритм Кнута-Морриса-Пратта. Алгоритм Бойера-Мура.

3

10

2

1

4

7

11

Представление графов в ЭВМ. Поиск в глубину. Поиск в ширину. Определение связности графа, древовидности. Определение компонент связности графа.

3

11

2

1

4

7

12

Определение компонент сильной связности графа. Построение графа Герца.

3

12

2

1

4

7

13

Поиск мостов. Поиск точек сочленения. Топологическая сортировка графа.

3

13

2

1

4

7

14

Кратчайшие пути. Поиск кратчайших путей в бесконтурном графе. Алгоритм Форда-Беллмана. Алгоритм Дейкстра. Алгоритм Флойда.

3

14

2

1

4

7

15

Минимальные покрывающие деревья. Алгоритм Прима. Алгоритм Крускала.

3

15

2

1

4

7

Контрольная

работа

16

Основы теории алгоритмов.

Вычислимые функции.

Рекурсивные функции.

Машина Тьюринга. Тезис Черча.

3

16

2

1

4

7

17

Основы теории сложности.

Классы P и NP.

3

17

2

1

4

7

18

NP-полные задачи.

3

17

2

1

4

7

Экзамен

ВСЕГО

16

18

54

108

5. Образовательные технологии: активные и интерактивные формы проведения занятий.

6. Учебно-методическое обеспечение самостоятельной работы студентов. Оценочные средства для текущего контроля успеваемости, промежуточной аттестации по итогам освоения дисциплины.

Средства и методы проведения лабораторных занятий. Для написания программ рекомендуется использование среды разработки Microsoft Visual . Для подготовки к лекциям можно использовать пособие: Воронов в методы решения комбинаторных оптимизационных задач / Петрозаводск: Изд-во ПетрГУ, 2006.

Требования и рекомендации к выполнению и оформлению лабораторных работ:

Все программы должны быть реализованы в одной из следующих сред программирования: Delphi, C++Builder, Microsoft VisualC++. Выбор другого языка или среды программирования должен быть согласован предварительно с преподавателем. Программы должны иметь удобный визуальный пользовательский интерфейс. Задания необходимо выполнять самостоятельно, запрещается пользоваться готовыми программами, в том числе скачанными с Интернета. Требуется составлять по возможности наиболее эффективные алгоритмы, однако допускается и использование эвристических методов. Текст программы должен содержать необходимые комментарии. Студент должен уметь пояснить любой фрагмент программы. Все большие по объему входные и выходные данные должны вводится и выводится через текстовый файл (input. txt и output. txt) (за исключением случая, когда для тестирования алгоритмов сортировки массивы заполняются случайными числами). Размеры массивов являются изменяемыми параметрами. При возможности необходимо использовать динамические структуры данных. Результаты расчетов должны быть представлены в наглядной форме. По каждой лабораторной работе должен быть составлен отчет (в электронном или бумажном виде). Лабораторные работы без отчета не принимаются. Отчет должен быть оформлен в среде MS Word. Текст должен хорошо читаться, не содержать ошибок, быть понятным, выровнен по ширине страницы. Структура отчета: Шапка отчета (номер работы, ФОИ, группа). Формулировка задания. Неформальное описание метода решения. Псевдокод алгоритма с пояснениями к используемым обозначениям и АТД. Оценка времени работы программы – временная сложность алгоритма. Описание структуры входных и выходных файлов программы. Список использованных источников. Если граф вводится через файл, то для ввода следует использовать списки ребер. Баллы за лабораторные работы: 3 балла – работа сдана в срок, 2 балла – работа сдана на одно занятие позже, 1 балл – работа сдана позже более чем на одно занятие.

Темы заданий к лабораторным работам:

Создание алгоритма и написание программы решения комбинаторной оптимизационной задачи Реализация абстрактного типа данных с помощью структур данных, процедур и функций языка высокого уровня Реализация одного из методов сортировки или поиска строки в тексте Решение комбинаторной задачи на графе Генерация комбинаторных объектов

Требования к сдаче экзамена. Для допуска к экзамену необходимо сдать не менее трех лабораторных работ. Студенты, не получившие допуск к экзамену, отправляются на повторное обучение (как не выполнившие учебный план). Билет на экзамене содержит 2 вопроса. Ответ на каждый вопрос оценивается по трехбалльной системе. Баллы, полученные при ответе на экзамене, складываются с баллами, полученными в ходе выполнения лабораторных работ. Шкала перевода баллов в итоговую оценку:

19 – 21 баллов «Отлично»;

15 – 18 баллов «Хорошо»;

10 – 14 баллов «Удовлетворительно»;

13 и менее «Неудовлетворительно».

Темы вопросов к экзамену

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

а) основная литература:

Введение в методы решения комбинаторных оптимизационных задач: метод. пособие. / сост. – Петрозаводск, 2006.

б) дополнительная литература:

труктуры данных и алгоритмы. М.: Вильямс, 2001. Новиков математика для программистов. М.: Питер, 2003. лгоритмы: построение и анализ / МЦНМО: БИНОМ. Лаборатория знаний, 2004. Романовский анализ. СПб: Невский диалект, 1999. скусство программирования для ЭВМ. т.1-3. М.: Наука, 1978. лгоритмы + структуры данных = программы. М.,1985. и др. Организация и обработка структур данных в ВС. М., 1987. омбинаторика для программистов. М., Наука, 1988.

8. Материально-техническое обеспечение дисциплины

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

Программа составлена в соответствии с требованиями Федерального государственного образовательного стандарта высшего профессионального образования (ФГОС ВПО) направления «Информационные системы и технологии» (квалификация Бакалавр) 2010 г. с учетом методических рекомендаций и Примерной основной образовательной программы ВПО по направлению «Информационные системы и технологии» квалификация Бакалавр.

Автор: доцент

Программа рассмотрена и утверждена на заседании кафедры Прикладной математики и кибернетики «24» октября 2011 года, протокол № 15

И. о. зав. кафедрой

Программа одобрена на заседании учебно-методической комиссии математического факультета  «__» __________ 2012 года, протокол № __.