.RU

Рабочая программа по дисциплине ен. В. 1 Алгоритмы. Построение и анализ


ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ

ГОСУДАРСТВЕННОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ

ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ

ДОНСКОЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ

(ДГТУ)


Факультет Информатики и вычислительной техники

Кафедра ПО ВТ и АС

УТВЕРЖДАЮ

Проректор по УР


А.С. Коробцов

«___» ___________ 200 _ г

Рег. № ____________
РАБОЧАЯ ПРОГРАММА
По дисциплине ЕН.В.1

АЛГОРИТМЫ. ПОСТРОЕНИЕ И АНАЛИЗ

По специальности: 220400 АСУ

Форма и срок освоения ООП очная, нормативный



Всего учебных часов - ^ 170 (час)

Всего аудиторных занятий - 90 (час)

Из них:

Лекции - 54 (час)

Лабораторные занятия - 36 (час)

Практические занятия (семинары) - (час)

Всего часов на самостоятельную работу студента - 80 (час)

Курсовой проект (работа) - __________ (семестр)
^ ФОРМЫ КОНТРОЛЯ
Экзамен - 4 (семестр)

Зачет - (семестр)

Адреса электронной версии программы


Ростов-на-Дону

2008 г.
^ Лист согласования

Рабочая программа по учебной дисциплине «Алгоритмы. Построение и анализ» составлена в соответствии с требованиями Государственного образовательного стандарта высшего профессионального образования по специальности:


АСУ


относится к циклу Естественнонаучн.

Специализация –


^ Шифр дисциплины по стандарту ЕН.В.1

Рабочая программа составлена доц. Глушкова В.Н. и рассмотрена

на заседании кафедры « ПО ВТ и АС »


Протокол № от « » 200 8 г.


Зав. кафедрой « ПО ВТ и АС » Р.А. Нейдорф


Председатель совета специальности

« »

«___» ___________ 200 _ г


СОГЛАСОВАНО:

Декан факультета Поркшеян В.М.

«___» ___________ 200 _ г

Заведующая организационно-методическим

отделом А.И. Азарова


«___» ___________ 200 _ г


Структура и содержание рабочей программы

^ Раздел 1 Общие положения


    1. Цели и задачи дисциплины, ее место в учебном процессе.


Целью изучения курса “Алгоритмы. Построение и анализ” является:

  • подготовка у будущих специалистов научной базы, на основе которой строится общеобразовательная и специальная подготовка специалистов;

  • привитие навыков освоения нового, развитие логического и алгоритмического мышления;

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



    1. ^ Требования к уровню подготовки студента, завершившего изучение данной дисциплины.


Студенты, завершившие изучение курса “Алгоритмы. Построение и анализ”, должны знать:

  • основные методы построения эффективных алгоритмов;

  • реализовывать базовые структуры представления данных.

Студенты, завершившие изучение курса“Алгоритмы. Построение и анализ”, должны уметь:

  • употреблять приобретенные знания для решения прикладных задач;

  • уметь использовать основные понятия и методы курса “Алгоритмы. Построение и анализ” для построения конкретных алгоритмов;

  • делать выводы о корректности реализации в рамках построенных моделей;

  • использовать методы оценки сложности алгоритмов для решения новых задач.



    1. ^ Связь с предшествующими дисциплинами и последующими
дисциплинами.

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


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


  • дискретная математика;

  • теория языков и трансляторов;

  • моделирование;

  • управление техническими системами.
^ Раздел 2 Тематический план и содержание дисциплины

Приводится выписка из ГОС «Требования к обязательному минимуму содержания основной образовательной программы» по дисциплине (для дисциплин федерального компонента) и развернутое содержание дисциплины с указанием дидактических единиц, тем и их содержания, рекомендуемой литературой.




ЕН.В.1

Алгоритмы. Построение и анализ.

170




