Очень доброжелательный и компетентный автор. Всегда был на связи, все разъяснил, предоставил несколько вариантов программы. Рекомендую.
Информация о работе
Подробнее о работе
Машина Тьюринга
- 50 страниц
- 2019 год
- 35 просмотров
- 1 покупка
Гарантия сервиса Автор24
Уникальность не ниже 50%
Фрагменты работ
⦁ ВВЕДЕНИЕ
В 1935 г. возникло такое положение: свойства, обнаруженные у некоторого точно определенного класса вычислимых теоретико-числовых функций, изучавшихся Чёрчем и Клини в 1932-1935 годах, упорно подсказывали мысль, что этот класс, может быть, охватывает все функции, которые в соответствии с нашим интуитивным представлением можно рассматривать как вычислимые. При этих обстоятельствах Чёрч выдвинул тезис (опубликован в 1936 г.), что все функции, которые интуитивно мы можем рассматривать как вычислимые, или, говоря его словами, как «эффективно вычислимые», являются общерекурсивными.
Несколько позже, но независимо появилась статья Тьюринга (1936), в которой был введен еще один точно определенный класс интуитивно вычислимых функций, «функции, вычислимые по Тьюрингу». Вскоре Тьюрингом в 1937 году было показано, что его вычислимые функции – это то же самое, что λ-определимые функции, и, следовательно, то же самое, что и общерекурсивные функции [1].
Логичным являлся вопрос: можно ли для любого математического утверждения указать конечную последовательность инструкций, которые могли бы выполняться механически одна за другой человеком или вычислительным устройством, и в итоге выяснить, истинно это утверждение или ложно? В качестве математической модели для описания таких алгоритмов было предложено абстрактное вычислительное устройство, которое впоследствии было названо машина Тьюринга (МТ). МТ – дискретное вычислительное устройство, изменяющее свои характеристики в определенные моменты времени. Хотя и доказано, что поставленная проблема в общем случае неразрешима, применение МТ вышло далеко за пределы первоначальной постановки задачи. Хотя МТ не стала реально действующим устройством, она до настоящего времени постоянно используется в качестве основной модели для выяснения сущности таких понятий, как «вычислительный процесс», «алгоритм», а также для выяснения связи между алгоритмом и вычислительными машинами [2].
Так как процесс составления алгоритма вручную занимает много времени, предпочтительно автоматизировать этот процесс. В связи с этим во время лабораторного практикума авторам необходимо разработать систему, моделирующую работу МТ, которая будет составлять алгоритмы, проверять их работоспособность и визуализировать свою работу.
При разработке будут использованы методология структурного подхода к проектированию, построенная на декомпозиции (разбиении) системы на автоматизируемые функции, и методология ООАП (объектно-ориентированный анализ и проектирование), в основе которой лежит объектная декомпозиция, а так же технология RAD (от англ. RapidApplicationDevelopment – быстрая разработка приложений), которая хороша в первую очередь для относительно небольших проектов, разрабатываемых для конкретного заказчика, так называемое заказное ПО [3].
Основные принципы технологии RAD:
− разработка приложений итерациями;
− необязательность полного завершения работ на каждом этапе ЖЦ
− обязательное вовлечение пользователей на этапе разработки;
− тестирование и развитие проекта одновременно с разработкой;
− грамотное руководство разработкой, четкое планирование и контроль выполнения работ.
⦁ ОПИСАНИЕ И АНАЛИЗ ПРЕДМЕТНОЙ ОБЛАСТИ
Предметная область – область деятельности в реальном мире, которая содержит элементы системы, процессы их взаимодействия между собой, информационные потоки, различные функциональные подсистемы, а также внешние по отношению к исследуемой системе процессы, события и явления [4].
⦁ Принципы работы машины Тьюринга
Машина Тьюринга – абстрактный исполнитель (абстрактная вычислительная машина). Была предложена Аланом Тьюрингом в 1936 году для формализации понятия алгоритма.
Машина Тьюринга является расширением конечного автомата и, согласно тезису Чёрча-Тьюринга, способна имитировать всех исполнителей (с помощью задания правил перехода), каким-либо образом реализующих процесс пошагового вычисления, в котором каждый шаг вычисления достаточно элементарен.
То есть всякий интуитивный алгоритм может быть реализован с помощью некоторой машины Тьюринга.
В состав машины Тьюринга входит неограниченная в обе стороны лента (возможны машины Тьюринга, которые имеют несколько бесконечных лент), разделённая на ячейки, и управляющее устройство (также называется головкой записи-чтения (ГЗЧ)), способное находиться в одном из множества состояний. Число возможных состояний управляющего устройства конечно и точно задано (на месте, вправо, влево). На рисунке 1.1 изображена структура МТ.
⦁ ВВЕДЕНИЕ
⦁ ОПИСАНИЕ И АНАЛИЗ ПРЕДМЕТНОЙ ОБЛАСТИ
⦁ ПРОЕКТИРОВАНИЕ СИСТЕМЫ
⦁ реализация СИСТЕМЫ
⦁ Реализация классов
ЗАКЛЮЧЕНИЕ
СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ
Приложение А
Руководство пользователя
ПРИЛОЖЕНИЕ Б
Листинг модулей программы
⦁ Характеристика объекта автоматизации:
⦁ объект автоматизации: машина Тьюринга (МТ);
⦁ виды автоматизируемой деятельности:
⦁ процесс работы МТ с заданным алгоритмом;
⦁ процесс визуализации работы МТ;
⦁ процесс составления алгоритма;
⦁ основание системы счисления – 10;
⦁ количество операндов – 2;
⦁ количество способов задания операндов – 2;
⦁ минимальная длина ленты – 500;
⦁ максимальная длина ленты – 500;
⦁ минимальное количество состояний МТ – 1;
⦁ максимальное количество состояний МТ – 100;
⦁ минимальная длина алфавита – 3;
⦁ максимальная длина алфавита – 100;
⦁ количество стандартных алгоритмов – 2;
⦁ количество команд перемещения, выполняемых МТ – 3;
⦁ количество режимов работы МТ – 3;
⦁ количество способов визуализации – 2;
⦁ количество скоростных режимов – 5;
⦁ минимальная величина задержки – 15мс;
⦁ максимальная величина задержки – 500мс.
⦁ Требования к информационному обеспечению:
⦁ информационное обеспечение разрабатывается на основе следующего источника:
⦁ Описание структуры машины Тьюринга [Электронный ресурс]. URL: ru.wikipedia.org/wiki/Машина_Тьюринга (дата обращения: 10.09.2017);
⦁ предусмотреть проверку на наличие бесконечных циклов;
⦁ трасса хранится в текстовом файле формата *.tmt
⦁ алгоритмы для МТ хранятся в файлах формата .tma, структура файла определяется в процессе проектирования.
Функции, реализуемые системой:
⦁ визуализация процесса работы МТ;
⦁ синтаксический анализ алгоритма;
⦁ семантический анализ алгоритма;
⦁ выдача справочной информации о системе;
⦁ выбор способа задания операндов;
⦁ редактирование символа на ленте;
⦁ выбор режима работы МТ;
⦁ выбор скорости визуализации работы МТ
⦁ создание алфавита;
⦁ редактирование алфавита;
⦁ выбор стандартного алгоритма;
⦁ ручное составление алгоритма;
⦁ запись алгоритма в файл;
⦁ загрузка алгоритма из файла;
⦁ формирование трассы выполняемого алгоритма;
⦁ сохранение трассы в файл.
⦁ Ресурсная эффективность алгоритмов [Электронный ресурс] // Intuit НОУ «ИНТУИТ». 2003-2017. URL: http://www.intuit.ru/studies/courses/648/504/lecture/11461%2525253Fpage%2525253D3 (дата обращения: 20.10.2019).
⦁ Алгоритм [Электронный ресурс] // Википедия: электрон. энциклопедия. 2001-2019. URL: https://ru.wikipedia.org/wiki/Алгоритм (дата обращения: 20.10.2019).
⦁ Среда .NET [Электронный ресурс] // StudFiles: файловый архив студентов. 2014-2019. URL: https://studfiles.net/preview/5946738/ (дата обращения: 04.11.2019).
⦁ Общие сведения о приложениях для Windows [Электронный ресурс] // Microsoft: [сайт]. URL: https://msdn.microsoft.com/ru-ru/library/5b13a7k4(v=vs.100).aspx (дата обращения: 28.11.2019).
⦁ Вас приветствует Visual Studio 2013 [Электронный ресурс] // Microsoft: [сайт]. URL: https://msdn.microsoft.com/ru-ru/library/dd831853(v=vs.120).aspx (дата обращения:
28.11.2019).
⦁ Понятие пользовательского интерфейса [Электронный ресурс] // Студопедия: [сайт]. URL: http://studopedia.ru/4_153814_udalennie-banki-dannih.html (дата обращения: 20.10.2019г.).
⦁ Меню (информатика) [Электронный ресурс]. – ⦁ https://ru.wikipedia.
org/wiki/Меню_(информатика) (дата обращения: 14.12.2019).
Форма заказа новой работы
Не подошла эта работа?
Закажи новую работу, сделанную по твоим требованиям
