Учебно-методический комплекс по дисциплине "структуры и алгоритмы обработки данных" Для специальности: "информатика и вычислительная техника"

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

Содержание

“структуры и алгоритмы обработки данных”
1. Цели и задачи преподавания дисциплины
2. Тематический план учебной дисциплины
Раздел, тема
Лекция 1. Основные типы данных
Лекция 2. Указатели. Динамическая память
Лекция 4.Основные структуры данных. Стандартные массивы
Лекция 5. Основные структуры данных. Динамические массивы
Лекция 6. Основные структуры данных. Записи. Множества
Лекция 7. Основные структуры данных. Списки.
Лекция 8. Основные структуры данных. Списки
Лекция 9. Основные структуры данных. Стеки
Лекция 11. Алгоритмы поиска данных
Лекция 13. Алгоритмы поиска данных
Лекция 15. Алгоритмы сортировки данных
Лекция 16. Алгоритмы сортировки данных
Лекция 17. Хеширование
Лекция 18. Хеш-таблицы
Лекция 20. Рандомизированные алгоритмы. Генерация случайных чисел
Лекция 21. Рандомизированные алгоритмы. Списки с пропусками
...
Полное содержание

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

Министерство образования и науки Российской Федерации

Федеральное государственное бюджетное образовательное учреждение

высшего профессионального образования

«Армавирская государственная педагогическая академия»

Институт прикладной информатики, математики и физики

Факультет прикладной информатики и информационных технологий

Кафедра информатики и информационных технологий обучения

Утверждено на заседании кафедры информатики и ИТО

Протокол № __ от ”____” ____________ 2012г.
Зав. Кафедрой___________________

УЧЕБНО-МЕТОДИЧЕСКИЙ КОМПЛЕКС

По дисциплине

“СТРУКТУРЫ И АЛГОРИТМЫ ОБРАБОТКИ ДАННЫХ”

Для специальности: “ИНФОРМАТИКА И ВЫЧИСЛИТЕЛЬНАЯ ТЕХНИКА”

2 курс, 3 семестр – зачет, 4 семестр – экзамен.

Составители:

доц. Козырева Г.Ф.,

ст. преп. Лапшин Н.А.

Армавир, 2012 г.

1. ЦЕЛИ И ЗАДАЧИ ПРЕПОДАВАНИЯ ДИСЦИПЛИНЫ

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

Изучение курса «Структуры и алгоритмы обработки данных в ЭВМ» опирается на знания, умения и навыки, которые студенты должны получить при изучении дисциплин: «Математический анализ», «Информатика», «Программирование», «Дискретная математика».

Целью изучения курса «Структуры и алгоритмы обработки данных в ЭВМ» является глубокое освоение студентами методов представления данных в памяти ЭВМ и основных алгоритмов, оперирующих с ними.

Студент должен иметь представление:

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

знать и уметь использовать:

основные понятия алгоритмических структур для построения алгоритмов и задач по их математическим моделям;

должен приобрести навыки:

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

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

Неотъемлемой частью курса является лабораторный практикум, при прохождении которого студентами приобретаются навыки программирования в интегрированной среде Borland Delphi 7

2. ТЕМАТИЧЕСКИЙ ПЛАН УЧЕБНОЙ ДИСЦИПЛИНЫ

№		Всего	В т.ч. аудиторных,час			Самост.
	Раздел, тема	часов	Всего	Из них		работа,
			Аудит.	Лекции	Практ.	час
3 семестр
	Основные типы данных. Указатели. Динамическая память.	9	4	4		5
	Рекурсия.	8	4	2	2	4
	Основные структуры данных. Стандартные и динамические массивы. Записи. Множества.	20	12	6	6	8
	Основные структуры данных. Списки. Стеки. Очереди.	20	12	8	4	8
	Алгоритмы поиска данных.	22	12	6	6	10
	Алгоритмы сортировки данных.	22	12	6	6	10
	Всего за 3 семестр:	101	56	32	24	45
4 семестр
	Хеширование и хеш-таблицы.	13	8	4	4	5
	Рандомизированные алгоритмы.	18	10	6	4	8
	Деревья и леса.	18	10	6	4	8
	Ориентированные графы.	16	8	4	4	8
	Алгоритмы на графах.	18	10	6	4	8
	NP-полные и труднорешаемые задачи	18	10	6	4	8
	Всего за 4 семестр:	101	56	32	24	45
