Рабочая программа по дисциплине «дискретная математика» для специальности



Скачать 359.54 Kb.
страница3/3
Дата22.12.2012
Размер359.54 Kb.
ТипРабочая программа
1   2   3

Программа практических занятий


Краткое описание технологии занятий. Занятия проводятся с группой под

руководством преподавателя и состоят в решении задач по каждой теме и

разбором их.

Тема 1. Основы формальных языков
Задачи на формализацию высказываний естественного языка.

Тема 2. Язык исчисления высказываний
Задачи на построение таблиц истинности, сокращенных таблиц истинности и

семантических таблиц Бета.

Тема 3. Язык исчисления предикатов
Задачи на формализацию математических утверждений с помощью языка

узкого исчисления предикатов.

Тема 4. Логико-предметные языки
Формулирование математических утверждений на специализированных

логико-предметных языках.

Тема 5. Логический вывод
Построение доказательств формул исчисления высказываний, исчисления

предикатов.

Тема 6. Аксиоматика формальных предметных теорий
Построение формул, однозначно определяющих математические операции.

Тема 7. Язык теории множеств
Формулирование математических утверждений на языке теории множеств.

Тема 8. Наивная теория множеств
Запись выражений, задающих математические объекты, на языке теории

множеств.

Тема 9. Аксиомы теории множеств
Построение формул, однозначно определяющих операции с множествами.

Тема 10. Отношения и функции в теории множеств
Определение математических отношений и функций на языке теории

множеств.

Тема 11. Упорядочения
Построение упорядочений с заданными свойствами.

Тема 12. Эквивалентности и разбиения
Построение эквивалентностей и разбиений с заданными свойствами.

Тема 13. Алгебры и алгебраические системы
Построение алгебраических систем с заданными свойствами.


  1. Программа самостоятельной работы студента


Первый семестр.

Неделя Форма контроля

1

2 Выдача индивидуального контрольного домашнего задания 1

3

4 Прием индивидуального контрольного домашнего задания 1

5

6 Выдача индивидуального контрольного домашнего задания 2

7

8 Прием индивидуального контрольного домашнего задания 2

9

10 Выдача индивидуального контрольного домашнего задания 3

11

12 Прием индивидуального контрольного домашнего задания 3

13

14 Выдача индивидуального контрольного домашнего задания 4

15

16 Прием индивидуального контрольного домашнего задания 4

17

18 Зачетная контрольная работа.



  1. Контролирующие материалы


8.1. Вопросы текущего тестирования
8.1.1.
Записать в виде формул логико-предметного языка,

используя указанные в скобках предикаты и функции:

8.1.1.1. Все люди смертны (Ч(), С()).

8.1.1.2. Если все люди смертны и Сократ человек, то Сократ смертен.

8.1.1.3. Гена - самый лучший в мире крокодил (K(), Л(,)).

8.1.1.4. Для любого вещественного числа найдется большее его натуральное

число (R(x), N(x)).

8.1.1.5. Функция возведения в квадрат непрерывна (x**2, |x|, x-y, меньше).

8.1.1.6. Существуют рациональные числа, сколь угодно близкие к нулю.
8.1.2. Контрольные вопросы

8.1.2.1. Подходит ли формула P(1) => Ax P(x) под схему A=>B?

8.1.2.2. Подходит ли формула P() => P() под схему B=>A?

8.1.2.3. Подходит ли формула P() = Q() под схему A=>A?

8.1.2.4. Применимо ли правило Ax (A(x)=>B) |- Ex A(x) => B

к формуле Ap (P(x) => P(x))?
8.1.3. Контрольные вопросы

8.1.3.1. Какие множества совпадают:

0, {0}, {0,0}, 1, {0,1}, {1,0}, 2, {1,2}, 3, {0,1,2}, 1 U 2?

8.1.3.2. Сколько элементов в множествах:

{{0,0},{0,0}}, {{0}}, {{0,0}}, {{0},{0}}, {0,{0}}.
8.1.4. Всегда ли выполнено

