Элементы теории алгоритмов дискретная математика реферат

Обновлено: 02.07.2024

Собрала для вас похожие темы рефератов, посмотрите, почитайте:

Введение

Алгоритм — точная инструкция исполнителю выполнить определенную последовательность действий для достижения цели в ограниченном количестве шагов.

Алгоритм может быть сконструирован таким образом, что он может быть выполнен человеком или автоматическим устройством. Создание алгоритма, даже самого простого, — это творческий процесс. Она доступна только живым существам, и долгое время считалось, что она только человеческая. Латинский перевод его математического трактата был подготовлен в 19 в. Европейцы узнали о десятичной системе счисления и правилах арифметики для многозначных чисел. Именно эти правила тогда назывались алгоритмами.

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

Такие качества:

Дискреция (разрыв, разделение) — алгоритм должен представлять процесс решения задачи в виде последовательности простых (или заранее определенных) шагов. Любое действие, предусмотренное алгоритмом, выполняется только после завершения предыдущего.
Определение — каждое правило алгоритма должно быть четким и однозначным и не оставлять места для произвола. Благодаря этой характеристике, выполнение алгоритма является механическим и не требует дополнительных инструкций или информации о решаемой задаче.
Эффективность (конечность) — алгоритм должен приводить к решению задачи за конечное число шагов.
Массовый — алгоритм решения задачи разрабатывается в общем виде, т.е. он должен быть применим к классу задач, отличающихся только исходными данными. В этом случае исходные данные могут быть выбраны из диапазона, называемого областью действия алгоритма.

Во-первых, неправильно связывать алгоритм с решением проблемы. Алгоритм может вообще не решить проблему.

Типы алгоритмов

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

Линейный алгоритм — набор команд (инструкций), которые выполняются одна за другой во времени.

Разветвленный алгоритм — алгоритм, содержащий хотя бы одно условие, в результате которого компьютер позволяет перейти на один из двух возможных этапов.

Циклический алгоритм — алгоритм, обеспечивающий многократное повторение одного и того же действия (одних и тех же операций) для новых исходных данных. На циклических алгоритмах сокращено большинство методов вычислений, поиск вариантов.

Цикл программы — это последовательность инструкций (серия, тело цикла), которую можно выполнять много раз (для новых исходных данных) до тех пор, пока не будет выполнено определенное условие.

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

На всех этапах подготовки к алгоритмизации задачи часто используется структурное представление алгоритма.

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

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

Требования к алгоритму

В языках программирования выделение памяти осуществляется декларативными операторами (операторами описания переменных). В языке Basic описаны не все переменные, обычно описываются только массивы. Но все же при запуске программы транслятор языка анализирует все идентификаторы в тексте программы и выделяет память для соответствующих переменных.

Третье правило — усмотрение. Алгоритм состоит из отдельных шагов (действий, операций, команд). Множество шагов, из которых алгоритм естественно составлен.

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

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

Заключение

Список литературы

Образовательный сайт для студентов и школьников

Содержание.
Введение.
Понятие алгоритма.
Свойства алгоритмов.
Дискретность.
Детерминированность.
Конечность.
Массовость.
Результативность.
Виды алгоритмов.
Линейный алгоритм.
Циклический алгоритм.
Разветвляющийся алгоритм.
Вспомогательный алгоритм.
Способы описания алгоритмов.
Словесный способ.
Блок-схемы.
Заключение.
Литература.

Презентация для защиты реферата.

Алферова З.В. Теория алгоритмов

формат djvu
размер 1.63 МБ
добавлен 02 сентября 2009 г.

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

Головешкин В.А., Ульянов М.В. Теория рекурсии

формат djvu
размер 7.81 МБ
добавлен 07 июня 2010 г.

Головешкин В. А., Ульянов М. В., Теория рекурсии - ФИЗМАТЛИТ, 2006. - 296с. Книга является учебным пособием по теории рекурсии в аспекте ее применения в области программирования. В ней рассматриваются основы теории рекурсии и ее использование в области разработки и анализа рекурсивных алгоритмов. Приводятся основные сведения о рекурсивных последовательностях и функциях, даны примеры рекурсивных алгоритмов, разработанных на основе рекуррентных со.

Кузюрин Н.Н. Фомин С.А. Сложность комбинаторных алгоритмов. Курс лекций