Всего:		202	112	64	48	90

3. СОДЕРЖАНИЕ УЧЕБНОГО МАТЕРИАЛА

3.1. Краткое содержание лекций

3 семестр

Лекция 1. Основные типы данных

Основные типы данных в языке программирования Turbo Pascal. Размерность и ограничения типов данных. Формы представления данных.

Лекция 2. Указатели. Динамическая память

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

Лекция 3. Рекурсия

Понятие рекурсии. Формы рекурсивных алгоритмов. Понятие глубины рекурсии. Преимущества и недостатки использования рекурсии.

Лекция 4.Основные структуры данных. Стандартные массивы

Способы описания стандартных массивов. Расположение массивов в памяти. Преимущества и недостатки использования стандартных массивов.

Лекция 5. Основные структуры данных. Динамические массивы

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

Лекция 6. Основные структуры данных. Записи. Множества

Тип данных запись. Организация данных в форме записи. Основные принципы работы с записями. Тип данных множества. Основные процедуры и функции работы с множествами. Преимущества и недостатки работы с множествами.

Лекция 7. Основные структуры данных. Списки.

Односвязные списки: узлы связного списка; создание односвязного списка; вставка и удаление элементов в односвязном списке; прохождение связного списка.

Лекция 8. Основные структуры данных. Списки

Двухсвязные списки: класс двухсвязного списка; вставка и удаление элементов в двухсвязном списке; достоинства и недостатки связных списков.

Лекция 9. Основные структуры данных. Стеки

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

Лекция 10. Основные структуры данных. Очереди

Очереди на основе односвязных списков. Очереди на основе массивов. Примеры использования очередей.

Лекция 11. Алгоритмы поиска данных

Понятие поиска. Процедуры сравнения данных. Обзор алгоритмов поиска данных.

Лекция 12. Алгоритмы поиска данных

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

Лекция 13. Алгоритмы поиска данных

Бинарный поиск в сортированных массивах. Бинарный поиск в связных списках.

Лекция 14. Алгоритмы сортировки данных

Задача сортировки (внешней и внутренней). Сортировка вставками, обменами, выбором.

Лекция 15. Алгоритмы сортировки данных

Быстрая сортировка. Процедура разделения. Рекурсивный и не рекурсивный алгоритмы быстрой сортировки. Анализ сложности. Оптимизация программы (неполная сортировка).

Лекция 16. Алгоритмы сортировки данных

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

4 семестр

Лекция 17. Хеширование

Функции хеширования: простая функция хеширования для строк; функции хеширования PJW. Разрешение конфликтов посредством линейного зондирования.

Лекция 18. Хеш-таблицы

Класс хеш-таблиц с линейным зондированием. Класс связных хеш-таблиц. Хеш-таблицы на диске.

Лекция 19. Рандомизированные алгоритмы. Генерация случайных чисел

Критерий Хи-квадрат. Метод средних квадратов. Линейный конгруэнтный метод.

Лекция 20. Рандомизированные алгоритмы. Генерация случайных чисел

Тестирование: тест на однородность; тест на пропуски. Комбинирование генераторов. Аддитивные генераторы. Тасующие генераторы.

Лекция 21. Рандомизированные алгоритмы. Списки с пропусками

Поиск в списке с пропусками. Вставка в список с пропусками. Удаление из списка с пропусками.

Лекция 22. Деревья и леса

Определение дерева, леса, бинарного дерева. Графическое и текстовое (скобочное) представление леса. Спецификация дерева, леса, бинарного дерева: базовые функции и аксиомы. Естественное соответствие бинарного дерева и леса.

Обходы бинарных деревьев: рекурсивные и не рекурсивные алгоритмы. Обходы дерева или леса.

Лекция 23. Бинарные деревья

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

Прошитые бинарные деревья: представление, обход, включение.

Лекция 24. Бинарные деревья

Пример использования бинарных деревьев в задаче упаковки сообщений: префиксные коды и бинарные деревья, метод кодирования Фано-Шеннона, критерий оптимальности кода, алгоритм кодирования (сжатия) информации по Хаффману (построение дерева, кодирование и декодирование), доказательство оптимальности кода Хаффмана, неравенство Крафта, теорема кодирования в отсутствие шума (энтропийная оценка средней длины кода). Динамическое кодирование по Хаффману.