8.1.4.1. (a,b) = (b,a) => a = b?

8.1.4.2. {(a,b),(b,a)} = {(b,a),(a,b)}?

8.1.4.3. {(a,b)} = {(b,a)}?

8.1.4.4. {(x,x),(y,y)} = {(x,y),(x,y)}?

8.1.4.5. {0,3}x{1,4}?

8.1.4.6. 2x3?
8.1.5. Вопросы

8.1.5.1. Построить наименьший частичный порядок, содержащий

{(1,2),(2,3),(4,3)}.

8.1.5.2. Построить наименьшее отношение эквивалентности,

содержащее

{(1,2),(3,4)}.

8.1.5.3. Построить для отношения эквивалентности из п. 2

соответствующие классы эквивалентности.
8.1.6. Являются ли функциями следующие отношения?

8.1.6.1. {(0,1),(0,2)}.

8.1.6.2. {(1,0),(2,0)}
8.1.7. Являются ли взаимно-однозначными соответствиями следующие

отношения?

8.1.7.1. {(0,1),(0,2)}.

8.1.7.2. {(1,0),(2,0)}

8.1.7.3. {(0,1),(1,0)}.

8.1.7.4. {(0,2),(1,2)}.

8.1.7.5. {(0,0),(1,1)}.
8.1.8. Построить взаимно-однозначное соответствие между множествами

3 и {1,3,5}.
8.1.9. Равномощны ли множества 0 и {0}?
8.1.10. Чему равно:

8.1.10.1. (0,1) +цел (0,1)

8.1.10.2. (1,2) -цел (1,3)

8.1.10.3. (1,2) *цел (0,2)

8.1.10.4. ((0,1),2) + ((1,1),3)

8.1.10.5. ((0,2),3) * ((1,2),3)
8.1.11. Пусть p=R(O,I32), q=I22 o R(O, I32), m=R(I11, p o I33).

Чему равно:

8.1.11.1. p(3,0)

8.1.11.2. p(2,1)

8.1.11.3. q(0)

8.1.11.4. q(2)

8.1.11.5. m(2,0)

8.1.11.6. m(2,1)

8.1.11.7. m(1,2)
8.1.12. Написать программу машины Тьюринга для сложения нескольких

чисел в монадической ("палочковой") системе счисления, разделенных

знаком "+".
8.1.13. Что делает машина Тьюринга

aq> qqr

bq> qqqr

q>1s

aqq>aqqr

bqq>bqqr

aqqq>aqqqr

bqqq>bqqqr

qq> qqqql

qqq> qqqqql

aqqqq> qqqqqql

bqqqqq> qqqqqql

aqqqqq> qqqqqqql

bqqqq> qqqqqqql

qqqq>1s

qqqqq>1s

aqqqqqq>aqqqqqql

bqqqqqq>bqqqqqql

aqqqqqqq> qqqqqqql

bqqqqqqq> qqqqqqql

qqqqqq> qr

qqqqqqq>0s

со словами: "", "a", "ba", "aba", "abba", "baba"?"
8.1.14. Что делает алгоритм

f(ex','ee)=ex':'f(ee);

f(ee)=ee;
f('a,b')=?, f('a')=?, f('a,b,c')=?
8.1.15. Сколько слов длины 5 в алфавите из 10 символов?
8.1.16. Сколько слов длины 16 в алфавите из 2 символов?
8.1.17. Сколькими способами можно разбить 6-элементное множество

на 3 непустых подмножества.
8.1.18. Сколько существует логических функций от

4 логических переменных?

8.1.19. Сколько существует логических функций от

логических функций от 2-х переменных?

8.1.20. Сколько существует логических функций от пар

логических функций от 2-х переменных?
8.1.21. Перечислите все монотонные логические функции 2-х аргументов.
8.1.22. Замкнуты ли классы

8.1.22.1. Логических функций, ограниченных сверху дизъюнкцией всех своих

аргументов?

8.1.22.2. - - - снизу конъюнкцией всех своих аргументов?

