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

Кафедра математического обеспечения и суперкомпьютерных технологий

Специальность: Прикладная математика и информатика, Программная инженерия, и Фундаментальная информатика и информационные технологии

Преподаватель: Гергель В.П.

Дисциплина «Алгоритмы и структуры данных» является второй частью двухгодичного курса по методам и технологиям программирования, общей целью которого является подготовка высококвалифицированных разработчиков сложных программных систем моделирования объектов и явлений реального мира, управления экономико-социальными и производственными процессами, а также решения других задач автоматизации, научных исследований и проектирования на основе применения современной вычислительной техники. Излагаемый набор знаний и умений составляет теоретическую основу для методов разработки сложных программ. Изучение курса поддерживается расширенным лабораторным практикумом.

Содержание

  1. Концепция структур данных (объекты и операции).
  2. Базовый анализ алгоритмов: асимптотический анализ наибольшей и средней сложности; установление различии между лучшим, средним и худшим случаями; О-большое и о-маленькое нотации; стандартные классы сложности; эмпирические измерения характеристик исполнения; затраты по объему памяти и времени; использование рекуррентных соотношений для анализа рекурсивных алгоритмов.
  3. Рекурсия: понятие рекурсии, рекурсивные математические функции, простые рекурсивные процедуры, стратегия «разделяй-и-властвуй», рекурсивный перебор с возвратами, реализация рекурсии.
  4. Базовые структуры данных: стеки, очереди, связные списки, хэш-таблицы, деревья, графы.
  5. Структуры хранения данных и их объектно-ориентированная разработка.
  6. Основные вычислительные алгоритмы: алгоритмы сортировки со сложностью O(N logN), хэш-таблицы и алгоритмы исключения коллизий, двоичные деревья поиска, представления графов, обходы в глубину и в ширину.
  7. Программная инженерия: разработка спецификаций, проектирование структуры создаваемого программного обеспечения, поэтапная разработка, проверка соответствия; основы тестирования, составление плана тестирования и генерация тестовых пакетов; тестирование объектно-ориентированных программ, подготовка документации.

Презентации по курсу "Алгоритмы и структуры данных".

Презентации по курсу "Алгоритмы и структуры данных" 2020.

Материалы по курсу - 2 тома  "Методы программирования".

Материалы по лабораторным работам.

Рабочие материалы по курсу.

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

  • Лабораторная работа 1. Структура хранения множеств.
  • Лабораторная работа 2. Структуры хранения матриц специального вида.
  • Лабораторная работа 3. Вычисление арифметических выражений.
  • Лабораторная работа 4. Обслуживание процессором ЭВМ очереди заданий.
  • Лабораторная работа 5. Система для арифметических действий над полиномами.
  • Лабораторная работа 6. Редактирование текстов.
  • Лабораторная работа 7. Структуры хранения геометрических объектов.
  • Лабораторная работа 8. Сравнительная характеристика способов организации таблиц.
  • Лабораторная работа 9. Обработка геометрических объектов на ЭВМ (графовые модели).

Литература

а) основная литература:

  1. Круз Р.Л. Структуры данных и проектирование программ. – М.: Бином. Лаборатория знаний, 2014.
  2. Топп У., Форд У. Структуры данных в С++.- М.: Бином, 1999
  3. Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ.- М.: МЦМО, 1999.
  4. Ахо Альфред В., Хопкрофт Джон, Ульман Джеффри Д. Структуры данных и алгоритмы- М.: Издательский дом Вильямс, 2000.
  5. Гергель В.П. и др. Методы программирования. Учебное пособие. Н.Новгород: ННГУ, 2016.

б) дополнительная литература:

  1. Вирт Н. Алгоритмы + структуры данных = программы.- М.:  Мир, 1985.
  2. Кнут Д. Искусство программирования для ЭВМ.  Том 1:  Основные алгоритмы.- М.: Мир, 1976. (3-е изд.: Уч.пос.-М.:Издательский дом “Вильямс”, 2000.)
  3. Кнут Д. Искусство программирования для ЭВМ. Том 3: Сортировка и поиск.- М.: Мир, 1978. (2-е изд.: Уч.пос.-М.:Издательский дом “Вильямс”, 2000.)
  4. Страуструп Б. Язык программирования С++. – М.: Бином, 2001.

Отчетность

  • Семестр 3: Зач
  • Семестр 4: Экз