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



Скачать 94.59 Kb.
Дата05.06.2016
Размер94.59 Kb.
ТипОтчет
Правила выполнения лабораторных работ

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

Задания лабораторных работ выполняются на языке программирования С/С++, среда программирования по выбору студента.

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

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

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

Для зачета по лабораторной работе студенту необходимо представить

         Исходные тексты программ с подробными комментариями;

         Исполняемые файлы;

         Отчет по лабораторной работе.

Отчет должен включать в себя следующие разделы

         Формулировку задания

         Очень краткое описание алгоритмов, используемых в лабораторной работе;

         Результаты работы программы (в виде файла или в виде скриншота);

         Анализ и сравнение полученных результатов с теоретическими оценками.

 

 



Лабораторная работа 1

Тема: Идеально сбалансированное дерево поиска (ИСДП)

 

Цель работы: Изучение процесса программного построения ИСДП.



 

1.    Написать подпрограммы для вычисления характеристик двоичного дерева, которые определяют

       размер дерева;

       высоту дерева;

       среднюю высоту дерева;

       контрольную сумму данных в вершинах дерева;

и проверить их работу на конкретном примере.



2.    Запрограммировать обход двоичного дерева слева направо и вывести на экран получившуюся последовательность данных.

3.    Разработать подпрограмму поиска вершины с заданным ключом в двоичном дереве поиска.

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

5.    Построить ИСДП из 100, 200,…, 500 вершин (данные в вершинах произвольные, но все различные). Распечатать обход дерева слева направо. Для построенных деревьев вычислить размер, контрольную сумму, высоту и среднюю высоту, используя разработанные функции. Заполнить таблицу и проанализировать полученные результаты:

 


Размердерева

ИСДП

Контр.

сумма


Высота

Теор. оценка для средней высоты

Средняя

высота


100

 

 

 

 

200

 

 

 

 

300

 

 

 

 

400

 

 

 

 

500

 

 

 

 

 

 

Лабораторная работа 2



Тема: Случайное дерево поиска (СДП)

 

Цель работы: Изучение процесса программного построения СДП.



 

1.    Разработать подпрограмму построения случайного дерева поиска (СДП).

2.    Построить СДП из 100, 200,…, 500 вершин (данные в вершинах произвольные, но все различные). Распечатать обход дерева слева направо.

3.    Для построенного дерева вычислить размер, контрольную сумму, высоту и среднюю высоту, сравнить их с аналогичными характеристиками ИСДП. ИСДП необходимо строить для той же последовательности данных, что и СДП. Заполнить таблицу и проанализировать полученные результаты:

 


Размердерева

СДП

ИСДП

Контр.

сумма


Высота

Средняя

высота


Контр.

сумма


Высота

Средняя

высота


100

 

 

 

 

 

 

200

 

 

 

 

 

 

300

 

 

 

 

 

 

400

 

 

 

 

 

 

500

 

 

 

 

 

 

 

Лабораторная работа 3

Тема: Сбалансированные по высоте деревья поиска (АВЛ)

 

Цель работы: Изучение процесса программного построения АВЛ-дерева.



 

1.    Разработать подпрограмму построения АВЛ-дерева для массива целых чисел.

2.    Построить АВЛ-дерево из 100, 200,…, 500 вершин (данные в вершинах произвольные, но все различные). Распечатать обход дерева слева направо.

3.    Для построенного АВЛ-дерева вычислить размер, контрольную сумму, высоту и среднюю высоту, сравнить их с аналогичными характеристиками ИСДП. ИСДП необходимо строить для той же последовательности данных, что и АВЛ-дерево. Заполнить таблицу и проанализировать полученные результаты:

 


Размер дерева

АВЛ-дерево

ИСДП

Контр.

сумма


Теор. оценки для сред. высоты

Средняя

высота


Контр.

сумма


Теор. оценки для сред. высоты

Средняя

высота


100

 

 

 

 

 

 

200

 

 

 

 

 

 

300

 

 

 

 

 

 

400

 

 

 

 

 

 

500

 

 

 

 

 

 

 

Лабораторная работа 4

Тема: Двоичное Б-дерево поиска (ДБД)

 

Цель работы: Изучение процесса программного построения ДБД.



 

1.    Разработать подпрограмму построения ДБ-дерева для массива целых чисел

2.    Построить ДБ-дерево из 100, 200,…, 500 вершин (данные в вершинах произвольные, но все различные). Распечатать обход дерева слева направо.

3.    Для построенного ДБ-дерева вычислить размер, контрольную сумму, высоту и среднюю высоту (как для двоичного дерева) и высоту ДБ-дерева как количество уровней, сравнить их с аналогичными характеристиками АВЛ-дерева. ДБ-дерево необходимо строить для той же последовательности данных, что и АВЛ-дерево. Заполнить таблицу и проанализировать полученные результаты:

 


Размердерева

АВЛ-дерево

ДБД

Контр.

сумма


Сред.

высота


Контр.

сумма


Кол-во уровней

Теор. оценки для высоты ДБД

Сред.

высота для дв. дерева.



100

 

 

 

 

 

 

200

 

 

 

 

 

 

300

 

 

 

 

 

 

400

 

 

 

 

 

 

500

 

 

 

 

 

 

 

Лабораторная работа 5

Тема: Дерево оптимального поиска (приближенные алгоритмы)

 

Цель работы: Изучение процесса программного построения почти оптимальных деревьев поиска.



1.    Реализовать программно алгоритмы А1 и А2 для построения почти оптимальных деревьев поиска.

2.    Построить почти оптимальные деревья поиска из 100, 200,…, 500 вершин (данные в вершинах произвольные, но все различные) с помощью алгоритмов А1 и А2, распечатать их обход слева направо.

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

Размердерева

А1

А2

Контр.

сумма


Средне-

взвешенная высота



Контр.

сумма


Средне-

взвешенная высота



100

 

 

 

 

200

 

 

 

 

300

 

 

 

 

400

 

 

 

 

500

 

 

 

 

Каталог: tasks
tasks -> Методические указания по выполнению контрольной работы По дисциплине «Математическое моделирование»
tasks -> Введении дается краткое обоснование тем, указывается ее актуальность и теоретическая значимость; отмечается состояние разработки проблемы в литературе, ставится цель и задачи исследования. В основной части
tasks -> Темы эссе по философии
tasks -> С. Г. Кара-Мурза //Социально-гуманитарные знания. 2000. № С. 21-24. Юревич, А. В. Звёздный час гуманитариев: социогуманитарная наука в современной России /А. В. Юревич //Вопросы философии. 2003
tasks -> Профиль: Музыкальное искусство Задания 2015-2016 уч года Этап: I (заочный)
tasks -> Правила работы в группе: Активное участие каждого школьника. Умение договариваться и выслушивать мнение каждого. Основные требования к работе в группе
tasks -> Контрольное задание №2
tasks -> Расчетная работа №1: в практикуме по статистике (авт. Шмойлова Р. А.), вложенном в пункте «Рекомендуемая литература»
tasks -> Вариант Состав группы


Поделитесь с Вашими друзьями:


База данных защищена авторским правом ©uverenniy.ru 2019
обратиться к администрации

    Главная страница