Программа для подготовки к зачету теоретическая часть

Вид материала

Программа для подготовки

Содержание Практическая часть Логика предикатов. 5. Если множество дизъюнктов S предложения унифицируемо, то найти НОУ Типовые билеты Если множество дизъюнктов S предложения унифицируемо, то найти НОУ Типовой билет 2 Учебно-методическое обеспечение дисциплины.

Подобный материал:

• Программа для подготовки к зачету I. Теоретическая часть, 68.7kb.
• Программа для подготовки к зачету (экзамену) теоретическая часть, 113.03kb.
• Программа для подготовки к зачету теоретическая часть, 54.03kb.
• Программа для подготовки к экзамену теоретическая часть, 101.03kb.
• Программа для подготовки к экзамену теоретическая часть, 254.95kb.
• Рабочая программа по дисциплине «теоретическая фонетика» методические рекомендации, 327.76kb.
• Содержание введение теоретическая часть, 38.74kb.
• Содержание введение теоретическая часть, 38.73kb.
• Программа для подготовки к сдаче вступительного экзамена в аспирантуру по специальности, 174.75kb.
• Л. И. Горбунова, Г. С. Келлер культурология часть I человек – общество культура, 2386.47kb.

МОСКОВСКАЯ ФИНАНСОВО-ЮРИДИЧЕСКАЯ АКАДЕМИЯ

Согласовано на 2008-2009 уч.год Начальник УМУ __________________С.В. Щедроткина «_____»_______________2009 г.

Дисциплина: Дискретная математика

Специальность (направление): Защита информации

Форма обучения: все


Программа для подготовки к зачету


ТЕОРЕТИЧЕСКАЯ ЧАСТЬ

Список тем

1. Понятие множества. Пустое множество. Наиболее употребляемые множества.
   
2. Множества и отношения. Подмножество.
   
3. Операции над множествами.
   
4. Алгебра множеств.
   
5. Сравнение множеств.
   
6. Упорядоченные множества.
   
7. Свойства и отношения.
   
8. Отображения.
   
9. Решетки.
   
10. Основные правила комбинаторики.
    
11. Перестановки, сочетания, размещения, размещения с повторениями.
    
12. Биноминальные коэффициенты.
    
13. Алгебра Буля.
    
14. Формулы алгебры логики.
    
15. Функции алгебры логики.
    
16. Нормальные формы булевой функции (КНФ, ДНФ).
    
17. СДНФ. СКНФ.
    
18. Двойственность алгебры логики.
    
19. Многочлен Жегалкина, классы Поста, теорема Поста.
    
20. Полнота логических связок.
    
21. Электронные логические элементы.
    
22. Язык логики высказываний.
    
23. Понятие семантики в логике высказываний.
    
24. Операции логики высказываний.
    
25. Нормальные формы логики высказываний (КНФ, ДНФ).
    
26. Таблица истинности для формулы.
    
27. Метод резолюции.
    
28. Теоретико-множественная форма представления предложения.
    
29. Понятие предиката.
    
30. Кванторы.
    
31. Язык логики предикатов.
    
32. Подстановка. Композиция.
    
33. Интерпретация и истинность в логике предикатов.
    
34. Унификация в логике предикатов.
    
35. Тавтология, выполнимость и противоречие в логике высказываний и предикатов.
    
36. Предварённая нормальная форма.
    
37. Сколемовская нормальная форма.
    
38. Метод резолюции в логике предикатов..
    
39. Графы. Основные понятия и определения.
    
40. Изоморфизм графов.
    
41. Маршруты, цепи и циклы.
    
42. Матричное задание графов.
    
43. Связность. Компоненты связности.
    
44. Степень вершин графа, орграфа.
    
45. Поиск маршрута в графе.
    
46. Поиск путей (маршрутов) с минимальным числом дуг (рёбер).
    
47. Минимальные пути (маршруты) в нагруженных орграфах (графах).
    
48. Эйлеровы графы.
    
49. Гамильтоновы графы.
    
50. Деревья.
    
51. Остовное дерево графа.
    
52. Понятие алгоритма;
    
53. Определение машины Тьюринга;
    
54. Применение машины Тьюринга к словам;
    