Оценка сложности алгоритма. Двоичные деревья поиска. Динамические порядковые статистики. Перемножение нескольких матриц. Динамическое программирование. Жадные алгоритмы. NP- полные задачи. Полиномиальная сводимость.









Дидакти-

ческие

единицы

(название)

Тема, литература

Содержание

Основные понятия об алгоритмах.

ДЕ 1

Математические основы анализа алгоритмов


1.1 Алгоритм. Размер входа. Время работы. Порядок роста. Асимптотические обозначения. -обозначение. Асимптотически точная оценка. О и -обозначения. - и о-обозначения. Сравнение функций. Стандартные функции (многочлены, экспоненты и т.п.).

[7.1.1, § 3, 7.1.2, гл.2]



Скорость роста функции; сравнение функций, формула Стирлинга.

1.2 Суммы и их свойства Оценки сумм. Рекуррентные соотношения. Метод подстановки. Метод итераций. Основная теорема о рекуррентных оценках. [7.1.3, § 3.1, 7. 1.4, §5]

Рекуррентные соотношения; метод подстановки и итерации, деревья рекурсии

1.3 Комбинаторика и вероятность.[ 7.1.3, § 5]

Подсчет количеств, дискретные случайные величины, геометрическое и биномиальное распределения




Деревьев поиска.

ДЕ 2

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

2.1 Двоичные (случайные) деревья поиска. Красно-черные деревья и их свойства. Оценка высоты красно-черного (RB) дерева. Алгоритмы вращения, добавления и удаления вершины в красно-черное дерево и их сложность. [7.1.1, гл.3]

Сбалансированные деревья; черная высота дерева; лемма о высоте RB-дерева, время работы алгоритма вставки вершины.

2.2 Динамические порядковые статистики. Обновление информации о размерах поддеревьев. Теорема о пополнении RB-деревьев.

[7.1.1, гл. 4]

Порядковое дерево, поиск i-гопо величине элемента; определение порядкового номера элемента.

Методы построения и анализа алгоритмов

ДЕ 3

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

3.1 Перемножение нескольких матриц. Вычисление оптимальной стоимости и ее оценка. Основные характеристики задач, решаемые методом динамического программирования. Алгоритм Штрассена умножения матриц.

[7.1.1, § 7, гл.5, 7.1.5, гл.4]

Количество расстановок скобок; строение оптимальной расстановки скобок

3.2 Динамическое программирование «сверху вниз». Наибольшая общая подпоследовательность (НОП) и ее строение. Вычисление длины НОП, варианты алгоритмов с оценкой сложности времени и памяти. [7.1.1, §5]

Теорема о строении НОП; рекуррентная формула для нахождеиия НОП.

3.3 Оптимальная триангуляция многоугольника и ее связь с задачей перемножения матриц. Строение оптимальной триангуляции. Примеры различных задач, решаемых методом динамического программирования. (битоническая задача коммивояжера, разбиение абзаца на строки, стоимость редактирования). [7.1.6, §2. 5]

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

ДЕ 4

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

4.1. Задача о выборе заявок. Анализ алгоритма и его корректность. Непрерывная и дискретная задачи о рюкзаке.

[7.1.1, гл.17]

Принципы применимости жадных алгоритмов. Сравнительный анализ динамического программирования с жадными алгоритмами.

4.2. Построение кода Хаффмена. Правильность алгоритма Хаффмена. Теорема об оптимальности префиксного кода.

[7.1.1, гл.17.3]

Равнолмерный и неравномерный коды; префиксные коды.

Амортизационный анализ.

ДЕ 5

Методы группировки и потенциалов.

5.1 Анализ методом группировки двоичного счетчика. Метод предоплаты.

[7.1.1, гл.18.1, 7.3.3, §3]

Операции со стеком, k- битовый двоичный счетчик. Стоимость последовательности операций, стоимость операции Increment.

5.2 Динамические таблицы. Расширение и сокращение таблицы. Применение метода потенциалов для нахождения учетной стоимости оценки сложности работы с динамическими таблицами.

