Лэти аисд экзамен

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

Федеральное
государственное автономное образовательное

учреждение высшего
профессионального образования

«Санкт-Петербургский
государственный электротехнический

университет «ЛЭТИ»
им. В. И. Ульянова (Ленина)»

(СПбГЭТУ «ЛЭТИ»)

Факультет
компьютерных технологий и информатики

Кафедра вычислительной
техники

Отчёт

по лабораторной
работе № 1

на тему:

“Множества”

по дисциплине
“Алгоритмы и структуры данных”

Вариант 19

Выполнили студенты
гр. 4306:

Табаков
А. В.,

Сыромятников
М. А.

Принял: Колинько
П. Г.

Санкт-Петербург
2015

Цель

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

Задание

Множество содержащие все цифры, общие
для AиB, а
также все цифры являющиеся общими дляCиD.

Универсум шестнадцатеричные цифры
(0123456789ABCDEF).

Способы задания множества

1. Последовательность
   символов

2. Список

3. Машинное
   слово

4. Массив
   битов

Контрольные примеры

Контрольные
примеры представлены в таблице 1.

Таблица. 1. Контрольные примеры

№	Исходные множества	Результат
A	B	C	D	E
1	0A23	23C5	2389	2389AB	2389
2	14	14	12	12	124
3	0	01	85	12	0
4	23A	24567CD	12ADEF	01348B	12
5	468ACE	123469CE	0239AC	168ABCDE	46ACE

1. Демонстрация
   работы программы с контрольным примером
   номер 1 из таблицы контрольных примеров.
   Способ представления: последовательность
   символов. Код программы см. приложение
   1.1.

1. Демонстрация
   работы программы с контрольным примером
   номер 2 из таблицы контрольных примеров.
   Способ представления: последовательность
   символов. Код программы см. приложение
   1.1

1. Демонстрация
   работы программы с контрольным примером
   номер 3 из таблицы контрольных примеров.
   Способ представления: список. Код
   программы см. приложение 1.2

1. Демонстрация
   работы программы с контрольным примером
   номер 1 из таблицы контрольных примеров.
   Способ представления: машинное слово.
   Код программы см. приложение 1.3

1. Демонстрация
   работы программы с контрольным примером
   номер 1 из таблицы контрольных примеров.
   Способ представления: массив битов.
   Код программы см. приложение 1.4

Временная сложность

Временная
сложность представлена в таблице 2.

Таблица. 2. Временная сложность

Способ представления	Ожидаемая	Фактическая
Последовательность	O(n^2)	O(n^4)
Список	O(n^2)	O(n^4)
Машинное слово	O(1)	O(1)
Массив битов	O(1)	O(1)

Результаты измерения времени обработки

Результаты
измерения времени обработки представлены
в таблице 3.

Таблица. 3. Результаты измерения времени
обработки

Способ представления	Количество тиков	Количество повторов цикла	Зависимость от количества в множестве
Последовательность	4321-15027	1000000	есть
Список	3246-14277	есть
Машинное слово	2-3	нет
Массив битов	600-750	нет

Вывод:
Машинное слово самый быстрый из
способов формирования множества, т.к.
данный способ не зависит от количества
элементов в множестве.

Классы и объекты

Использование
классов и объектов представлено в
приложении 1.4.

Вывод:
Использование классов и объектов
облегчают понимание программы. Дают
возможность защиты переменных от
несанкционированного изменения.

Результаты решения задачи

При выполнении программы были получены
результаты, совпадающие со значениями,
приведенными в таблице 1. Ошибок не
обнаружено.

Вывод

При выполнении лабораторной работы
были получены практические навыки
работы c
с логическими операциями над
множествами на языке
программирования «С/C++».

Соседние файлы в предмете [НЕСОРТИРОВАННОЕ]

• #
• #
• #
• #
• #
• #
• #
• #
• #
• #
• #