55. Правильная вычислимость функций на машине Тьюринга;
    
56. Тезис Тьюринга;
    
57. Основные понятия теории рекурсивных функций;
    
58. Примитивно рекурсивные функции;
    
59. Тезис Чёрча;
    
60. Марковские подстановки;
    
61. Нормальные алгоритмы и их применение к словам;
    
62. Нормально вычислимые функции и принцип нормализации Маркова;
    
63. Разрешимость и перечислимость множеств;
    
64. Неразрешимые алгоритмические проблемы.
    
65. Теория порождающих грамматик;
    
66. Иерархия Хомского для порождающих грамматик;
    
67. Конечные автоматы;
    
68. Стековые автоматы;
    
69. Машины Тьюринга;
    
70. Линейно ограниченные автоматы.
    

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


ПРАКТИЧЕСКАЯ ЧАСТЬ

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


Множества.

1. Доказать тождества.
   

а) (АВ)(А)=А; б) А\В=А

2. Найдите множество Х, удовлетворяющее следующему равенству .

3. Доказать тождество.

(АВ)(А)=А

4. Верно ли, что .
   

4. Доказать тождество.
   

(В)А=АВ

4. Верно ли, что .
   

4. Доказать Тождество.
   

(А\В)\С=(А\С)\(В\С)

4. Верно ли, что если и , то, В = С.
   

4. Докажите (символ означает «тогда и только тогда, когда»).
   

4. Докажите (символ означает «тогда и только тогда, когда»).
   

4. Доказать тождество.
   

А(В\С)=(АВ)(А)

4. Докажите (символ означает «тогда и только тогда, когда»).
   

4. Доказать тождество.
   

(А\В)()=(АВ)\(АВ)

4. Докажите и (символ означает «тогда и только тогда, когда»).
   

4. Доказать тождество.
   

()()=(АВ)\(АВ)


Комбинаторика.


1. Сколько существует способов разместить 3 человека на скамейке?

2. Сколько существует способов расставить 8 книг на полке так, чтобы 3 данные книги стояли вместе?

3. Сколькими различными способами можно выбрать три лица на три различных должности из 8 кандидатов?

4. Сколькими способами можно выбрать 3 лица на 3 одинаковые должности из 8 кандидатов?

5. Сколько различных 6-ти значных чисел можно записать с помощью цифр 1;1;2;2;2;3?


6. Cколько различных перестановок букв можно сделать в словах: замок, ротор, топор, колокол?


7. Сколько прямых можно провести через 8 точек, никакие 3 из которых не лежат на одной прямой, так чтобы каждая прямая проходила через 2 точки?

8. Сколько различных шестизначных чисел, начинающихся цифрой 2 и оканчивающихся цифрой 5, можно составить из цифр 1, 2, 3, 4, 5, 6 при условии, что каждая цифра в обозначении числа встречается 1 раз?
   

9. Найти m и n, если .


10. Вычислить: .

11. Сколько существует кодовых комбинаций в замке, имеющем 5 дисков и на каждом диске 6 цифр.

Булевы функции.


1. Привести к СДНФ с помощью таблицы истинности и равносильных преобразований. Записать в виде многочлена Жегалкина и построить логическую схему в базисе “И-НЕ”.




2. Доказать, что формула тождественно равна 0 или 1.




3. Привести к СДНФ с помощью таблицы истинности и равносильных преобразований.

Записать в виде многочлена Жегалкина и построить логическую схему в базисе “И-НЕ”.



4. Доказать, что формула тождественно равна 0 или 1.




5. Привести к СКНФ с помощью таблицы истинности и равносильных преобразований. Записать в виде многочлена Жегалкина и построить логическую схему в базисе “И-НЕ”.



6. Упростить формулу.

7. Привести к СКНФ с помощью таблицы истинности и равносильных преобразований. Записать в виде многочлена Жегалкина и построить логическую схему в базисе “И-НЕ”.



8. Упростить формулу.

9. Привести к СКНФ с помощью таблицы истинности и равносильных преобразований. Записать в виде многочлена Жегалкина и построить логическую схему в базисе “ИЛИ-НЕ”.



10. Доказать равносильность.


