1 курс, весенний семестр
лекции - 54 часа
лабораторные занятия - 36 час
Форма итогового контроля - экзамен

Темы лекций

Тип и структура данных. Элементарные типы данных. Фундаментальные структуры данных. Представление данных. Шестнадцатиричная система счисления. Представление элементарных типов: byte, char.

Представление элементарных типов: word, integer, real, Boolean, перечислимые и ограниченные типы. Представление фундаментальных структур: массив, запись, множество.

Распределение памяти при выполнении программы. Данные динамической структуры. Указатели и динамические переменные.

Пример использования динамических переменных (записная книжка). Списки. Очередь.

Включение и исключение элементов. Двунаправленные и кольцевые списки.

Стек. Использование стека. Пример. Представление стека. Поиск в таблицах.

Эффективность программ и сложность алгоритмов. Неупорядоченные таблицы. Линейный поиск. Поиск с барьером.

Упорядоченные таблицы. Упорядочение по частоте. Линейный поиск с барьером. Двоичный поиск в упорядоченной таблице. Деревья и древовидные таблицы. Примеры деревьев. Основные понятия. Двоичные деревья. Представление двоичных деревьев.

Древовидные таблицы и деревья поиска. Идеально сбалансированное дерево. Поиск в дереве элемента с заданным ключем. Построение дерева поиска. Обход дерева.

Исключение элемента из дерева. Балансировка деревьев. АВЛ-деревья. Перемешанные таблицы. Функция расстановки. Алгоритм заполнения таблицы с открытым перемешиванием. Вторичная расстановка.

Поиск в перемешанной таблице. Выбор функции расстановки. Анализ эффективности перемешанной таблицы с открытым перемешиванием. Перемешанные таблицы с цепочками переполнения.

Сортировка. Сортировка массивов. Прямые методы сортировки. Эффективность и устойчивость алгоритмов сортировки. Сортировка извлечением (простым выбором). Обменная (пузырьковая) сортировка.

Сортировка простыми вставками. Сравнение простых сортировок. Улучшенные методы сортировки.

Сортировка Д.Шелла. Сортировка с помощью дерева. Построение двоичного дерева сортировки.

Быстрая сортировка. Сравнение методов сортировки массивов. Внешняя сортировка.

Структурное программирование. Теорема структурирования.

Алгоритмы сжатия данных.

Алгоритм быстрого поиска строки.

Перебор и его сокращение. NP-полные и трудно-решаемые задачи.

Лабораторные работы

Лабораторные работы выполняются по индивидуальным заданиям.
Темы индивидуальных заданий:

1. Програмирование задач машинной графики и анимации (2 задания).
2. Обработка списков.
3. Исследование алгоритмов поиска.

Литература

1. Йенсен К.,Вирт Н. Паскаль.Руководство для пользователя и описание языка /Пер. с англ.,предисл. и послесл. Д.Б. Подшивалова-М.:Финансы и статистика,1982.-151с.ил.
2. Абрамов С.А. Зима Е.В. Начала информатики.- М.:Наука. Гл.ред. физ.- мат. лит.,1989.-256с.(Библиотечка програмиста).
3. С.А.Абрамов, Г.Г.Гнездилова, Е.Н.Капустина, М.И.Селюн. Задачи по программированию - М.:Наука. Гл.ред. физ-мат.лит., 1988.-224с.
4. Абрамов В.Г. Трифонов Н.П. Трифонова Г. Н. Введение в язык Паскаль. Учеб. пособие.- М.:Наука. Гл. ред. физ.- мат. лит.,1988.-320с.
5. Вьюкова Н.И. Галатенко В.А. Ходулев А.В. Систематический подход к программированию (Под ред. физ.- мат. лит. 1988.-208с.- ( Библиотечка програмиста)).
6. Грогоно П. Программирование на языке Паскаль: Пер. с англ.- М.:Мир,1982.-384с.,ил.
7. Перминов О.Н. Программирование на языке Паскаль.- М.:Радио и связь,1988-224с.:ил.
8. Дал У., Дейкстра Э., Хоор Н. Структурное программирование. Пер. с англ. Зенецкий С.Д., Мартынюк В.В.,Ухов Л.В.- М.:Мир,1975
9. Зелковиц М., Шоу А., Гэннон Дж. Принципы разработки программного обеспечения:Пер. с англ.- М.:Мир,1982.-368с.,ил.
10. Лингер Р.,Миллс Х.,Уитт Б. Теория и практика структурного программирования :Пер. с англ.- М.:Мир,1982.-406с.,ил.
11. Мейер Б.,Бодуэн К. Методы программирования :В 2-х томах.Т.1.Пер. с франц. Ю.А.Первина.Под ред. и с предисловием А.П.Ершова.- М.:Мир,1982.-356с.
12. Мейер Б.,Бодуэн К. Методы программирования:В 2-х томах. Пер. с франц. Ю.А.Первина.Под ред. А.П.Ершова.- М.:Мир,1982.-368с.
13. Д.Ван Тассел Стиль, разработка, эффективность, отладка и испытание программ :Пер. с англ.- 2-е изд.,испр.,- М.:Мир,1985.-332с.,ил.
14. Вирт Н. Алгоритмы+структуры данных = программы: Пер. с англ.-М.Мир,1985.-406 с., ил.
15. Вирт Н. Алгоритмы и структуры данных: Пер. с англ.-М.Мир,1989.-360 с., ил.
16. Кнут Д. Искусство программирования для ЭВМ. В семи томах. т.1. Основные алгоритмы. М.: Мир, 1976
17. Кнут Д. Искусство программирования для ЭВМ. В семи томах. т.2. Получисленные алгоритмы. М.: Мир, 1977
18. Кнут Д. Искусство программирования для ЭВМ. В семи томах. т.3. Сортировка и поиск. М.: Мир, 1978

---

Университет | Отделение прикладной математики | Рабочие программы