Расписания занятий и экзаменов

  Уважаемые студенты! Занятия, выделенные красным цветом (номера аудиторий, начинающиеся с цифры 6), проводятся в 6 корпусе по адресу: ул. Профессора Попова, дом 37Б.

---

---

Подборка по базе: Методические указания 2-3.docx, Теоретические и методические основы организации продуктивных вид, Методические указания (КР, КП).DOC, Методические указания к ВКР (3).docx, Требования к оформлению и общие методические указания по выполне, ТЕМА 1 Теоретический материал, методические указания для обучающ, Метод указания по курсовой работе ОП 05 ДО.pdf, Методические указания. Тема 1.doc, Методические указания для выполнения практических работ по элект, Методические указания по изучению курса.pdf

---

МИНОБРНАУКИ РОССИИ

–––––––——————————–––––––

Санкт-Петербургский государственный
электротехнический университет «ЛЭТИ»

————————————————————

АЛГОРИТМЫ И СТРУКТУРЫ ДАННЫХ

Методические указания к лабораторным работам,
практическим занятиям
и курсовому проектированию

Санкт-Петербург
Издательство СПбГЭТУ «ЛЭТИ»
2013

УДК 004.424:004.422.63(075.8)
Алгоритмы и структуры данных: методические указания к лабораторным работам, практическим занятиям и курсовому проектированию. Федеральный образовательный стандарт / сост.: П. Г. Колинько. –– СПб.: Изд-во СПбГЭТУ «ЛЭТИ», 2013. — 64 с.

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

Пособие предназначено для студентов бакалавриата по направлению 230100.62 «Информатика и вычислительная техника» дневной, очно-заочной и заочной форм обучения.

Утверждено
редакционно-издательским советом университета
в качестве методических указаний

© П. Г. Колинько, 2012–2014 (0127)

© СПбГЭТУ «ЛЭТИ», 2013

ВВЕДЕНИЕ

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

Методические указания покрывают первый семестр двухсеместрового курса «Алгоритмы и структуры данных» и состоит из трёх разделов. Тема первого раздела «Множества» является вводной. В ней показывается, что абстрактные данные могут быть реализованы в программе разными способами и что от способа реализации зависит существенная характеристика алгоритма — его временная сложность. Вводится понятие объекта как естественного расширения языка С++ для поддержки пользовательских типов данных.

Изучение темы разбито на этапы по схеме от простого — к сложному. На усмотрение преподавателя — объединить некоторые этапы для сильных студентов или ограничиться их частью для слабых. Практические занятия состоят в изучении учебных примеров, имеющихся в пособии или прилагаемых к нему, а также в постановке опытов с программным кодом и исследовании алгоритмов.

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

Третья тема «Графы» выносится на курсовое проектирование для закрепления навыков, полученных при изучении двух первых тем.

Объём теоретических сведений об абстрактных данных и алгоритмах в методических указаниях минимален. Предполагается, что студенты могут взять недостающее из параллельно изучаемого курса «Дискретная математика», а также из рекомендованной литературы.

Предполагается, что студенты уже знакомы с такими элементарными структурами данных, как массивы, списки, очереди и стеки.

Все примеры проверены в оболочке Visual C++ 2012, используемой в учебном процессе СПбГЭТУ «ЛЭТИ». В более ранних оболочках, например, в Borland C++ 3.1, они могут быть потребовать небольшой модификации.

В частности, может потребоваться исключить предложение «using namespace std», добавить определение enum bool {false, true}, заменить «надёжные» функции _getch( ), gets_s( ) их классическими аналогами getch( ), gets( ) и т. п.

Для самостоятельной работы могут быть использованы любые доступные программные оболочки С++, поддерживающие по крайней мере стандарт C++98: Borland C++ Builder 6.0, Microsoft Visual С++ 2005 и более современные, в том числе свободно распространяемые компиляторы (DEV C++ и т. п.), а также компиляторы в ОС Linux.

Множество — абстрактная структура данных, для которой определена операция принадлежности. Новые множества создаются из существующих с помощью операций объединения, пересечения, разности, симметрической разности.