11. Привести к СДНФ с помощью таблицы истинности и равносильных преобразований. Записать в виде многочлена Жегалкина и построить логическую схему в базисе “ИЛИ-НЕ”.




12. Доказать равносильность.

13. Известно, что х=1. Что можно сказать о значении:

и .

14. Известно, что . Что можно сказать о значении:

.

15. Известно, что , а . Что можно сказать о значении:


Логика высказываний.


1.Доказать, что высказывание логически ложно.

а. АВ)(ВС)(АС);

б. ((АВ)(АВ)А;

в. А(ВВ))А.


2. Доказать, что высказывание логически истинно.

а. (АВ)(АВ).

б. (А(АВ))В.

в. (АВ)АВ


3. Докажите, что высказывание является тавтологией.

а. (А→В)(АВ)

б. АВВА.

в. (АВ)(ВА).


4. Найти означивания при которых формула истинна.

а. А(АВ).

б. (АВ)(ВА).

в. (АВ)(АВ).


5. Методом резолюции доказать, что множество S противоречиво.

а. S={ABD, BDA, DA, AB, BD, AB}.

б. S={AB, BC, CA, AC, AC}.

в. S={ABC, ABC, AB, AC, AC}.


6. Методом резолюции доказать, что

а. {AB, CD, DB, BCD}├ BC.

б. {ABC, AB} ├ AC.


7. Представьте следующее высказывание как множество дизъюнктов.

а. А(ВС).

б. ((АВ)С).


8. Определить выполнимо ли множество. Если да, то найти означивания подтверждающие его выполнимость.

а. {{A,B}, {A,B}}.

б. {{A}, {A,B}, {B}}.


9. Определить множество резольвент дизъюнктов S.

а. S={{A,B}, {A,B}, {A}}

б. S={{A}, {B},{A,B}}

в. S={{A}, {B},{A,B}}

Логика предикатов.

1. Выявить логическую форму предложения и записать её на языке логики предикатов.

а. “Каждый студент знает хотя бы некоторых преподавателей”.

б. “Неверно, что никто не знает русского языка.”

в. “Все любят Джейн, но она не любит ни кого.”

г. “Ничто не вечно”.

д. “Разность любых двух положительных чисел меньше суммы этих чисел”.

е. Если он мой отец , то он старше и мудрее меня.”


2. Запишите следующие высказывания на языке логики предикатов:

а. х – мать у, если х – женщина и родитель у.

б. х – отец у, если х – мужчина и родитель у.

в. х – человек, если его родитель человек.

г. х – человек, если отец х – человек.

д. Никто не родитель самому себе.


3. Привести к ПНФ и далее записать предложения в СНФ

а. (х)Р(х)(х)Q(х).

б. (х)(у)[(z)P(x,y)Р(x,z)](u)Q(x,y,u).

в. (x)(y)[(z)P(x,y,z)[(u)Q(x,u)(u)Q(y,u)]].


4. Записать предложение в теоретико-множественной форме.

а. (x)(y)(z)[(P(x,y)Q(x)R(z))(P(x,y)Q(x))(P(x,y)R(z))].

б. (х)(y)[P(x,y)Q(y)].

в. [(x)P(x)(y)(z)Q(y,z)].

5. Если множество дизъюнктов S предложения унифицируемо, то найти НОУ

а. S={{P(a, x, h(g(z)))}, P(z, h(y), h(y))}}.

б. S ={{любит(w,(у))}, {любит(Джон, футбол)}}.

в. S={{Q((w), a, z)}, Q(w, b, (z))}.

г. S={{R(w,y), Q(w, (z),z), R(w,w)}, {R(w,z), Q((w),w,z)}}.

д. S={{P((x),a)},{P(y,(w))}}.


Графы.

1. Найти минимальный путь из v₁ в v₆ методом «фронта волны».
   

2. Найти минимальный путь из v₁ в v₇ в орграфе, заданном матрицей смежности методом «фронта волны».
   

А(D) =

3. Определить минимальный путь из v₁ в v₇ в нагруженном орграфе D с числом дуг не более 5.
   

С(D) =

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

A(G) = , A(G) =


Теория алгоритмов.