8.1.22.3. - - - сверху одним из своих аргументов?

8.1.22.4. - - - снизу - - - - ?

8.1.22.5. - - - сверху первым аргументом?

8.1.22.6. - - - снизу - - ?

8.1.22.7. - - - сверху последним - ?

8.1.22.8. - - - снизу - - ?

8.1.22.9. - - равных конъюнкции аргументов, от которых они зависят?

8.1.22.10. - - - дизъюнкции - - - - - ?
8.1.23. Сколько существует классов изоморфных мультиграфов с двумя

вершинами?


  1. Теоретические вопросы


1. Алфавит, слова, выражения, предложения, логические языки.

2. Алгебра логики, функции, таблицы истинности.

3. Исчисление высказываний, определение языка формул.

4. Интерпретация, истинность, тавтологии, выполнимые формулы, модели.

5. Язык исчисления предикатов 1-го порядка.

6. Интерпретация, истинность формул на заданной интерпретации.

7. Выполнимость и общезначимость формулы 1-го порядка, модели.

8. Язык арифметики натуральных чисел.

9. Язык теории слов в конечном алфавите.

10. Общее понятие логического вывода и выводимой (доказуемой) формулы.

11. Структура логического вывода в естественной форме записи.

12. Системы аксиом и правила вывода.

13. Правила вывода исчисления высказываний для естественной формы записи.

14. Правила введения и правила удаления.

15. Теорема о полноте исчисления высказываний.

16. Правила вывода для исчисления предикатов.

17. Введение и удаление кванторов.

18. Полнота исчисления предикатов.

19. Узкое исчисление предикатов с равенством.

10. Аксиомы и схемы аксиом равенства.

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. Элементарные функции, множества и отношения

71. Графы.

72. Изоморфизм графов.

73. Связность графов.

74. Планарность графов.

75. Деревья.

76. Алгоритмы обхода вершин графа.

77. Перестановки, размещения, сочетания, сочетания с повторениями.

78. Рекуррентные соотношения в комбинаторике.

79. Производящая функция, бином Ньютона.

80. Алгоритмы генерирования комбинаторных объектов.

81. Дизъюнктивная нормальная форма, совершенная ДНФ

82. Принцип двойственности для логических функций.

83. Полнота и замкнутость систем логических функций.

84. Алфавитное кодирование.

85. Помехоустойчивое кодирование.

86. Методы сжатия информации с помощью кодирования.

87. Применение кодирования для защиты информации.

Примеры (образцы) зачётных задач

01. Сформулировать на ЯУИП (U - люди) "Некоторые студенты

[С(x)] получили зачет [З(студент,предмет)] по всем предметам

[П(x)], которые они изучали [И(студент,предмет)].
02. Сформулировать на ЯУИП (U - люди) "Все студенты

[С(x)] получили зачет [З(студент,предмет)] по некоторым предметам

[П(x)], которые они изучали [И(студент,предмет)].
03. Сформулировать на ЯУИП (U - люди) "Все студенты

[С(x)] получили зачет [З(студент,предмет)] по всем предметам

[П(x)] которые они изучали [И(студент,предмет)].
04. Сформулировать на ЯУИП (U - люди) "Некоторые студенты

[С(x)] получили зачет [З(студент,предмет)] по некоторым предметам

[П(x)], которые они изучали [И(студент,предмет)].
05. Сформулировать на ЯУИП (U - люди) "По всем предметам

[П(x)] получили зачет [З(студент,предмет)] некоторые студенты

[П(x)], которые их изучали [И(студент,предмет)].
06. Сформулировать на ЯУИП (U - люди) "По некоторым предметам

[П(x)] получили зачет [З(студент,предмет)] все студенты

[П(x)], которые их изучали [И(студент,предмет)].
07. При каких интерпретациях истинна формула

Ax(C(x)=>EyB(x,y))&EzC(z)=>EtEuB(t,u)?
08. При каких интерпретациях истинна формула

