|          главная    |    о центре развития карьеры    |    расписание          | Институт точной механики и оптики ХэшКод
Новости Семинары     Студенческое отделение Студенческие проекты
Расписание занятий Организация обучения Школьное отделение Отделение олимпиадной подготовки Контакты

  Факультет Информационных Технологий и Программирования

  График отмены занятий в ноябре 2017 года

  Набор на программы 2017-2018 уч. года для школьников

  Ведется запись в школьное отделение Академии информатики и программирования (осень 2016)

Алгоритмы и структуры данных

Цели и задачи курса: структуры данных, алгоритмы обработки данных, работа с динамическими структурами, графами.

Требования: Слушатели должны знать основы программирования на одном из алгоритмических языков программирования (Pascal, С/C ++, Java, C#).

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

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

Стандартные типы данных. Типы данных, определяемые пользователем. Метки. Комбинированные типы данных: массивы, записи, строки. Процедурный тип. Совместимость типов.
Файлы.  Блок. Время жизни и область видимости переменных. Статическое и автоматическое распределение памяти. Построение структуры программы. Понятие модулей. Понятие библиотек.
Процедуры и функции. Подпрограммы, концепции использования подпрограмм. Описание процедур. Описание функций. Методы передачи параметров в процедуры и функции. Рекурсия.

Работа с статическими массивами, методы сортировки, поиска

Методы вставки. Алгоритм простых вставок. Бинарные вставки. Двухпутевые вставки. Вставки одновременно нескольких элементов. Вставки с убывающим шагом (метод Шелла).
Вставки в связанный список . Вставки в несколько связанных списков. Обменная сортировка.  Метод пузырька.  Модификация метода  пузырька. Быстрая сортировка.
Обменная поразрядная сортировка. Параллельная сортировка Бэтчера. Сортировка посредством выбора. Использование связанного списка для хранения  информации о промежуточных максимумах.
Пирамидальная сортировка. Сортировка посредством слияния. Естественное двухпутевое слияние. Простое двухпутевое слияние. Слияние связанных списков.
Распределяющая сортировка. Последовательный поиск. Последовательный поиск по связанному списку. Последовательный поиск с перестановкой элементов.
Последовательный поиск в упорядоченном файле.  Бинарный поиск в упорядоченном файле. Однородный бинарный поиск. Интерполяционный поиск. Поиск по бинарным деревьям. 
Поиск по бинарному дереву.  Удаление из бинарного дерева.  Построение оптимальных бинарных деревьев поиска. Цифровой поиск по дереву. Цифровой поиск для длинных ключей, хранимых в  текстовом массиве (Патриция).

Динамические структуры, стеки, очереди (Абстрактные типы данных)

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

Понятие графа, бинарные деревья, обход дерева, графа

Понятие графа. Псевдографы, мультирафы. Ориентированные и неориентированные графы. Подграфы. Способы представления графов. Матрицы смежности и инциндентности.
Маршруты, цепи, пути, циклы в графах. Основные типы графов. Операции над графами. Изоморфизм и гомеоморфизм графов. Метрические характеристики графов. Достижимость и связность в графах.
Алгоритмы определения компонент связности неорграфов и сильных компонент орграфов. Деревья. Понятие остова графа. Методы обхода графа (поиск в глубину и в ширину) и их использование для построения остовов.
Алгоритмы Краскала и Прима построения кратчайшего остова взвешенного графа. Циклы и разрезы в графе. Цикломатическое и коцикломатическое числа графа. Построение матриц фундаментальных циклов и разрезов графа.
Обходы графа. Эйлеровы графы, цепи, циклы. Теорема Эйлера. Метод Флери построения эйлерова цикла в графе. Гамильтоновы цепи, пути, циклы в графе. Алгоритм Робертса и Флореса построения гамильтонова цикла в графе.
Независимость и покрытия. Независимые и доминирующие множества графа. Ядро графа. Паросочетания, покрытия, клики. Реберная и вершинная раскраски графа. Хроматическое число. Эвристическая процедура раскраски графа.
Определение кратчайших путей (маршрутов( в графах. Алгоритм определения пути с минимальным числом дуг. Алгоритмы Дейкстры и Форда определения кратчайшего пути между двумя фиксированными вершинами взвешенного графа.
Алгоритм Форда определения кратчайших путей между всеми парами вершин графа. Потоки в транспортных сетях. Теорема о максимальном потоке и минимальном разрезе. Алгоритм Форда-Фалкерсона определения максимального потока в сети.
Некоторые прикладные задачи теории графов. Использование алгоритмов теории графов в автоматизированном проектировании.

 

Практические занятия: 

Построение простейших линейных программ

Использование стандартных модулей

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

Вычисление значений функционального ряда с помощью рекурсий

Сортировка одномерного массива.

Поиск в массиве. Поиск в строке.

Построении стека.

Построение очереди.

Построение бинарного дерева.


Контактная информация:
Санкт-Петербург, Кронверский пр., 49, м. Горьковская
email:
, тел: (812) 941-76-25
Сделано в 1ADW
Главная    |    Новости