Лекция 25. Ориентированные графы

Графы: определения и примеры. Упорядоченный граф. Представления графов: матрица инциденций, матрица смежности, список пар, структура смежности (списки инцидентности). Преобразования представлений.

Лекция 26. Ориентированные графы

Остовные деревья графа. Минимальное остовное дерево. Теорема "о минимальном ребре". Жадный алгоритм (Краскал). Алгоритм "ближайшего соседа" (Прим, Дейкстра).

Лекция 27. Алгоритмы на графах

Поиск в графе: алгоритм пометок. Поиск в ширину. Поиск в глубину.

Связные компоненты. Алгоритм сложности О(m*log n) построения минимального остова. Построение и свойства остовных деревьев при поиске в глубину и в ширину. Поиск в глубину и топологическая сортировка.

Нахождение компонент двусвязности: точки сочленения графа и их свойства в глубинном остовном дереве. Алгоритм нахождения компонент двусвязности.

Лекция 28. Алгоритмы на графах

Сильная связность. Поиск в глубину в орграфе. Алгоритм нахождения сильно связных компонент.

Клики. Алгоритм порождения клик графа.

Лекция 29. Алгоритмы на графах

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

Лекция 30. NP-полные и труднорешаемые задачи

Массовая и индивидуальная задачи. Сложность алгоритма и кодирование входных и выходных данных. Полиномиальные алгоритмы и класс P. Недетерминированные алгоритмы и класс NP.

Различные формы постановки задач комбинаторной оптимизации: оптимизационная, вычислительная, форма распознавания. Примеры.

Лекция 31. NP-полные и труднорешаемые задачи

Полиномиальная преобразуемость задач. NP-трудные и NP-полные задачи. Задача о выполнимости булева выражения, представленного в конъюнктивной нормальной форме. Доказательство NP-полноты задачи о выполнимости.

Преобразуемость задачи о выполнимости в задачу о 3-выполнимости. Полиномиальность задачи о 2-выполнимости.

Задача о клике графа. Преобразуемость задачи о 3-выполнимости в задачу о клике.

Лекция 32. NP-полные и труднорешаемые задачи

Задача о многопроцессорном расписании (МПР). Преобразуемость задачи о клике в задачу о МПР.

Задача о 0-1-рюкзаке и криптография.

Практическое решение NP-полных задач.

3.2. Краткое содержание лабораторных работ

3 семестр

Лабораторная работа 1. Рекурсивные функции и процедуры

Цель: Рассмотреть принципы построения рекурсивных функций и процедур.

Рекомендации по СРС: изучить материалы лекций и дополнительной литературы.

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

Лабораторная работа 2. Стандартные массивы

Цель: Рассмотреть принципы объявления и обработки массивов.

Рекомендации по СРС: изучить материалы лекций и дополнительной литературы.

Содержание работы: Решение задач на методы формирования и обработку массивов (нахождение максимального, минимального, суммы, среднего арифметического и т.д).

Лабораторная работа 3. Динамические массивы

Цель: Рассмотреть принципы объявления и работы с динамическими массивами.

Рекомендации по СРС: изучить материалы лекций и дополнительной литературы.

Содержание работы: Решение задач на методы формирования и обработку массивов (нахождение максимального, минимального, суммы, среднего арифметического и т.д).

Лабораторная работа 4. Записи и множества

Цель: Рассмотреть структуру и принципы работы с записями и множествами.

Рекомендации по СРС: изучить материалы лекций и дополнительной литературы.

Содержание работы: Решение задач на формирование структур данных на основе записей и принципы их обработки; организация и основные операции над множествами.

Лабораторная работа 5. Списки

Цель: Рассмотреть структуру и принципы работы со списками.

Рекомендации по СРС: изучить материалы лекций и дополнительной литературы.

Содержание работы: Решение задач на формирование структур данных на основе списков и принципы их обработки (создание, вставка, удаление и т.д.).

Лабораторная работа 6. Стеки и очереди

Цель: Рассмотреть структуру и принципы работы с очередями и стеками.

Рекомендации по СРС: изучить материалы лекций и дополнительной литературы.

Содержание работы: Решение задач на формирование структур данных стека на основе массивов и списков, а также их обработка; формирование структур данных очереди на основе массивов и списков, а также их обработка.