формат pdf
размер 1.62 МБ
добавлен 21 февраля 2011 г.

Московский физико-технический институт. 2007 г. 135 стр. Элементы теории сложности Несложно о сложности. Примеры алгоритмов Формально об алгоритмах Сложность алгоритмов Вероятностные вычисления Вероятностно проверяемые доказательства Схемы и схемная сложность Коммуникационная сложность Диаграмма классов сложности Приближенные алгоритмы с гарантированными оценками точности Приближенные алгоритмы с фиксированными оценками точности Приближенные алго.

Основы математической логики и теории алгоритмов

формат doc
размер 1.96 МБ
добавлен 22 октября 2009 г.

Автор неизвестен. Конспект лекций по курсу "Матем. логика и теория алгоритмов". 2008 год. - 80 стр. Исчисления высказываний. Определение формального исчисления. Исчисление высказываний генценовского типа. Эквивалентность формул. Нормальные формы. Семантика исчисления секвенций. Исчисление высказываний гильбертовского типа. Алгоритмы проверки общезначимости и противоречивости в ИВ. Логика и исчисления предикатов. Алгебр. системы. Формулы сигнатуры.

Пильщиков В.Н. и др. Машина Тьюринга и алгоритмы Маркова. Решение задач

формат pdf
размер 541.65 КБ
добавлен 04 ноября 2009 г.

Уч-метод. пособие - М.: ВМК МГУ, 2006. – 47 с. Задачи на составление алгоритмов в виде машины Тьюринга и нормальных алгоритмов Маркова, а также задачи теоретического характера. Сведения по теории алгоритмов, типичные приёмы решения задач и большой набор задач для самостоятельного решения. Пособие рассчитано на студентов 1 курса факультета ВМК МГУ и преподавателей, ведущих семинарские занятия по программированию. Содержание: Машина Тьюринга. Кра.

Пильщиков В.Н., Абрамов В.Г., Вылиток А.А., Горячая И.В. Машина Тьюринга и алгоритмы Маркова. Решение задач

формат djvu
размер 255.05 КБ
добавлен 04 января 2012 г.

М.: МГУ, 2006. – 47 с. Учебно-методическое пособие Задачи на составление алгоритмов в виде машины Тьюринга и нормальных алгоритмов Маркова, а также задачи теоретического характера. Сведения по теории алгоритмов, типичные приёмы решения задач и большой набор задач для самостоятельного решения. Пособие рассчитано на студентов 1 курса факультета ВМК МГУ и преподавателей, ведущих семинарские занятия по программированию.

Презентация - Теория алгоритмов

формат ppt
размер 159.5 КБ
добавлен 18 ноября 2010 г.

24 слайда//Теория алгоритмов это. Возникновение теории алгоритмов. Модели вычисления. Машина Тьюринга. Машина Поста. Устройство машины Тьюринга.

Презентация - Элементы теории алгоритмов

формат ppt
размер 1.86 МБ
добавлен 05 июня 2011 г.

Понятие алгоритма. Свойства алгоритмов. Дискретность. Детерминированность. Конечность. Массовость. Результативность. Виды алгоритмов. Линейный алгоритм. Циклический алгоритм. Разветвляющийся алгоритм. Вспомогательный алгоритм. Способы описания алгоритмов. Словесный способ. Блок-схемы. Литература. Презентация была использована для защиты реферата Элементы теории алгоритмов. .

Реферат - Принципы развития теории алгоритмов

формат doc
размер 137 КБ
добавлен 04 января 2012 г.

Автор Лифшиц Ю.М. РАН СПб. Отделение Математического Института им. В.А. Стеклова, Лаборатория математической логики Содержание Введение Хронология теории алгоритмов Современное состояние теории алгоритмов Использование других наук в алгоритмах Наиболее значимые применения алгоритмов Идеи и техники в теории алгоритмов Формирование популярных направлений исследований Стили проведения научных исследований Заключение и выводы Список источников В эт.

Успенский В.А., Семенов А.Л. Теория алгоритмов: основные открытия и приложения

формат djvu
размер 3.55 МБ
добавлен 01 ноября 2009 г.

