Раздел 8. Вычислимые функции . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75

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

Методы построения машин Тьюринга . . . . . . . . . . . . . . . . . . . . . . . . . . . 79

Описание технологии программирования для машин Тьюринга. . . . . . . 84

Вычислимые функции . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87

Операции С, Пр и µ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90

Классы вычислимых и рекурсивных функций . . . . . . . . . . . . . . . . . . . . . 93

Эквивалентность класса рекурсивных функций и функций, вычислимых

на машинах Тьюринга . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94

Задания для самостоятельной работы . . . . . . . . . . . . . . . . . . . . . . . . . . . 96

Раздел 9. Теория кодирования . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100

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

Критерий однозначности декодирования . . . . . . . . . . . . . . . . . . . . . . . . .102

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

Самокорректирующиеся коды. Коды Хэмминга . . . . . . . . . . . . . . . . . . . 114

Задания для самостоятельной работы . . . . . . . . . . . . . . . . . . . . . . . . . . . .119

Литература . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122

Введение

Дискретная математика – часть математики, которая зародилась в глубокой древности. Главной её спецификой является дискретность, т.е. антипод непрерывности.

В широком смысле дискретная математика включает в себя и такие сложившиеся разделы математики, как теория чисел, алгебра, математическая логика и ряд разделов, которые наиболее интенсивно стали развиваться в середине 20 века в связи с внедрением ЭВМ.

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

криптография и т.п. Теория функциональных систем включает в себя алгебру логики; конечнозначную логику; ограниченно-детерминированные (автоматные) функции; вычислимые функции.

Дискретная математика сегодня является не только фундаментом математической кибернетики, но и важным звеном математического образования. Главной задачей курса дискретной математики является обучение методам и мышлению, характерным для дискретной математики. Материал курса дискретной математики подобран таким образом, чтобы сократить число необходимых понятий до минимума и, с другой стороны, дать небольшое количество (10-15) серьезных теорем с непохожими доказательствами, а также познакомить с применениями понятия алгоритма, владение которым особенно важно для специалистов в области прикладной математики.

В основу данного курса дискретной математики положен курс, который впервые был прочитан С.В.Яблонским (научным руководителем лектора данного курса) на механико-математическом факультете МГУ имени М.В.Ломоносова в 1964 году, с определенными изменениями, связанными с течением времени, бурным развитием вычислительной техники и появлением новых и новых специальностей, для которых дискретная математика является обязательным курсом.

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

1. Элементы теории множеств.

2. Элементы комбинаторики.

3. Алгебра логики.

4. Синтез схем из функциональных элементов.

5. Графы.

6. Элементы математической логики.

7. Конечнозначная логика.

8. Ограниченно-детерминированные (автоматные) функции.

9. Вычислимые функции.

10. Теория кодирования.

11. Криптография. Первые пять разделов читаются в первом семестре, остальные разделы - во втором.