Лабораторные работы 7,8,9. Алгоритмы поиска данных

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

Рекомендации по СРС: изучить материалы лекций и дополнительной литературы.

Содержание работы: Осуществление последовательного поиска по заданному условию в массивах и связных списках. Осуществление бинарного поиска по заданному условию в массивах и связных списках.

Лабораторные работы 10,11,12. Алгоритмы сортировки данных

Цель: Рассмотреть основные алгоритмы сортировки данных в различных структурах.

Рекомендации по СРС: изучить материалы лекций и дополнительной литературы.

Содержание работы: Медленные алгоритмы сортировки: пузырьковая сортировка, шейкер-сортировка, сортировка методом выбора, сортировка методом вставок. Быстрые алгоритмы сортировки: сортировка методом Шелла, сортировка слиянием, быстрая сортировка.

4 семестр

Лабораторные работы 13,14. Хеширование и хеш-таблицы.

Цель: Рассмотреть основные алгоритмы работы с хеш-таблицами.

Рекомендации по СРС: изучить материалы лекций и дополнительной литературы.

Содержание работы: Функция хеширования. Простая функция хеширования для строк. Функции хеширования PJW. Алгоритм линейного зондирования. Поиск, удаление, увеличение элементов из хеш-таблицы.

Лабораторные работы 15,16. Рандомизированные алгоритмы.

Цель: Рассмотреть основные рандомизированные алгоритмы работы.

Рекомендации по СРС: изучить материалы лекций и дополнительной литературы.

Содержание работы: моделирование генераторов случайных чисел. Тестирование: тест «покер», тест «сбор купонов».

Лабораторные работы 17,18. Деревья и леса.

Цель: Рассмотреть основные алгоритмы работы с деревьями.

Рекомендации по СРС: изучить материалы лекций и дополнительной литературы.

Содержание работы: Обходы бинарных деревьев: рекурсивные и не рекурсивные алгоритмы. Пример использования бинарных деревьев в задаче упаковки сообщений: префиксные коды и бинарные деревья, метод кодирования Фано-Шеннона, критерий оптимальности кода, алгоритм кодирования (сжатия) информации по Хаффману (построение дерева, кодирование и декодирование), доказательство оптимальности кода Хаффмана, неравенство Крафта, теорема кодирования в отсутствие шума (энтропийная оценка средней длины кода). Динамическое кодирование по Хаффману.

Лабораторные работы 19,20. Ориентированные графы.

Цель: Рассмотреть построение ориентированных графов.

Рекомендации по СРС: изучить материалы лекций и дополнительной литературы.

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

Лабораторные работы 21,22. Алгоритмы на графах.

Цель: Рассмотреть алгоритмы на графах.

Рекомендации по СРС: изучить материалы лекций и дополнительной литературы.

Содержание работы: Поиск в графе: алгоритм пометок. Поиск в ширину. Поиск в глубину. Алгоритм порождения клик графа. Алгоритм Дейкстры. Алгоритм Форда-Беллмана.

Лабораторные работы 23,24. NP-полные и труднорешаемые задачи.

Цель: Рассмотреть алгоритмы труднорешаемых задач.

Рекомендации по СРС: изучить материалы лекций и дополнительной литературы.

Содержание работы: Полиномиальные алгоритмы и класс P. Недетерминированные алгоритмы и класс NP. Задача о клике графа. Задача о многопроцессорном расписании (МПР). Практическое решение NP-полных задач.

4. Рекомендации для изучения разделов курса самостоятельно

Тема 1. Основные типы данных. Указатели. Динамическая память. (Трудоемкость – 5 ч.)

Изучить литературу:

Бауэр Ф.Л., Гооз Г. Информатика. Вводный курс: В 2 ч.- М.:Мир, 1990.
Голодов Е.А., Лапшин Н.А., Николаева Л.Г. Информатика и программирование: учебно-методический комплекс. – Армавир: 2009.

Тема 2. Рекурсия. (Трудоемкость – 4 ч.)

Изучить литературу:

Кнут Д. Искусство программирования для ЭВМ. Том 1: Основные алгоритмы.- М.: Мир, 1976. (3-е изд.: Уч.пос.-М.:Издательский дом “Вильямс”, 2000.)

Тема 3. Основные структуры данных. Стандартные и динамические массивы. Записи. Множества. (Трудоемкость – 8 ч.)

