Презентация «Уточнение понятия алгоритм и его формализации»
Смотреть слайды в полном размере 
Вы можете ознакомиться с презентацией онлайн, просмотреть текст и слайды к ней, а также, в случае, если она вам подходит - скачать файл для редактирования или печати. Документ содержит 82 слайда и доступен в формате ppt. Размер файла: 1.22 MB
Pic.1
Уточнение понятия алгоритм и его формализации
Pic.2
В широком смысле слова алгоритм– это текст, который в определенных обстоятельствах может привести к однозначному развитию событий– процессу выполнения алгоритма.
Pic.3
Каждый алгоритм служит для решения некоторого класса задач. Каждый алгоритм служит для решения некоторого класса задач. Задачи должны быть записаны на некотором языке. Результат применения алгоритма– …
Pic.4
Свойства алгоритма Дискретность. Алгоритм – это процесс последовательного построения выражений таким образом, что в начальный момент задается исходное конечное выражение, а в каждый следующий момент …
Pic.5
Детерминированность. Выражение, получаемое в какой-то не начальный момент, однозначно определяется выражением, полученным в предшествующие моменты времени.
Pic.6
Элементарность шагов алгоритмов. Закон получения последующего выражения из предшествующего должен быть простым. (Для исполнителя!).
Pic.7
Массовость алгоритма. Начальное выражение может выбираться из некоторого потенциально бесконечного множества. Иначе говоря, алгоритм должен обеспечивать решение некоторому множеству (классу) задач с …
Pic.8
Результативность алгоритма. Последовательный процесс построения выражений языка должен быть конечным и давать результат, то есть решение задачи.
Pic.9
Основная задача теории алгоритмов – это решение проблемы алгоритмической разрешимости, а не поиск правила (способа/метода) ее решения. Основная задача теории алгоритмов – это решение проблемы …
Pic.10
В рамках такого подхода к определению понятия алгоритма можно определить три основных направления: В рамках такого подхода к определению понятия алгоритма можно определить три основных направления: …
Pic.11
Второе направление связано с машинной математикой. Здесь сущность понятия алгоритма раскрывается путем рассмотрения процессов, осуществляемых в некой механистической абстрактной конструкции - машине. …
Pic.12
Третье направление связано с понятием нормальных алгоритмов, введенным и разработанным российским математиком А. А. Марковым. Это направление получило название нормальные алгоритмы Маркова.
Pic.13
Третье направление связано с понятием нормальных алгоритмов, введенным и разработанным российским математиком А. А. Марковым. Это направление получило название нормальные алгоритмы Маркова.
Pic.14
Частично рекурсивные функции
Pic.15
Таким образом процесс алгоритмического решения задачи должен быть дискретным. Он распадается на элементарные шаги и представляет собой цепочку преобразований вида Таким образом процесс …
Pic.16
Поскольку, тексты (слова над конечным алфавитом) могут быть занумерованы, то цепочка текстов «задача– решение» превратится в числовую цепочку их номеров:
Pic.17
Такой цепочке можно поставить в соответствие числовую функцию Такой цепочке можно поставить в соответствие числовую функцию реализующую отображение определенную на множестве номеров задач и …
Pic.18
Далее, если не сделано специальных оговорок, мы будем предполагать, что рассматриваемые функции являются числовыми, их значения и аргументы принадлежат множеству натуральных чисел Далее, если не …
Pic.19
Если функция определена на собственном подмножестве множества Если функция определена на собственном подмножестве множества то будем называть ее частично рекурсивной.
Pic.20
Определим простейшие функции и элементарные операции над функциями.
Pic.21
Элементарные операции над частичными функциями. 1. Суперпозиция(или композиция). Пусть даны частичная функция и частичные функции
Pic.22
Pic.23
В противном случае функция считается неопределенной. Для функции полученной суперпозицией функций В противном случае функция считается неопределенной. Для функции полученной суперпозицией функций …
Pic.24
Примеры.
Pic.25
2. Рекурсия Начнем с частных случаев. Пусть заданы функция и число a. Уравнения: однозначно определяют функцию
Pic.26
Последовательно вычисляя, находим: Последовательно вычисляя, находим:
Pic.27
Pic.28
Pic.29
Pic.30
Pic.31
Pic.32
Pic.33
3. Минимизация.
Pic.34
Pic.35
Pic.36
Частичные функции, которые могут быть получены из простейших с помощью конечного числа операций суперпозиции, рекурсии и минимизации, называются рекурсивными (или частично рекурсивными). Частичные …
Pic.37
Запись частично рекурсивной функции с помощью простейших функций и операций будем называть рекурсивной схемой. Рекурсивная схема фактически задает алгоритм вычисления функции.
Pic.38
По рекурсивной схеме функции f может быть построено ее рекурсивное описание: конечная последовательность частичных функций По рекурсивной схеме функции f может быть построено ее рекурсивное описание: …
Pic.39
Одна и та же функция может быть определена с помощью разных рекурсивных схем. Это согласуется с представлением о том, что одну и ту же функцию можно вычислять по-разному.
Pic.40
Pic.41
Рекурсивная схема представляет собой слово над счетным алфавитом, содержащим в качестве символов натуральные числа, обозначения для простейших функций, элементарных операций, скобки, запятую и точку …
Pic.42
Вычислимость и разрешимость Отметим, что традиционно считающиеся вычислимыми функции имеют рекурсивные описания и, значит, частично рекурсивны. Обычно используемые вычислительные схемы также …
Pic.43
Тезис Черча. Числовая функция тогда и только тогда алгоритмически вычислима, когда она частично рекурсивна. Тезис Черча. Числовая функция тогда и только тогда алгоритмически вычислима, когда она …
Pic.44
Подмножество множества натуральных чисел называется разрешимым, если его характеристическая функция рекурсивна.
Pic.45
Содержательно разрешимость множества M означает, что существует алгоритм, позволяющий по любому числу x определить за конечное число шагов, принадлежит это число множеству M или нет.
Pic.46
Подмножество множества натуральных чисел M⊂N называется перечислимым, если оно является областью значений некоторой общерекурсивной функции f. Перечислимость множества M означает, что его элементы …
Pic.47
Утверждение: Всякое непустое разрешимое множество M является перечислимым. Доказательство. Определим перечисляющую функцию f. Пусть m– произвольный элемент множества M. Определяем по рекурсии:
Pic.48
Обратное, вообще говоря, неверно. Не всякое перечислимое множество является разрешимым. Перечислимое множество разрешимо лишь в том случае, когда перечислимо также и его дополнение.
Pic.49
Поскольку, что частично рекурсивные функции можно эффективно перенумеровать, используя их рекурсивные описания, то некоторые номера соответствуют общерекурсивным функциям. Обозначим множество таких …
Pic.50
Теорема. Множество номеров общерекурсивных функций не перечислимо. Теорема. Множество номеров общерекурсивных функций не перечислимо. Доказательство. Предположим противное. Пусть – общерекурсивная …
Pic.51
Это определение дает алгоритм вычисления значений функции . В соответствии с тезисом Черча, функция частично рекурсивна, и, значит, общерекурсивна, поскольку функция определена для любого . Значит, …
Pic.52
Вообще неперечислимые и неразрешимые семейства функций– это не «экзотика», а, скорее, норма. Вообще неперечислимые и неразрешимые семейства функций– это не «экзотика», а, скорее, норма. Приведем без …
Pic.53
Иными словами, если C– некоторое семейство вычислимых функций такое, что есть функции, входящие в это семейство, а есть и не входящие в него, то множество номеров функций из C неразрешимо. Не …
Pic.54
Так, по номеру функции нельзя узнать, является ли она монотонной, периодической и т. п. Заметим, что, нумеруя частично рекурсивные функции, мы на самом деле нумеровали их рекурсивные описания, то …
Pic.55
Теорема Райса утверждает, что по номеру алгоритма нельзя узнать, периодична ли, например, функция, вычисляемая в соответствии с этим алгоритмом.
Pic.56
Машина Тьюринга Если для решения некоторой массовой проблемы известен алгоритм, то для его реализации необходимо лишь четкое выполнение предписаний этого алгоритма. Автоматизм, необходимый при …
Pic.57
Идею такой машины предложил в 1937 году английский математик А. Тьюринг.
Pic.58
Машина Тьюринга включает в себя: Машина Тьюринга включает в себя: Внешний алфавит - конечное множество символов В этом алфавите в виде слова кодируется та информация, которая подается в машину. …
Pic.59
Внутренний алфавит - конечное множество символов Для любой машины число состояний фиксировано. Два состояния имеют особое назначение - начальное состояние машины, - заключительное состояние …
Pic.60
Операторы перемещения Т={Л, П, Н}. Л, П, Н – это символы сдвига «влево», «вправо» и «на месте». Операторы перемещения Т={Л, П, Н}. Л, П, Н – это символы сдвига «влево», «вправо» и «на месте». …
Pic.61
Управляющая головка. Управляющая головка (УГ) передвигается вдоль ленты и может останавливаться напротив какой-либо клетки, т. е. считывать символ
Pic.62
Логическое устройство. В зависимости от текущего внутреннего состояния, и считанного с ленты символа, переходит в новое внутренне состояние, и «премещает» управляющую головку.
Pic.63
Программа машины Тьюринга (Р) - совокупность всех команд, Программа представляется в виде таблицы и называется Тьюринговой функциональной схемой. Программа машины Тьюринга (Р) - совокупность всех …
Pic.64
Таким образом, машина Тьюринга может быть представлена в виде четверки:
Pic.65
Информация, хранящаяся на ленте, является набором символов из внешнего алфавита. Начальное состояние управляющей головки характеризуется символом внутреннего алфавита . Информация, хранящаяся на …
Pic.66
Работа машины складывается из тактов. В течение любого такта машина Тьюринга осуществляет следующие действия: машина Тьюринга находится во внутреннем состоянии , считывает входной символ и по таблице …
Pic.67
Если в результате операции машина перейдет в состояние , то работа машины останавливается. Если состояние недостижимо, то значит по данному входному слову машина Тьюринга не достигает конечного …
Pic.68
ПРИМЕР Построим машину Тьюринга, которая будет стирать последнюю единицу в последовательности единиц.
Pic.69
Внешний алфавит - . Внутренний алфавит - , при этом состояние сохраняется до тех пор, пока не будет найден конец последовательности единиц, состояние - стирание последней единицы.
Pic.70
При этом следует заметить, что ситуация в работе машины Тьюринга невозможна, поэтому соответствующая клеточка доопределена произвольно, например .
Pic.71
Начальное состояние , головка установлена на первой единице последовательности единиц. Рабочая программа машины Тьюринга имеет вид: Начальное состояние , головка установлена на первой единице …
Pic.72
Проверим работоспособность машины Тьюринга: Проверим работоспособность машины Тьюринга:
Pic.73
Тезис А. Черча. Если функция выполнима, то она всегда может быть представлена в виде машины Тьюринга.
Pic.74
Нормальные алгоритмы Маркова Нормальный алгоритм Маркова представляет собой систему подстановок
Pic.75
Слово z считается включенным в слово у, если у может быть представлено как:
Pic.76
Работа нормального алгоритма Маркова: Исходное слово просматривается слева направо с целью выявления вхождения первого правила подстановки. Как только находится первое вхождение первого правила …
Pic.77
После того, как первое правило больше не встречается в данном слове, аналогично применяется второе правило подстановки. Работа алгоритма заканчивается тогда, когда ни одна из подстановок не …
Pic.78
ПРИМЕР ПРИМЕР Построить нормальный алгоритм Маркова, стирающий последовательность единиц. Нормальный алгоритм Маркова для данной задачи представляет собой две подстановки :
Pic.79
Первая подстановка стирает все единицы до последней. Вторая (заключительная) подстановка заменяет последнюю единицу пробелом .
Pic.80
Тезис А. Черча. Если функция выполнима, то она может быть представлена в виде нормального алгоритма Маркова. Тезис А. Черча. Если функция выполнима, то она может быть представлена в виде нормального …
Pic.81
Один из видов чертежей– графы, которые, сохранив присущую чертежам наглядность, допускают точное теоретико-множественное описание и тем самым становятся объектом математического исследования.
Pic.82
Если вам понравился сайт и размещенные на нем материалы, пожалуйста, не забывайте поделиться этой страничкой в социальных сетях и с друзьями! Спасибо!