1. Имеется машина Тьюринга с внешним алфавитом А={a_,1}, множеством внутренних состояний Q={q₀,q₁) и системой команд q₁aq₀1, q₁1q₁1П (q₀ – заключительное состояние). Определите, в какое слово перерабатывает машина каждое из следующих слов, если она находится в начальном состоянии q₁ и обозревает указанную ячейку:
   

а. 1а11аа11 (обозревается ячейка 4, считая слева);

б. 11а111а1 (обозревается ячейка 2);

в. 1аа111 (обозревается ячейка 3);

г. 1111а11 (обозревается ячейка 4);

д 11а1111 (обозревается ячейка 3);

е. 1111111 (обозревается ячейка 4);

ж.11111(обозревается ячейка 5);

2. Напишите программу для машины Тьюринга, которая бы к натуральному числу в десятичной системе счисления прибавляла единицу.
   
3. Напишите программу для машины Тьюринга, которая бы от натурального числу в десятичной системе счисления отнимала единицу.
   
4. Сконструируйте машину Тьюринга с внешним алфавитом A={a,1}, которая каждое слово длиной n в алфавите А₁={1} перерабатывает в слово длиной n +1 в том же алфавите А (машина имеет два внутренних состояния q₀ и q₁).
   
5. Постройте машины Тьюринга, которые правильно вычисляют следующие функции:
   

а. f(x) = x+1; б. O(x) = 0.

6. Докажите, что функция вычислима по Тьюрингу.
   
7. Докажите, что следующие функции примитивно рекурсивны, руководствуясь непосредственно определением примитивно рекурсивной функции: a: (x) = n; b. (x) = n + x; c. (x,y) = x + y; d. . (x,y) = xy.
   
8. Пусть для слов в алфавите А={a,b,c,d} заданы следующие марковские подстановки: а. abdc; б. bca; в. ddbb; г. acdc; д. cbd; е. abc; ж. cba; з. da; и. dacacd; к. ba; л. abd; Примените каждую из них к слову abcddacba.
   
9. Нормальный алгоритм в алфавите {a,b,1}задается схемой: a1, b1. Примените его к слову: а. ababaa; б. bababbaa; в. aaa; г. bbbb; д. aabbb11; е. 11aab; ж. baaab1a; з. 111aab1; и. aabb; к.abbba; л. abaabbb.
   
10. Нормальный алгоритм в алфавите {a,b,1}задается схемой: a1, b1, 11. Примените его к следующим словам : а. bbaab; б. bababab; в. aaaa; г. bbbbb; д. aabaabb; е. bbbaaa; ж. baaab1a; з. abbabba; и. baab; к.abbbbba; л. abbbaaab.
    

11. Нормальный алгоритм в алфавите {a,b}задается схемой: aba, b., ab. Примените его к следующим словам: а. bbaab; б. bababab; в. aaaa; г. bbbbb; д. aabaabb; е. bbbaaa; ж. baaab1a; з. abbabba; и. baab; к.abbbbba; л. abbbaaab.
    

Теория автоматов.


1. Для регулярной грамматики G построить конечный автомат М.

G = ( N, T, P, S ), где N = { S, A, B }, Т = { a, b },

P = { S aA,

S bB,

S a,

A aA,

A aS,

A bB,

B bB

B b,

B a}.

2. Для конечного автомата М построить регулярную грамматику G.

М = (Q, Σ, t, , F), где Q = {}, Σ = {0, 1), F = {, },

t = {

















}.

ТИПОВЫЕ БИЛЕТЫ

ТИПОВОЙ БИЛЕТ 1

1	Верно ли, что .
2	Сколько положительных целых чисел меньших 100 не делятся на 8?
3	Доказать, что формула тождественно равна 0 или 1.
4	Дано высказывание Q: ((AB)C)A(BC). Методом резолюции доказать, что Q├ C.
5	Если множество дизъюнктов S предложения унифицируемо, то найти НОУ S ={{любит(w,(у))}, {любит(Джон, футбол)}}.
6	Определить минимальный путь из v1 в v7 в нагруженном орграфе D с числом дуг не более 5. С(D) =
7	Имеется машина Тьюринга с внешним алфавитом А={a,1}, множеством внутренних состояний Q={q0,q1) и системой команд q1aq01, q11q11П (q0 – заключительное состояние). Определите, в какое слово перерабатывает машина слово1а11аа11 (обозревается ячейка 4, считая слева), если она находится в начальном состоянии q1 и обозревает указанную ячейку:
8	Напишите программу для машины Тьюринга, которая бы к натуральному числу в десятичной системе счисления прибавляла единицу.
9	Докажите, что функция (x) = n примитивно рекурсивна, руководствуясь непосредственно определением примитивно рекурсивной функции.
10	Нормальный алгоритм в алфавите {a,b}задается схемой: aba, b., ab. Примените его к слову bbaab.