Изучить литературу:

Бакнелл Д. Фундаментальные алгоритмы и структуры данных в Delphi. Библиотека программиста. – М.: ООО «ДиаСофтЮП»; СПб.: Питер, 2006. – 557 с.
Вирт Н. Алгоритмы + структуры данных = программы.- М.: Мир, 1985. (Алгоритмы и структуры данных.- М.: Мир, 1989.) (Алгоритмы и структуры данных. – СПб.: Невский Диалект, 2001. (2-е изд., испр.))
Ахо Альфред В., Хопкрофт Джон, Ульман Джеффри Д. Структуры данных и алгоритмы: Пер. с англ.: Уч.пос.- М.: Издательский дом “Вильямс”, 2000.

Тема 4. Основные структуры данных. Списки. Стеки. Очереди. (Трудоемкость – 8 ч.)

Изучить литературу:

Бакнелл Д. Фундаментальные алгоритмы и структуры данных в Delphi. Библиотека программиста. – М.: ООО «ДиаСофтЮП»; СПб.: Питер, 2006. – 557 с.
Вирт Н. Алгоритмы + структуры данных = программы.- М.: Мир, 1985. (Алгоритмы и структуры данных.- М.: Мир, 1989.) (Алгоритмы и структуры данных. – СПб.: Невский Диалект, 2001. (2-е изд., испр.))
Ахо Альфред В., Хопкрофт Джон, Ульман Джеффри Д. Структуры данных и алгоритмы: Пер. с англ.: Уч.пос.- М.: Издательский дом “Вильямс”, 2000.

Тема 5. Алгоритмы поиска данных. (Трудоемкость – 10 ч.)

Изучить литературу:

Кнут Д. Искусство программирования для ЭВМ. Том 3: Сортировка и поиск.- М.: Мир, 1978. (2-е изд.: Уч.пос.-М.:Издательский дом “Вильямс”, 2000.)
Бакнелл Д. Фундаментальные алгоритмы и структуры данных в Delphi. Библиотека программиста. – М.: ООО «ДиаСофтЮП»; СПб.: Питер, 2006. – 557 с.

Тема 6. Алгоритмы сортировки данных. (Трудоемкость – 10 ч.)

Изучить литературу:

Кнут Д. Искусство программирования для ЭВМ. Том 3: Сортировка и поиск.- М.: Мир, 1978. (2-е изд.: Уч.пос.-М.:Издательский дом “Вильямс”, 2000.)
Бакнелл Д. Фундаментальные алгоритмы и структуры данных в Delphi. Библиотека программиста. – М.: ООО «ДиаСофтЮП»; СПб.: Питер, 2006. – 557 с.

Тема 7. Хеширование и хеш-таблицы.. (Трудоемкость – 5 ч.)

Изучить литературу:

Кнут Д. Искусство программирования для ЭВМ. Том 3: Сортировка и поиск.- М.: Мир, 1978. (2-е изд.: Уч.пос.-М.:Издательский дом “Вильямс”, 2000.)
Бакнелл Д. Фундаментальные алгоритмы и структуры данных в Delphi. Библиотека программиста. – М.: ООО «ДиаСофтЮП»; СПб.: Питер, 2006. – 557 с.

Тема 8. Рандомизированные алгоритмы.. (Трудоемкость – 8 ч.)

Изучить литературу:

Кнут Д. Искусство программирования для ЭВМ. Том 3: Сортировка и поиск.- М.: Мир, 1978. (2-е изд.: Уч.пос.-М.:Издательский дом “Вильямс”, 2000.)
Бакнелл Д. Фундаментальные алгоритмы и структуры данных в Delphi. Библиотека программиста. – М.: ООО «ДиаСофтЮП»; СПб.: Питер, 2006. – 557 с.

Тема 9. Деревья и леса.. (Трудоемкость – 8 ч.)

Изучить литературу:

Ахо Альфред В., Хопкрофт Джон, Ульман Джеффри Д. Структуры данных и алгоритмы: Пер. с англ.: Уч.пос.- М.: Издательский дом “Вильямс”, 2000
Кнут Д. Искусство программирования для ЭВМ. Том 3: Сортировка и поиск.- М.: Мир, 1978. (2-е изд.: Уч.пос.-М.:Издательский дом “Вильямс”, 2000.)
Бакнелл Д. Фундаментальные алгоритмы и структуры данных в Delphi. Библиотека программиста. – М.: ООО «ДиаСофтЮП»; СПб.: Питер, 2006. – 557 с.

