Кафедра программного обеспечения ВТ и АС

Российской федерации

ФГБОУ ВПО

«Дагестанский Государственный Технический

Университет»

Факультет КТВТиЭ

 

Кафедра программного обеспечения ВТ и АС

 

 

Методические указания

к выполнению курсовой работы

по дисциплине

 

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

 

для студентов направления подготовки бакалавров 231000.62 – «Программная инженерия»

 

 

Махачкала - 2014г.

УДК 517.11

 

 

Методические указания к выполнению курсовой работы по дисциплине «Алгоритмы и структуры данных» для студентов направления подготовки бакалавров 231000.62 – «Программная инженерия». Махачкала, ДГТУ, 2014. –14с.

Методические указания предназначены для использования при выполнении курсовой работы по дисциплине «Алгоритмы и структуры данных». Сформулированы цели и задачи, содержание и порядок выполнения проекта, приводится пример оформления проекта.

 

Составитель: Сулейманова О.Ш., старший преподаватель кафедры ПОВТиАС

Шахпазова И.Ф., к.ф.-м.н., старший преподаватель кафедры ПОВТиАС

Рецензенты: Исабекова Т.И., к.ф.-м.н., доцент, зав. кафедры ПМиИ,

Кобзаренко Д.Н., д.т.н., зав.лаборатории информационных технологий в энергетике ФГБУН «Института проблем геотермии ДНЦ РАН»

 

Печатается по постановлению Ученого совета Дагестанского Государственного Технического университета

 

 

Оглавление

 

Цель выполнения курсовой работы.. 4

Теоретические сведения. 4

Порядок выполнения работы.. 6

Требования к функциональным характеристикам. 9

Требования к оформлению пояснительной записки. 10

Тематика курсовых работ. 11

Список рекомендуемой литературы.. 12

Приложение. Образец формы титульного листа курсовой работы.. 13

 

 

 

Цель выполнения курсовой работы

 

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

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

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

Основные задачи, решаемые разработчиком в процессе выполнения курсовой работы:

- программная реализация задачи;

- разработка программы для оценки качества реализованного алгоритма;

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

- документирование курсовой работы в соответствии с установленными требованиями.

 

Теоретические сведения

 

Непрерывная и дискретная информация

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

Математически такие поля представляются с помощью функций

Y = f(x,t), (1)

где t - время, x - точка, в которой измеряется поле, у - величина поля в

этой точке.

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

Если же установить минимальные шаги изменения всех скалярных величин, входящих в формулу (1), то получим так называемое дискретное представление информации или дискретную информацию. Это вполне оп­равданный подход, т.к. точность измерений, как и человеческого воспри­ятия, всегда ограничена. Т.е. даже непрерывную информацию мы всегда воспринимаем в дискретном виде. Но любая непрерывная информация может быть аппроксимирована дискретной информацией с любой степе­нью точности, поэтому дискретная форма представления информации - универсальна.

Результаты измерения любых скалярных величин представляются, в конце концов, в виде числа с конечным набором цифр (при заданной точ­ности измерений). Поэтому дискретную информацию часто отождествля­ют с цифровой информацией.

Данные и ЭВМ

Обработка цифровой информации должна обеспечивать решение за­дач, связанных с реальным миром. Однако бесконечное множество объек­тов и связей между ними, составляющих наш мир, не может быть пред­ставлено в ограниченном объеме памяти любой машины, какой бы боль­шой она ни была. Следовательно, необходимо построить некую ограни­ченную масштабную модель реального мира, которая учитывала бы только те данные или информацию и связи между объектами, которые касаются именно рассматриваемой проблемы. Такая модель обычно имеет два уровня. Первый уровень является результатом абстракции и задает упро­щенную логическую структуру данных. Второй уровень определяет пре­образование этой структуры в физическую структуру данных, которая мо­жет быть непосредственно отображена в памяти машины и обработана с помощью программного обеспечения.

Структура данных - это набор правил и ограничений, которые пока­зывают связи между отдельными элементами данных или группами дан­ных. Она ничего не говорит об отдельных элементах данных, и любая ин­формация о них является излишней при условии, что связи между ними установлены. Если некоторые данные в структуре сами являются структу­рами данных, то образуется некая иерархия структур данных.

Объекты предметной области

При решении конкретных проблем обычно ограничиваются той ча­стью реального мира, которая является областью данной деятельности. Ее называют предметной областью (ПО). Для решения проблем деятельности нужна информационная модель ПО - описание структур данных на логи­ческом уровне. Проектируя модель ПО, обычно связывают структуры дан­ных с объектами ПО.

Объектами могут быть:

