Разработка электронного учебного пособия

«ЭЛЕКТРОННОЕ ПОСОБИЕ "АБСТРАКТНОЕ ВЫЧИСЛИТЕЛЬНОЕ УСТРОЙСТВО: МАШИНА ТЬЮРИНГА"»

СОДЕРЖАНИЕ

Введение 3

Глава 1. Абстрактные вычислительные устройства 5

1.1. Алгоритмы и абстрактные вычислительные устройства 5

1.2. История появления и принципы работы машины Тьюринга 13

1.3. Интерпретатор машины Тьюринга, Поста - Алго2000 20

1.4. Интерпретатор машины Тьюринга - Машина Тьюринга v.1.1 24

1.5. Примеры реализации алгоритмов с помощью машины Тьюринга 25

Выводы к главе 1 33

Глава 2. Требования к разработке и средства разработки электронного пособия «Абстрактное вычислительное устройство: машина Тьюринга» 34

2.1. Электронные пособия и требования к их разработке 34

2.2. Обзор средств разработки электронных пособий 38

2.3. Средства разработки электронного пособия «Абстрактное вычислительное устройство: машина Тьюринга» 44

Выводы к главе 2 52

Глава 3. Руководство пользователя электронным пособием «Абстрактное вычислительное устройство: машина Тьюринга» 53

3.1. Технические требования 53

3.2. Описание электронного пособия «Абстрактное вычислительное устройство: машина Тьюринга» 53

Выводы к главе 3 57

Заключение 58

Список использованных источников 60

Введение

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

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

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

Электронное пособие - это программно-методический обучающий комплекс, предназначенный для изучения учащимся учебного материала по определенным дисциплинам.

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

Целью работы является разработка электронного пособия «Абстрактное вычислительное устройство: машина Тьюринга».

Задачи, поставленные для достижения цели:

• Изучить литературу для исследования предметной области;

• Изучить историю появления и принципы работы машины Тьюринга;

• Рассмотреть принципы работы интерпретаторов машины Тьюринга: Алго2000 и Машина Тьюринга v1.1;

• Рассмотреть примеры реализации алгоритмов с помощью машины Тьюринга;

• Рассмотреть электронные пособия и средства их разработки;

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

Объектом является процесс разработки электронного пособия «Абстрактное вычислительное устройство: машина Тьюринга».

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

Глава 1. Абстрактные вычислительные устройства

1.1. Алгоритмы и абстрактные вычислительные устройства

Математическая логика стала бурно развиваться вначале ХХ в., когда Гильберт представил на международном конгрессе математиков в 1900 году список из 23 проблем математики. Имеется 10-я проблема, которая гласит: «Есть ли универсальный метод решения диофантовых уравнений?» (Диофантово уравнение - это уравнение вида P (x1,…, x_m) = 0, где Р - целочисленная функция, а переменные x_i принимают целые значения). То, что в формулировке этой проблемы было названо «универсальным методом», позже было формализовано в виде понятия «алгоритм». До того времени математикам обычно приходилось доказывать существование алгоритма путем его предъявления. Для этих целей не требуется точного определения, что такое алгоритм. Однако многочисленные попытки положительно решить 10-ю проблему Гильберта, то есть предъявить алгоритм, не приводили к успеху (были получены лишь частичные методы решения для очень узких классов уравнений). Это привело к гипотезе о том, что необходимо пытаться отрицательно решить эту проблему, то есть доказать, что алгоритма не существует. Чтобы иметь возможность доказывать отсутствие алгоритма строгими математическими средствами, необходимо точно определить само понятие алгоритма.

Это привело к возникновению в начале 1930-х годов новой области математической логики - теории алгоритмов. Первые уточнения этого понятия появились в работах А. Тьюринга, А. Чёрча, Э. Поста.

Первую идею вычислительной машины высказал математик Чарльз Бэббедж еще в 30-е гг. XIX в. Это была первая машина, управляемая внешней программой. Однако, она так и не была закончена, главным препятствием на пути ее создания стал низкий уровень развития технологий того времени. И только сто лет спустя логики разработали четыре математически эквивалентные модели понятия алгоритма. Именно в теории алгоритмов были предугаданы основные концепции, которые легли в основу принципов построения и функционирования вычислительной машины с программным управлением и принципов создания языков программирования. Идею такой вычислительной машины впервые смогли реализовать болгарский ученый С. Атанасов в 1940 г. и немецкий ученый К.Цузе в 1942 г. Четыре главные модели алгоритма породили разные направления в программировании.

Первая модель - это абстрактная вычислительная машина (устройство) (А. Тьюринг, Э. Пост). Она явилась абстрактным прообразом реальных вычислительных машин.

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

Исходя из свойств алгоритма, можно сформулировать общие требования к таким машинам:

1. Характер их функционирования должен быть дискретным, т.е. состоять из отдельных шагов (команд), каждый из которых выполняется только после завершения предыдущего;

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

3. Перед началом работы машине предоставляются исходные данные из области определения алгоритма;

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

5. Машина должна быть универсальной, т.е. такой, чтобы с ее помощью можно быть бы выполнить любой алгоритм.

Чем проще структура (устройство) описанной машины и чем элементарнее ее шаги, тем больше оснований считать, что ее работа и есть выполнение алгоритма.

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