Тема 10. Ориентированные графы.. (Трудоемкость – 5 ч.)

Изучить литературу:

Вирт Н. Алгоритмы + структуры данных = программы.- М.: Мир, 1985. (Алгоритмы и структуры данных.- М.: Мир, 1989.) (Алгоритмы и структуры данных. – СПб.: Невский Диалект, 2001. (2-е изд., испр.))
Кнут Д. Искусство программирования для ЭВМ. Том 3: Сортировка и поиск.- М.: Мир, 1978. (2-е изд.: Уч.пос.-М.:Издательский дом “Вильямс”, 2000.)
Бакнелл Д. Фундаментальные алгоритмы и структуры данных в Delphi. Библиотека программиста. – М.: ООО «ДиаСофтЮП»; СПб.: Питер, 2006. – 557 с.

Тема 11. Алгоритмы на графах.. (Трудоемкость – 5 ч.)

Изучить литературу:

Вирт Н. Алгоритмы + структуры данных = программы.- М.: Мир, 1985. (Алгоритмы и структуры данных.- М.: Мир, 1989.) (Алгоритмы и структуры данных. – СПб.: Невский Диалект, 2001. (2-е изд., испр.))
Кнут Д. Искусство программирования для ЭВМ. Том 3: Сортировка и поиск.- М.: Мир, 1978. (2-е изд.: Уч.пос.-М.:Издательский дом “Вильямс”, 2000.)
Бакнелл Д. Фундаментальные алгоритмы и структуры данных в Delphi. Библиотека программиста. – М.: ООО «ДиаСофтЮП»; СПб.: Питер, 2006. – 557 с.

Тема 12. NP-полные и труднорешаемые задачи.. (Трудоемкость – 5 ч.)

Изучить литературу:

Вирт Н. Алгоритмы + структуры данных = программы.- М.: Мир, 1985. (Алгоритмы и структуры данных.- М.: Мир, 1989.) (Алгоритмы и структуры данных. – СПб.: Невский Диалект, 2001. (2-е изд., испр.))
Кнут Д. Искусство программирования для ЭВМ. Том 3: Сортировка и поиск.- М.: Мир, 1978. (2-е изд.: Уч.пос.-М.:Издательский дом “Вильямс”, 2000.)
Бакнелл Д. Фундаментальные алгоритмы и структуры данных в Delphi. Библиотека программиста. – М.: ООО «ДиаСофтЮП»; СПб.: Питер, 2006. – 557 с.
Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. М.: МЦМНО, 1999.
Райли Д. Абстракция и структуры данных: Вводный курс.- М.: Мир, 1993

5. ЛИТЕРАТУРА

Основная

№	Название, библиографическое описание
	Бакнелл Д. Фундаментальные алгоритмы и структуры данных в Delphi. Библиотека программиста. – М.: ООО «ДиаСофтЮП»; СПб.: Питер, 2006. – 557 с.
	Ахо Альфред В., Хопкрофт Джон, Ульман Джеффри Д. Структуры данных и алгоритмы: Пер. с англ.: Уч.пос.- М.: Издательский дом “Вильямс”, 2000.
	Бауэр Ф.Л., Гооз Г. Информатика. Вводный курс: В 2 ч.- М.:Мир, 1990.
	Голодов Е.А., Лапшин Н.А., Николаева Л.Г. Информатика и программирование: учебно-методический комплекс. – Армавир: 2009.
	Вирт Н. Алгоритмы + структуры данных = программы.- М.: Мир, 1985. (Алгоритмы и структуры данных.- М.: Мир, 1989.) (Алгоритмы и структуры данных. – СПб.: Невский Диалект, 2001. (2-е изд., испр.))
	Кнут Д. Искусство программирования для ЭВМ. Том 1: Основные алгоритмы.- М.: Мир, 1976. (3-е изд.: Уч.пос.-М.:Издательский дом “Вильямс”, 2000.)
	Кнут Д. Искусство программирования для ЭВМ. Том 3: Сортировка и поиск.- М.: Мир, 1978. (2-е изд.: Уч.пос.-М.:Издательский дом “Вильямс”, 2000.)
	Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. М.: МЦМНО, 1999.
	Райли Д. Абстракция и структуры данных: Вводный курс.- М.: Мир, 1993.