1	Найдите множество Х, удовлетворяющее следующим условиям A\X=A и AX=U
2	Сколько существует вариантов ответов на тест из 30 вопросов., если на каждый вопрос требуется ответ да или нет?
3	Записать в виде многочлена Жегалкина
4	Записать предложение на языке логики предикатов . « Всякий человек имеет родителей».
5	Привести к ПНФ и далее записать предложение в СНФ (х)Р(х)(х)Q(х).
6	Проверить существуют ли в мультиграфе, заданном матрицей смежности, эйлеровы цепи и циклы, если да то найти их. A(G) =
7	Напишите программу для машины Тьюринга, которая бы от натурального числу в десятичной системе счисления отнимала единицу.
8	Докажите, что функция (x,y) = x+y примитивно рекурсивна, руководствуясь непосредственно определением примитивно рекурсивной функции.
9	Пусть для слова в алфавите А={a,b,c,d} задана марковская подстановка а. abdc. Примените её к слову abcddacba.
10	Для регулярной грамматики G построить конечный автомат М. G = ( N, T, P, S ), где N = { S, A, B }, Т = { a, b }, P = { S aA, S bB, S a, A aA, A aS, A bB, B bB B b, B a}.

ТИПОВОЙ БИЛЕТ 2


ТИПОВОЙ БИЛЕТ 3

1	. Существуют ли множества? AB, AC=, (AB)\C=
2	Если многоугольник имеет n сторон, то сколько у него диагоналей?
3	Известно, что х=1. Что можно сказать о значении: и .
4	Доказать, что следующее высказывание является тавтологией (А→В)(АВ).
5	Записать на языке логики предикатов «Всякий ребенок имеет родителей»
6	2. Найти минимальный путь из v1 в v6 методом «фронта волны».
7	Докажите, что функция вычислима по Тьюрингу
8	Докажите, что функция (x) = n +х примитивно рекурсивна, руководствуясь непосредственно определением примитивно рекурсивной функции.
9	Пусть для слова в алфавите А={a,b,c,d} задана марковская подстановка da; . Примените её к слову abcddacba.
10	. Для конечного автомата М построить регулярную грамматику G. М = (Q, Σ, t, , F), где Q = {}, Σ = {0, 1), F = {, }, t = { }.

УЧЕБНО-МЕТОДИЧЕСКОЕ ОБЕСПЕЧЕНИЕ ДИСЦИПЛИНЫ.

Базовые учебные пособия.

1. 20. Нефедов В.Н., Осипова В. А. Курс дискретной математики. М.: Изд. МАИ. 1992. 264 с.
   
2. С.В. Судоплатов, Е.В. Овчинникова Элементы дискретной математики. М.: ИНФРА-М, Новосибирск: Изд-во НГТУ 2002. 280 с.
   
3. В.И. Игошин Математическая логика и теория алгоритмов. М: Издательский центр «Академия», 2004.- 448 с.
   
4. С.Д. Шапорев Математическая логика. Курс лекций и практических занятий. СПб
   

БХВ-Петербург, 2005.-416 с.

5. Куликов Л. Я., Москаленко А. И., Фомин А. А. Сборник задач по алгебре и теории чисел. М.: Просвещение. 1993. 288 с.
   
6. Лавров И. А., Максимова Л. Л. Задачи по теории множеств, математической логике и теории алгоритмов. М.: ФИЗМАТЛИТ. 2001. 256 с.
   
7. Игошин В.И. Задачи и упражнения по математической логике и теории алгоритмов. М. Академия. 2005.- 304 с.