[7.1.1, гл.19.1, 7.2.4, §4]

Потенциальная функция, операции со стеками, учетные стоимости операции Increment.

Сложные структуры данных

ДЕ 6

Биномиальные деревья и

фибоначчиевые кучи.

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

[7.1.1, гл.20, 7.3.3 гл1]

Операции с биномиальными кучами, биномиальные деревья.

6.2 Строение фибоначчиевой (ф) кучи. Алгоритм соединения двух ф-куч с временной сложностью О(1). Алгоритм удаления минимальной вершины. Оценки учетной стоимости операций удаления вершины. Оценка максимальной степени вершин в ф-куче.

[7.1.1, гл.21, 7.3.3 гл. 2]

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

6.3 Системы непересекающихся множеств. Сложность реализации операций с непересекающимися множествами. [7.1.1, гл. 22]

Реализация с помощью списков, объединение по рангам со сжатием путей.

Анализ работы арифметических схем

ДЕ 7

Схемы для сложения и

умножения.

7.1 Схемы из функциональных элементов. Каскадное сложение. Параллельная префиксная схема с предвычислением переносов.

[7.1.1, гл. 28]

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

7.2 Умножение с помощью дерева Уоллеса.

[7.1.1, гл. 29.3 ]

Частичные произведегния характеристики дерева Уоллеса.

Поиск подстрок.

ДЕ 8

Алгоритмы Рабина-Карпа и Кнута-Морриса-Пратта.

8.1 Поиск подстрок с помощью конечного автомата. [7.1.1, гл.34, 7.3.3, §4.1]

Лемма о двух суффиксах; поиск образца; автоматы для поиска подстрок.

8.2 Время работы алгоритма Кнута-Морриса-Пратта. и его корректность. [7.1.1, гл.35, 7.3.3, §4.1]

Префикс-функция, ассоциированная с образцом; лемма об итерациях префикс-функции.

NP- полнота.

ДЕ 9

Класс Р и NP языков.

9.1 Задачи рапознавания. Теорема о полиномиальной сводимости.

[7.1.1, гл.36]

Полиномиальное время, формальные языки, сертификат.


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

[7.1.1, гл.36,]

Многоленточная детерминированная машин Тьюринга, теорема о полиномиальной сводимости.

8.3 NP-полнота. Открытая проблема . NP- полнота проблемы выполнимости булевых формул. [7.1.1, гл.36]

Проверка принадлежности языка классу NP. Гамильтонов цикл



Раздел 3 Распределение бюджета времени по видам занятий


3.1 Лекционные занятия




рейтингового блока

№ дидактической единицы

№ темы


Объем времени, час

Очная

заоч

ная

1

2

3

4

5

1



ДЕ1

Математические основы анализа алгоритмов


1.1

2

1.2

2

1.3

2




ДЕ 2
^ Сложность преобразования деревьев поиска

2.1

4

2.2

2

ДЕ 3

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


3.1

2

3.2

2




3.3

2



^ ДЕ 4 Жадные алгоритмы.
4.1

2




4.2

2




ДЕ 5
^ Методы группировки и потенциалов.

5.1

2




5.2

2




2

ДЕ 6

Биномиальные деревья и

фибоначчиевые кучи

6.1

2




6.2

4




ДЕ 7

Схемы для сложения и

умножения.

7.1

2




7.2

2







ДЕ 8

Алгоритмы Рабина-Карпа и Кнута-Морриса-Пратта.

8.1

2




8.2

2




ДЕ 9

Класс Р и NP языков.

9.1

2




9.2

4




9.3

2






3.2 Лабораторные занятия




рейтингового

блока

Тема и содержание практического (семинарского) и(или) лабораторного занятия

№ темы

из раздела 2

Объем времени, час

очная

заочная

1

2

3

4

5

1

1.1 Вычисление значений многочленов с использованием схемы Горнера.

1.2

2




1.2 Реализация операций преобразования красно-черных деревьев.

