1. Цели и задачи дисциплины

Дисциплина "Методы программирования" имеет целью обучить студентов принципам построения и анализа алгоритмов, способствовать развитию логического мышления, формированию научного мировоззрения и прививать склонность к творчеству. При изучении курса используются знания, полученные слушателями в процессе изучения курсов "Математический анализ", "Теория вероятностей", "Языки программирования высокого уровня". Знания и практические навыки, полученные из курса "Методы программирования", используются обучаемыми при изучении научных дисциплин, а также при разработке курсовых и дипломных работ.

Задачи дисциплины - дать основы:

• структур данных;

• оценки сложности работы алгоритма;

• aлгоритмов сортировки;

• алгоритмов поиска;

• алгоритмов на графах;

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

• алгоритмов генерации подстановок.

2. Требования к уровню освоения содержания дисциплины.

В результате изучения дисциплины студенты(слушатели) должны

Иметь представление:

• о способах оценки сложности работы алгоритмов;

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

Знать:

• принципы лежащие в основе алгоритмов сортировки и поиска информации;

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

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

Уметь:

• сформулировать задачу и использовать для ее решения известные методы;

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

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

Иметь навыки:

• написания и отладки программ, реализующих алгоритмы сортировки, поиска и алгоритмы на графах.

• получения эмпирических оценок трудоемкости алгоритма.

3. Объем дисциплины и виды учебной работы(часы):

Вид занятий	Всего часов	Семестры
Общая трудоемкость	200	-	-
Аудиторные занятия	100	50	50
Лекции	48	24	24
Практические занятия (ПЗ)	48	24	24
Семинары (С)	-	-	-
Лабораторные работы (ЛР)	-	-	-
Контрольные работы	4	2	2
Самостоятельная работа	100	50	50
Курсовой проект (работа)	-	-	-
Расчетно-графические работы	-	-	-
Реферат	-	-	-
Иные виды работ	-	-	-
Вид итогового контроля	36	зачет	экзамен

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

4.1. Тематический план.

Раздел дисциплины	Лекции(час)	ПЗ или С(час)	ЛР(час)
Структуры данных.	12	8	-
Алгоритмы сортировки.	12	12	-
Алгоритмы поиска.	8	12	-
Алгоритмы на графах.	8	8	-
Генерация псевдослучайных последовательностей и алгоритмы порождения перестановок.	8	8	-

4.2. Содержание разделов дисциплины

РАЗДЕЛ 1.СТРУКТУРЫ ДАННЫХ

Цели и задачи курса. Место дисциплины в учебном процессе. Методические рекомендации по изучению курса. Обзор литературы.

Элементарные и простые структуры данных. Сложные структуры данных. Статические и динамические структуры.

РАЗДЕЛ 2. АЛГОРИТМЫ СОРТИРОВКИ

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

Основные понятия и стратегии сортировки. Алгоритмы сортировки вставками, выбором, слиянием, обменная сортировка, распределяющая сортировка. Оценка сложности работы алгоритмов внутренней сортировки.

Основные понятия внешней сортировки. Алгоритмы многофазного и каскадного слияния.

РАЗДЕЛ 3.АЛГОРИТМЫ ПОИСКА

Основные понятия. Алгоритмы исчерпывающего поиска.

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

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

Хеширование. Разрешение коллизий.

РАЗДЕЛ 4. АЛГОРИТМЫ НА ГРАФАХ

Возможные представления графов в ЭВМ.

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

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

РАЗДЕЛ 5. ГЕНЕРАЦИЯ ПСЕВДОСЛУЧАЙНЫХ ПОСЛЕДОВАТЕЛЬНОСТЕЙ И АЛГОРИТМЫ ПОРОЖДЕНИЯ ПЕРЕСТАНОВОК

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

Алгоритмы порождения перестановок в лексикографическом порядке, циклическим сдвигом и в порядке минимального изменения. Коды Грея.

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

5. Лабораторный практикум

не предусмотрен.

6. Учебно-методическое обеспечение дисциплины

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

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

1. Кнут Д. Искусство программирования для ЭВМ. т.1,2,3, Сортировка и поиск. - М.: Мир,.

2. Кормен. Т., Леверсон Ч., Ртвест Р. Алгоритмы. Построение и анализ.-М.; МЦНМО, 1999, 960 с.

3. Грехем Р., Кнут Д., Поиашник О. Конкретная математика.М.. Мир.,1998, 702 с.

4. Мачкевич И.В. Алгоритмы сортировки. Курс лекций.. М.: в/ч 33965, 1991.

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

1. Ахо А. , Хопкрофт ДЖ. Построение и анализ вычислительных алгоритмов. - М; Мир, 1979. - 536 с.

2. Кнут Д. Искусство программирования для ЭВМ. т.3, Сортировка и поиск. - М.: Мир, 1978, ,848с.

3. Мейер Б., Бодуэн К. Методы программирования. т.1, - М.; Мир, 1982г. 362с.

4. Рейнгольд Э., Нивергелд Ю., Део Н.. Комбинаторные алгоритмы . Теория и практика, М., Мир., 1980г., 480с.

5. Нивергельд Ю., Рейнголд Э., Фаррар Дж. Машинный подход к решению математических задач. М. Мир. 1977, 351с.

6. Акулинин Ю.А. Исаев О.В. , Кривенко М.П., Мацкевич И.В. Специальное применение ЭВМ. Курс лекций. М.: в/ч 33965, 1986