RUS ENG

Мощенский А. В. Математические основы информатики

Мощенский А. В. Математические основы информатики: Пособие для студентов специальности G 31 03 04 «Информатика» / А. В. Мощенский, В. А. Мощенский. -Мн., БГУ, 2002. - 150 с.

ISBN 98—445-564-5

Пособие включает важные дискретные разделы математики, лежащие в основе информатики. Излагаются логико-математический язык, основы комбинаторики и теории формальных грамматик, математические основы алгоритмов с уклоном на современные проблемы.

Предназначено для студентов университета, изучающих информатику.


Оглавление

Предисловие

3

1. Я3ЫК ТЕОРИЙ ПEPBOГО ПОРЯДКА

4

1.1. Язык, логики высказываний

4

l.1.1. Логические операции

5

1.1.2. Основные равносильности. Тавтологии

7

1.1.3. Логическое следствие

10

1.2. Язык логики предикатов первого порядка

15

l.2.1. Формулы логики предикатов первого порядка. Интерпретации

16

1.2.2. Равносильные формулы. Приведенная и нормальная формы

20

2. ЭЛЕМЕНТЫ ТЕОРИИ МНОЖЕСТВ И КОМБИНАТОРИКИ

22

2.1. Множества, способы их задания. Подмножества

22

2.2. Операции над множествами. Основные равенства

25

2.3. Упорядоченная пара. Декартово произведение множеств. Отношения

28

2.4. Свойства бинарных отношений. Отношение эквивалентности

29

2.5. Функции. Счетные множества

32

2.6. Размещения и размещения с повторениями

36

2.7. Сочетания и сочетания с повторениями

37

2.8. Формула бинома Ньютона

41

2.9. Рекуррентные соотношения и их решения

44

2.10. Формула включений и исключений

49

2.11. Производящие функции

54

2.12. Неориентированные графы

60

3. ФОРМАЛЬНЫЕ ГРАММАТИКИ И ЯЗЫКИ

69

3.1. Основные понятия

69

3.2. Важнейшие примеры грамматик

72

3.3. А-грамматики и автоматы

74

3.4. Некоторые свойства грамматик

75

3.5. Иерархия языков

77

3.6. Грамматический разбор

79

3.7. КС-языки и синтез языков программирования

82

3.8. Аксиоматические грамматики

85

4. АЛГОРИТМЫ

87

4.1. Индуктивное понятие алгоритма и необходимость его уточнения

87

4.2. Машины Тьюринга

89

4.3. Функции, вычислимые по Тьюрингу. Тезис Тьюринга

93

4.4. Операции над машинами Тьюринга

96

4.5. Частично-рекурсивные функции (класс Ч)

99

4.6. Классы Ч и Т

104

4.7. Одна просто определяемая невычислимая функция

106

4.8. Алгоритмические неразрешимые проблемы

108

4.9. Универсальные машины Тьюринга и функции1

111

4.10. Некоторые общие теоремы теории алгоритмов

114

4.11. k –Ленточные машины Тьюринга,  (детермированные и недетермированные)

120

4.12. Классы P и N Р . Проблема P =?NP . -полные и -трудные проблемы

125

4.13. О машинно-независимой теории сложности вычислений

130

4.14. Перечисление рекурсивно-перечислимых множеств

134

4.15. Конечные автоматы

135

4.15.1. Автоматы Мура и Мили

136

4.15.2. Эквивалентность автоматов Мили и Мypa

137

4.15.3. Множества слов, вычислимые в реальное время

139

4.16. Приближенные (эвристические) алгоритмы

140

4.16.1.Оценки качества приближенных алгоритмов

142

4.16.2. Примеры приближенных алгоритмов

144

ЛИТЕРАТУРА

147

Другие сайты факультетаСтруктураОбразованиеМагистратураНаукаМеждународное сотрудничествоСтудентуНИРСАСовет молодых ученыхОлимпиадыАбитуриентуШкольникуЦентр
Компетенций
по ИТ
Microsoft
Imagine Premium
ИсторияИздания факультетаПрофбюро ФПМИПерсональные страницыФотогалереи Газета ФПМыНаши партнеры