2.1

6




1.3 Динамическое умножение матриц


3.1

4




1.4 Алгоритм нахождения наибольшей общей подпоследовательности.


3.2

4




1.5 Алгоритм реализации кодов Хаффмена.

4.2

4




2

2.1 Представление и преобразование множеств операциями над биномиальными и фибоначчиевыми кучами.


6.2

6




2.2 Применение конечного автомата к поиску подстрок и его минимизация

6.3

6




2.3 Алгоритм реализации задачи о расписании

4.1

4






3.3 Самостоятельная работа студентов



п.п.

Вид самостоятельной работы

Объем времени, час

Рекомендуемая литература

очная

заочная

1

2

3

4

5

1

Выполнение домашних заданий

24




7.1.1 – 7.1.6

2

Подготовка к лекциям

16




7.1.1 – 7.1.6

3

Подготовка к экзаменам и зачетам

20




7.1.1 – 7.1..6

4

Выполнение лабораторных работ

20




7.1.1



^ Раздел 4 Организация итогового и промежуточного контроля знаний 4.1 Комплект тестовых заданий


1. Определение красно-черного дерева и оценка сложности алгоритма добавления вершины.

2. Динамическое программирование. Оптимальное число умножений последовательности матриц.

3. Жадные алгоритмы и задача о выборе заявок.

4. Алгоритм нахождения наибольшей общей подпоследовательности

5. Реализация множеств сложными структурами данных.

II. Типовые задачи, решение которых предусматривается курсом.

1. Сравнить скорость роста функций и , и , используя формулу Стирлинга

, и .


2. Описать трассировку программы Matrix-Chain-Order (p), p=


3. Описать трассировку программы LCS(X,Y), где X= Y=


4. Описать трассировку программы RB-Insert(T,x), где красная вершина х имеет ключ 13, T имеет вид:

11





8 15

2 9

9.5

3 7 12

19


1 11.5 14




5. Построить код Хаффмена для таблицы частот:

a b c d e f g h

12 40 23 17 45 15 17 21


^ Раздел 5 Программно–информационные обучающие материалы

5.1 Пакет MathCAD

5.2 Пакет Maple

Раздел 7 Литература

Карта методического обеспечения дисциплины






Автор


Название


Издательство


и

г з

р д

и а

ф н

и

я


Год издания


Кол-во в библиотеке


Наличие на

электронных

носителях


Электронные

уч. пособия,

размещенные

на сайте ЦДО

(кафедры)

1

2

3

4

5

6

7

8

9

7.1 Основная литература

7.1.1

Кормен Т., Лейзерсон Ч., Ривест Р.

Алгоритмы: построение и анализ.

М.:МЦНМО, 2001




2005

5







7.1.2

Джеймс Андерсон

Дискретная математика и комбинаторика

М. –С-П-Киев

Изд.дом «Вильямс»




2003

1








7.1.3

Ахо А., Хопкрофт Дж., Ульман Дж.

Структуры данных и алгоритмы.

М., Спб, Киев,

Вильямс, 2001




2004

2







7.1.4

Кнут Д.

Искусство программирования, т.3: Сортировка и поиск

М.:Спб:Киев:Вильямс,2000.




2003

3







7.1.5

Иванов Б.Н

Дискретная математика. Алгоритмы и программы

М.:Лаборатория Базовых Знаний,




2005


10







7.1.6

Дж. Макконелл

Анализ алгоритмов. Вводный курс.

Техносфера. Москва.





2005

3







7.2 Периодическая литература

7.2.1

























7.3 Дополнительная литература

7.3.1

Непейвода Н.Н.

Прикладная логика.

Новосибирск, изд-во Новосиб. ун-та




2000

2







7.3.2

Евстигнеев В.А.

Применение теории графов в программировании.

М:Наука,




200

4







7.3.3

Нефёдов В.Н., Осипова В.А..

Курс дискретной математики

М., изд-во МАИ.




