Обложка Шиханович Ю.А. Минимум по теории алгоритмов: Для нематематиков
Id: 273189
314 руб.

Минимум по теории алгоритмов:
Для нематематиков Изд. 2

URSS. 2021. 152 с. ISBN 978-5-9710-8961-2.

Аннотация

В предлагаемом учебном пособии изложены самые начала теории алгоритмов — во-первых, базисные понятия теории алгоритмов: предписание (исходное неопределяемое понятие), перечислимое множество, алгоритм, вычислимая функция, разрешимое множество и, во-вторых, один из формальных универсальных языков для записи предписаний, работающих со словами, — машины Тьюринга.

Пособие предназначено для нематематиков и для его чтения не требуется никаких предварительных... (Подробнее)


Содержание
Оглавление3
Предисловие7
Введение. Сигнифика9
1. Буква9
2. Алфавит11
3. Слово12
4. Конструктивный объект19
Глава I. Общая теория алгоритмов23
§ 1. Предписания24
§ 2. Перечислимые множества30
1. Перечислимое множество30
2. Операции над перечислимыми множествами31
3. Существование не перечислимого множества натуральных чисел33
4*. Относительная перечислимость36
§ 3. Алгоритмы38
1. Алгоритм38
2. Алгоритмы и перечислимые множества42
3. Каноническое задание (разложение) программы алгоритма43
§ 4. Вычислимые функции46
1. Вычислимая функция46
2. Существование не вычислимой всюду определенной функции типа N ( N49
3. Вычислимые функции и алгоритмы50
4. Вычислимые функции и перечислимые множества51
§ 5. Разрешимые множества54
1. Разрешимое множество54
2. Операции над разрешимыми множествами56
3. Вычислимые функции и разрешимые множества58
4. Множество, разрешимое относительно перечислимого надмножества60
5. Разрешимые и перечислимые множества61
6*. Разрешимые и относительно перечислимые множества62
Глава II. Машины Тьюринга65
§ 1. Тьюринговы алгоритмы65
1. Тьюрингов алгоритм65
2. Вычисление «арифметических» функций на машинах Тьюринга76
3. Принцип тьюрингизации78
§ 2. Кодирование тьюринговых алгоритмов81
1. Кодирование тьюринговых алгоритмов81
2. Пример не перечислимого множества натуральных чисел83
3. Универсальная машина Тьюринга84
§ 3. Алгоритмически неразрешимые проблемы87
1. Алгоритмически неразрешимые проблемы87
2. Существование перечислимого не разрешимого множества91
3. Нераспознаваемые свойства92
ДОПОЛНЕНИЯ99
Глава III. Нормальные алгорифмы101
Глава IV. Рекурсивные функции105
Глава V. Универсальная функция113
Глава VI. Нумерационная теория алгоритмов117
§ 1. Основные понятия117
§ 2. Нумерации класса  и наследственные нумерации122
ПРИЛОЖЕНИЯ129
1. Две теоремы о натуральных числах131
2. Три определения133
3. Программа135
Примечания143
Упомянутая литература145
Указатель терминов146
Указатель обозначений 150152

Об авторе
Шиханович Юрий Александрович
Кандидат педагогических наук. В 1955 г. окончил механико-математический факультет МГУ имени М. В. Ломоносова. В 1955–1957 гг. преподавал в Московском авиационном институте (МАИ) и Московском энергетическом институте (МЭИ), работал в Лаборатории электромоделирования АН СССР. В 1960–1968 гг. преподавал математику на Отделении структурной и прикладной лингвистики филологического факультета МГУ. В 1968–1972 гг. работал инженером в Специальном конструкторском бюро биофизической аппаратуры и электронных машин, в 1975–1983 гг. — редактором в журнале «Квант». С 1995 по 2011 гг. преподавал в Российском государственном гуманитарном университете (РГГУ) математику студентам-лингвистам.

Ю. А. Шиханович стал одним из тех, кто вел в СССР пропаганду и преподавание современной математики. Он был редактором книги В. А. Успенского «Лекции о вычислимых функциях», изданной в серии «Математическая логика и основания математики», и, по свидетельству автора, «без его помощи эта книга, вероятно, не была бы написана». Вместе с Г. Н. Поваровым он перевел на русский язык книгу коллектива французских математиков, объединившихся под псевдонимом Н. Бурбаки: «Начала математики: Основные структуры анализа». В 1965 г. им была опубликована книга «Введение в современную математику: Начальные понятия» (в 1967 г. книга была издана в Японии). В 2005 г. вышла книга «Введение в математику» — переработанное и дополненное переиздание книги 1965 г. Он также опубликовал следующие книги: «Группы, кольца, решетки» (книга по алгебре) (2006), «Минимум по теории алгоритмов для нематематиков» (2009), «Начальные главы математического анализа в полуформальном изложении» (2010), «Логические и математические исчисления» (2011).