RUS ENG

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

Мощенский А.В. Математические основы информатики : пособие для студентов спец. 1-31 03 04 «Информатика» / А. В. Мощенский, В. А. Мощенский. — 2-е изд., перераб. и доп. — Минск : БГУ, 2008. — 155 с. :ил.

ISBN 978-985-485-916-3

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

Во втором издании были исправлены допущенные неточности и переработаны некоторые разделы.

Предназначено для студентов факультета прикладной математики и информатики БГУ.


Оглавление

От авторов

3

1. ЯЗЫК ТЕОРИЙ ПЕРВОГО ПОРЯДКА

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

4

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

16

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

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

23

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

26

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

29

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

31

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

33

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

37

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

38

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

42

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

45

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

50

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

55

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

61

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

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

73

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

75

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

77

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

79

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

81

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

82

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

85

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

90

4. АЛГОРИТМЫ

 

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

93

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

95

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

98

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

101

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

104

4.6. Классы Ч и Т

109

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

111

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

113

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

117

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

119

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

125

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

130

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

134

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

138

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

139

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

146

ЛИТЕРАТУРА

151

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