ЦЕЛЬ И ЗАДАЧИ ИЗУЧЕНИЯ ДИСЦИПЛИНЫ

Цель изучения дисциплины "Структуры и алгоритмы обработки данных" заключается в том, чтобы познакомить студентов с различными способами представления данных в памяти ЭВМ, с различными классами задач и типами алгоритмов, встречающихся при решении задач на современных ЭВМ.

В результате изучения данного курса, студент должен эффективно решать вопросы, возникающие на стадии разработки или выбора алгоритма. К этим вопросам относятся: обоснование и выбор структуры представления данных, анализ сложности разработанного алгоритма, оценка затрат на разработку алгоритма в зависимости от класса решаемых задач и наличных или требуемых для их решения вычислительных средств.

Задачи дисциплины:

·        сформировать базовые теоретические понятия, лежащие в основе процесса разработки алгоритмов и структур данных;

·        заложить в основу конструирования и использования сложных (динамических) структур данных модель (парадигму) абстрактного типа данных (спецификация + представление + реализация);

·        сформировать представления и знания об основных классах алгоритмов (исчерпывающий поиск, быстрый поиск, сортировки, алгоритмы на графах и т.п.), используемых в них структурах данных и общих схемах решения задач на их основе;

·        научить реализации типовых алгоритмов и структур данных и их модификаций на выбранном рабочем языке программирования;

·        сформировать представления и знания об анализе сложности алгоритмов и программ.

Дисциплина "Структуры и алгоритмы обработки данных" дает основы, на которых строится изучение ряда специальных курсов.

___________________________________________________________

ТРЕБОВАНИЯ К УРОВНЮ УСВОЕНИЯ

В результате изучения курса, студенты должны:

Знать:

·        основные методы разработки машинных алгоритмов и программ, структуры данных, используемые для представления типовых информационных объектов, основные задачи анализа алгоритмов;

·        основные машинные алгоритмы и характеристики их сложности для типовых задач, часто встречающихся и ставших «классическими» в области информатики и программирования;

Уметь:

·        разрабатывать алгоритмы, используя изложенные в курсе общие схемы, методы и приемы построения алгоритмов, выбирая подходящие структуры данных для представления информационных объектов;

·        доказывать корректность составленного алгоритма и оценивать основные характеристики его сложности;

·        реализовывать алгоритмы и используемые структуры данных средствами языков программирования высокого уровня;

·        экспериментально (с помощью компьютера) исследовать эффективность алгоритма и программы;

Иметь представление о:

·        некоторых математических методах анализа алгоритмов;

·        классификации алгоритмических задач по их сложности, сводимости алгоритмических задач к известным задачам определенного класса сложности.

Эти вопросы являются фундаментальными в различных областях программирования, начиная от несложных прикладных программ и заканчивая такими системными программами как операционные системы и системы управления базами данных.

__________________________________________________________________

ТЕМЫ ДИСЦИПЛИНЫ:

1. Основные понятия о типах и структурах данных
2. Классификация структур данных
3. Нелинейные связные структуры
4. Древовидные структуры
5. Задачи поиска и кодирования (сжатия) данных
6. Многомерные структуры данных
7. Метрические структуры данных
8. Темпоральные структуры данных
9. Общие понятия о сортировке
10. Классификация основных методов поиска
11. Быстрый поиск: бинарный поиск, хеширование
12. Анализ сложности и эффективности алгоритмов поиска и сортировки
13. Исчерпывающий поиск
14. Файлы: организация и обработка, представление деревьями
15. Сетевые структуры и алгоритмы их обработки
16. Теория сложности алгоритмов: NP-сложные и труднорешаемые задачи

___________________________________________________________

РЕКОМЕНДУЕМАЯ ЛИТЕРАТУРА:

1. Кнут Д. Искусство программирования для ЭВМ т.1, Основные алгоритмы М: Издательский дом "Вильямс" 2000.
2. Кнут Д. Искусство программирования для ЭВМ т.3, Сортировка и поиск М: Издательский дом "Вильямс" 2000.
3. Вирт Н. Алгоритмы и структуры данных Москва, «МИР», 1989
4. Гулаков В.К. Многомерные структуры данных/ В.К. Гулаков, А.О. Трубаков - Брянск: БГТУ, 2010. – 387 с.
5. Гулаков В.К. Деревья: алгоритмы и программы / В.К. Гулаков – М: Машиностроение-1, 2005. – 206 с.

__________________________________________________________________ 

Учебные материалы по дисциплине

Ведущие преподаватели: проф. Гулаков В.К., доц. Трубаков А.О., ст. преп. Зимин С.Н.

<<назад к списку дисциплин