Дополнительная

	Название, библиографическое описание
	Рейнгольд Э., Нивергельт Ю., Део Н. Комбинаторные алгоритмы. Теория и практика.- М.: Мир, 1980.
	Седжвик Р. Фундаментальные алгоритмы на С++. Анализ/Структуры данных/Сортировка/Поиск: Пер. с англ. – К.: Издательство “ДиаСофт”, 2001.
	Альсведе Р., Вегенер И. Задачи поиска.- М.: Мир, 1982.
	Гудман С., Хидетниеми С. Введение в разработку и анализ алгоритмов.- М.: Мир, 1981.
	Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи.- М.: Мир, 1982.
	Дал У., Дейкстра Э., Хоор К. Структурное программирование. М.: Мир, 1975.
	Калинин А.Г., Мацкевич И.В. Универсальные языки программирования. Семантический подход.- М.: Радио и связь, 1991
	Кристофидес Н. Теория графов. Алгоритмический подход.- М.: Мир, 1978.
	Кушниренко А.Г., Лебедев Г.В. Программирование для математиков: Учеб. пособие для вузов - М.: Наука, 1988.
	Лисков Б., Гатэг Дж. Использование абстракций и спецификаций при разработке программ.- М.: Мир, 1989.
	Лэнгсам Й., Огенстайн М., Тененбаум А. Структуры данных для персональных ЭВМ. - М.: Мир, 1989.
	Майкл Ласло. Вычислительная геометрия и компьютерная графика на С++.-М.: "Издательство БИНОМ", 1997.
	Мейер Б., Бодуэн К. Методы программирования: В 2-х томах.- М.: Мир, 1982.
	Пападимитриу Х., Стайглиц К. Комбинаторная оптимизация. Алгоритмы и сложность. М.: Мир, 1985.
	Свами М., Тхуласираман К. Графы, сети и алгоритмы.- М.: Мир, 1984.
	Сибуя М., Ямамото Т. Алгоритмы обработки данных.- М.: Мир, 1986.
	Теория расписаний и вычислительные машины/Под ред.Э.Г.Коффмана.- М.: Наука, 1984. - 335 с. (Серия: "Экономико-математическая библиотека"), (Ульман Дж. Сложность задач упорядочения, гл.4.)
	Хендерсон П. Функциональное программирование. Применение и реализация. М.: Мир, 1983.

6. ТРЕБОВАНИЯ К ЗАЧЕТУ И ЭКЗАМЕНУ

Зачет по дисциплине выставляется только на основе балльно-рейтинговой системы. Нижняя граница баллов для выставления зачетов (порог успешности) равна 45 баллам.

30 баллов на аудиторную работу

Из них 10 баллов за выполнение всех лабораторных занятий и 20 баллов за посещение всех лекций. Баллы за посещение части занятий пересчитываются пропорционально.

30 баллов на СРС

Содержание СРС и шкала баллов за каждый вид работы:

Индивидуальный проект – 8 баллов;
Подготовка статьи для публикации (от 4 стр.) – 6 баллов;
Участие в олимпиаде по дисциплине – 8 баллов;
Тестирование ФЭПО – 6 баллов;
Выполнение домашней самостоятельной работы – 2 баллов.

На рубежный контроль отводится 30 баллов.

Защита всех лабораторных работ – 25 баллов (при защите части лабораторных работ баллы пересчитываются пропорционально).

Выполнение контрольной работы на "отлично" – 5 баллов, "хорошо" – 4 балла, "удовлетворительно" – 3 балла.

Учет балльно-рейтинговой системы при проведении экзамена.

1. Освобождение от практического задания на экзамене для студента набравшего 45 баллов и более (по желанию студента).

2. Выставление оценки «отлично» на экзамене для студента набравшего 75 баллов и более.

3. Выставление оценки «удовлетворительно» на экзамене для студента набравшего 45 баллов и более (по желанию студента).

4. Выставление экзаменационной оценки без ответа студента с учетом следующей шкалы:

от 45 до 59 баллов - «3» (удовлетворительно);

от 60 до 74 баллов – «4» (хорошо);

от 75 до 90 баллов – «5» (отлично) (по желанию студента).

Blog