• люди, например, перечисленные в платежной ведомости;

• предметы, например, детали;

• построения, например, счета в задаче получения счетов.

Объект - это некая абстракция, которой можно дать уникальное и осмысленное имя. Оно отделяет конкретный объект от других подобных абстракций. Например, в ПО ВУЗ существует объект СТУДЕНТ - лицо, проходящее обучение в ВУЗе. В той же ПО существует объект ПРЕПОДАВАТЕЛЬ - лицо, обучающее СТУДЕНТов. Таким образом, объ­ект есть тип, множество экземпляров, обладающих (в моделируемой ПО) сходными свойствами. Так, конкретный Иванов Виктор Леонидович явля­ется экземпляром объекта СТУДЕНТ.

Каждый объект обладает вполне определенным уникальным набо­ром свойств. Эти свойства называются атрибутами. Атрибуты, как и объ­екты, имеют осмысленные имена. Так, атрибутами объекта СТУДЕНТ мо­гут быть Фамилия, Имя, Отчество, Дата рождения, Номер студбилета, а атрибутами объекта ПРЕПОДАВАТЕЛЬ - Фамилия, Имя, Отчество, Дата рождения, Ученая степень,...Отметьте, что наборы атрибутов различных объектов могут пересекаться, но не могут совпадать. Таким образом, мож­но понимать объект как некоторый набор атрибутов.

Набор атрибутов должен быть достаточным для описания объекта в данной предметной области и не должен содержать избыточных атрибу­тов.

Экземпляр объекта описывается конкретным набором значений ат­рибутов. Например, совокупность значений "Иванов", "Виктор", "Леони­дович", "17.05.79", "9443625",... является описанием экземпляра объекта СТУДЕНТ. Такие совокупности называются кортежами. Поскольку кор­теж соответствует экземпляру объекта, можно трактовать объект как мно­жество кортежей.

 

Представление информации об объектах

Для любого объекта существует некоторая совокупность информа­ции, которую можно назвать записью. Отдельные атрибуты образуют поля записи. Совокупность записей об объектах называют набором данных или файлом.

С точки зрения программиста объекту ПО соответствует тип записи. Отдельные атрибуты образуют поля записи.

Между этими категориями существует следующая связь:

• файл соответствует объекту;

• число экземпляров объекта равно числу записей в файле;

• число атрибутов, описывающих объект, равно числу полей в каждой записи.

Каждому полю соответствует имя поля. Поле записи имеет свое зна­чение поля. Значение (содержимое) поля описывает атрибут.

Порядок выполнения работы

 

Описание алгоритма

В пункте необходимо описать алгоритм или несколько алгоритмов, которые используются для решения поставленной задачи. Алгоритм можно описать абстрактным языком или представить в виде блок-схемы.

 

Например, алгоритм сортировки вставками в виде блок-схемы представлен на рис.4.

Этот же алгоритм на абстрактном языке представлен ниже.

Алгоритм сортировки вставками, состоит из 3 простых шагов:
1. Ищем в нашей последовательности данных минимальный элемент.
2. Перемещаем найденный элемент на первое место, остальные элементы сдвигаем вправо.
3. Теперь уже среди N-1 элемента ищем минимальный и проделываем такие же действия.

 

Описание сценария диалога

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

Описание процедур и функций

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

Требования к функциональным характеристикам

 

Проектируемая система должна обеспечивать выполнение следующих основных функций:

- ввод исходных данных задачи;

- расчет параметров;

- оценка стоимости реализации алгоритма по временным и объемным параметрам;

- хранение исходных данных с возможностью их загрузки для повторной обработки;

- хранение результатов решения с возможностью их повторной визуализации;

- вывод результирующих данных;

- хранение исходных данных с возможностью их загрузки для повторной обработки;

- хранение результатов решения с возможностью их повторной визуализации.

 

 

Требования к оформлению пояснительной записки

 

Пояснительная записка должна отражать связь выполненной работы с изучаемым предметом и содержать следующие пункты:

1. Введение.

2. Содержательная постановка и описание задачи.

3. Анализ предметной области.

4. Описание организации структур данных.

5. Описание алгоритма.

6. Формальное описание входных данных.

7. Формальное описание выходных данных.

8. Описание диалога.

9. Описание процедур и функций.

10. Результаты тестирования программы.

11. Заключение.

12. Список литературы.

Кроме этого, в приложение необходимо включить:

1. Графическое описание данных.

2. Формат выходного документа.

3. Листинг программы.

В приложении приведены пример оформления титульного листа.

 

 

 

Тематика курсовых работ

 

1. Применение линейных структур данных при разработке программных приложений:

