Дискретная математика в примерах и задачах (Тишин)
Популярный учебник (или, все же скорее сборник задач) по дискретной математике под авторством Тишина В.В. часто используется для выдачи домашних заданий студентам технических специальностей (наряду с классическими задачниками Гаврилова и Сапоженко, Гиндикина, Яблонского, Лаврова и Максимовой и др.).
Немного фактов
- Сборник основан на лекциях и практических занятиях автора, проводимых в СГАУ им. С.П. Королёва
- Сборник переиздавался несколько раз, последнее издание 2016 года можно найти, например, тут.
- В последнем издании 336 страниц и оооочень много задач.
- Каждое задание дано в 30 индивидуальных вариантах.
- Все задания снабжены примерами решений, которые помогут справиться с самостоятельной работой.
- Ответов на задания нет, проверить решение таким образом невозможно:(.
Главы задачника:
- Множества, графики, соответствия, отношения.
- Булевы функции
- Теория алгоритмов
- Предикаты
- Комбинаторика
- Конечные автоматы
Решебник Тишина
Как уже говорилось, полного сборника решений заданий из Тишина не существует, но мы рады предложить вам услуги по решению ваших задач. Для оценки оформления и помощи в самостоятельной работе приложим некоторые решенные задачи.
Множества, графы, соответствия, отношения
Задача 1. Пусть $A$, $B$ и $C$ - множества точек плоскости, координаты которых удовлетворяют условиям $\alpha$, $\beta$ и $\gamma$ соответственно. Изобразите в системе координат $xOy$ множество $D$, полученное из множеств $A$, $B$ и $C$ по формуле $\delta$.
Задача 2. Дано соответствие $Г=(X,Y,G)$. $X=\{a,b,c,d\}$, $Y=\{1,2,3,4\}$, $G=\{(a,3),(b,4),(c,3),(d,1)\}$
1. Изобразить соответствие в виде графа.
2. Выяснить, какими из 4 основных свойств (всюду определённость, сюръективность, функциональность, инъективность) обладает $Г$.
3. Найти образ множества $A=\{a,c\}$ и прообраз множества $B=\{1,3\}$ при данном соответствии.
4. Построить соответствие между бесконечными множествами, обладающее тем же набором свойств, что и $Г$.
5. Построить соответствие между конечными множествами, обладающее набором свойств, противоположным данному.
Замечание. Для данного и построенных соответствий отметить случаи отображений, указать их тип, отметить случаи биекций.
Задача 3. Для данного отношения $Ф=(\{1,2,3,4,5\},G)$, где $G=\{(3,5),(4,2),(1,2)\}$, проделать следующее:
1. Изобразить Ф графом.
2. Достроить Ф до отношения эквивалентности, указать фактор-множество.
3. Достроить Ф до отношения частичного порядка, указать максимальные, минимальные элементы, а также пары несравнимых элементов.
4. Достроить Ф до отношения линейного порядка, указать наибольший и наименьший элементы.
5. Достроить Ф до отношения строгого порядка.
6. Достроить Ф до отношения строгого линейного порядка.
Замечание: отношение достраивается с помощью введения минимально необходимого числа дополнительных рёбер.
Комбинаторика
Задача 4. Сколько различных слов можно получить перестановкой букв слова «переходим», при условии, что согласные и гласные должны чередоваться?
Задача 5. Найти коэффициент при $x^{30}$ в разложении данного выражения по полиномиальной формуле, полученный после раскрытия скобок и приведения подобных членов. $$(x^7+3-x^2)^{16}$$
