Задача 14. Можно ли нарисовать картинки, не отрывая карандаша от бумаги и проводя каждую линию ровно один раз? Какие из них являются эйлеровыми графами?
0) ![]() | 1) ![]() | 2) ![]() |
3) ![]() | 4) ![]() | 5) ![]() |
6) ![]() | 7) ![]() | |
8) ![]() | 9) ![]() |
Задача 15. Приведите к предваренной нормальной форме следующие формулы логики предикатов:
0)
Ø"y "x U(y, x) & $x "y R(y, x) ;
"y $x T(y, x) É "y "x Q(y, x);
1)
"y ($x "y G(y, x) Ú "s $x N(y, x, s)) ;
$y "x $z H(x, y, z) É $y $x G(y, x) ;
2)
Ø"y $x K(y, x) Ú $z $y "x Q(y, x, z) ;
"x $y A(x, y) É $y Ø "x R(y, x) ;
3)
$y "m U(y, m) & "x "y Q(y, x);
"z $x T(z, x) É "y $x U(y, x) ;
4)
$x "y T(y, x) Ú "y "x H(y, x) ;
"x Ø"y A(x, y) É $y "z T(y, z) ;
5)
$n "y "x P(n, y, x) & "y Ø$n A(n, y) ;
$n "y "x P(n, y, x) É "y Ø$n A(n, y) ;
6)
"z $x T(z, x) Ú "y $x U(y, x) ;
$x "y T(y, x) É "y "x H(y, x) ;
7)
"x Ø"y A(x, y) Ú $y "z T(y, z) ;
"x (Ø($y A(x, y) É $y P(y, x))) ;
8)
"y "z U(y, z) & "x $y P(y, x);
"y "z A(y, z) É $y "z P(y, z) ;
9)
$y "x $z H(x, y, z) Ú $y "x G(y, x);
"y Ø$x H(y, x) É "x "y P(y, x);
Автоматы.
Задачи синтеза автоматов
Задача 16. Постройте конечный автомат, выдающий на выходе символ “!”, всякий раз, когда во входной двоичной последовательности встречается:
0)последовательность 0000;
1)последовательность 1111;
2)последовательность 0110;
3)последовательность 0111;
4)последовательность 1000;
5)последовательность 0011;
6)последовательность 0010;
7)последовательность 1110;
8)последовательность 0001;
9)последовательность 1100.
Задача 17. Постройте конечный автомат таблично, складывающий:
0)четные натуральные числа в D5; | 1)нечетные натуральные числа в D8; |
2)натуральные числа в D4; | 3)нечетные натуральные числа в D6; |
4)четные натуральные числа в D6; | 5)нечетные натуральные числа в D5; |
6)четные натуральные числа в D7; | 7)натуральные числа в D3; |
8)четные натуральные числа в D8; | 9)нечетные натуральные числа в D7 |
Рекомендуемая литература
1. Акимов О.Е. Дискретная математика: логика, группы, графы.- М: Лаборатория Базовых Знаний, 2003 2. Гаврилов Г.П., Сапоженко А.А. Задачи и упражнения по курсу дискретной математики - М.: Наука, 2003. 3. Горбатов В.А. Фундаментальные основы дискретной математики: информатика и математика.- М: Наука. Изд.фирма «Физ.-мат.лит», 2001 4. Гульден Я., Джексон Д. "Перечислительная комбинаторика", - М.: Наука, 2004. 5. Иванов Б.Н. Дискретная математика: алгоритмы и программы. Лаборатория Базовых Знаний, 2003 6. Карпов В.Г., Мощенский В.А. Математическая логика и дискретная математика. – Минск: Вышэйш. школа, 2001 |
7. Кузнецов О.П., Адельсон-Вельский Г.М. Дискретная математика для инженера. – М.:Энергоатомиздат, 2001 8. Кук Д., Бейз Г. Компьютерная математика. – М.: Наука, 2001 9. Липский В. Комбинаторика для программистов. – М.: Мир, 2004. |
10. Лорьер Ж.Л. Системы искусственного интеллекта. – М.: Мир, 2001. 11. Нефедов В.Н., Осипова В.А. Курс дискретной математики. – М.: Издательство МАИ, 2002. 12. Новиков Ф. Дискретная математика для программистов. - СПб: Питер, 2000 13. Оре О. Теория графов. – М.: Наука, 2001. 14. Риордан Дж. "Введение в комбинаторный анализ", - М.: ИЛ. 2003. 15. Романовский И.В. Дискретный анализ. – СПб: Невский диалект, 2003 16. Фляйшнер Г. Эйлеровы графы и смежные вопросы – М.: Мир, 2002 |