Краткое содержание курса Форматы данных, структура данных Структура программы Подпрограммы, рекурсия



Дата09.11.2012
Размер47.5 Kb.
ТипКраткое содержание


Программа курса
Алгоритмы программирования
Цели и задачи курса: структуры данных, алгоритмы обработки данных, работа с динамическими структурами, графами.
Требования: Слушатели должны знать основы программирования на одном из алгоритмических языков программирования (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

Сортировка графа, поворот



Похожие:

Краткое содержание курса Форматы данных, структура данных Структура программы Подпрограммы, рекурсия icon1. Предмет и задачи курса, структура Пролог-программы. Структура программы на Турбо-прологе. Объекты данных Пролога. Сопоставление
Логическое программирование один из подходов к информатике, при котором в качестве языка высокого уровня используется логика предикатов...
Краткое содержание курса Форматы данных, структура данных Структура программы Подпрограммы, рекурсия iconЛабораторная работа №2 «структура программы в паскале. Ввод и вывод данных. Линейные программы»
Цель работы: усвоить назначения и использование операторов ввода данных и вывода результата, оформления программы на Паскале, освоение...
Краткое содержание курса Форматы данных, структура данных Структура программы Подпрограммы, рекурсия iconБилеты к выпускному экзамену по информатике
Структура программы в Паскале. Вещественный и целый тип данных. Стандартные функции и процедуры для работы с целым и вещественным...
Краткое содержание курса Форматы данных, структура данных Структура программы Подпрограммы, рекурсия iconЛабораторная работа №9 структура программы. Скалярные типы данных. Выражения и присваивания
Цель: Изучить категории типов данных, виды выражений и операций и работу с ними на языке Си
Краткое содержание курса Форматы данных, структура данных Структура программы Подпрограммы, рекурсия iconСервис «Шлюз2» Структура базы данных и сообщений Реквизиты документа
В данном документе описана структура таблиц базы данных и сообщений системы Шлюз2
Краткое содержание курса Форматы данных, структура данных Структура программы Подпрограммы, рекурсия iconО. А. Кучерявенко Разработка базы данных электронного гербария. Состояние вопроса
Рассмотрены и проанализированы варианты разработки и функционирования существующих баз данных по электронным гербариям. Предложена...
Краткое содержание курса Форматы данных, структура данных Структура программы Подпрограммы, рекурсия iconБазы данных по экологии финского залива и их структура
Базы данных по экологии Финского залива и их структура (глава 5) // "Невская губа" опыт моделирования (коллективная монография под...
Краткое содержание курса Форматы данных, структура данных Структура программы Подпрограммы, рекурсия iconКраткое содержание курса Теория баз данных Модели данных и языки запросов Транзакции и согласованность
Субд в прикладных системах. Основные функции субд. Взаимодействие субд с другими компонентами программного обеспечения. История развития...
Краткое содержание курса Форматы данных, структура данных Структура программы Подпрограммы, рекурсия iconКраткое содержание лекций Тема Архитектура Oracle Файлы данных и табличные пространства Oracle это современная система управления реляционной базой данных, поддерживающая работу в различных операционных средах
Информация обо всех файлах данных, составляющих физическое пространство базы данных, хранится в виде словаря данных dba data files,...
Краткое содержание курса Форматы данных, структура данных Структура программы Подпрограммы, рекурсия iconОсновы работы с базами данных Содержание
В хорошо спроектированной базе данных избыточность данных исключается, и вероятность сохранения противоречивых данных минимизируется....
Разместите кнопку на своём сайте:
ru.convdocs.org


База данных защищена авторским правом ©ru.convdocs.org 2016
обратиться к администрации
ru.convdocs.org