АИСД (1 семестр) на c# / Лабораторная1
.docxМИНОБРНАУКИ РОССИИ
Санкт-Петербургский государственный
электротехнический университет
«ЛЭТИ» им. В.И. Ульянова (Ленина)
отчет
по лабораторной работе №1
по дисциплине «Алгоритмы и структуры данных»
Тема: Множества
Студенты гр. |
|
|
Преподаватель |
|
|
Санкт-Петербург
2022
Цель работы исследование четырех способов хранения множеств в памяти ЭВМ.
Задание:
Cоставить и отдалить программу, реализующую обработку множеств по предложенному заданию:
Вариант 2: Прописные латинские буквы. Множество, содержащее все символы из множества А, за исключением символов, содержащихся в В или С, а также все символы множества D.
Язык программирования:
В данной работе используется С# так как:
В C# управление памятью происходит автоматически. Не нужно вручную выделять и освобождать память для объектов до и после завершения задачи. А так же использовать указатели. Благодаря этому увеличивается скорость разработки приложения и улучшается читаемость кода.
Ход работы
Временная сложность
Тип представления данных |
Ожидаемая временная сложность |
Фактическая временная сложность
|
Массив элементов |
O( |
O( ) |
Список |
O( ) |
O( ) |
Машинное слово |
O(1) |
O(n) |
Массив битов |
O(n) |
O(n) |
)
В данной таблице приведено среднее временя обработки множеств каждым способом для 5 испытаний.
Исходные данные |
Время обработки |
|||
Массив элементов |
Список |
Машинное слово |
Массив битов |
|
A:{A}; B:{A}; C:{E}; D:{C} |
1.7 ms |
0.73 ms |
0.66 ms |
0.96 ms |
A:{A,B,C}; B:{S,B,M}; С:{T,Y,A}; D:{U,I,K} |
1.84 ms |
1.15 ms
|
0.94 ms |
1.28 ms |
A:{A,B,C,D,E,F} B:{M,N,A,C,E,R} C:{F,K,L,P,O,N} D:{D,F,G,H,J,K} |
1.96 ms |
1.374 ms |
1.26 ms |
1.3 ms |
A:{A,B,C,D,E,F,G,O,P,Q} B:{M,N,U,Y,E,T,W,R,H,N} C:{F,G,L,K,M,P,W,Q,A,Z} D:{P,O,R,T,Y,H,Y,U,D,F} |
2.32 ms |
1.9 ms |
1.9 ms |
2.2 ms |
Для каждого способа обработки наблюдается зависимость времени обработки от размера данных.
Выводы о результатах испытания:
1) Самый эффективный способ обработки машинное слово.
2) Самый неэффективный способ по времени работы – массив элементов.
Контрольные тесты:
Сначала пользователю предоставляется выбор каким образом будет созданы множества.
d – пользователь самостоятельно вводит все символы множеств.
а – программа самостоятельно рандомно генерирует множества символов.
Для ввода или генерации доступны все прописные латинские буквы.
Когда будут созданы необходимые данные, программа вновь предложит выбор, на этот раз каким способом будут обработаны созданные множества:
Массивом
Списком
Машинным словом
Массивом битов
Для выбора пользователю необходимо ввести номер, соответствующий списку выше.
После этого программа производит обработку введенных множеств выбранным способом и выводит результат вычисления пятого множества.
После произведенных вычислений пользователь может продолжить работу в программе и с помощью ввода команды «y» перейти обратно к выбору способов обработки.
На предоставленном скриншоте продемонстрирован тест программы, в котором пользователь выбрал автоматическую генерацию множеств, а затем попробовал обработать их каждым из способов вычисления пятого множества. Во всех случаях программа вывела одинаковый результат пятого множества. Однако время обработки множеств разными способами оказалось тоже отличным друг от друга.
Список использованных источников
Колинько, П. Г. Пользовательские структуры данных: Методические указания по дисциплине “Алгоритмы и структуры данных, часть 1”.– СПБ.: СПБГЭТУ “ЛЭТИ”, 2022. – 64 с.
Приложение. Код программы:
Вывод: в ходе работы была написана программа, которая производит вычисления, по указанной формуле, над четырьмя заданными множествами и выводит на экран пятое множество. Множества представляются в форме массива, списка, машинного слова и массива битов. Результаты измерения времени обработки каждым способом занесены в таблицу. В ходе анализа данной таблицы был сделан вывод о том, что самый эффективный способ обработки множества - машинное слово, неэффективный - массив.