Ax(D(x)=>B(x)\/C(x))&EyD(y)=>EzB(z)\/EuC(u)?
09. При каких интерпретациях истинна формула

Ax(D(x)=>B(x)&C(x))&EyD(y)=>EzB(z)&EuC(u)?
10. При каких интерпретациях истинна формула

Ax(C(x)=>AyB(x,y))&EzC(z)=>EuAvB(u,v)?
11. При каких интерпретациях истинна формула

Ax(C(x)=>EyB(x,y))&EzAu~B(z,u)=>Ev~C(v)?
12. При каких интерпретациях истинна формула

Ax(D(x)=>B(x)\/C(x))&Ez(B(z)\/~C(z))=>Eu~D(u)?
13. При каких интерпретациях истинна формула

Ax(D(x)=>B(x)&C(x))&EyD(y)&Ey~B(y)&Ez~C(z)=>Eu~D(u)?
14. При каких интерпретациях истинна формула

Ax(C(x)=>AyB(x,y))&EzEu~B(z,u)=>Ev~C(v)?
15. Найти {1,2,3}x{4,1}.
16. Найти P({1,3}).
10.4.17. Найти {1,3}^{2,1}.
10.5.18. Найти минимальное отношение строгого частичного порядка,

содержащее {(2,1),(1,3),(1,4)}.
10.5.19. Найти минимальное отношение нестрогого частичного порядка,

содержащее {(2,1),(1,3),(1,4)}.
10.5.20. Найти минимальное отношение строгого линейного порядка,

содержащее {(2,1),(1,3),(1,4)}.
10.5.21. Найти минимальное отношение нестрогого линейного порядка,

содержащее {(2,1),(1,3),(1,4)}.
10.5.22. Использовав функциональные символы f, g и предикаты

Меньше и =,

записать в виде формулы ЛПЯ утверждение: Все локальные максимумы

функции f больше всех локальных максимумов g.
10.5.23. Использовав функциональные символы f, g и предикаты Меньше и =,

записать в виде формулы ЛПЯ утверждение: на всех тех отрезках, на

которых функция f убывает, функция g возрастает.
10.5.24. Использовав функциональные символы f, g и предикаты Меньше и =,

записать в виде формулы ЛПЯ утверждение: множества значений f и g

совпадают.
10.5.25. Использовав функциональные символы f, g и предикаты Меньше и =,

записать в виде формулы ЛПЯ утверждение: Каждое значение f больше

некоторого значения g.
10.5.26. Использовав функциональные символы f, g и предикаты Меньше и =,

записать в виде формулы ЛПЯ утверждение: между любыми двумя

значениями f есть хотя бы одно значение g.
10.5.27. Использовав функциональные символы f, g и предикаты Меньше и =,

записать в виде формулы ЛПЯ утверждение: между любыми локальными

максимумами функции f есть локальный максимум функции g.



  1. Список литературы (основная, дополнительная)


. Основная литература
1. Гаврилов Г.П., Сапоженко А.А. "Сборник задач по дискретной

математике": Учеб.пособие. М.: Наука, 1977-1992. 408 с.
2. Ершов Ю.Л. и др. "Математическая логика", 1973-1987 и далее.
3. Иложарский В.К. "Математическая логика и алгоритмы", 1970.
4. Карпов В.Г., Нощенский В.А. "Математическая логика и дискретная

математика", 1977.
5. Колмогоров А.Н., Драгалин "Введение в математическую логику",

1982.
6. "Математическая логика" / Ред. Столяр А.А., 1991.
7. Мендельсон Э. "Введение в математическую логику", 1971-1984 и

далее.
8. Непейвода Н.Н. "Прикладная логика": Учебное пособие, Ижевск, Изд-во

УдГУ, 1997, 384с.
9. Нефедов В.Н., Осипова В.А. "Курс дискретной математики", 1992
10. Шенфилд Д. "Математическая логика", 1975.
11. Эдельман С.Л. "Математическая логика", 1975.


Дополнительная литература

1. Александров П.С. "Введение в теорию множеств и общую

