x-uni.com
x-uni.com
x-uni.com
Математика
Биология
Литература
Русский язык
География
Физика
Химия
История
Английский
Информатика
География
Информатика
Лекции по математической логике и теории алгоритмов, Часть 3, Вычислимые функции, Верещагин Н.К., Шень А., 2012

Лекции по математической логике и теории алгоритмов, Часть 3, Вычислимые функции, Верещагин Н.К., Шень А., 2012

Лекции по математической логике и теории алгоритмов, Часть 3, Вычислимые функции, Верещагин Н.К., Шень А., 2012.

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

Вычислимые функции.
Функция f с натуральными аргументами и значениями называется вычислимой, если существует алгоритм, ее вычисляющий, то есть такой алгоритм A, что
• если f(n) определено для некоторого натурального n, то алгоритм А останавливается на входе п и печатает f(n);
• если f(п) не определено, то алгоритм А не останавливается на входе п.

Несколько замечаний по поводу этого определения:
1. Понятие вычислимости определяется здесь для частичных функций (областью определения которых является некоторое подмножество натурального ряда). Например, нигде не определённая функция вычислима (в качестве А надо взять программу, которая всегда зацикливается).

2. Можно было бы изменить определение, сказав так: «если f(n) не определено, то либо алгоритм А не останавливается, либо останавливается, но ничего не печатает». На самом деле от этого ничего бы не изменилось (вместо того, чтобы останавливаться, ничего не напечатав, алгоритм может зацикливаться).

3. Входами и выходами алгоритмов могут быть не только натуральные числа, но и двоичные строки (слова в алфавите {0,1}), пары натуральных чисел, конечные последовательности слов и вообще любые, как говорят, «конструктивные объекты». Поэтому аналогичным образом можно определить понятие, скажем, вычислимой функции с двумя натуральными аргументами, значениями которой являются рациональные числа.

Оглавление
Предисловие
1. Вычислимость, разрешимость и перечислимость
1.1. Вычислимые функции
1.2. Разрешимые множества
1.3. Перечислимые множества
1.4. Перечислимые и разрешимые множества
1.5. Перечислимость и вычислимость
2. Универсальные функции и неразрешимость
2.1. Универсальные функции
2.2. Диагональная конструкция
2.3. Перечислимое неразрешимое множество
2.4. Перечислимые неотделимые множества
2.5. Простые множества: конструкция Поста
3. Нумерации и операции
3.1. Главные универсальные функции
3.2. Вычислимые последовательности функций
3.3. Главные универсальные множества
4. Свойства главных нумераций
4.1. Множества номеров
4.2. Однозначные нумерации
4.3. Новые номера старых функций
4.4. Изоморфизм главных нумераций
4.5. Перечислимые свойства функций
5. Теорема о неподвижной точке
5.1. Неподвижная точка и отношения эквивалентности
5.2. Программа, печатающая свой текст
5.3. Системный трюк: ещё одно доказательство
5.4. Несколько замечаний
6. m-сводимость и свойства перечислимых множеств
6.1. m-сводимость
6.2. m-полные множества
6.3. m-полнота и эффективная неперечислимость
6.4. Изоморфизм неполных множеств
6.5. Продуктивные множества
6.6. Пары неотделимых множеств
7. Вычисления с оракулом
7.1. Машины с оракулом
7.2. Эквивалентное описание
7.3. Релятивизация
7.4. 0' - вычисления
7.5. Несравнимые множества
7.6. Теорема Мучника Фридберга: общая схема
7.7. Теорема Мучника Фридберга: выигрышные условия
7.8. Теорема Мучника Фридберга: метод приоритета
7.9. Решётка Медведева
8. Арифметическая иерархия
8.1. Классы Σn и Пn
8.2. Универсальные множества в Σn и Пn
8.3. Операция скачка
8.4. Классификация множеств в иерархии
9. Машины Тьюринга
9.1. Зачем нужны простые вычислительные модели?
9.2. Машины Тьюринга: определение
9.3. Машины Тьюринга: обсуждение
9.4. Ассоциативные исчисления
9.5. Моделирование машин Тьюринга
9.6. Двусторонние исчисления
9.7. Полугруппы, образующие и соотношения
10. Арифметичность вычислимых функций
10.1. Программы с конечным числом переменных
10.2. Машины Тьюринга и программы
10.3. Арифметичность вычислимых функций
10.4. Теоремы Тарского и Геделя
10.5. Прямое доказательство теорем Тарского и Гёделя
10.6. Арифметическая иерархия и перемены кванторов
11. Рекурсивные функции
11.1. Примитивно рекурсивные функции
11.2. Примеры примитивно рекурсивных функций
11.3. Примитивно рекурсивные множества
11.4. Другие виды рекурсии
11.5. Машины Тьюринга и рекурсивные функции
11.6. Частично рекурсивные функции
11.7. Вычислимость с оракулом
11.8. Оценки скорости роста. Функция Аккермана
Литература
Предметный указатель
Указатель имён.

Предложения интернет-магазинов

Рекурсивные функции

Автор(ы): Марченков Сергей Серафимович   Издательство: Физматлит, 2007 г.

Цена: 293 руб.   Купить

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


Математическая культура учителя информатики. Теоретико-методический аспект. Монография

Автор(ы): Мирзоев Махмашариф Сайфович   Издательство: Прометей, 2015 г.

Цена: 585 руб.   Купить

В монографии рассмотрены проблемы развития математического образования будущего учителя информатики в свете формирования математической культуры. Исследование математической культуры учителя информатики рассматривается в контексте развития математики в областях дискретной математики, математической логики, теории алгоритмов, информационного моделирования. Существенное внимание уделено интеграции предметных областей "Информатика" и "Математика". Определены и обоснованы структура и содержание математических дисциплин дискретного блока с учетом интеграции предметных областей "Математика" и "Информатика" и основных аспектов развития общеобразовательного курса информатики. Представлено учебно-методическое обеспечение формирования математической культуры будущего учителя информатики на базе ИКТ. Монография адресована научным сотрудникам, преподавателям, аспирантам, студентам педагогических вузов, учителям, слушателям факультетов повышения квалификации, другим специалистам, заинтересованным исследованием проблемы математической культуры.


Математика. Теория вероятностей и дискретная математика: Элементы теории, решение задач

Автор(ы): Баюк Олег Александрович, Маркарян Елена Георгиевна   Издательство: Просвещение, 2013 г.  Серия: Сложные темы ЕГЭ

Цена: 377 руб.   Купить

Пособие предназначено учащимся общеобразовательных учреждений (школ, гимназий, колледжей) для углублённого изучения теории вероятностей и связанных с ней разделов дискретной математики (теории множеств, математической логики, комбинаторики, теории графов и математической статистики) в целях успешной сдачи ЕГЭ по математике. В пособии изложены основные теоретические сведения, необходимые для решения задач, приводятся решения типичных заданий ЕГЭ, а также содержатся задания для самостоятельной работы (с ответами, указаниями к решению или решениями). Книга может быть использована в качестве сборника задач на подготовительных курсах, факультативных занятиях, при самостоятельной подготовке к поступлению в вуз и при последующем обучении в вузе.


Теоретическая фонетика английского языка. Лекции, семинары, упражнения. Учебное пособие

Автор(ы): Евстифеева Марина Владимировна   Издательство: Флинта, 2012 г.

Цена: 256 руб.   Купить

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