М., Наука, 1987г. -288 с. Важнейшие достижения теории алгоритмов. Приложения теории алгоритмов к математической логике, теории вероятностей, теории информации и др. Влияние теории алгоритмов на алгоритмическую практику. Содержание: Основные математические приложения теории алгоритмов: 1. Исследование массовых проблем. 2. Приложения к основаниям математики. 3. Приложения к математической логике. 4. Вычислимый анализ. Нумерованные структуры. 5.

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

Общество 21в. – общество информационное. Центр тяжести в решении задач переместился от задач вычислительной математики к задачам на дискретных структурах. Математика нужна не как метод расчета, а как метод мышлению средство формирования и организации…

Такое владение математикой богатой культуры, понимание важности точных формулировок.

В дисциплине мало методов, но много определений и терминов. В основе дискретной математике 4 раздела:

Язык дискретной математики;

Логические функции и автоматы;

Графы и дискретные экстремальные задачи.

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

Одной из важнейших проблем в дискретной математики является проблема сложности вычислений.

Теория сложности вычислений помогает оценить расход времени и памяти при решении задач на ЭВМ. Теория сложности позволяет выделить объективно сложные задачи (задачи перебора) и неразрешимые задачи.

Мы будем заниматься решением задач реальной размерности с учетом ограниченности временных и емкостных ресурсов ЭВМ.

Множества и операции над ними

Одно из основных понятий математики – множество.

Множеством называется совокупность, набор предметов, объектов или элементов.

Множество обозначают: M,N …..

A M – принадлежность элемента к множеству;

А М – непринадлежность элемента к множеству.

Примеры числовых множеств:

1,2,3,… множество натуральных чисел N;

…,-2,-1,0,1,2,… - множество целых чисел Z.

множество рациональных чисел а.

I – множество иррациональных чисел.

R – множество действительных чисел.

K – множество комплексных чисел.

Множество А называется подмножеством В, если всякий элемент А является элементом В.

А В – А подмножество В (нестрогое включение)

Множества А и В равны, если их элементы совпадают.

Если А В и А В то А В (строгое включение).

Множества бывают конечные и бесконечные.

|М| - мощность множества (число его элементов).

Конечное множество имеет конечное количество элементов.

Пустое множество не содержит элементов: M = .

Пример: пустое множество:

1) множество действительных корней уравнения x 2 +1=0 пустое: M = .

2) множество , сумма углов которого 180 0 пустое: M = .

Если дано множество Е и множество и мы рассматриваем все его подмножества, то множество Е называется униварсельным.

Пример: Если за Е взять множество книг то его подмножества: художественные книги, книги по математике, физики, физики …

Если универсальное множество состоит из n элементов, то число подмножеств = 2 n .

Объединение системы множеств можно записать

Объединение трех множеств:

2) Пересечением множеств А и В называется множество, состоящие из элементов принадлежащих одновременно множествам А и В.

Пересечение прямой и плоскости

если прямые || пл., то множество пересечений – единственная точка;

если прямые II пл., то M ;

если прямые совпадают, то множество пересечений = множество прямой.

Пересечение системы множеств:

Разностью 2-х множеств А и В называется множество, состоящее из всех элементов А, не входящих в В.

В отличии от предыдущих операций разность: 1) строго двухместна;

2) не коммутативна, т.е. A\B B\A.

а) взаимнооднозначное соответствеие (отображение)

а) не взаимнооднозначное соответствеие (отображение)

Определение: Между множествами M_X и M_Y установлено взаимноодназночное соответствие, если каждому хM_X соответствует 1 элемент yM_Y и обратное справедливо.

Пример: 1) (х,у) в круге

не взаимнооднозначное соответствие.

Пусть даны две функции f: AB и g: BC, то функция y:AC называется композицией функций f и g.

Y=f o g o – композиция.

Способы задания функций:

таблицы, определены для конечных множеств;

Способы 1-3 частные случаи выч. процедуры.

Пример процедуры, не относящейся к 3 способам задания функций n!

Взаимнооднозначное соответствие и мощности множеств.

Определение: Множества равномощны |A|=|B| если между ними взаимнооднозначное соответствие.

Теорема: Если для конечного множества А мощность равна |A| то количество всех подмножеств 2 | A | =2 n .

Множества равномощные N называются счетными, т.е. в них можно выполнить нумерацию элементов. N – множество натуральных чисел.

Множество N 2 – счетно.

