litceysel.ru
добавить свой файл
1
Вопросы по курсу «Дискретные модели»


(магистратура, 1-й курс, весенний семестр 2010-2011 учебного года),

(лектор – доцент Селезнева С.Н.)


1. Комбинаторные объекты и комбинаторные числа: размещения, перестановки, размещения с повторениями, сочетания, сочетания с повторениями; их число и рекуррентные формулы для них.

2. Свойства. Формула включений-исключений (разные ее варианты).

3. Бинарные отношения, их виды. Отношение эквивалентности: классы эквивалентности, их свойства, фактор-множество. Отношения частичного порядка: сравнимые и несравнимые элементы, линейный порядок; минимальные и максимальные, наименьший и наибольший элементы, их свойства.

4. Частично упорядоченные множества, цепи и антицепи в них, длина и ширина конечных частично упорядоченных множеств. Булев куб, его длина и ширина.

5. Булевы функции. Элементарные булевы функции, формула и функция, реализуемая формулой. Канонические формы: ДНФ, КНФ, полиномы, теоремы о задании булевых функций ими. Операция замыкания, замкнутый класс и полная система, примеры полных систем. Классы функций, сохраняющих константу, линейных, монотонных и самодвойственных функций. Теорема Поста.

6. Многозначные функции. Элементарные k-значные функции, формула и функция, реализуемая формулой. Канонические формы: первая и вторая формы, полиномы, теоремы о задании k-значных функций ими. Операция замыкания, замкнутый класс и полная система, примеры полных систем. Система Поста, ее полнота, следствия из ее полноты, функция Вебба. Теорема Кузнецова.

7. Графы, основные понятия. Сеть, транспортная сеть, поток в транспортной сети, его величина. Сечение сети, его пропускная способность. Теорема Форда и Фалкерсона о величине потока в сети. Алгоритм построения максимального потока в сети.

8. Конечные автоматы, их функционирование, автоматные функции. Диаграммы Мура, канонические уравнения. Функция единичной задержки. Теорема о преобразовании периодической последовательности автоматной функцией. Примеры неавтоматных функций. Отличимые и неотличимые состояния конечного автомата. Теорема Мура. Приведенная диаграмма Мура.


9. Последовательности, виды их задания. Рекуррентные уравнения, линейные рекуррентные уравнения, однородные и неоднородные. Характеристический многочлен линейного однородного рекуррентного уравнения. Общие решения линейных однородных и неоднородных рекуррентных уравнений.


Типовые задачи


1. Решить комбинаторную задачу с применением комбинаторных объектов.

2. При помощи формулы включений-исключений подсчитать число элементов конечного множества, обладающих заданными свойствами.

3. По описанию бинарного отношения на заданном множестве определить его вид (отношение эквивалентности, частичного порядка и т.д.) и свойства (классы эквивалентности, минимальные и максимальные, наименьший и наибольший элементы, и т.д.).

4. Найти заданные объекты на булевом кубе.

5. Найти булеву функцию по заданной формуле; построить совершенную ДНФ или КНФ, полином Жегалкина для заданной булевой функции; выяснить, является ли заданное множество булевых функций полной системой (по теореме Поста).

6. Найти k-значную функцию по заданной формуле; записать в первой или второй форме заданную k-значную функцию; построить полином по модулю k при простом k заданной k-значной функции; выяснить, задается ли полиномом по модулю k при составном k заданная k-значная функция; доказать, что заданное множество k-значных функций является полной системой (сведением к одной из известных полных систем).

7. Построить максимальный поток в заданной транспортной сети по алгоритму Форда и Фалкерсона.

8. Определить, является заданная функция автоматной или неавтоматной (с доказательством); построить для автоматной функции диаграмму Мура, найти в ней неотличимые состояния, преобразовать диаграмму Мура к приведенной; найти канонические уравнения автоматной функции.

9. Решить заданное линейное однородное или неоднородное линейное рекуррентное уравнение с известными начальными условиями.