x-uni.com
регистрация / вход
сейчас на линии 25 чел.
x-uni.com
x-uni.com
 
Математика
Биология
Литература
Русский язык
ВИДЕО
Физика
Химия
История
Английский
 
ВИДЕО
 
 
регистрация / вход
сейчас на линии 25 чел.
Лекции по математической логике и теории алгоритмов, Часть 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. Оценки скорости роста. Функция Аккермана
Литература
Предметный указатель
Указатель имён.

Скачать бесплатно на сайте fileskachat.com

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

Математика для гуманитариев: задачи и решения

Автор(ы): Просветов Георгий Иванович   Издательство: Альфа-Пресс, 2008 г.

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

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


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

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

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

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


События. Вероятности. Статистическая обработка данных: Доп. параграфы к курсу алгебры 7-9 классов

Автор(ы): Мордкович Александр Григорьевич, Семенов Павел Владимирович   Издательство: Мнемозина, 2009 г.  Серия: Математика

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

Пособие предназначено для ознакомления учащихся с элементами теории вероятностей и математической статистики. На большом количестве примеров изложены начальные понятия, идеи и методы комбинаторики, теории вероятностей и статистики. Даны задачи с решениями и ответами, а также упражнения с возрастающей степенью сложности для самостоятельной работы школьников (включая ответы). 6-е издание.


Информатика. Теоретические основы. Учебное пособие для подготовки к ЕГЭ (+CD)

Автор(ы): Нурмухамедов Геннадий Михайлович, Соловьева Людмила Федоровна   Издательство: BHV, 2012 г.  Серия: Информатика и ИКТ

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

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

ПЕДСОВЕТ / ФОРУМ

Новости образования

Новости науки

флаг италииX-UNI рекомендует репетитора итальянского языка: yuliyavenezia (Скайп).

Репетитор по Скайпу без посредников

Неограниченная аудитория, свободный график. Начните свой бизнес здесь!