1992

30










7.4 Практические (семинарские) и (или) лабораторные занятия

7.4.1

Коледов Л.В., Ларченко В.В., Мишняков Н.Т.

Минимизация булевых функций

ДГТУ. - Ростов н/Д




2000

100







7.4.2

Баранов И. В. , Глушкова В.Н., Ларченко В.В.

Задачи по дискретной математике,

ДГТУ. - Ростов н/Д




2001

100







7.4.3

Глушкова В.Н., Ларченко В.В.

Дискретная математика в задачах

ДГТУ. - Ростов н/Д




2007

100







7.4.4

Лавров И.А.,

Максимова Л.Л.

Задачи по теории множеств, математической логике и теории алгоритмов.

М., Наука, Главная ред. физ.- мат. литературы




1984

5







7.5 Курсовая работа (проект)

7.5.1

























7.6 Контрольные работы

7.6.1

























raspolozhenie-v-80-m-ot-morya-i-v-25km-ot-centra-g-evpatoriya-v-rajone-novogo-plyazha.html
rasporyadok-dnya.html
rasporyazheni-e-stranica-3.html
rasporyazhenie-02-aprelya-2012-goda-444-r-ob-organizacii-lichnogo-priema-grazhdan-v-administracii-municipalnogo-obrazovaniya-gorod-salehard.html
rasporyazhenie-09-iyunya-2012-g-1400-oprovedenii-gorodskogo-festivalya-molodezhnih-subkultur-andegraund-put-k-svetu.html
rasporyazhenie-15-04-2011-0141-p-ob-utverzhdenii-kriteriev-ocenki-effektivnosti-deyatelnosti-rukovoditelej-municipalnih-avtonomnih-uchrezhdenij.html
  • urok.bystrickaya.ru/predvaritelnie-itogi-deyatelnosti-ministerstva-finansov-respubliki-kazahstan-za-2006-god.html
  • literatura.bystrickaya.ru/sonata-dlya-klarneta-solo-1972-chislennim-i-daleko-ne-ordinarnim-vzglyadam-etogo-talantlivejshego-muzikanta-i-filosofa.html
  • literatura.bystrickaya.ru/ryazanskaya-oblast-spasskij-municipalnij-rajon-shema-territorialnogo-planirovaniya-tom-1-polozheniya-o-territorialnom-planirovanii.html
  • assessments.bystrickaya.ru/bezopasnost-zhiznedeyatelnosti-laboratornij-praktikum-sankt-peterburg-izdatelstvo-politehnicheskogo-universiteta-2010.html
  • upbringing.bystrickaya.ru/konkursnoj-komissii-stranica-13.html
  • thesis.bystrickaya.ru/programma-disciplini-vvedenie-v-politologiyu-dlya-napravleniya-030200-62-politologiya-podgotovka-bakalavra-stranica-2.html
  • uchenik.bystrickaya.ru/grazhdansko-processualnij-kodeks-iskovoe-proizvodstvo-chast-2.html
  • ucheba.bystrickaya.ru/prilozhenie-5-nauchno-issledovatelskaya-rabota-i-podgotovka-k-eyo-provedeniyu.html
  • university.bystrickaya.ru/finansovoe-obespechenie-deyatelnosti-pravoslavnih-religioznih-organizacij-voprosi-teorii-i-praktiki.html
  • paragraf.bystrickaya.ru/yarkim-svetom-briznuli-sofiti-rossijskaya-blagotvoritelnost-v-zerkale-smi.html
  • esse.bystrickaya.ru/rabochaya-programma-disciplina-opd-f-01-teoreticheskie-osnovi-tovarovedeniya-i-ekspertizi-indeks-naimenovanie-disciplini.html
  • shkola.bystrickaya.ru/rol-netradicionnih-urokov-v-formirovanii-kommunikativnih-navikov-na-nachalnom-etape-obucheniya-inostrannim-yazikam.html
  • uchit.bystrickaya.ru/tematika-referatov-po-istorii-pedagogiki-k-kandidatskomu-ekzamenu-obshenauchnoj-discipline.html
  • institute.bystrickaya.ru/finansovoe-obespechenie-osushestvleniya-organami-mestnogo-samoupravleniya-municipalnih-rajonov-otdelnih-gosudarstvennih-polnomochij-po-raschetu-i-predostavleniyu-dotacij-poseleniyam.html
  • znanie.bystrickaya.ru/andrej-bogolyubskij.html
  • abstract.bystrickaya.ru/3-programmnoe-obespechenie-biznes-planirovaniya-metodicheskij-kompleks-po-discipline-sovremennie-informacionnie.html
  • assessments.bystrickaya.ru/dolgo-budet-kareliya-snitsya-2-dnya1-noch-109147g-moskva-ul-marksistskaya-d-22-of-703.html
  • diploma.bystrickaya.ru/zolotoj-kletke-stranica-3.html
  • write.bystrickaya.ru/godovoj-otchet-otkritogo-akcionernogo-obshestva-refservis-po-rezultatam-raboti.html
  • uchitel.bystrickaya.ru/protokol-sankt-peterburg-ul-torzhkovskaya-d-4.html
  • portfolio.bystrickaya.ru/osobennosti-rassledovaniya-prestuplenij-korrupcionnoj-napravlennosti.html
  • laboratornaya.bystrickaya.ru/programma-uchebnoj-praktiki-annotaciya-osnovnoj-obrazovatelnoj-programmi.html
  • nauka.bystrickaya.ru/vospitannost-konkursnie-materiali.html
  • crib.bystrickaya.ru/kafedra-obshej-ekonomicheskoj-teorii-redakcionnij-sovet.html
  • prepodavatel.bystrickaya.ru/teoreticheskie-i-metodicheskie-osnovi-obucheniya-obratnim-zadacham-dlya-differencialnih-uravnenij-v-usloviyah-gumanitarizacii-visshego-matematicheskogo-obrazovaniya.html
  • otsenki.bystrickaya.ru/sanatornaya-shkola-internat-5-kirovskogo-rajona-g-permi-stranica-2.html
  • bukva.bystrickaya.ru/sochetanie-ubezhdeniya-i-prinuzhdeniya-v-administrativnom-upravlenii-chast-2.html
  • znanie.bystrickaya.ru/b-ocenka-sostoyaniya-vnedreniya-programmi-ohranyaemih-territorij-chetvertij-nacionalnij-doklad.html
  • portfolio.bystrickaya.ru/opredelyayushee-rasskaz-v-ekskursii-86.html
  • uchitel.bystrickaya.ru/razdel-2-uchebnoe-posobie-nizhnij-tagil-2002-bbk-uvarov-v-m-metodi-pedagogicheskogo-issledovaniya-uchebnoe-posobie.html
  • textbook.bystrickaya.ru/holodnie-zakuski-uchebnoe-posobie-dlya-studentov-specialnosti-271200-tehnologiya-produktov-obshestvennogo-pitaniya.html
  • thesis.bystrickaya.ru/prezident-budet-bespartijnim-a-premer-liderom-partii-grizlov-b-v-monitoring-smi-16-aprelya-2008-g.html
  • lecture.bystrickaya.ru/annotaciya-primernoj-programmi-uchebnoj-disciplini-vichislitelnie-sistemi-seti-i-telekommunikacii-celi-i-zadachi-disciplini-stranica-3.html
  • textbook.bystrickaya.ru/gsev00-gosudarstvennij-obrazovatelnij-standart-visshego-professionalnogo-obrazovaniya-specialnost-032103.html
  • writing.bystrickaya.ru/glava-5-gendernie-otnosheniya-v-seme-i-referentnoj-gruppe-kniga-mozhet-bit-pol.html
  • © bystrickaya.ru
    Мобильный рефератник - для мобильных людей.