- применение стеков при разработке приложений;

- применение очередей при разработке приложений;

- применение деков при разработке приложений;

- применение иерархических списков при разработке приложений.

 

2. Применение нелинейных структур данных при разработке программных приложений:

- работа с бинарными деревьями поиска;

- работа со сбалансированными деревьями поиска;

- работа с оптимальными деревьями поиска;

- работа с B-деревьями;

- работа с крупномасштабными деревьями;

- применение бинарных деревьев при решении задачи сжатия информации (алгоритм Хаффмена).

 

3. Организация исчерпывающего поиска:

- применение рекурсии при решении задач поиска;

- применение алгоритмов с возвратом;

- применение метода ветвей и границ;

- применение метода динамического программирования.

 

4. Алгоритмы сортировки:

- алгоритмы внутренней сортировки (вставкой, обменом, выбором);

- алгоритмы быстрой сортировки (метод Шелла, пирамидальная сортировка, сортировка разделением);

- алгоритмы внешней сортировки.

 

5. Алгоритмы решения задач на графах:

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

- алгоритмы решения задач оценки связности графов;

- алгоритмы решения задач нахождения кратчайших путей;

- алгоритмы решения задач нахождения остовных деревьев;

- алгоритмы решения задач упорядочения графов;

- алгоритмы решения задач нахождения циклов в графах.

Список рекомендуемой литературы

 

1. Ахо А., Хопкрофт Дж., Ульман Дж. Структуры данных и алгоритмы. – М.: Вильямс, 2001.

2. Вирт Н. Алгоритмы и структуры данных. – СПб.: Невский диалект, 2001.

3. Кнут Д. Искусство программирования для ЭВМ. Т.1. Основные алгоритмы. – М.: Вильямс, 2000.

4. Кнут Д. Искусство программирования для ЭВМ. Т.1. Получисленные алгоритмы. – М.: Вильямс, 2000.

5. Кнут Д. Искусство программирования для ЭВМ. Т.3. Сортировка и поиск. – М.: Вильямс, 2000.

6. Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: Построение и анализ. М.: МЦНМО, 2001.

7. Баррон Г. Рекурсивные методы в программировании. – М.: Мир, 1974.

8. Гудман С., Хидетниеми С. Введение в разработку и анализ алгоритмов. – М.: Мир, 1981.

9. Макконелл Дж. Анализ алгоритмов: Вводный курс. – М.: Техносфера, 2002.

10. Хусаинов Б. С. Структуры и алгоритмы обработки данных: Примеры на языке Си: Учебное пособие для вузов. – М.: Финансы и статистика, 2004.

 

 

Приложение. Образец формы титульного листа курсовой работы

 

 

Министерство образования РФ

 

ФГБОУ ВПО «Дагестанский государственный технический университет»

Факультет КТВТиЭ

 

Российской федерации

ФГБОУ ВПО

«Дагестанский Государственный Технический

Университет»

Факультет КТВТиЭ

 

Кафедра программного обеспечения ВТ и АС

 

 

Методические указания

к выполнению курсовой работы

по дисциплине

 

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

 

для студентов направления подготовки бакалавров 231000.62 – «Программная инженерия»

 

 

Махачкала - 2014г.

УДК 517.11

 

 

Методические указания к выполнению курсовой работы по дисциплине «Алгоритмы и структуры данных» для студентов направления подготовки бакалавров 231000.62 – «Программная инженерия». Махачкала, ДГТУ, 2014. –14с.

Методические указания предназначены для использования при выполнении курсовой работы по дисциплине «Алгоритмы и структуры данных». Сформулированы цели и задачи, содержание и порядок выполнения проекта, приводится пример оформления проекта.

 

Составитель: Сулейманова О.Ш., старший преподаватель кафедры ПОВТиАС

Шахпазова И.Ф., к.ф.-м.н., старший преподаватель кафедры ПОВТиАС

Рецензенты: Исабекова Т.И., к.ф.-м.н., доцент, зав. кафедры ПМиИ,

Кобзаренко Д.Н., д.т.н., зав.лаборатории информационных технологий в энергетике ФГБУН «Института проблем геотермии ДНЦ РАН»

 

Печатается по постановлению Ученого совета Дагестанского Государственного Технического университета

 

 

Оглавление

 

Цель выполнения курсовой работы.. 4

Теоретические сведения. 4

Порядок выполнения работы.. 6

Требования к функциональным характеристикам. 9

Требования к оформлению пояснительной записки. 10

Тематика курсовых работ. 11

Список рекомендуемой литературы.. 12

Приложение. Образец формы титульного листа курсовой работы.. 13