![]() Заглавная страница Избранные статьи Случайная статья Познавательные статьи Новые добавления Обратная связь КАТЕГОРИИ: ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ТОП 10 на сайте Приготовление дезинфицирующих растворов различной концентрацииТехника нижней прямой подачи мяча. Франко-прусская война (причины и последствия) Организация работы процедурного кабинета Смысловое и механическое запоминание, их место и роль в усвоении знаний Коммуникативные барьеры и пути их преодоления Обработка изделий медицинского назначения многократного применения Образцы текста публицистического стиля Четыре типа изменения баланса Задачи с ответами для Всероссийской олимпиады по праву ![]() Мы поможем в написании ваших работ! ЗНАЕТЕ ЛИ ВЫ?
Влияние общества на человека
Приготовление дезинфицирующих растворов различной концентрации Практические работы по географии для 6 класса Организация работы процедурного кабинета Изменения в неживой природе осенью Уборка процедурного кабинета Сольфеджио. Все правила по сольфеджио Балочные системы. Определение реакций опор и моментов защемления |
Критерий же существования гамильтонова цикла В произвольном графе еще не найден . ⇐ ПредыдущаяСтр 10 из 10
Рис.10. Гамильтонов Рис.11. Полугамильтонов Рис.12. Не гамильтонов граф граф граф Рассмотрим несколько достаточных условий существования гамильтоновых циклов в графе. 1) всякий полный граф является гамильтоновым. Действительно, он содержит такой простой цикл, которому принадлежат все вершины данного графа. 2) если граф, помимо простого цикла, проходящего через все его вершины, содержит и другие ребра, то он также является гамильтоновым. Пример: если гамильтонов граф объединить с еще одной вершиной ребром так, что образуется висячая вершина, то такой граф гамильтоновым не является, поскольку не содержит простого цикла, проходящего через все вершины графа.
Примеры выполнения заданий
Решение: Пусть оба эти графа - плоские. Тогда у них вместе не более, чем 2. Докажите, что граф, имеющий 10 вершин, степень каждой из которых равна 5, - не плоский. Решение: Не выполняется неравенство 3V - 6 ≥ E. 3. Семиугольник разбит на выпуклые пяти- и шестиугольники, причем так, что каждая его вершина является вершиной по крайней мере двух многоугольников разбиения. Докажите, что число пятиугольников разбиения не меньше 13. Решение: Докажите сначала неравенство E £ 3V - 6, используя то, что из каждой вершины выходит по крайней мере 3 ребра. Обозначим количество пятиугольников через a, количество шестиугольников через b. Заметим, что 5a + 6b + 7 = 2E £ 6F – 12 = 6(a + b + 1) – 12. Отсюда a ³ 13. 4. Граф задан геометрически. А) Определите, содержит ли данный граф гамильтонов цикл? Б) Выпишите гамильтонов цикл у данного графа, если он есть: Решение: А) да, содержит, т.к. граф – полный и не содержит перекладин и висячих вершин. Б) гамильтонов цикл выделен сплошной линией: (1,2), (2,3), (3,4), (4,5), (5,1).
Задания для самостоятельного выполнения
Запишите: 1) любой путь, не являющийся цепью; 2) цепь и простую цепь; 3) цикл, простой цикл, если таковые имеются. Можно ли нарисовать картинки, не отрывая карандаша от бумаги и проводя каждую линию ровно один раз? Какие из них являются эйлеровыми графами?
3. Граф задан геометрически. Выпишите гамильтонов цикл у данного графа, если он есть:
Практические занятия №13,14 Автоматы
Элементы теории
Система A=(X;Q;Y;j;y) называется конечным автоматом,
Существуют следующие способы задания автоматов: - с помощью таблицы. Функции j и y задаются таблицей, строки которой соответствуют буквам входного алфавита, а столбцы – состояниям. В пересечении строки aj и столбца qi помещается состояние - в виде диаграммы. Состояния qi изображаются на плоскости кружками, из которого проводится стрелка в qu, если автомат, находящийся в состоянии qi, при подаче некоторого входного символа может быть переведен в состояние qu; - совокупностью четверок вида: qiaj ® qlap,. Если на вход автомата, находящегося в состоянии qi, в момент времени t подается символ aj, то на выходе автомата в этот же момент времени появляется символ ap, и в следующий момент времени t+1 автомат будет находиться в состоянии ql.
- в виде системы булевых функций. Каждому qj ÎQ взаимно-однозначно ставится в соответствие двоичная последовательность длины r - двоичный код a(q) = z1z2…zr. Аналогично каждому aiÎX и каждому bk ÎY ставим взаимно-однозначно в соответствие двоичные последовательности b(a) = x1x2…xk; g(b) = y1y2…ys.В результате автомат будет задан системой булевых функций {j1,j2,…,jr,y1,y2,…,ys}; - в виде канонических уравнений. Если в момент времени t=1,2,… на вход автомата A=(X; Q; Y; j; y) последовательно подаются входные символы x(t)ÎX и при этом автомат находится в состоянии q(t)ÎQ, то под воздействием символа x(t) автомат перейдет в новое состояние q(t+1)ÎQ и выдаст выходной сигнал y(t). Величины x(t), y(t), q(t), q(t+1) связаны между собой следующими каноническими уравнениями: К задачам теории автоматов относятся: задачи анализа и синтеза автоматов, задачи полноты, минимизации, эквивалентных преобразований автоматов и другие. Задачи анализа автоматов Задача анализа состоит в том, чтобы по заданному описанию автомата (или по неполным данным об автомате и его функционированию) задать его поведение и установить те или иные его свойства. Примеры выполнения заданий 1. Работа автомата задана таблично и выдает на выходе символ “*”, всякий раз, когда во входном алфавите встречается цепочка из комбинаций символов 0, 1, 2. Опишите работу автомата с помощью совокупности четверок. X = {0, 1, 2}, Y = {0, 1, 2} и Q = {q0, q1, q2, q3}. Определите, что распознает автомат.
Автомат распознает цепочку вида: 1111* 2. Описание автомата - двоичного сумматора последовательного действия задано с помощью совокупности четверок. X = {00, 01, 10, 11}, Y = {0, 1}, Q = { q 0, q 1 }. Опишите работу автомата с помощью диаграммы.
Задания для самостоятельного выполнения 1. Работа автомата задана с помощью совокупности четверок и выдает на выходе символ “ * ”, всякий раз, когда во входной последовательности алфавита { a, b } встречается цепочка символов. Определите, что распознает автомат. Опишите работу автомата таблично. 0)
1)
2)
3)
4)
5)
6)
7)
8)
9)
Решение:
2. Работа автомата задана таблично и выдает на выходе символ “&”, всякий раз, когда во входном алфавите встречается цепочка символов. Определите, что распознает автомат. Опишите работу автомата с помощью совокупности четверок. 0)
1)
2)
3)
4)
5)
6)
7)
8)
9)
3.Работа автомата задана с помощью диаграммы и выдает на выходе символ “*", всякий раз, когда во входном алфавите встречается цепочка символов. Определите, что распознает автомат. Опишите работу автомата с помощью совокупности четверок 0) (б, б) (К, б) Ú (б, *)
(К, К)
|
1) (м, м) (с, м) Ú (м, *)
(с, с) | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
2) (б, б) (М, б) Ú (б, *)
(М, М) |
3) (г, г) (к, г) Ú (г, *)
(к, к) | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
4) (б, б) (Г, б) Ú (б, *)
(Г, Г) |
5) (м, м) (д, м) Ú (м, *)
(д, д) | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
6) (г, г) (м, г) Ú (г, *)
(м, м) |
7) (б, б) (Т, б) Ú (б, *)
(Т, Т) | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
8) (а, а) (г, а) Ú (а, *)
(г, г)
|
9) (м, м) (к, м) Ú (м, *)
(к, к)
|
Практические занятия №15-17. Задачи
синтеза автоматов
Элементы теории
Задача синтеза автоматов состоит в построении автомата с наперед заданным поведением или функционированием.
Примеры выполнения заданий
1. Постройте конечный автомат, воспринимающий на входе двоичную последовательность и выдающий на выходе специальный символ ‘ *’, если во входной последовательности подряд встретится 4 единицы. В остальных случаях автомат на выходе повторяет входной символ.
Решение.
q00® q00 q01® q11 | q10® q00 q11® q21 | q20® q00 q21® q31 | q30® q00 q31® q0* |
2. Постройте конечный автомат таблично, представляющий двоичный сумматор последовательного действия.
Решение. Обозначим через q0 и q1 его состояния, соответствующие отсутствию и наличию переноса.
Символы алфавита | Состояния | ||
x1 | x2 | q0 | q1 |
0 | 0 | q0,0 | q0,1 |
0 | 1 | q0,1 | q1,0 |
1 | 0 | q0,1 | q1,0 |
1 | 1 | q1,0 | q1,1 |
Задания для самостоятельного выполнения
1. Постройте конечный автомат, выдающий на выходе символ “!”, всякий раз, когда во входной двоичной последовательности встречается:
0) последовательность 0000;
1) последовательность 1111;
2) последовательность 0110;
3) последовательность 0111;
4) последовательность 1000;
5) последовательность 0011;
6) последовательность 0010;
7) последовательность 1110;
8) последовательность 0001;
9) последовательность 1100.
2. Постройте конечный автомат, выдающий на выходе символ “♫”, всякий раз, когда во входной последовательности в алфавите
0) {А, н, ю, т} встречается имя “Анюта”;
1) {А, л, е, ш} встречается имя “Алеша”;
2) {И, р, н, а} встречается имя “Ирина”;
3) {С, а, ш} встречается имя “Саша”;
4) {Д, а, я, н} встречается имя “Даяна”;
5) {Н, и, а} встречается имя “Нина”;
6) {А, н, ж, е, л} встречается имя “Анжела”;
7) {А, н, т, о} встречается имя “Антон”;
|
8) {С, е, р, ж, а} встречается имя “Сережа”;
9) {Л, и, я} встречается имя “Лилия”.
| Поделиться: |
Читайте также:
Последнее изменение этой страницы: 2021-05-27; просмотров: 236; Нарушение авторского права страницы; Мы поможем в написании вашей работы!
infopedia.su Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Обратная связь - 3.143.4.117 (0.151 с.)