Вопросы к экзамену по дискретной математике

1. Предмет дискретной математики. Множества, способы их задания. Операции над множествами. Диаграммы Вена. Примеры.
2. Отношения на множествах. Унарные и бинарные отношения. Основные свойства бинарных отношений. Примеры.
3. Отношения эквивалентности и порядка на множествах. Примеры.
4. Булевы функции, табличное их задание, задание в векторной форме. Число БФ от n переменных.
5. Существенность переменных БФ. Критерий существенности. Равенство БФ. Примеры.
6. Аналитическое представление БФ, операция суперпозиции. Представимость над множеством БФ.
7. Понятие логической формулы. Строгое определение класса ЛФ на языке БНФ.
8. Интерпретация логических формул. Подформулы, суперпозиция формул. Соответствие между классом ЛФ и классом БФ.
9. Отношение двойственности на множестве БФ. Самодвойственность БФ. Примеры.
10. Строение, равенство и двойственность ЛФ. Принцип двойственности. Примеры.
11. Теорема о разложении Бф по её переменным.
12. Понятие о СДНФ и СКНФ. Разложение функции в СДНФ.
13. Понятие о полноте классов БФ. Примеры полных и неполных классов. Полнота класса {or, and, not}.
14. Теорема о сводимости и её применение для доказательства полноты систем {not, or}, {not, and}, {0, ->}. Полнота систем «штрих Шеффера» и «стрелка Пирса».
15. Полнота системы {+, ., 1}. Разложение БФ в полином Жегалкина.
16. Два способа построения полиномов Жегалкина. Примеры.
17. Замыкание классов БФ, свойства замыкания. Понятие о замкнутых классах. Примеры.
18. Эталонные классы Т0 и Т1, их замкнутость и число принадлежащих им n-арных функций.
19. Эталонный класс S, его замкнутость и число принадлежащих ему n-арных функций.
20. Отношение предшествования двоичных наборов длины n. Эталонные классы M и L. Примеры.
21. Леммы о несамодвойственной (с доказательством) и о немонотонной функциях.
22. Лемма о нелинейной БФ (с доказательством).
23. Теорема Поста о полноте. Доказательство необходимого условия. Применение теоремы.
24. Теорема Поста о полноте. Доказательство достаточного условия. Предполные классы.
25. Схемы из функциональных элементов (оr, and, not). Проектирование и реализация одноразрядного двоичного сумматора.
26. Построение функциональной схемы n-разрядного двоичного сумматора. Элементы задержки и примеры их использования.
27. Понятие о релейно-контактных схемах. РКС -реализация функциональных элементов. Примеры.
28. Понятие о графах и орграфах. Смежность (вершин, рёбер), инцидентность (вершин и рёбер). Степени вершин. Маршруты, цепи, простые цепи, циклы. Примеры.
29. Матрицы смежностей и их реализация в языках программирования. Примеры.
30. Компьютерное представление графов списками смежностей. Примеры.
31. Подграфы. Изоморфизм и гомеоморфизм графов. Примеры.
32. Планарность графов. Графы Куратовского K 5 и K 3,3. Теорема Куратовского о планарности.
33. Связность графов и орграфов – определения, примеры. Компоненты связности.
34. Алгоритм обхода связного графа. Две основные стратегии обхода.
35. Алгоритм выявления компонент связности графа.
36. Деревья, корневые деревья. Бинарное кодирование корневых деревьев. БНФ-определение класса бинарных кодов корневых деревьев.
37. Понятие о двухполюсных транспортных сетях и их практическом использовании. Потоки в сетях, дивергенция.
38. Мощность потока в сети. Полные и максимальные потоки. Неформальный алгоритм построения полного потока. Пример.
39. Аугментальные цепи. Общая идея и пример построения максимального потока в сети.
40. Понятие о кодировании информации и основных разделах теории кодирования.

Спасибо, со списком вопросов

Спасибо, со списком вопросов удобней готовиться

Добрый день, Валерий

Добрый день, Валерий Шахамболетович! А экзамен по дискретной математике 11 или 12?

Для ПМ я не уточнял, у ИС во

Для ПМ я не уточнял, у ИС (они первые) во вторник.

Спасибо, Валерий

