Вопросы для самопроверки

1.4 Вопросы для самопроверки

1) Какими свойствами обладает отношение частичного порядка? Приведите примеры этого отношения.

2) Дайте определение отношения линейного порядка.

3) Сформулируйте постановку задачи сортировки.

4) В чём заключается преимущество отсортированных (упорядоченных) данных?

5) Как рассматривается задача сортировки с точки зрения программирования?

6) От каких факторов зависит эффективность алгоритма сортировки?

7) Перечислите наиболее часто используемые на практике методы поиска и сортировки.

8) Каким образом могут быть представлены данные при поиске и сортировке?

9) Перечислите основные операции при работе с данными.

10) В чём заключается алгоритм линейного поиска?

11) В чём заключается алгоритм бинарного поиска?

12) Опишите кратко поиск в бинарных деревьях.

13) Какие функции используются при оценке времени исполнения алгоритма?

14) В чём заключается метод сортировки вставками?

15) В чём заключается метод сортировки с помощью включения, прямого включения?

16) В чём заключается метод Шелла?

17) Опишите сортировку с помощью обменов.

18) Опишите алгоритм быстрой сортировки, предложенный Ч. Хоаром (QuickSort).

Практическая работа № 2. Представление множеств в компьютере

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

2.1 Теоретическая часть

2.1.1 Множества и операции над ними

Множество – это совокупность объектов, называемых элементами множества. Например:

• {Эссекс, Йоркшир, Девон};

• {2, 3, 5, 7, 11}.

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

S = {3, 2, 11, 5, 7} – множество, содержащее целые числа. Заметим, что множество S совпадает с одним из множеств, выписанных выше, поскольку порядок, в котором записываются элементы множества, значения не имеет.

В общем случае запись аS означает, что объект а – элемент множества S. Часто говорят, что а принадлежит множеству S. Если объект а не принадлежит S, то пишут: а S.

В современных языках программирования требуется, чтобы переменные объявлялись как принадлежащие к определенному типу данных. Тип данных представляет собой множество объектов со списком стандартных операций над ними. Определение типа переменных равносильно указанию множества, из которого переменным присваиваются значения [22].

Существует несколько способов конструирования нового множества из двух данных. Опишем коротко эти операции на множествах. Прежде всего, отметим, что все элементы некоторых множеств принадлежали другим большим множествам. Например, все элементы множества С = {0, 1, 4, 9, 16,…} содержатся в множестве

Z = {0, ±1, ±2, ±3,…}.

Рисунок 2.1 – Диаграмма Венна подмножества А S

Объединением двух множеств А и В называется множество

АВ = {х: х  А или х  В}.

Оно состоит из тех элементов, которые принадлежат либо множеству A, либо множеству В, а возможно и обоим сразу. Диаграмма Венна объединения показана на рисунке 2.2.

Пересечением двух множеств А и В называется множество

А  В = {х: х  А и х В}.

Оно состоит из элементов, которые принадлежат как множеству А, так и множеству B. Диаграмма Венна пересечения приведена на рисунке 2.3.

Рисунок 2.2 – Диаграмма Венна Рисунок 2.3 – Диаграмма Венна для объединения множеств для пересечения множеств

Дополнением множества В до множества А называется

A\В = {х: х  А и x В}.

Дополнение А \ В состоит из всех элементов множества А, которые не принадлежат В (см. рисунок 2.4). Если мы оперируем подмножествами некоего большого множества U, мы называем U универсальным множеством для данной задачи. На наших диаграммах Венна прямоугольник как раз и символизирует это универсальное множество. Для подмножества А универсального множества U можно рассматривать дополнение А до U, т. е. U \ А. Поскольку в каждой конкретной задаче универсальное множество фиксировано, множество U \ А обычно обозначают  и называют просто дополнением множества А. Таким образом, понимая, что мы работаем с подмножествами универсального множества U можно записать

 = {х: не (х А)} ó  = {х: х  A}.

Диаграмма Венна дополнения изображена на рисунке 2.5.

Симметрической разностью двух множеств А и В называют множество А Δ В = {х: (х  А и х  В) или (х  В и х  А)}.

Оно состоит из всех тех и только тех элементов универсального множества, которые либо принадлежат А и не принадлежат В, либо наоборот, принадлежат В, но не А. Грубо говоря, симметрическая разность состоит из элементов, лежащих либо в А, либо в В, но не одновременно. Диаграмма Венна, иллюстрирующая симметрическую разность, начерчена на рисунке 2.6.

Рисунок 2.6 – Диаграмма Венна симметрической разности А Δ В

Похожие работы

Дискретная математика

Скачать

11313

1

5

... Е и множество и мы рассматриваем все его подмножества, то множество Е называется униварсельным. Пример: Если за Е взять множество книг то его подмножества: художественные книги, книги по математике, физики, физики … Если универсальное множество состоит из n элементов, то число подмножеств = 2n. Если , состоящее из элементов E, не принадлежащих А, называется дополненным. Множество можно задать: ...

Конспект по дискретной математики

Скачать

6003

0

1

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

Решение практических заданий по дискретной математике

Скачать

14778

4

22

... которой были разработаны в последней четверти 19 века Георгом Кантором. Цель контрольной работы – ознакомится с основными понятиями и методами решения по дискретной математике, уметь применить полученные знания при решении практического задания. Задание 1 Представить с помощью кругов Эйлера множественное выражение . Используя законы и свойства алгебры множеств, упростить заданное ...

Применение методов дискретной математики в экономике

Скачать

34329

6

25

элементы теории нечетких множеств можно применять для решения экономических задач в условиях неопределённости. 1. применение Логических функций   1.1 Применение методов дискретной математики в экономике   При исследовании, анализе и решении управленческих проблем, моделировании объектов исследования и анализа широко используются методы формализированного представления, являющегося предметом ...