x-uni.com
x-uni.com
x-uni.com
Математика
Биология
Литература
Русский язык
География
Физика
Химия
История
Английский
Информатика
География
Информатика
ВИДЕОКУРСЫ
Справочная книга по математической логике, Часть 3, Теория рекурсии, Барвайс Дж., 1982

Справочная книга по математической логике, Часть 3, Теория рекурсии, Барвайс Дж., 1982

Справочная книга по математической логике, Часть 3, Теория рекурсии, Барвайс Дж., 1982.

Понятие алгоритма становится в настоящее время одним из важнейших понятий как теоретической, так и прикладной математики. Это связано в первую очередь с современным развитием электронной вычислительной техники и необходимостью создания мощного математического обеспечения для этой техники. Немаловажными являются и связи теории алгоритмов с математической логикой и основаниями математики; точное математическое определение понятия алгоритма впервые было найдено в рамках формальных систем математической логики. Теория рекурсии — так называется этот третий том «Справочной книги по математической логике» — составляет теоретическую основу современного учения об алгоритмах. Первая вводная глава этого тома, написанная Эндертоном, довольно подробно и мотивированно знакомит читателя с тем разделом теории алгоритмов, который теперь называется «классической» теорией рекурсии. Две следующие главы, написанные соответственно Девисом и Рабином, знакомят читателя с постановками различных алгоритмических проблем, возникающих в арифметике, алгебре, математической логике и других разделах математики. Наряду с формулировками проблем здесь имеются указания на методы решения таких проблем и даны примеры. Следует отметить, что обе эти главы не могут служить обзорами по рассматриваемой проблематике, так как отбор материала в этих главах отражает довольно субъективные взгляды авторов, не заботившихся, по-видимому, ни о достаточно полном обзоре результатов, ни о точности указаний на авторство приводимых утверждений.

Машины Тьюринга.
Существует много эквивалентных способов формулировки определения рекурсивности. Формулировка, выраженная в терминах воображаемой вычислительной машины, была дана английским математиком Аланом Тьюрингом в его фундаментальной статье [1]. (Аналогичная работа была сделана одновременно, но независимо, Эмилем Постом из Нью-Йорка; см. Пост [1].) Главная трудность при нахождении этого определения была в том, что Тьюринг искал его до создания реальных цифровых вычислительных машин. На самом деле познание шло от абстрактного к конкретному: фон Нейман был знаком с работой Тьюринга, и сам Тьюринг позднее сыграл вдохновляющую роль в развитии вычислительных машин. На неформальном уровне мы можем начать описывать машину Тьюринга как некий черный ящик с лентой. Лента разбита на ячейки и каждая ячейка может содержать пустой символ О, либо непустой символ 1. Лента потенциально бесконечна в обе стороны в том смысле, что мы никогда не придем к ее концу, но в любое время лишь конечное число ячеек может быть непустым. В начале лента содержит числа входа, в конце — число-выход. В промежуточное время лента используется как пространство памяти для вычисления.

Если мы откроем черный ящик, то обнаружим, что он устроен очень просто. В любой момент времени он может обозревать лишь одну ячейку памяти. Устройство содержит конечный список инструкций (или состояний) q0, q1,...,qn. Каждая инструкция может указать два возможных направления действий; одного нужно придерживаться, если на обозреваемой ячейке ленты находится 0, а другого, — если там находится 1. В любом случае следующее действие может состоять из таких трех типов элементарных шагов.

СОДЕРЖАНИЕ
Введение
§ 1. Неформальная вычислимость
§ 2. Машины Тьюринга
§ 3. Тезис Чёрча
§ 4. Универсальные машины и нормальная форма
§ 5. Оракулы и функционалы
§ 6. Рекурсивная перечислимость
§ 7. Логика и теория рекурсии
§ 8. Степени неразрешимости
§ 9. Креативные и меньшие множества
§ 10. Определимость и рекурсия
§ 11. Рекурсивные аналоги классических объектов
Литература.

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

ЕГЭ по математике. Алгебра. Профильный уровень. Практическая подготовка

  Издательство: BHV, 2017 г.

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

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


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

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

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

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


Математика. 1 класс. Тетрадь. В 2-х частях. Часть 1. ФГОС

Автор(ы): Истомина Наталия Борисовна, Редько Зоя Борисовна   Издательство: Ассоциация 21 век, 2015 г.  Серия: Математика

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

Тетрадь на печатной основе содержит материал, который поможет учителю организовать самостоятельную работу учащихся на уроке. Структура тетради соответствует логике построения содержания учебника "Математика, 1 класс", часть 1 (автор Н. Б. Истомина). 15-е издание, исправленное.


Математика. 1 класс. Тетрадь. В 2-х частях. Часть 2. ФГОС

Автор(ы): Истомина Наталия Борисовна, Редько Зоя Борисовна   Издательство: Ассоциация 21 век, 2015 г.  Серия: Математика

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

Тетрадь на печатной основе содержит материал, который поможет учителю организовать самостоятельную работу учащихся на уроке. Структура тетради соответствует логике построения содержания учебника "Математика. 1 класс", часть 2 (автор Н.Б. Истомина). 15-е издание, исправленное.