топологию", 1977.
2. Верещагин Н.К., Шень А. "Начала теории множеств", 1999.
3. Верещагин Н.К., Шень А. "Языки и исчисления", 2000
4. Клини С.К. "Математическая логика", 1973.
5. Колмогоров А.Н., Драгалин "Математическая логика,

дополнительные главы", 1984.
6. Косовский Н.К. "Основы теории элементарных алгоритмов", 1987.
7. Косовский Н.К., Тишков А.В. "Логики конечнозначных

предикатов на основе неравенств", СПб, 2000.
8. Чень Ч., Ли Р. "Математическая логика и автоматическое

доказательство теорем", 1983.
9. Яблонский С.В. Введение в дискретную математику: Учеб.пособие.

М.: Наука, 1986. 384 с.

10. Кристофидес Н. Теория графов:алгоритмический подход. - М.: Мир,

1978.

Другие учебно-методические материалы
Материалы по лекциям (А.П.Бельтюков):

URL:http://ulm.uni.udm.ru/~belt/apbmatlo.txt

URL:http://ulm.uni.udm.ru/~belt/apblogic.txt

URL:http://ulm.uni.udm.ru/~belt/apblogir.txt

URL:http://ulm.uni.udm.ru/~belt/discmatq.txt

URL:http://ulm.uni.udm.ru/~belt/work-pgm/clac.htm
1   2   3

Похожие:

Рабочая программа по дисциплине «дискретная математика» для специальности iconРабочая программа по дисциплине «дискретная математика» для специальности
Рабочая программа составлена на основании гос впо 010200 – Прикладная математика и информатика, утвержденного в 2000 г
Рабочая программа по дисциплине «дискретная математика» для специальности iconРабочая учебная программа по дисциплине «Дискретная математика» для специальности «050201 Математика»
Рабочая учебная программа обсуждена на заседании кафедры алгебры и теории чисел Ургпу
Рабочая программа по дисциплине «дискретная математика» для специальности iconУчебная программа для специальности: (рабочий вариант) 1-310301-02 Математика
Рабочая программа составлена на основе учебной программы по дисциплине “Дискретная математика”, утверждённой 05. 09. 2008
Рабочая программа по дисциплине «дискретная математика» для специальности iconРабочая учебная программа по дисциплине «Дискретная математика» для ооп «010400 Прикладная математика и информатика»

Рабочая программа по дисциплине «дискретная математика» для специальности iconРабочая учебная программа по дисциплине «Элементарная математика» для специальности «050201 Математика» по циклу дпп. Ф. 13 -дисциплины предметной подготовки
Рабочая программа обсуждена на заседании кафедры методики преподавания математики
Рабочая программа по дисциплине «дискретная математика» для специальности iconРабочая учебная программа по дисциплине «Геометрия» для специальности «050201 Математика»
Программа предназначена для работы со студентами, обучающимися по специальности «050201 Математика». Программа составлена на основе...
Рабочая программа по дисциплине «дискретная математика» для специальности iconРабочая программа по дисциплине «Дискретная математика»

Рабочая программа по дисциплине «дискретная математика» для специальности iconРабочая программа по дисциплине «Математика» для специальности
Рабочая программа составлена на основании Государственного образовательного стандарта высшего профессионального образования по специальности:...
Рабочая программа по дисциплине «дискретная математика» для специальности iconРабочая программа по дисциплине "Дискретная математика" для специальности 230105 (220400)
Гос во по направлению 654600 Информатика и вычислительная техника (специальность 230105 (220400) – “Программное обеспечение вычислительной...
Рабочая программа по дисциплине «дискретная математика» для специальности iconРабочая программа по математике для специальности 270800
Рабочая программа по дисциплине “Математика” составлена для студентов специальности 270800 в соответствии с требованиями государственного...
Разместите кнопку на своём сайте:
ru.convdocs.org


База данных защищена авторским правом ©ru.convdocs.org 2016
обратиться к администрации
ru.convdocs.org