Структуры и алгоритмы компьютерной обработки данных Представление дисциплины

2 Общие сведения по дисциплине Название: Структуры и алгоритмы компьютерной обработки данных Читается для специальности – Математическое обеспечение и администрирование информационных систем. Важность изучения дисциплины Данная дисциплина является фундаментальным разделом компьютерной науки (Computer Science), который по своей сути закладывает начальные основы, без которых в настоящее время не представляется возможным подготовка высококвалифицированных специалистов в области информационных технологий и соответствующего программного обеспечения. Сфера профессионального использования Проектирование корректных и эффективных структур данных и алгоритмов при разработке программного обеспечения информационных систем.

3 Цели и задачи преподавания дисциплины Цели дисциплины Дисциплина "Структуры и алгоритмы компьютерной обработки данных" имеет целью обучить студентов принципам построения структур данных и алгоритмов компьютерной обработки информации, способствовать развитию логического мышления, формированию научного мировоззрения и прививать склонность к творчеству. Задачи дисциплины Задачей преподавания дисциплины является приобретение студентами теоретических знаний и практических навыков в разработке и анализе корректных и эффективных алгоритмов и структур данных.

4 Место дисциплины среди смежных дисциплин Данная дисциплина требует предварительного изучения курсов программирование; дискретная математика; математическая логика; информатика. В то же время дисциплина является одной из базовых для изучения дисциплин теория вычислительных процессов и структур; технология разработки ПО.

5 Итоговые знания, умения и навыки В результате изучения дисциплины студенты должны иметь ПРЕДСТАВЛЕНИЯ: о способах оценки сложности работы алгоритмов; о возможности модификации алгоритмов и структур данных с учетом конкретных практических задач. В результате изучения дисциплины студенты должны ЗНАТЬ: фундаментальные компьютерные алгоритмы и структуры данных; классификацию алгоритмов по степени их сложности и по типам используемых структур данных, особенности реализации алгоритмов каждого класса; стратегии разработки алгоритмов и анализ их сложности. В результате изучения дисциплины студенты должны приобрести УМЕНИЯ И НАВЫКИ: разработки эффективных алгоритмов различных классов с учетом накопленного опыта их реализации; применения математического аппарата для анализа сложности алгоритмов; реализации алгоритмов на языках программирования высокого уровня и выбора структуры данных для хранения информации.

6 Содержание лекционного курса Тема 1. Введение в структуры и алгоритмы компьютерной обработки данных. Тема 2. Базовые типы данных языков программирования высокого уровня. Тема 3. Анализ алгоритмов и их сложности. Тема 4. Алгоритмы сортировки и поиска на массивах. Тема 5. Типы данных линейной структуры. Тема 6. Типы данных нелинейной структуры.

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

8 Тема 2. Базовые типы данных языков программирования высокого уровня Целью данной темы является рассмотрение вопросов представления базовых типов данных в языках программирования. В ней описываются физический уровень представления данных в компьютере, простые базовые типы данных, а также поддерживаемые современными языками составные структуры данных, такие как массивы, строки, структуры (записи) и множества.

9 Тема 3. Анализ алгоритмов и их сложности Целью данной темы является рассмотрение вопросов оценки временной сложности алгоритмов. В ней демонстрируется существование нескольких алгоритмов решения некоторых задач, и рассматривается проблема сравнения и выбора алгоритма из множества эквивалентных по решаемым задачам алгоритмов. Вводиться понятие временной сложности алгоритма, рассматривается математический аппарат для оценки временной сложности и правила применения этого аппарата.

10 Тема 4. Алгоритмы сортировки и поиска на массивах Целью данной темы является изучение алгоритмов сортировки и поиска элементов массива. В ней осуществляется постановка задачи сортировки, формулируются свойства алгоритмов сортировки, рассматриваются базовые алгоритмы: сортировка обменом, вставками и выбором, а так же их различные улучшения, позволяющие существенно сократить их временную сложность. Так же, в этой теме осуществляется постановка задачи поиска и рассматриваются алгоритмы линейного, блочного и бинарного поиска. Проводится сравнительный анализ всех рассмотренных алгоритмов.

11 Тема 5. Типы данных линейной структуры Целью данной темы является изучение типов данных линейной структуры. В ней рассматриваются такие линейные структуры данных как списки, стеки, очереди и хеш- таблицы. Рассматриваются вопросы их программной реализации.

12 Тема 6. Типы данных нелинейной структуры Целью данной темы является изучение типов данных нелинейной структуры, таких как графы и деревья. В ней рассматриваются основные понятия и определения теории графов, способы представления графов в памяти ЭВМ, алгоритмы обхода графов, основные понятия и определения деревьев, широко распространенный частный случай деревьев – двоичные деревья и их применение, структуры данных для представления и операции над двоичными деревьями.

13 Лабораторный практикум Лабораторная работа 1 (по теме 2). Представление базовых типов данных языка С++ на физическом уровне. Лабораторная работа 2 (по теме 3). Оценка временной сложности алгоритмов. Лабораторная работа 3 (по теме 4). Программная реализация и сравнение алгоритмов сортировки. Лабораторная работа 4 (по теме 5). Программная реализация списков. Лабораторная работа 5 (по теме 6). Структуры данных для хранения графов.

14 Контрольные мероприятия Промежуточный контроль: Отчет по лабораторным работам Рубежный тест Итоговый контроль: Зачет

15 Список литературы Основная Ахо А., Хопкрофт Дж., Ульман Дж. Структуры данных и алгоритмы. – М.: Вильямс, Вирт Н. Алгоритмы и структуры данных. – СПб.: Невский диалект, Кнут Д. Искусство программирования для ЭВМ. Т.1. Основные алгоритмы. – М.: Вильямс, Кнут Д. Искусство программирования для ЭВМ. Т.1. Получисленные алгоритмы. – М.: Вильямс, Кнут Д. Искусство программирования для ЭВМ. Т.3. Сортировка и поиск. – М.: Вильямс, Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: Построение и анализ. М.: МЦНМО, 2001.

16 Список литературы Дополнительная Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. – М.: Мир, Баррон Г. Рекурсивные методы в программировании. – М.: Мир, Вирт Н. Алгоритмы + структуры данных = программы. – М.: Мир, Грис Д. Наука программирования. – М.: Мир, Гудман С., Хидетниеми С. Введение в разработку и анализ алгоритмов. – М.: Мир, Дейкстра Э. Дисциплина программирования. – М.: Мир, Лорин Г. Сортировка и системы сортировки. – М.: Наука, Макконелл Дж. Анализ алгоритмов: Вводный курс. – М.: Техносфера, Мальцев А. М. Алгоритмы и рекурсивные функции. – М.: Наука, Сибуя М., Ямомото Т. Алгоритмы обработки данных. – М.: Мир, Холл П. Вычислительные структуры. Введение в начисленное программирование. – М.: Мир, Холстед М. Х. Начала науки о программах. – М.: Финансы и статистика, Хусаинов Б. С. Структуры и алгоритмы обработки данных: Примеры на языке Си: Учебное пособие для вузов. – М.: Финансы и статистика, 2004.

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

18