Разобьем N 2 на классы

К 1-ому классу отнесем N₁ (1; 1)

1-ый элемент 1-го множества

Ко 2-му классу N₂

Каждый класс будет содержать i пар.

Упорядоченный классы по возрастанию индекса i, а пары внутри класса упорядоченные по направлению первого элемента а.

Занумеруем последовательность классов, что и доказывает счетность множества N 2 .

Аналогично доказывается счетность множеств N 3 ,…,N k .

Множество всех действительных чисел на отрезке [0;1] не является счетным.

Допустим это множество счетно изобразим его числа десятичными дробями.

Эта дробь не может выйти в последовательность т.к. отличается от всех чисел, значит нельзя пронумеровать числа на отрезке [0;1].

Множество нечетно и называется континуальным, а его мощность континуум.

Метод, используемый при доказательстве, называется диагональным методом Кантора.

Пусть дано RM n – n местное отношение на множество М.

Будем изучать двухместные или бинарные отношения. Если а и b находятся в отношении R, то записывается а R b.

Проведем отношение на множество N:

А) отношение выполняется для пар (7,9) (7,7_

Б) (9,7) не выполняется.

Пример отношения на множество R

А) отношение находится на одинаковом расстоянии от начала координат выполняется для пар (3; 4) и (2; 21)

Б) (3; 4) и (1; 6) не выполняется.

Для задания бинарных отношений можно использовать любые способы задания множеств.

Для конечных множеств используют матричный способ задания множеств.

Матрица бинарного отношения на множество M=, тогда матрица отношения С равна

Отношение Е заданные единичной матрицей называется отношением равенства.

Отношением назовется обратным к отношением R, если a_jR_ai тогда и только тогда, когда a_jR_ai обозначают R -1 .

Если aRa ==> очн. рефлексивное и матрица содержит на главной диагонали единицу

если ни для какого а не … ==> отношение антирефлексивное

главная диагональ содержит нули

отношение R симметричное. В матрице отношения элементы

сумм C_ij=C_ji. Если из aRb и bRa следует a=b ==> отношение R – антисимметричное.

Пр. Если а b и b a ==> a=b

Если дано a,b,c из aRb и aRc следует aRC ==> отношение называемое транзитивным.

Отношение называется отношением эквивалентности, если оно рефлексивно, симметрично и транзитивно.

Пр. отношение равенства E

5. Отношение называется отношением нестрогого порядка, если оно рефлексивно,

антисимметрично и транзитивно. Отношение называется отношением строгого порядка,

если оно антирефлексивно, антисимметрично и транзитивно.

Пр. а) отношение u для чисел отношение нестрогого

б) отношение для чисел отношение строгого

Элементы общей алгебры

Операции на множествах

Множество М вместе с заданной на нем совокупностью операций = 1,…, _m>, т.е. система А = 1;₁,…, _m> называется алгеброй. - сигнатура.

Пр. 1. Алгебра (R;+;*) – называется полем действительных чисел обе операции бинарные и

поэтому тип этой алгебры (2;2)

B=(Б;;) – булева алгебра. тип операций (2;2;1)

Р. Свойства бинарных алгебраических операций

1. (ab)c=a(bc) – ассоциативная операция

Пр. +,x – сложение и умножения чисел ассоциативно

2. ab = ba – коммутативная операция

умножение мат AB BA – некоммутативно.

3. a(bc) = (ab) (ac) –дистрибутивность слева

(ab)c) = (aс) (bc) –дистрибутивность справа.

Пр. (ab) e =a e b e – возведение в степень дистрибутивного отношения произведения справа

но не a bc a b a c

Гомоморфизм и изоморфизм

Алгебры с разными членами имеют различные строения. Алгебры с одинаковыми членами имеют сходство. Пусть даны две алгебры A=(K; _I) и B=(M; _I) – одинакового типа.