Американский математик и логик Эмиль Леон Пост (1897-1954) предложил абстрактную вычислительную конструкцию, позволяющую формально определить алгоритм и названную впоследствии машиной Поста. При разработке вычислительной конструкции Пост руководствовался принципом создания максимально простой абстракции: минимумом операций при обработке информации, входная информация должна быть закодирована с использованием минимального набора символов.

Несмотря на "примитивность" машины Поста, любой существующий алгоритм может быть записан в виде программы для машины Поста. В теории алгоритмов существует так называемый "тезис Поста": "Всякий алгоритм представим в форме машины Поста". Этот тезис одновременно является формальным определением алгоритма. Алгоритм (по Посту) - программа для машины Поста, приводящая к решению поставленной задачи.

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

Машина Поста - это абстрактная (т.е. не существующая в арсенале действующей техники), но очень простая вычислительная машина. Она способна выполнять лишь самые элементарные действия, и потому ее описание и составление простейших программ может быть доступно ученикам начальной школы. Тем не менее на машине Поста можно запрограммировать - в известном смысле - любые алгоритмы. Изучение машины Поста можно рассматривать как начальный этап обучения теории алгоритмов и программированию. Разработка программ для машин Поста - достаточно эффективный этап в обучении алгоритмизации, т.к. в процессе написания этих программ учащиеся учатся разбивать интуитивно понятные вычислительные процедуры на элементарные действия. Изучение машины Поста полезно как школьникам, интересующимся информатикой и математикой, так и студентам младших курсов, обучающимся по специальности "прикладная математика и информатика". При этом теоретический материал доступен даже школьникам младших классов.

Машина Поста состоит из ленты и каретки (называемой также считывающей и записывающей головкой). Лента бесконечна и разделена на секции одинакового размера - ячейки.

Рис. 1.1 Фрагмент ленты машины Поста

В каждой ячейке ленты может быть либо ничего не записано, либо стоять метка V. Информация о том, какие ячейки пусты, а какие содержат метки, образует состояние ленты. Иными словами, состояние ленты - это распределение меток по ячейкам. Состояние ленты меняется в процессе работы машины. Заметим, что наличие метки в ячейке можно интерпретировать как "1", а отсутствие - "0". Такое двоичное представление информации подобно представлению, используемому практически во всех современных ЭВМ.

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

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

1. записать 1 (метку), перейти к i-й строке программы;

2. записать 0 (стереть метку), перейти к i-й строке программы;

3. сдвиг влево, перейти к i-й строке программы;

4. сдвиг вправо, перейти к i-й строке программы;

5. остановка;

6. если 0, то перейти к i, иначе перейти к j.

Приведем список недопустимых действий, ведущих к аварийной остановке машины:

• попытка записать 1 (метку) в заполненную ячейку;

• попытка стереть метку в пустой ячейке;

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

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

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

Пример программы, которая не применима ни к одному состоянию машины Поста:

Рассмотрим задачу для машины Поста и ее решение.

Задача. На ленте проставлена метка в одной-единственной ячейке. Каретка стоит на некотором расстоянии левее этой ячейки. Необходимо подвести каретку к ячейке, стереть метку и остановить каретку слева от этой ячейки.

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

Программа для машины Поста:

Вторая модель - это рекурсивные функции, идея которых восходит к гильбертовскому аксиоматическому подходу. От них унаследовало свои основные конструкции современное структурное программирование.

Третий способ описания алгоритмов - нормальные алгоритмы А.А.Маркова. Они послужили основой языка Рефал и многих других языков обработки символьной информации.

Нормальные алгоритмы Маркова (НАМ), введенные советским математиком А. А. Марковым, представляют собой класс алгоритмов, применимых к словам некоторого алфавита.

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

Формулой подстановки называется запись вида α→β (читается «α заменить на β»), где α и β - любые слова (возможно, и пустые). При этом α называется левой частью формулы, а β - правой частью.

Сама подстановка (как действие) задается формулой подстановки и применяется к некоторому слову Р. Суть операции сводится к тому, что в слове Р отыскивается часть, совпадающая с левой частью этой формулы (т.е. с α), и она заменяется на правую часть формулы (т.е. на β). При этом остальные части слова Р (слева и справа от α) не меняются. Получившееся слово R называют результатом подстановки. Условно это можно изобразить так:

P: x α y → R: x β y

Необходимые уточнения:

1. Если левая часть формулы подстановки входит в слово Р, то говорят, что эта формула применима к Р. Но если α не входит в Р, то формула считается неприменимой к Р, и подстановка не выполняется.

2. Если левая часть α входит в Р несколько раз, то на правую часть β, по определению, заменяется только первое вхождение α в Р:

P: x α y α z → R: x β y α z

3. Если правая часть формулы подстановки - пустое слово, то подстановка α→ сводится к вычеркиванию части α из Р (отметим попутно, что в формулах подстановки не принято как-либо обозначать пустое слово):

P: x α y → R: x y

4. Если в левой части формулы подстановки указано пустое слово, то подстановка →β сводится, по определению, к приписыванию β слева к слову P:

P: x → R: β x

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

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

Рис 1.2 Эмулятор нормальных алгоритмов А. А. Маркова

Четвертое направление в теории алгоритмов - так называемое λ-исчисление - базируется на идеях советского логика Р. Шейнфинкеля и американского логика Х. Б. Карри. Для определения всех вычислимых функций достаточно операций так называемой λ - абстракции и суперпозиции. Идеи λ-исчисления активно используются в языке Лисп, функциональном программировании и во многих других перспективных направления современного программирования.

