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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

уметь:

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

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

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

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

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

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

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

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

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

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

№	Раздел дисциплины	Лекции	ПЗ или С	ЛР
1	Структуры данных.	12	8
2	Алгоритмы сортировки.	12	12
3	Алгоритмы поиска.	8	12
4	Алгоритмы на графах.	8	8
5	Генерация псевдослу­чайных последователь­ностей и алгоритмы по­рождения перестановок.	8	8

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

Раздел 1. Структуры данных.

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

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

Раздел 2. Алгоритмы сортировки.

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

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

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

Раздел 3. Алгоритмы поиска.

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

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

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

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

Раздел 4. Алгоритмы на графах.

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

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

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

Раздел 5. Генерация псевдослучайных последовательностей и алгорит­мы порождения перестановок.

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

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

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

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

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

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

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

ОСНОВНАЯ:

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

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

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

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

ДОПОЛНИТЕЛЬНАЯ:

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

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

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

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

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

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