Спасибо, Валерий Шахамболетович. А кто считается допущенным к экзамену?

Допущены с баллом 26 и более.

Допущены с баллом 26 и более.

Здравствуйте

Здравствуйте Валерий Шахамболетович а подготовка 10-го числа будет проведена?(у ИС), если да, то во сколько?

Добрый вечер

дада, группе ИС хотелось бы узнать, во сколько будет консультация по дискретной математике?

ааа, прошу прощения, не

ааа, прошу прощения, не увидел , что выше написано время!15:00

Добрый день Валерий

Добрый день Валерий Шахамболетович, можно узнать у Вас, когда на сайте будут вопросы к экзамену по ИП? Спасибо.

Добрый вечер, Валерий

Добрый вечер, Валерий Шахамболетович! А во сколько завтра консультация у 1ПМ?

да тут у 1ИС завтра экзамен,

да тут у 1ИС завтра экзамен, мы вопросов еще не знаем, а вы тут со своими консультациями...

Поддерживаю!:(

Поддерживаю!:(

и я присоединяюсь!

и я присоединяюсь!

Списка вопросов не будет

1. Списка экзаменационных вопросов не будет. Никто из Вас о нём не позаботился - не предоставил конспекта лекций.
2. Консультация идёт полным ходом (отвечаю на предметные вопросы on-line и сегодня и завтра) - можете спрашивать...

будет ли практика с объектами

будет ли практика с объектами (описание, использование) ?

Кто-нибудь знает во сколько

Кто-нибудь знает во сколько экзамен?

Да, нужно уметь реализовать

Да, нужно уметь реализовать объектовый тип и использовать в решении задачи. Разберитесь с задачей о реверсе последовательности.

Экзамен в начале десятого.

Пересдача!

Валерий Шахамболетович можно узнать результаты пересдачи по ДМ? Заранее спасибо!

ДМ-Пересдача 1 - результаты

Из 20 возможных баллов:
1. Немыкин В. - 0
2. Пецура Д. - 14
3. Бедненко С. - 3
4. Четыз Т. - 0
5. Мерчалов А. - 1
6. Ведлер А. - 9
7. Артемьев М. - 8
8. Черевань Р. - 1
9. Ешану А. - 4
10. Тюльпаров Х. - 9
11. Хафизов Д. - 9
12. Гостев Б. - 0
Сдавшие, если они есть, выявятся только в понедельник.

Валерий Шахамболетович кто

Валерий Шахамболетович кто сдал неизвестно?

Добрый вечер В.Ш. можно

Добрый вечер В.Ш. можно узнать сдал я или нет? Вы говорили придете сегодня в университет специально чтобы взять ведомости

Далер и др.

Моё молчание объясняется просто - по набранным за прошлый семестр и за пересдачу баллам не проходит никто!
Обратите внимание - ПЕРЕСДАЧА экзамена, это не то же самое, что его ДОСДАЧА. Поэтому, я не склонен суммировать сюда же баллы за летний экзамен.
Одним словом, готовьтесь все - у нас будет ещё одна встреча до решения о повторке (это касается и дискретки и программирования).

Спасибо за информацию, если

Спасибо за информацию, если не ошибаюсь вроде баллы за семестр, экзамен и 2 пересдачи суммируются, по другим предметам у нас так, когда у нас примерно будет пересдача?
P.S: Почему остальные молчите, как будто вам это не надо

Далер

Некому не безразлично у некоторых эти 2 предмета решают все но кураторы говорили что препадователь вправе оценивать по своей системе так что стоит попробовать ещё раз другого выхода невижу !

Вопрос

Добрый вечер. Не совсем понятно построение функциональной схемы n-разрядного двоичного сумматора и не могу разобраться с алгоритмом построения полного потока в сети.

Давайте попорядку...

1. Понятна ли работа 1-разрядного сумматора?

да, понятна

да, понятна

Если разрядов n, то

Если разрядов n, то 1-разрядный сум-р работает в каждом из них. Правда складывает он не только "cвои" разряды суммируемых чисел, а прибавляет к ним ещё и разряд переноса справа (возможно нулевой). А ещё, сформировав сумму (2-значное двоичное число) он отправляет левый (старший) её разряд на вход соседнему слева одноразрядному сумматору. Если не поняли, задайте вопрос КОНКРЕТНЕЙ - что именно не понятно.

2. Я описал словесный

2. Я описал словесный алгоритм построения полного потока. Какой шаг не понятен?
Ведь суть проста - поэтапно насыщаем имеющие резерв орцепи, ведущие от истока к стоку. Каждое такое насыщение увеличивает общий поток. на своё дельта. Как только очередная орцепь насытилась, исключаем из неё насыщенные рёбра - через них дальнейшего прирощения уже не получить.
Снова жду УТОЧНЕНИЯ Вашего вопроса, если не понятно.

Спасибо, более менее

Спасибо, более менее разобралась...

Вопрос

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

Укажите то, которое считаете

Укажите то, которое считаете самым неочевидным.

св-ва замыканий

пожалуй 3. что [F] в объединении с [G] является подмножеством [F в объединении с G]

Итак, утверждаем, что [F

Итак, утверждаем, что [F ]+[G] <= [F + G].
1. Т. к. F и G вместе со своими ВНУТРЕННИМИ комбинациями ф-ций входят и в левую и в правую часть делает очевидным то, что левая часть включена в правую.
2. Но правая часть может быть шире чем левая, т.к. в ней возможны ещё и ПЕРЕКРЁСТНЫЕ комбинации ф-ций множеств F и G.

Вот тривиальный пример: F={not X}, G={Y and Z}.
Тогда [F] = {X, not X}, [G]= все ф-ции вида X1 and X2 and ... and Xn
[F ]+[G]={X, not X, все ф-ции вида X1 and X2 and ... and Xn}
[F + G] =[{not, and}] - все БФ, т.к. класс {not, and} полон.

Можете напомнить что такое

Можете напомнить что такое суперпозиция?

Добрый вечер. Скажите

Добрый вечер. Скажите пожалуйста во сколько будет экзамен у ИС? сразу две группы будут сдавать?

Суперпозиция - это...

Суперпозиция - это, если попросту, подстановка в функцию вместо её аргументов, других функций (т.е. сочетание, комбинирование ф-ций друг с другом). В результате могут получаться новые функции. Так, суперпозициями БФ not и and, например, будут: X and (not Y), not(X and Y and Z), X,
not(not X and not Y) и многие, многие другие (бесконечное число новых ф-ций)

ДАВАЙТЕ НАЧНЁМ В 13-00

ДАВАЙТЕ НАЧНЁМ В 13-00. И 25-го и 26-го. ИСы -обе группы.
Народу немного, так что позволим себе чуть-чуть продлить время подготовки (или, быть может, кому-то сна?).

Нашей группе тоже к 13:00?

Нашей группе тоже к 13:00?

Спасибо за дополнительное

Спасибо за дополнительное время для подготовки. Значит ИС 26-ого в 13.00 обе группы

ИТОГИ ПО ДМ (2015)

ПМ:
Гидзева З - ОТЛ.
Жужуев Б. - 16
Зайцев Ю. - 19
Ивашиненко Д. - 56
Косяненкова А. - 32
Купчин А. - 50
Кушу Т. - 65
Мкртчан З. 26
Нибо А. - 83
Раджабов А. - 64
Шукаев С. - 42

ИС1
Гамова А. - 78
Батыры Э. - 57
Казаков А. - 56
Кушхов З. -33
Моргунова Т. - 37
Свиридов Д. - 36
Сиренко А. - 65
Шефрукова Р. - 72

ИС2
Айвазян К. - 8 (не допущена к экзамену)
Ананко С. - 56
Воробьёв И. - 50
Гарынин В. - 33
Гриньков И. - ОТЛ.
Духу А. - 78
Ким Р. - 60
Фалеева М. - 66
Полонский В. - 26

Примерный перечень вопросов по ДМ.

Примерный перечень вопросов по ДМ смотрите вверху страницы ( http://it-starter.ru/content/voprosy-k-ekzamenu-po-diskretnoi-matematike ) . Можете посмотреть комменты на вопросы ко мне ст-тов других поколений.
Из перечня исключены экзаменационные вопросы: 21-24 (опущены все леммы и доказательства), 37-39. Добавлены вопросы о шифровании с симметричным ключом и упаковке по Лемпелу-Зиву.