1.2. История появления и принципы работы машины Тьюринга

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

Рис. 1.3 Алан Мэтисон Тьюринг

Большинство исследований Алана сводится к тому, что для решения любой проблемы не надо думать, и уж тем более - угадывать. Достаточно разработать определенный метод. Если механически следовать этому порядку действий, правильное решение можно будет получить гораздо быстрее. Тьюринг разработал свои собственные ходы и ввел понятие «определенного метода», который позже получил название «алгоритм».

Машина Тьюринга (МТ) - абстрактный исполнитель (абстрактная вычислительная модель).

Рис. 1.4 Машина Тьюринга

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

Рис. 1.5 Фрагмент ленты машины Тьюринга

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

Рис. 1.6 Схема работы машины Тьюринга

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

Оставшись на бумаге и потеряв надежду воплотиться «в железе», машина Тьюринга начала жизнь воображаемого инструмента для изучения разрешимости математических проблем. На этом поприще она и прославилась, заняв прочное место в новом разделе математики - теории конечных автоматов.

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

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

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

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

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

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

Работа машины происходит в нашем воображении. Следовательно, машины Тьюринга - вовсе не машины в обычном смысле, а скорее тексты на некотором языке, что вполне соответствует нашему интуитивному представлению об алгоритме.

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

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

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

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

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

1.3. Интерпретатор машины Тьюринга, Поста - Алго2000

Программа "Интерпретатор машины Поста и машины Тьюринга" предназначена для интерпретации алгоритмов, написанных для абстрактных машин Поста и машин Тьюринга.

Требования:

• компьютер IBM PC AT 486 и выше;

• наличие операционной системы Windows' 95/98/NT;

• палитра не менее 16 разрядов.

Программа была разработана в 2000 году Зартдиновым Радиком.

Рис. 1.7 Интерпретатор Машины Тьюринга - Алго2000

Рис. 1.8 Интерпретатор Машины Поста - Алго2000

Файл машины Поста имеет расширение *.pst, а файл машины Тьюринга - *.tur

Главное меню

Файл

• Новый - создает новый файл текущей машины с именем 'Без имени'

• Открыть - загружает ранее сохраненный файл текущей машины

• Сохранить - сохраняет файл текущей машины на диск

• Сохранить как - сохраняет файл текущей машины на диск с новым именем

• Выход - выход из программы

Интерпретатор - переход на соответствующую машину:

• Машина Поста

• Машина Тьюринга

Вид - прячет / показывает соответствующие компоненты программы:

• Панель инструментов

• Условие задачи

• Строка состояния

Команды

• Каретка влево - сдвиг каретки влево на одну ячейку

• Каретка вправо - сдвиг каретки вправо на одну ячейку

• Поставить/ удалить метки (Машина Поста (МП)) - отметить/ удалить метки в выделенных ячейках ленты

• Отметить символ на ленте (Машина Тьюринга) - занести текущий символ внешнего алфавита в выделенные ячейки ленты

• Изменить символ (Машина Тьюринга) - изменить значение в выделенных ячейках ленты

• Очистить - очищает содержимое соответствующих компонентов программы:

• Условие задачи

• Информационную ленту

• Таблицу

в Машину Тьюринга для очистки таблицы полностью нужно очистить внешний алфавит

• Столбец

• Строку

• Внешний алфавит (Машина Тьюринга)

• Комментарии (Машина Тьюринга)

• Все

Манипуляции со строками и столбцами в таблице:

• Удалить столбец (Машина Тьюринга)

• Вставить столбец (Машина Тьюринга)

• Добавить столбец (Машина Тьюринга)

• Удалить строку (Машина Поста)

• Вставить строку (Машина Поста)

• Добавить строку (Машина Поста)

в Машине Тьюринга строки добавляются (удаляются) добавлением (удалением) символов во внешнем алфавите

• Запомнить ленту - запоминает ленту

• Восстановить ленту - восстанавливает запомненную ленту

работают отдельно (независимо) для Машины Поста и Машины Тьюринга

Пуск

• Запустить - начинает выполнение программы (для Машины Поста с команды номер 1, для Машины Тьюринга с состояния q0)

• Пауза - приостановить выполнение программы (затем можно продолжить выполнение с данного места)

• Пошагово - пошаговое выполнение программы

• Прервать - прервать выполнение программы (продолжить выполнение с прерванного места нельзя)

Скорость - изменяет скорость выполнения программы

• Очень быстро

• Быстро

• Средне

• Медленно

• Очень медленно

Помощь

Справка - вызов справки

О программе - информация о программе Algo2000

1.4. Интерпретатор машины Тьюринга - Машина Тьюринга v.1.1

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

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

Дата выхода: 07.01.2007 г.

Поддерживаемые ОС: Microsoft Windows 95, 98, Me, NT 4.0, 2000, XP, 2003, Vista.

Отличительные черты:

• Возможность быстрого и эффективного редактирования алгоритмы, его сохранения в файл или загрузки в любой момент времени;

• Быстрое добавление повторяющихся данных на ленту;

• Возможность проверки условной корректности написанных программ;

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

• Удобный в использовании оконный интерфейс приложения;

• Наличие расширенной справочной системы;

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

Рис. 1.9 Интерпретатор машины Тьюринга - Машина Тьюринга v.1.1

