Элементы теории конечных автоматов

Курган - 2013

ОБЩИЕ УКАЗАНИЯ

В курсе «Дискретная математика» студенты-заочники изучают такие разделы математики как графы, комбинаторика, элементы теории конечных автоматов и теории кодирования.

Изучение этих разделов дискретной математики занимает важное место в формировании специалиста прикладной информатики высокой квалификации и служит теоретической основой многих специальных учебных дисциплин. Знание этих разделов имеет большое значение при решении вопросов, связанных с решением задач в разных разделах человеческой деятельности. Это необходимо для общей подготовки студентов, создания у них прочной базы независимо от области, в которой они в будущем будут работать. В методических указаниях к контрольной работе приводится список рекомендованной учебной литературы, изучение которой необходимо для выполнения заданий. Указываются номера глав и параграфов учебников, а также номера задач, предназначенных для самостоятельной работы. В случае возникновения затруднений студент может обратиться на кафедру за письменной консультацией. Необходимо строго придерживаться следующих правил:

1. Студент обязан делать работу только своего варианта, отсылая ее в Университет на рецензирование в сроки, предусмотренные графиком!

2. Контрольную работу следует выполнять на листах формата А4 чернилами любого цвета, кроме красного.

3. В конце работы необходимо привести список использованной литературы.

4. Перед решением задачи нужно полностью выписать ее условие. Если несколько задач имеют общую формулировку, переписывать следует только условие задачи нужного варианта.

Решение каждой задачи студент должен сопровождать подробными объяснениями и ссылками на соответствующие формулы, теоремы и правила. Вычисления должны быть доведены до конечного числового результата. Ответы и выводы, полученные при решении задач, следует подчеркнуть.

5. После получения отрецензированной работы студенту необходимо исправить все отмеченные ошибки и недочеты.

6. Если работа не зачтена, то следует переделать те задачи, на которые указывает рецензент, а при отсутствии такого указания вся контрольная работа должна быть выполнена заново. Переделанная работа высылается на повторное рецензирование обязательно с не зачтенной ранее работой и рецензией к ней. При этом на обложке следует указать фамилию рецензента.

7. Работы, выполненные без соблюдения этих правил, к зачету не принимаются и возвращаются без рецензирования для переработки.

При подготовке к экзамену следует еще раз обратиться к методическим указаниям и примерам, разобранным в них, вопросам для самопроверки и задачам, которые рекомендуется решить.

На экзамен студент должен являться с зачтенными контрольными работами и рецензиями на них. Каждому студенту предлагается индивидуальное задание, состоящее из пяти задач в каждой из четырех контрольных работ.

Для определения индивидуального задания контрольной работы нужно использовать таблицу 1.

Номера задач контрольных работ определяются по соответствующей таблице с помощью двух последних цифр номера зачетной книжки студента.Например, для студента, имеющего зачетную книжку с номером 87128, на пересечении горизонтальной колонки 2 и столбца 8 таблицы 1 указаны следующие номера задач его индивидуального задания контрольной работы: 08, 21, 54, 66, 83, 118.

ДЛЯ ОПРЕДЕЛЕНИЯ ИНДИВИДУАЛЬНОГО ЗАДАНИЯ

КОНТРОЛЬНОЙ РАБОТЫ

КОНТРОЛЬНАЯ РАБОТА

I. Элементы комбинаторики

Элементы теории графов

Тема 3. Основные понятия; способы представления графов

Ориентированные и неориентированные графы. Способы задания графов. Цепи. Циклы. Связные графы. Изоморфизм графов.

Понятие об эйлеровых и гамильтоновых графах. Теорема Эйлера.

Понятие дерева и леса. Цикломатическое число. Задача коммивояжера.

Обходы графа по глубине и ширине. Разрезы. Понятие планарного графа. Примеры планарных графов.

Теорема Эйлера и ее следствия. Непланарность графов К₅ и К_3,3.

Тема 4. Сети; алгоритмы решения задач на сетях

Ориентированные графы. Алгоритмы Дейкстры, Флойда. Сети планирования, транспортные сети. Теорема Форда – Фалкерсона.

Элементы теории конечных автоматов

Тема 5.Элементы теории конечных автоматов

Понятие конечного автомата. Автоматы Мили и Мура. Автоматы преобразователи и распознаватели. Минимизация автоматов.

4. Элементы теории кодирования

Элементы комбинаторики

[1]: гл.2; §§ 1 – 4;

[3]: гл.3, §§ 1-5;

Вопросы для самопроверки

1. Когда применяется правило суммы, а в какой ситуации – правило произведения?

2. Что такое перестановка и как подсчитать число различных перестановок из n различных элементов?

3. Что такое размещение и как подсчитать число различных размещений из n различных элементов по m?

4. Что такое сочетание и как подсчитать число различных сочетаний из n различных элементов по m?

5. Что такое перестановка и как подсчитать число различных перестановок из nэлементов среди которых могут быть одинаковые?

6. Что такое размещение и как подсчитать число различных размещений из n элементов по m среди которых могут быть одинаковые?

7. Что такое сочетание и как подсчитать число различных сочетаний из n различных элементов по m среди которых могут быть одинаковые?

8. Что такое бином Ньютона и биномиальные коэффициенты?

9. Свойства биномиальных коэффициентов?

10. Что такое полиномиальная теорема и полиномиальные коэффициенты?

11. Как решаются задачи о разделе некоторого множества объектов на группы, которые удовлетворяют поставленным требованиям?

12. Когда применяется формула для подсчета числа различных разбиений множества на классы?

13. В чем суть метода включений и исключений?

Задача 1