Программа курса Алгоритмы программирования
| Вид материала | Программа курса |
- Введение Предмет "Программирование", 19.2kb.
- Программа элективного курса по информатике для учащихся 9 класса «Язык программирования, 369.94kb.
- Программа дисциплины Языки и технологии программирования Семестры, 20.19kb.
- Borland Turbo Pascal, знать простые основные алгоритмы работы с простыми типами данных, 324.26kb.
- Учебная программа курса «основы программирования в среде «Delphi» ( 9 класс, 86.93kb.
- Программа учебной дисциплины «Информатика и программирование» Программа дисциплины, 135.24kb.
- Программа курса " Азы программирования", 26.19kb.
- Рабочая программа дисциплины Графы и алгоритмы Направление подготовки, 133.78kb.
- Предлагаемая программа ориентирована на изучение языка программирования Visual Basic, 95.46kb.
- Курс, 1-й семестр лекции (51 час), экзамен практикум на ЭВМ (68 часов), зачет (с оценкой), 24.4kb.
Программа курса
Алгоритмы программирования
Цели и задачи курса: структуры данных, алгоритмы обработки данных, работа с динамическими структурами, графами.
Требования: Слушатели должны знать основы программирования на одном из алгоритмических языков программирования (Pascal, С/C ++, Java, C#).
Краткое содержание курса
Форматы данных, структура данных
Структура программы
Подпрограммы, рекурсия
Работа с статическими массивами, методы сортировки, поиска
Динамические структуры, стеки, очереди (Абстрактные типы данных)
Понятие графа, бинарные деревья, обход дерева, графа
Практические занятия
Содержание разделов дисциплины
Форматы данных, структура данных
Стандартные типы данных. Типы данных, определяемые пользователем. Метки. Комбинированные типы данных: массивы, записи, строки. Процедурный тип. Совместимость типов. Файлы. Блок. Время жизни и область видимости переменных. Статическое и автоматическое распределение памяти.
Структура программы
Построение структуры программы. Понятие модулей. Понятие библиотек.
Подпрограммы, рекурсия
Процедуры и функции. Подпрограммы, концепции использования подпрограмм. Описание процедур. Описание функций. Методы передачи параметров в процедуры и функции. Рекурсия
Работа с статическими массивами, методы сортировки, поиска
Методы вставки. Алгоритм простых вставок. Бинарные вставки. Двухпутевые вставки. Вставки одновременно нескольких элементов. Вставки с убывающим шагом (метод Шелла). Вставки в связанный список . Вставки в несколько связанных списков. Обменная сортировка. Метод пузырька. Модификация метода пузырька. Быстрая сортировка. Обменная поразрядная сортировка. Параллельная сортировка Бэтчера. Сортировка посредством выбора. Использование связанного списка для хранения информации о промежуточных максимумах. Пирамидальная сортировка. Сортировка посредством слияния. Естественное двухпутевое слияние. Простое двухпутевое слияние. Слияние связанных списков. Распределяющая сортировка. Последовательный поиск. Последовательный поиск по связанному списку. Последовательный поиск с перестановкой элементов. Последовательный поиск в упорядоченном файле. Бинарный поиск в упорядоченном файле. Однородный бинарный поиск. Интерполяционный поиск. Поиск по бинарным деревьям. Поиск по бинарному дереву. Удаление из бинарного дерева. Построение оптимальных бинарных деревьев поиска. Цифровой поиск по дереву. Цифровой поиск для длинных ключей, хранимых в текстовом массиве (Патриция).
Динамические структуры, стеки, очереди (Абстрактные типы данных)
Абстрактные типы данных. Стек. Очередь. Список, семейство списков. Реализация АТД с использованием массивов, построение менеджера памяти на основе циклического списка свободных ячеек. Использование стеков и очередей: обратная польская запись, перевод в обратную польскую запись, вычисление значения выражения в обратной польской записи, правильные скобочные последовательности, числа с фиксированным набором простых множителей.
Понятие графа, бинарные деревья, обход дерева, графа
Понятие графа. Псевдографы, мультирафы. Ориентированные и неориентированные графы. Подграфы. Способы представления графов. Матрицы смежности и инциндентности. Маршруты, цепи, пути, циклы в графах. Основные типы графов. Операции над графами. Изоморфизм и гомеоморфизм графов. Метрические характеристики графов. Определение центра, радиуса, диаметра, медианы графа. Достижимость и связность в графах. Алгоритмы определения компонент связности неорграфов и сильных компонент орграфов. Деревья. Понятие остова графа. Методы обхода графа (поиск в глубину и в ширину) и их использование для построения остовов. Алгоритмы Краскала и Прима построения кратчайшего остова взвешенного графа. Циклы и разрезы в графе. Цикломатическое и коцикломатическое числа графа. Построение матриц фундаментальных циклов и разрезов графа. Обходы графа. Эйлеровы графы, цепи, циклы. Теорема Эйлера. Метод Флери построения эйлерова цикла в графе. Гамильтоновы цепи, пути, циклы в графе. Алгоритм Робертса и Флореса построения гамильтонова цикла в графе. Независимость и покрытия. Независимые и доминирующие множества графа. Ядро графа. Паросочетания, покрытия, клики. Реберная и вершинная раскраски графа. Хроматическое число. Эвристическая процедура раскраски графа. Определение кратчайших путей (маршрутов( в графах. Алгоритм определения пути с минимальным числом дуг. Алгоритмы Дейкстры и Форда определения кратчайшего пути между двумя фиксированными вершинами взвешенного графа. Алгоритм Форда определения кратчайших путей между всеми парами вершин графа. Потоки в транспортных сетях. Теорема о максимальном потоке и минимальном разрезе. Алгоритм Форда-Фалкерсона определения максимального потока в сети. Некоторые прикладные задачи теории графов. Использование алгоритмов теории графов в автоматизированном проектировании.
Практические занятия:
| № п/п | № раздела дисциплины | Наименование практических занятий |
| 1 | 1 | Построение простейших линейных программ |
| 2 | 2 | Использование стандартных модулей |
| 3 | 3 | Построение программ с использование подпрограмм. |
| 4 | 3 | Вычисление значений функционального ряда с помощью рекурсий |
| 5 | 4 | Сортировка одномерного массива. |
| 6 | 4 | Поиск в массиве. Поиск в строке. |
| 7 | 5 | Построении стека. |
| 8 | 5 | Построение очереди |
| 9 | 6 | Построение бинарного дерева |
| 10 | 6 | Обход бинарного дерева |
| 11 | 6 | Построение графа |
| 12 | 6 | Сортировка графа, поворот |