1.5. Примеры реализации алгоритмов с помощью машины Тьюринга

Пример 1 (перемещение автомата, замена символов)

А={0,1,2,3,4,5,6,7,8,9}. Пусть Р - непустое слово; значит, Р - это последовательность из десятичных цифр, т.е. запись неотрицательного целого числа в десятичной системе. Требуется получить на ленте запись числа, которое на 1больше числа Р.

Решение

Для решения этой задачи надо выполнить такие действия:

1) перегнать автомат под последнюю цифру числа.

2) если это цифра от 0 до 8, то заменить её цифрой на 1 больше и остановиться; например:

1 9 5 7 → 1 9 5 7 → 1 9 5 8

↑ ↑ ↑

3) если же это цифра 9, тогда заменить её на 0 и сдвинуть автомат к предыдущей цифре, после чего таким же способом увеличить на 1 эту предпоследнюю цифру; например:

6 4 9 → 6 4 9 → 6 4 0 → 6 5 0

↑ ↑ ф ↑ ↑

4) особый случай: в Р только девятки (например, 99). Тогда автомат будет сдвигаться влево, заменяя девятки на нули, и в конце концов окажется под пустой клеткой. В эту пустую клетку надо записать 1 и остановиться (ответом будет 100):

9 9 → 9 9 → 9 0 → 0 0 → 1 0 0

↑ ↑ ↑ ↑ ↑

В виде программы для МТ эти действия описываются следующим образом:

Рис. 1.10 Фрагмент Машины Тьюринга - замена символов

q1 - это состояние, в котором автомат «бежит» под последнюю цифру числа. Для этого он всё время движется вправо, не меняя видимые цифры и оставаясь в том же состоянии. Но здесь есть одна особенность: когда автомат находится под последней цифрой, то он ещё не знает об этом (ведь он не видит, что записано в соседних клетках) и определит это лишь тогда, когда попадёт на пустую клетку.

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

q2 - это состояние, в котором автомат прибавляет 1 к той цифре, которую видит в данный момент. Сначала это последняя цифра числа; если она - в диапазоне от 0 до 8, то автомат заменяет её цифрой, которая на 1 больше, и останавливается. Но если это цифра 9, то автомат заменяет её на 0 и сдвигается влево, оставаясь в состоянииq2. Тем самым, он будет теперь прибавлять 1 к предыдущей цифре. Если и эта цифра равна 9, то автомат заменяет её на 0 и сдвигается влево, оставаясь по-прежнему в состоянии q2, т.к. должен выполнить то же самое действие - увеличить на 1 видимую цифру. Если же автомат сдвинулся влево, а в видимой клетке нет цифры (а есть «пусто»), то он записывает сюда 1 и останавливается.

Отметим, что для пустого входного слова наша задача не определена, поэтому на этом слове МТ может вести себя как угодно. В нашей программе, например, при пустом входном слове МТ останавливается и выдает ответ 1.

Пример 2 (анализ символов)

А={a, b, c}. Перенести первый символ непустого слова Р в его конец.

Например: a c b c → c b c a

Решение

Для решения задачи, очевидно, следует:

1) первый символ слова P запомнить и стереть его.

2) подвинуть автомат вправо под первую пустую клетку за словом P и записать в неё этот символ.

Из первого примера мы научились «бегать» вправо. Но как запомнить первый символ? Ведь в МТ нет другого запоминающего устройства, кроме ленты, а запоминать символ в какой-то клетке на ленте бессмысленно: как только автомат сдвинется влево или вправо от этой клетки, он тут же забудет данный символ. Что делать?

Выход здесь таков - надо использовать разные состояния автомата. Если первый символ - это a, то надо перейти в состояние q2, в котором автомат бежит вправо и записывает в конце a. Если же первым был символ b, тогда надо перейти в состояние q3, где делается всё то же самое, только в конце записывается символ b. Если же первым был символ c, тогда переходим в состояние q4, в котором автомат дописывает за входным словом символ c. Следовательно, то, каким был первый символ, мы фиксируем переводом автомата в разные состояния. Это типичный приём при программировании на МТ.

Рис. 1.11 Фрагмент Машины Тьюринга - анализ символов

С учётом сказанного программа будет такой:

• q1-анализ 1-го символа, удаление его, разветвление

• q2-запись a справа

• q3-запись b справа

• q4-запись c справа

Рассмотрим поведение этой программы на входных словах, содержащих не более одного символа. При пустом слове, которое является «плохим» для задачи, программа зациклится - автомат, находясь в состоянии q1 и попадая всё время на пустые клетки, будет бесконечно перемещаться вправо. (Конечно, в этом случае программу можно было бы остановить, но мы специально сделали зацикливание, чтобы продемонстрировать такую возможность.)

Если же во входном слове ровно один символ, тогда автомат сотрёт этот символ, сдвинется на одну клетку вправо и запишет в неё данный символ:

c → → c

↑ ↑ ↑

q1 q4 !

Таким образом, слово из одного символа попросту сдвинется на клетку вправо.

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

Пример 3 (удаление символа из слова)

А={a, b}. Удалить из слова Р его второй символ, если такой есть.

Решение

Казалось бы, эту задачу решить просто - надо сдвинуть автомат под клетку со вторым символом и затем очистить эту клетку:

b a a b → b a a b → b a b

↑ ↑ ↑

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

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

