Итоговое повторение темы 1. Контрольная работа № 1.

1. Основные вопросы.

1. Что называется объединением, пересечением, разностью, симметрической разностью множеств, дополнением множества?

2. Что такое инъективное, сюръективное, биективное отображение (с примерами)?

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

4. Что такое правило произведения (с примером)?

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

6. Что такое сочетания и что Вы знаете о числе сочетаний (с примером)?

7. Что такое размещения и что Вы знаете о числе размещений (с примером)?

8. Что такое перестановки с повторениями и что Вы знаете об их числе (с примером)?

9.Что такое рефлексивное, симметричное, транзитивное отношение, отношение эквивалентности и каково его основное свойство?

10. Что такое рефлексивное, симметричное, транзитивное отношение, отношение эквивалентности и каково его основное свойство?

11. Что такое отношение нестрогого порядка, строгого порядка?

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

Вариант 0

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

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

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

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

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

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

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

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)}.

Тема 2. Основы теории графов

Раздел 6 «Основные понятия теории графов».

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

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

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

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

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

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

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

2. Задачи для усвоения материала.

1. Представить карту бывшего СССР в виде плоского графа (вершины – республики, ребра - границы).

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

3. Двое играют в игру "ним". Имеется две кучки по 2 спички в каждой. Игрок может взять любое (ненулевое) число спичек, но только из одной (по его выбору) кучки. Игрок, забравший последнюю спичку, проигрывает. Требуется:

а) изобразить игру в виде орграфа (вершины – позиции, дуги – все ходы);

б) разработать оптимальную стратегию игры, анализируя пути из исходной позиции выигрышной. Кто выигрывает при правильной игре обоих?

4. То же, если в одной кучке 2 спички, а в другой 3 спички.

5. То же, если в обеих кучках по 3 спички.

6. То же, если всего три кучки: в первой 1 спичка, во второй – 2 спички, а в третьей 3 спички.

7. Двое играют в следующую игру. Первый пишет любую из цифр 1,2 или 3, второй приписывает справа любую из этих же цифр, первый приписывает справа любую из этих же цифр. Если полученное трехзначное число – простое, то выигрывает первый игрок, если составное – то второй игрок.

а) изобразить игру в виде орграфа (вершины – позиции, дуги – все ходы);

б) разработать оптимальную стратегию игры, анализируя пути из исходной позиции выигрышной. Кто выигрывает при правильной игре обоих?