Тема 1 Основы теории множеств и комбинаторики.

Тема 1 Основы теории множеств и комбинаторики.

Раздел 1, «Операции над множествами»

I. Необходимые определения и формулировки теорем.

1. Назовите синонимы слова «множество».

2. Что такое «элемент множества»?

3. Что означает фраза «Множество А является подмножеством множества В»?

4. Что такое «пустое множество»?

5. Какие два множества называются равными?

6. Когда два множества равны? (поясните суть метода включений)

7. Какие операции на множествах существуют?

8. Что такое «объединение множеств»?

9. Что такое «пересечение множеств»?

10. Что такое «разность множеств А и В»?

11. Что такое «универсальное множество»?

12. Что такое «диаграммы Эйлера-Венна» и для чего они используются?

13. Поясните понятие «симметрическая разность множеств» и проиллюстрируйте его на диаграмме Эйлера-Венна.

14. Поясните понятие «дополнение множества до универсального» и проиллюстрируйте его на диаграмме Эйлера-Венна.

III. Самостоятельная работа.

Вариант 0

1) Задано множество U={1,3,5,7}

а) Выписать все его подмножества.

б) Выписать все элементы множества , где

2) Изобразить множества:

a) . Не понимаю смысл задачи.

3) Проиллюстрировать на диаграмме Эйлера-Венна множество

.

4) Проиллюстрировать на диаграммах Эйлера-Венна и доказать методом включений тождество:

Раздел 2

«Декартово произведение множеств. Отображения множеств»

I. Необходимые определения и формулировки теорем.

1. Что такое «декартово произведение множеств А и В»?

2. Что такое «отображение множеств»?

3. Что такое «однозначное отображение множеств»?

4. Что такое «многозначное отображение множеств»?

5. Как вы понимаете термин «образ элемента»?

6. Как вы понимаете термин «образ множества»?

7. Как вы понимаете термин «прообраз элемента»?

8. Как вы понимаете термин «прообраз множества»?

9. Какое отображение называется сюръективным?

10. Какое отображение называется инъективным?

11. Какое отображение называется биективным?

Раздел 3

«Основы комбинаторики»

I. Самостоятельная работа. Ну да, здесь она не смотрится

Вариант 0

1) Задано отображение f: R R,

a) Найти образ отрезка

b) Найти прообраз отрезка

c) Определить, является ли отображение инъективным.

d) Определить, является ли отображение сюръективным.

e) Определить, является ли отображение биективным.

2) Задано отображение f: R R,

a) Определить, является ли отображение инъективным.

b) Определить, является ли отображение сюръективным.

c) Определить, является ли отображение биективным

3) Составить декартово произведение множеств , если .

4) Изобразить на координатной плоскости множество

.

II. Необходимые определения и формулировки теорем.

1. Что изучает комбинаторика?

2. Сформулируйте правило произведения.

3. Что такое перестановки?

4. Что Вы знаете о числе перестановок?

5. Что такое сочетания?

6. Что Вы знаете о числе сочетаний?

7. Что такое размещения?

8. Что Вы знаете о числе размещений?

9. Что такое перестановки с повторениями?

10. Что Вы знаете о числе перестановок с повторениями?

Раздел 4

«Мощность множеств»

I. Необходимые определения и формулировки теорем.

1. Что такое мощность множества?

2. Как связаны мощность множества и биекция?

3. Сформулируйте «правило произведения» (чему равна мощность декартового произведения двух множеств?)

4. Что Вы знаете о мощности множества всех подмножеств данного множества?

5. Что такое ?

6. Что Вы знаете о мощности множества двоичных наборов?

7. Что Вы знаете о мощности объединения двух множеств?

8. Верно ли, что мощность объединения двух множеств равна сумме их мощностей? В каких случаях это верно?

9. Что Вы знаете о мощности разности множеств А и В?

10. Верно ли, что мощность разности двух множеств равна разности их мощностей? В каких случаях это верно?

11. Существует ли общая формула для нахождения мощности пересечения множеств?

12. Верно ли, что мощность пересечения двух множеств равна произведению их мощностей? В каких случаях это верно?

Раздел 5

«Отношения на множестве»

I. Самостоятельная работа. Тоже здесь не смотрится

Вариант 0

1. Сколько четырёхзначных чисел с различными цифрами можно составить из цифр 2,3,5,7,8,9?

2. Найти мощность множества всех двухбуквенных слов, составленных из букв л, е, с, к, а

3. В соревнованиях по бегу принимают участие 10 студентов. Сколькими способами могут быть распределены первое и второе места между участниками?

4. Используя теорию множеств решить задачу:

Из 100 учеников гимнастикой занимается 28 человек, волейболом – 42, плаванием – 30, гимнастикой и волейболом занимается 10 человек, гимнастикой и плаванием – 8, волейболом и плаванием – 5. Всеми тремя видами спорта занимается 3 ученика. Сколько учеников не занимается спортом?

II. Необходимые определения и формулировки теорем.

1. что такое отношение на множестве?

2. Какие виды отношений на множестве Вы знаете?

3. Какое отношение называется рефлексивным?

4. Какое отношение называется антирефлексивным?

5. Какое отношение называется симметричным?

6. Какое отношение называется асимметричным?

7. Какое отношение называется антисимметричным?

8. Какое отношение называется транзитивным?

9. Что такое «отношение эквивалентности»?

10. Сформулируйте основное свойство отношения эквивалентности.

11. Что такое «отношение порядка»?

12. Что такое «отношение строгого порядка»?

13. Что такое «отношение нестрогого порядка»?

14. Какое множество называется вполне упорядоченным?

15. Какое множество называется частично упорядоченным?

16. Что такое цепь?

II. Контрольная работа.

Вариант 0

1. Вопрос по теории (один из экзаменационных по теме 1).

2. Даны множества A={2,3,c}, B={3,4,c,d}.

Найти и их мощности.

3. Задано отображение f: R R,

a) Определить, является ли отображение инъективным.

b) Определить, является ли отображение сюръективным.

c) Определить, является ли отображение биективным

4. Найти мощность множества всех двухбуквенных слов, составленных из букв т,а,ч,к,а

5. Сколько различных пятизначных чисел можно составить из цифр 3,5,6,7,9? А сколько четырехзначных чисел?

6. Имеются буквы А,Б,В,Г,Д и цифры 2,3,4,5. Из них надо составить пароль, в котором три различные буквы и две (не обязательно различные) цифры. Сколько различных паролей можно составить?

7. Сколько различных чисел можно составить, используя все таблички с цифрами 1,1,1,2,2,3,3,3,3?

8. Выяснить, является ли отношение Г на множестве A отношением эквивалентности: A={2,3,7}, Г={(2,7), (7,2), (7,7)}.

Раздел 6

«Основные понятия теории графов».

I. Необходимые определения и формулировки теорем.

1. Что такое «орграф»?

2. Что такое «граф»?

3. Для каких объектов применимы термины: «вершина», «дуга», «ребро» «путь», «цепь», «контур», «цикл»?

4. Что такое «вершина», «дуга», «ребро»?

5. Что такое «путь», «цепь»?

6. Что такое «контур», «цикл»?

Раздел 7.

«Поиск путей в графе».

I. Необходимые определения и формулировки теорем.

1. Что такое «вес дуги (ребра)»?

2. Какой граф называется взвешенным?

3. Каков алгоритм решения задачи о кратчайшем пути в невзвешенном графе?

4. Каков алгоритм решения задачи о кратчайшем пути во взвешенном графе?

Раздел 8.

«Эйлерова цепь (цикл). Формула Эйлера.

Плоские и планарные графы»

I. Необходимые определения и формулировки теорем.

1. Что такое эйлерова цепь?

2. Что такое эйлеров цикл?

3. У каких графов существует эйлерова цепь?

4. У каких графов существует эйлеров цикл?

5. В чем состоит формула Эйлера?

6. Для каких объектов верна формула Эйлера?

7. Как выглядят непланарные графы № 1, № 2, типов 1, 2?

8. В чем состоит теорема Куратовского-Понтрягина?

 

Раздел 9.

«Раскраски графа».

I. Необходимые определения и формулировки теорем.

1. В чем состоит задача о раскраске вершин графа?

2. Каков алгоритм решения задачи о раскраске графа?

3. В чем состоит задача о раскраске ребер графа?

4. Что Вы знаете о хроматическом индексе?

II. Контрольная работа.

Вариант 0

1. Вопрос по теории.

2. Обладает ли эйлеровой цепью (или эйлеровым циклом) следующий граф?

 

3. Является ли данный граф плоским? (планарным)

 

4. Считая данный граф планарным, определить количество его граней.

 

 

5. Дан граф:

 

Найти кратчайший путь из точки в точку В (в смысле наименьшего количества рёбер).

6. Дан граф.

B

A

а) Превратить его во взвешенный, используя следующие данные

б) Найти кратчайший путь из точки в точку В (в смысле наименьшей суммы весов).

7. Найти хроматическое число графа

 

Раздел 10.

«Матрицы смежности и инццдентности. Код Харари».

I. Необходимые определения и формулировки теорем.

1. Что такое матрица смежности орграфа?

2. Каким свойством обладает матрица смежности неориентированного графа?

3. Что такое матрица инцидентности оргрфа?

4. Как строится код Харари?

5. Какая нумерация вершин графа считается канонической?

Раздел 11.

Раздел 12.

«Префиксный код. Код Прюфера

Обход бинарного ордерева.»

I. Необходимые определения и формулировки теорем.

1. Как строится префиксный код бинарного ордерева?

2. Как строится код Прюфера?

3. Какие три способа обхода бинарного ордерева Вы знаете?

E h j k