Рис. 1.12 Фрагмент Машины Тьюринга - удаление символа

В виде программы для Машины Тьюринга всё это записывается так:

• q 1-анализ и удаление 1-го символа, разветвление

• q2-замена 2-го символа на a

• q3-замена 2-го символа на b

Пример 4 (формирование слова на новом месте)

А={a, b, c}. Удалить из P все вхождения символа a.

Решение

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

Конкретно предлагается выполнить следующие действия:

1) выходное слово будем строить справа от входного. Чтобы разграничить эти слова, отделим их некоторым вспомогательным символом, например знаком =, отличным от всех символов алфавита A (см. шаг 1). (Напомним, что на ленте могут быть записаны не только символы из алфавита входного слова.)

2) после этого возвращаемся к началу входного слова (см. шаг 2).

а b c → a b c = → a b c = →

↑ 1 ↑ 2 ↑ 3

3) теперь наша задача - перенести в цикле все символы входного слова, кроме a, вправо за знак = в формируемое выходное слово.

Для этого анализируем первый символ входного слова. Если это a, тогда стираем его и переходим к следующему символу (см. шаг 3). Если же первый символ - это b или c, тогда стираем его и «бежим» вправо до первой пустой клетки (см. шаг 4), куда и записываем этот символ (см. шаг 5).

→ b c = → c = → c = b →

3 ↑ 4 ↑ 5 ↑ 6

Снова возвращаемся налево к тому символу, который стал первым во входном слове, и повторяем те же самые действия, но уже по отношению к этому символу (см. шаги 6-9).

→ c = b → = b → = b c →

6 ↑ 7 ↑ 8 ↑ 9

4) этот цикл завершается, когда при возврате налево мы увидим в качестве первого символа знак =. Это признак того, что мы полностью просмотрели входное слово и перенесли все его символы, отличные от a, в формируемое справа выходное слово. Надо этот знак стереть, сдвинуться вправо под выходное слово и остановиться (см. шаг 10).

→ = b c → b c

9 ↑ 10 ↑

С учётом всего сказанного и строим программу для МТ. При этом отметим, что помимо символов a, b и c в процессе решения задачи на ленте появляется знак =, поэтому в таблице должен быть предусмотрен столбец и для этого знака.

Рис. 1.13 Фрагмент Машины Тьюринга - формирование слова

q1 - записать справа знак =

q2 - влево к 1-му символу слова

q3 - анализ и удаление его, разветвление

q4 - запись b справа, возврат налево (в цикл)

q5 - запись c справа, возврат налево (в цикл)

Выводы к главе 1

10-я проблема Гильберта привела к возникновению новой области математической логики - теории алгоритмов. Первые уточнения этого понятия появились в работах А. Тьюринга, А. Черча, Э. Поста.

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

В первой главе рассмотрены история появления и основные принципы работы машины Тьюринга. Так же представлено описание интерпретаторов машин Тьюринга и Поста - Алго2000, Машина Тьюринга v.1.1 - предназначенных для составления и изменения алгоритмов.

Глава 2. Требования к разработке и средства разработки электронного пособия «Абстрактное вычислительное устройство: машина Тьюринга»

2.1. Электронные пособия и требования к их разработке

2.1.1 Электронные пособия в современном образовании

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

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

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

Электронное пособие - это программно-методический обучающий комплекс, предназначенный для изучения учащимся учебного материала по определенным дисциплинам.

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

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

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

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

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

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

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

2.1.2. Требования к электронному пособию

1. Требования к структуре электронного учебного пособия

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

Главная страница

Функциональность учебного пособия не исключает проработку дизайна главной страницы. Эта страница должна быть связующим звеном между различными разделами пособия и позволять без проблем перейти к любому из них. На главной странице должны присутствовать:

• Название курса, по которому сделан учебник.

• Ссылка на список (меню) основных разделов пособия.

• Ссылка на методические рекомендации, которые должны содержать цель и задачи изучаемого курса, программу, список рекомендованной литературы.

• Ссылка на информацию об авторах.

Навигационная система

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

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

Разделы тоже могут иметь свое собственное меню для содержания в нем тем. Вызов страниц с конкретными темами должен быть возможен только из меню раздела. Перемещение между страницами осуществляется только в пределах объединяющего их раздела.

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

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

2. Требования к техническому исполнению

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

2.2. Обзор средств разработки электронных пособий

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

• Традиционные алгоритмические языки:

• Инструментальные средства общего назначения;

• Средства мультимедиа;

• Гипертекстовые и гипермедиа средства.

Традиционные алгоритмические языки. Характерные черты электронных пособий, созданных средствами прямого программирования:

1. Разнообразие стилей реализации (цветовая палитра, интерфейс, структура электронного пособия, способ подачи материала и т.д.);

2. Сложность модификации и сопровождения;

3. Большие затраты времени и трудоемкость;

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

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

1. Формирование структуры электронного пособия;

2. Ввод, редактирование и форматирование текста (текстовый редактор);

3. Подготовка статической иллюстративной части (графический редактор);

4. Подготовка динамической иллюстративной части (звуковых и анимационных фрагментов);

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

К достоинствам инструментальных средств общего назначения следует отнести:

1. Возможность создания электронных пособий лицами, которые не являются квалифицированными программистами;

2. Существенное сокращение трудоемкости и сроков разработки электронного пособия;

3. Невысокие требования к компьютерам и программному обеспечению.

Вместе с тем ИСОН имеет ряд недостатков, таких как:

• Меньшие, по сравнению с мультимедиа и гипермедиа системами, возможности;

• Отсутствие возможности создания программ дистанционного обучения.

Существует множество ИСОН: Адонис, АосМикро, Сценарий, ТесСис, Интегратор и др.

Рис. 2.1 Окно программы Adonis

Средства мультимедиа

Еще до появления новой информационной технологии эксперты, проведя множество экспериментов, выявили зависимость между методом усвоения материала и способностью восстановить полученные знания некоторое время спустя. Если материал был звуковым, то человек запоминал около 14 его объема. Если информация была представлена визуально - около 13. При комбинировании воздействия (зрительного и слухового) запоминание повышалось до половины, а если человек вовлекался в активные действия в процессе изучения, то усвояемость материала повышалось до 75%.

Итак, мультимедиа означает объединение нескольких способов подачи информации - текст, неподвижные изображения (рисунки и фотографии), движущиеся изображения (мультипликация и видео) и звук (цифровой и MIDI) - в интерактивный продукт.

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

Динамический видеоряд практически всегда состоит из последовательностей статических элементов (кадров). Здесь выделяются три типовых элемента: обычное видео (около 24 фото в секунду), квазивидео (6-12 фото в секунду), анимация. Использование видеоряда в составе мультисреды предполагает решение значительно большего числа проблем, чем использование аудио. Среди них наиболее важными являются: разрешающая способность экрана и количество цветов, а также объем информации.

Характерным отличием мультимедиа продуктов от других видов информационных ресурсов является заметно больший информационный объем, поэтому в настоящее время основным носителем этих продуктов является оптический диск CD-ROM стандартной емкостью 640 Мбайт. Для профессиональных применений существует ряд других устройств (CD-Worm, CD-Rewritaeble, DVD и др.), однако они имеют очень высокую стоимость.

Средства мультимедиа: OnViz и CourseBuilder, Dazzler Deluxe, HyperStudio и др.

Рис. 2.2 Окно программы HyperStudio

Рис. 2.3 Окно программы Dazzler Deluxe

Гипертекстовые и гипермедиа средства

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

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

В настоящее время существует множество различных гипертекстовых форматов (HTML, DHTML, PHP и др.).

Критерии выбора средств

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

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

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

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

2.3. Средства разработки электронного пособия «Абстрактное вычислительное устройство: машина Тьюринга»

HTML

HTML - это язык гипертекстовой разметки текста. Гипертекстовым HTML называется потому, что с его помощью на странице можно устанавливать ссылки на другие web -документы.

HTML, в своем первоначальном виде, был основан на языке SGML - Standart Generalized Markup Language (стандартный обобщенный язык разметки).

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

Также отдельно от существующего текста выносился DTD - файл, определяющий тип документа, для гарантии его обработки.

Разработчик HTML документа может выбрать способ работы с ним. Теоретически с гипертекстом можно работать даже на уровне MSDOS в любом редакторе, открывающем ASCII файлы. Правда, это требует от пользователя обязательного знания большинства элементов HTML. Можно использовать для создания гипертекста и браузер. Любая из этих программ имеет режим редактирования web - страницы в режиме «источника». Для этого может подключаться один из установленных на компьютере текстовых редакторов. Браузеры имеют и встроенные редакторы гипертекста. Наконец, существуют гипертекстовые редакторы, которые используются только для разработки Web-страниц и создания на последних всевозможных визуальных и звуковых эффектов.

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

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

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

Несмотря на то, что спецификация HTML является стандартом, этот язык дополняется новыми элементами (расширениями). Поэтому некоторые Web-страницы удобнее просматривать при помощи определенных браузеров. Расширения создаются только известными фирмами, которые разрабатывают программное обеспечение для WWW, а рядовые пользователи могут совершенствовать свои Web-страницы при помощи программирования.

Синтаксис HTML

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

Элементы условно можно разделить на две группы. Большинство элементов (называемые также контейнерами) задаются с помощью трех компонентов: начальный тег, содержимое и конечный тег. В начальном теге в угловых скобках указывается имя элемента и список атрибутов, в конечном - только имя элемента, предваряемое символом слэш ( / ). Содержимое элемента располагается между начальным и конечным тегами и интерпретируется браузером согласно правилам, определенным в спецификации стандарта HTML. Например, элемент b ( от английского bold ) задает полужирное начертание для текста, расположенного между тегами и . Некоторые элементы могут вкладываться друг в друга, например, вложение элемента b (полужирное начертание) в элемент i (курсив) обеспечит полужирный курсив; фрагмент документа

«начало текста один два три продолжение текста»

будет отображен браузером так:

начало текста один два три продолжение текста

Элементы другой группы (называемые также автономными) не имеют содержимого и конечного тега. При их интерпретации в отображаемый документ вставляется тот или иной объект. Например, тег , встречающийся в тексте HTML-документа, вызывает вставку графического изображения из файла img8.png .

HTML-документ заключается в теги и . Между этими тегами располагаются два раздела: раздел заголовка ( элемент head ) и раздел тела документа ( элемент body для простого документа либо элемент frameset, задающий набор кадров ). Все указанные элементы имеют начальный и конечный тег.

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

Формально, согласно спецификации HTML 4+, первым в документе должен указываться элемент doctype, сообщающий браузеру об использованной версии HTML (а версии, как уже говорилось, различаются наборами допустимых элементов и правилами их объявления). В элементе doctype указывается также адрес, с которого браузер может загрузить определение типа документа - Dtd (Document Type Definition). На практике же этот элемент зачастую опускают без ущерба для отображения документа.

Вот пример HTML-документа:

<meta charset="utf-8">

<title>Абстрактное вычислительное устройство: машина Тьюрингаtitle>

<body>

Электронное пособие
"Абстрактное вычислительное устройство: машина Тьюринга"

Понятие алгоритма

Формализация понятий алгоритм

<p><a href="algorithm.html">Алгоритмы и абстрактные вычислительные устройстваa>p>

<p><a href="history.html">История появления и принципы работы машины Тьюрингаa>p>

Машина Тьюринга

Свойства машины Тьюринга как алгоритма

<p><a href="algo2000.html">Интерпретатор машин Тьюринга и Поста - Алго 2000a>p>

<p><a href="pract.html">Примеры реализации алгоритмов с помощью машины Тьюрингаa>p>

<p><a href="practice.html">Практические заданияa>p>

<p><a href="solving.html">Решения Заданийa>p>

Тест

PHP

PHP (Hypertext Preprocessor) - наиболее простой скриптовый язык программирования, широко применяющийся при создании динамически генерируемых web-страниц. Основная масса Интернет ресурсов, на данный момент, написана с использованием именно этого языка программирования. При всей своей простоте, PHP позволяет разрабатывать профессиональные web-проекты любой сложности, от небольших сайтов до крупных порталов. PHP-код программы выполняется на стороне сервера. После того, как пользователь совершил на сайте некое действие, например клик по ссылке в меню, с целью перейти на другую страницу сайта, браузер посылает запрос серверу на соответствующую страницу с PHP-кодом. Далее, PHP-код обрабатывается интерпретатором PHP и генерируется HTML-код, который возвращается серверу. Сервер в свою очередь, передаёт этот HTML-код обратно браузеру. В результате пользователь видит отображение в браузере новой страницы, имеющей свой HTML-код. При просмотре же исходного кода этой страницы виден будет только HTML-код, а PHP-код остается недоступен для просмотра. Большой плюс языка PHP состоит в том, что PHP-код можно внедрять непосредственно в HTML-файлы. PHP-код встраивается в HTML-страницы при помощи угловых скобок и знака вопроса:

<?php

$counter = 0;

if($_POST[1] == 1)

$counter++;

if($_POST["2"] == 1)

$counter++;

if($_POST["3"] == 2)

$counter++;

if($_POST["4"] == 1)

$counter++;

if($_POST["5"] == 3)

$counter++;

if($_POST["6"] == 1)

$counter++;

if($_POST["7"] == 4)

$counter++;

if($_POST["8"] == 2)

$counter++;

if($_POST["9"] == 1)

$counter++;

if($_POST["10"] == 3)

$counter++;

echo "Правильных ответов: $counter из 10";

?>

Сами же файлы, в которых присутствует PHP-код, имеют расширение ***.php. Для создания web-проектов на языке php, необходимо программировать, используя либо установленный локальный сервер на своём компьютере, либо работая с помощью удалённого сервера. Удалённый сервер не всегда удобен, да и, как правило, за это надо платить. Для создания сервера на своём компьютере понадобятся следующие программы: Apache или Denver (сервер), MySQL (базы данных), PHP. Все программы актуальных версий можно найти на официальных сайтах разработчиков. Создание PHP-файлов, написание кода и работа с ним ничем не отличается от того же процесса, что и при работе с HTML. Работать с php-кодом можно также в обычном текстовом редакторе, но делать это с помощью php-редактора намного удобнее.

Синтаксис PHP прост и во многом похож на синтаксист языка C.

Общие принципы построения синтаксиса языка таковы:

• Весь код обязательно заключается в "скриптовые скобки": . Всё что находится внутри скобок, исполняется как PHP-инструкции, а всё что снаружи - передаётся пользователю в браузер без изменений

• Имена всех переменных начинаются со знака $.

• Имена функций обязательно завершаются парой скобок (), даже если функция не имеет параметров. Исключение составляют некоторые базовые функции PHP, которые являются частью языка, например, echo.

Выводы к главе 2

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

Электронное пособие - это программно-методический обучающий комплекс, предназначенный для изучения учащимся учебного материала по определенным дисциплинам.

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

Так же описаны основные особенности HTML и PHP - средства разработки электронного пособия «Абстрактное вычислительное устройство: машина Тьюринга».

Глава 3. Руководство пользователя электронным пособием «Абстрактное вычислительное устройство: машина Тьюринга»

3.1. Технические требования

Минимальные системные требования:

• Операционная система - Windows'98 и Windows ME и Windows XP / Vista;

• Оперативная память - 64 Мб;

• Подключение к сети Internet;

• Internet Explorer 6+ или любой другой браузер.

3.2. Описание электронного пособия «Абстрактное вычислительное устройство: машина Тьюринга»

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

Разработанное пособие позволяет в короткие сроки ознакомиться с основами теории алгоритмов, особенностями использования машины Тьюринга. Изучить синтаксис машины Тьюринга и научиться составлять собственные программы. Весь материал изложен в удобно читаемом виде. Также пособие содержит набор примеров реализации алгоритмов с помощью машины Тьюринга.

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

Пособие выполнено таким образом, что может быть размещено на web-ресурсе, что позволит иметь доступ к материалу с любой точки мира.

Рис. 3.1 Электронное пособие «Абстрактное вычислительное устройство: машина Тьюринга» - Понятие алгоритма

Рис. 3.2 Электронное пособие «Абстрактное вычислительное устройство: машина Тьюринга» - Тест

Рис. 3.3 Электронное пособие «Абстрактное вычислительное устройство: машина Тьюринга» - Решения заданий

Рис. 3.4 Электронное пособие «Абстрактное вычислительное устройство: машина Тьюринга» - Машина Тьюринга

Выводы к главе 3

Электронное пособие «Абстрактное вычислительное устройство: машина Тьюринга» разработано для ознакомления учеников с фундаментальными основами компьютерных вычислений.

В третьей главе описывается данное пособие, и определяются минимальные системные требования.

Заключение

Первая модель алгоритма - это абстрактная вычислительная машина (устройство). Она явилась абстрактным прообразом реальных вычислительных машин.

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

Исходя из свойств алгоритма, можно сформулировать общие требования к таким машинам:

1. Характер их функционирования должен быть дискретным, т.е. состоять из отдельных шагов (команд), каждый из которых выполняется только после завершения предыдущего;

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

3. Перед началом работы машине предоставляются исходные данные из области определения алгоритма;

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

5. Машина должна быть универсальной, т.е. такой, чтобы с ее помощью можно быть бы выполнить любой алгоритм.

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

В ходе выполнения данной квалификационной работы были рассмотрены несколько интерпретаторов машины Тьюринга - Алго2000 и Машина Тьюринга v.1.1. Помимо них существует множество online - эмуляторов - предназначенных для реализации алгоритмов.

В рамках квалификационной работы было разработано электронное пособие «Абстрактное вычислительное устройство: машина Тьюринга».

Разработанное пособие позволяет в короткие сроки ознакомиться с основами теории алгоритмов, особенностями использования машины Тьюринга. Изучить синтаксис машины Тьюринга и научиться составлять собственные программы. Весь материал изложен в удобно читаемом виде. Также пособие содержит набор примеров реализации алгоритмов с помощью машины Тьюринга.

Список использованных источников

1. Игошин В.И. Математическая логика и теория алгоритмов : учеб. пособие для студ. высш. учеб. заведений / В. И. Игошин. - 2-е изд., стер. - М.: Издательский центр «Академия», 2008. - 448 с.

2. Гильберт Д., Аккерман В. Основы теоретической логики. - М.: Издательская группа URSS, 2010. - 304 с.

3. Минский М. Вычисления и автоматы: - М.: Издательская группа «Мир», Москва, 1-й Рижский пер. 2, 1971. - 366 с.

4. Ясинский В.Б. Каким должен быть электронный учебник в формате HTML // Электронный журнал "Исследовано в России", 4, 115-129 , 2001.

5. Михалищева М. А. Использование электронных учебных пособий в учреждениях профессионального образования [Текст] / М. А. Михалищева, С. В. Турукина // Проблемы и перспективы развития образования: материалы IV междунар. науч. конф. (г. Пермь, июль 2013 г.). - Пермь: Меркурий, 2013. - С. 127-129.

6. Ильина М.А. Электронные учебные пособия, и их важность в учебном процессе // Электронный научный журнал «Информационно-коммуникационные технологии в педагогическом образовании», 2012. - Режим доступа: journal.kuzspa.ru/articles/87/

7. Шауцукова Л.З. Информатика 10 - 11. - М.: Просвещение, 2000 г. [Электронный ресурс]. - Режим доступа: book.kbsu.ru/theory/index.html

8. Котова А. , Машина Тьюринга. Научно-популярный
   физико-математический журнал "Квант" 1992г, номер 7 [Электронный ресурс]. - Режим доступа: kvant.mccme.ru/1992/07/mashina_tyuringa.htm

9. Лавров И. А. Сложность вычислений на абстрактных машинах ispras.ru/proceedings/docs/2007/12/isp_12_2007_95.pdf

10. Научно образовательный портал. Алан Мэтисон Тьюринг. [Электронный ресурс]. - Режим доступа: originweb.info/education/informatics/alan_turing.html

11. Фонд знаний «Ломоносов». Математическая логика. [Электронный ресурс]. - Режим доступа: lomonosov-fund.ru/enc/ru/encyclopedia:0165:article

12. Гультяев А. Разработка мультимедийных учебных курсов. СПб.: Учитель и ученик: КОРОНА принт., 2002. - 400 с.

13. Гончаров А. Самоучитель HTML М.: Наука, 1999. - 310 с.

14. Леонтьев Б. Web-дизайн: Тонкости, хитрости и секреты. М.: Познавательная книга плюс, 1999. - 192 с.

15. Трахтенброт Б.А. Алгоритмы и мышиное решение задач. -М.: Государственное издательство технико - теоретической литературы, 1957 г, - 96 с.

16. Булос Дж., Джеффри Р. Вычислимость и логика. Пер. с англ. - М., Мир, 1994 - 396с.

17. Фомичев В.С. Формальные языки, грамматики и автоматы. [Электронный ресурс]. - Режим доступа: iitam.omsk.net.ru/~eugene/docums/formallang/Fomichev/