Пусть отображение Г:KM при условии Г(_I₎₌ _I(Г), (1) т.е. результат не зависит от последовательности возможных операций: Или сначала вып. операции _I b А и затем отображении Г, или сначала отображение Г, или сначала отображение Г и затем отображение _I в В.

Тогда условие (1) называется Гомоморфизмом алгебры А в алгебру В.

Когда существует взаимооднозначный гомоморфизм его называют изоморфизмом. В этом случае существует обратное отображение Г -1 .

Мощности изоморфных алгебр равны.

Пр. Алгебры (Q_N_; +) и (Q_2; +) – отображение типа и условие (1) запишется как 2(а+b)=2а+2b.

Отношение изоморфизма является отношением эквивалентности на множестве алгебр, т.е вычисление рефлексивное, симметричности и транзитивности. Изоморфизм важнейшее понятие в математике. Полученные соотношения в алгебре А автоматически …. на изоморфные алгебры.

1. Дискретная математика: теория алгоритмов и сложность вычислений

разделы
недели
1-6
мероприятия
КР1, КР2, Т1
баллы
22
Раздел 2 Числовые
множества и
арифметические
вычисления
7-11
Т2
12
Раздел 3 Рекурсивные
функции и сложность
вычислений
12-15
КР3, Т3
16
Раздел 1 Формальные
описания алгоритмов
Устная часть (зачет \ экзамен)
Автоматизированная часть
(зачет \ экзамен)
10 \ 25
20 \ 25
Письменная часть (экзамен)
20
Итого за семестр
100

недели
3(4)
5(6)
7(8)
11 (12)
13 (14)
15 (16)
мероприятия
ЛР №1 (КР1) – м. Тьюринга
баллы
7
ЛР №2 (КР2) – а. Маркова
7
Тест №1 (Т1) – теория 1 раздела
5
Тест №2 (Т2) – теория 2 раздела
9
ЛР №3 (КР3) – Рекурсии
7
Тест №3 (Т3) – теория 3 раздела
6

5. Лекция 1. Основные понятия

6. Причины появления теории

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

7. Задача нахождения единообразной формы записи алгоритмов

Определение алгоритма через понятие
вычислительной машины (машины
Тьюринга, предложено Тьюрингом в
1937г. и машины Поста в то же время);
Определение алгоритма через процедуру
переработки слов по заданным правилам
(нормальные алгоритмы, предложены
Марковым в 1956г.);
Определение алгоритма через
рекурсивную функцию (предложено
Клини и Геделем в 1936г.).

8. Алгоритмы: определение и основные свойства

слово “алгоритм” является производным от
имени среднеазиатского ученого Аль Хорезми,
уроженца Хивы, жившего в IX веке нашей эры.
Алгоритм – это точное предписание о выполнении в
некотором порядке системы операций, определяющих
процесс перехода от исходных данных к искомому
результату для решения задачи данного типа.
Это понятие относится к исходным математическим
понятиям, которые не могут быть определены через
другие, более простые понятия.

9. Свойства и параметры

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

Всеобщий алгоритм
"А нельзя ли создать Всеобщий
Алгоритм, который решал бы
любую математическую задачу
аксиоматической теории?"
Готфрид Вильгельм Лейбниц:
такой алгоритм будет найден!
1920е годы: две точки зрения
Все проблемы
алгоритмически разрешимы,
но для некоторых алгоритм
еще не найден, поскольку
еще не развиты
соответствующие разделы
математики.
Есть
проблемы,
для
которых алгоритм вообще
не может существовать.
задача точного определения
понятия алгоритма

11. Историческая справка

Неразрешимые проблемы пример
Найти
алгоритм,
определяющий
для
любого
диафантова уравнения, имеет ли оно целочисленное
решение.
Диафантово
уравнение
есть
уравнение
вида F(x,y,…,z)=0, где F(x,y,…,z) — многочлен с целыми
показателями степеней и с целыми коэффициентами.
В общем случае эта проблема долго оставалась
нерешенной (в 1970 г. советский математик Ю. В.
Матиясевич доказал ее неразрешимость).

Принципы построения
машины
Каждый шаг алгоритма таков, что его может
выполнить достаточно простое устройство (машина).
Желательно,
чтобы
это
устройство
универсальным, т.е. чтобы на нем можно
выполнять любой алгоритм.
было
было
Механизм работы машины должен быть максимально
простым по логической структуре, но настолько точным,
чтобы эта структура могла служить предметом
математического исследования.

14. Историческая справка

Эмиль Леон Пост (Emil Leon Post)
1897 - 1954
американский математик и логик
•один из основателей многозначной логики (1921);
•предложил абстрактную вычислительную машину машину Поста.

15. Машина Поста

16. Команды машины Поста

17. Историческая справка

18. Классические машины Тьюринга

Задача описания алгоритма может быть сведена к построению
машины некоторого типа, которая способна воспринимать набор
правил, выраженных на некотором языке, и делать то, что
предписано этими правилами.
А.М.Тьюринг, 1937 год
Машина Тьюринга – абстрактная (воображаемая)
"вычислительная
машина"
некоторого
точно
охарактеризованного типа, дающая пригодное для
целей математического рассмотрения уточнение
общего интуитивного представления об алгоритме.

Требования к машине
Тьюринга
1. машина должна быть полностью детерминированной
(вычисления должны быть точные и общепонятные) и
действовать в соответствии с заданной системой
правил.
2. должна допускать ввод различных “начальных данных”
(соответствующих различным задачам из данного
класса задач).
3. заданная система правил работы машины и класс
решаемых задач должны быть согласованы так, чтобы
всегда можно было “прочитать” результат работы машины.
С помощью машины Тьюринга можно доказать
существование или не существование
алгоритмов решения различных задач.

20. Одноленточная машина Тьюринга

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

21. Лента

Поскольку бесконечную ленту физически смоделировать затруднительно,
обычно предполагается, что она конечная, и разбита на конечное число ячеек.
В процессе работы к существующим ячейкам машина может пристраивать
новые ячейки, так что лента может считаться потенциально неограниченной в
обе стороны.
Каждая ячейка ленты может находиться в одном из конечного множества
состояний. Эти состояния мы будем обозначать символами a0, a1, …, am или
другими символами. По сути это и есть символы, записанные в ячейках ленты.
Совокупность таких символов называется внешним алфавитом машины, а сама
лента часто называется внешней памятью машины.
Если ячейка пустая, будем считать, что в ней записан условный символ λ.
В процессе работы машины ячейки ленты могут изменять свое содержимое, но
могут и не делать этого.
Все вновь пристраиваемые ячейки пристраиваются пустыми (содержат условный
символ λ). Без ограничения общности ленту можно считать бесконечной лишь с
одной стороны. В этом случае для удобства введем специальный символ ∂,
обозначающий начало ленты. Этот символ имеет строго определенное место,
его нельзя ни стирать, ни сдвигать. Тогда ленту можно считать
однонаправленной (бесконечной вправо) и ее ячейки удобно просматривать
слева направо.

22. Управляющая головка

23. Внутренняя память

25. Механическое устройство

Предполагается, что машина снабжена особым механизмом, который в
зависимости от символа в воспринимаемой ячейке и состояния внутренней
памяти может выполнить следующие действия:
изменить состояние внутренней памяти,
одновременно изменить содержимое воспринимаемой ячейки,
сдвинуть (вправо, влево) управляющую головку в соседнюю ячейку.
В частном случае содержимое воспринимаемой ячейки и/или состояние
внутренней памяти могут оставаться неизменными, а управляющая головка –
неподвижной (Н).
Если управляющая головка находится в самой правой ячейке и по ходу работы
машина должна сдвинуть управляющую головку в соседнюю справа
(отсутствующую) ячейку, то предполагается, что, сдвигая головку, машина
одновременно пристроит недостающую ячейку с пустым символом.
Аналогично работает машина и в случае, когда головка воспринимает самую
левую ячейку и по ходу дела машине надо сдвинуть головку еще левее.
Впрочем, далее предполагается, что лента бесконечна вправо, а ее самая
левая ячейка занята специальным символом начала ленты, обозначаемым ∂.

27. Программа машины Тьюринга

28. Реальные машины Тьюринга

29. Тезис Тьюринга

– любой алгоритм можно
преобразовать в машину Тьюринга.
Эту гипотезу невозможно доказать, потому что она
оперирует неформальным понятием алгоритма.
Однако обоснование гипотезы есть: все алгоритмы,
придуманные в течение столетий, могут быть реализованы
на машине Тьюринга.
Кроме
того,
эквивалентность
всех
формальных
определений алгоритма неслучайна и говорит в пользу
гипотезы.
Чтобы опровергнуть основную гипотезу необходимо
придумать такой алгоритм, который невозможно было бы
реализовать на машине Тьюринга, но пока такого
алгоритма нет.

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

Читайте также: