Новости Словари Конкурсы Бесплатные SMS Знакомства Подари звезду
В нашей
базе уже
59876
рефератов!
Логин

Пароль

Программное и методическое обеспечение к интерпретатору машины Тьюринг

Программное и методическое обеспечение к интерпретатору машины Тьюринг.
Программное и методическое обеспечение к интерпретатору машины Тьюринга



Министерство общего и профессионального образования Российской Федерации Филиал ОмГПУ в г. Таре Математический факультет ВЫПУСКНАЯ КВАЛИФИКАЦИОННАЯ РАБОТА по специальности математика Программное и методическое обеспечение к интерпретатору машины Тьюринга Выполнила студентка 5 курса Самсонова Н.Д. Научный руководитель к.т.н., доцент Червенчук В.Д. Тара 2000 г. СОДЕРЖАНИЕ Введение 3 Глава 1. Машина Тьюринга, как математическая модель алгоритма. 4 1.1.Устройство машины Тьюринга 4 1.2. Вычисления на машинах Тьюринга 8 1.3. Машины Тьюринга с двумя выходами 15 Глава 2. Методика обучения машинам Тьюринга старших школьников 21 2.1. Характеристика познавательного развития учащихся старшего школьного возраста 21 2.2. Организация занятий по обучению машинам Тьюринга 23 2.3. Инструкция по использованию интерпретатора 26 2.4. Анализ результатов экспериментального исследования 30 Заключение 33 Список литературы 34 Приложения 36 ВВЕДЕНИЕ Понятие алгоритма является одним из основных понятий современной математики. Еще на самых ранних ступенях развития математики в ней стали возникать различные вычислительные процессы чисто механического характера. С их помощью искомые величины ряда задач вычислялись из исходных величин по определенным правилам и инструкциям. Со временем все такие процессы в математике получили название алгоритмов. Первоначально теория алгоритмов возникла в связи с внутренними потребностями теоретической математики. Математическая логика, основания математики, алгебра, геометрия и анализ остаются и сегодня одной из основных областей приложения теории алгоритмов. Другая ее область возникла в 40-х годах в связи с созданием быстродействующих электронных вычислительных и управляющих машин. Появление ЭВМ способствовало развитию теории алгоритмов, вызвало к жизни разделы этой теории (алгоритмические системы и алгоритмические языки), имеющие ярко выраженную прикладную направленность. Наконец, теория алгоритмов оказалась тесно связанной и с рядом областей лингвистики, экономики, физиологии мозга и психологии, философии, естествознания. Примером одной из задач этой области может служить точное описание алгоритмов, реализуемых человеком в процессе умственной деятельности. Чтобы иметь возможность более уверенно решать алгоритмические задачи, возникающие в различных разделах теоретической и прикладной математики, необходимо иметь достаточно развитую теорию алгоритмов [3]. В процессе изучения курса "Теория алгоритмов" целесообразно определить понятие алгоритма, рассмотреть такие алгоритмические системы, как рекурсивные функция, машина Поста, машина Тьюринга; исследовать связи теории алгоритмов с теорией автоматов и с универсальными ЭВМ. Определение математического понятия алгоритма через машину Тьюринга эквивалентно и другим известным определениям этого понятия. В этом мы видим актуальность исследования машин Тьюринга. Несмотря на большой интерес к теме машины Тьюринга как со стороны профессоров и доцентов, так и со стороны студентов, до сих пор мы не встречали методики обучения школьников этой теме с помощью интерпретатора, позволяющего наглядно демонстрировать специфику работы машины. В этом мы видим проблему исследования [15, 16, 17]. Целью нашего исследования является разработка методики обучения машинам Тьюринга на базе специально адаптированного для условий школы интерпретатора машины Тьюринга. В связи с этим мы ставим перед собой следующие частные задачи: 1. изучить основы машин Тьюринга; 2. освоить технику программирования машин Тьюринга; 3. изучить основные режимы работы программы-интерпретатора; 4. составить инструкцию для пользователя при работе с интерпретатором; 5. разработать методику обучения учащихся машинам Тьюринга; 6. проверить степень усвоения учениками материала. Предмет исследования: методика обучения учащихся машинам Тьюринга. Глава 1. МАШИНА ТЬЮРИНГА, КАК МАТЕМАТИЧЕСКАЯ МОДЕЛЬ АЛГОРИТМА. 1.1 УСТРОЙСТВО МАШИНЫ ТЬЮРИНГА Английский математик А.М.Тьюринг в 1937 году впервые предложил вариант уточнения понятия алгоритма в виде воображаемой вычислительной машины, известной теперь под названием машина Тьюринга. Это воображаемая машина - машина " на бумаге " или математическая модель машины. Машины Тьюринга - чистая абстракция и никогда не были реализованы. Польза от нее в том, что с ее помощью можно доказать существование или несуществование алгоритмов решения различных задач. Так как машина выполняет определенный алгоритм, то к машине предъявляются требования, вытекающие из свойств алгоритмов. Во-первых, машина должна быть полностью детерминированной (вычисления должны быть точные и общепонятные) и действовать в соответствии с заданной системой правил. Во-вторых, она должна допускать ввод различных "начальных данных" (соответствующих различным задачам из данного класса задач). В-третьих, заданная система правил работы машины и класс решаемых задач должны быть согласованы так, чтобы всегда можно было "прочитать" результат работы машины. Теперь приступим к описанию одного из возможных вариантов функционирования машин Тьюринга, предложенную Э.Мендельсоном[7]. Имеется бесконечная одномерная лента, разделенная на ячейки, в каждой из которых может быть записан только один из символов конечного алфавита {}. В каждый момент времени каждая ячейка может быть занята не более чем одним символом. Машина обладает некоторым конечным множеством внутренних состояний {}. В каждый данный момент времени машина находится в точности только в одном из этих состояний. Наконец, имеется считывающая и записывающая головка, которая в каждый данный момент времени находится в одной из ячеек ленты. Машина действует не непрерывно, а лишь в дискретные моменты времени. Если в какой-то момент времени t читающая головка воспринимает ячейку (то есть стоит на ячейке), содержащей символ и машина находится во внутреннем состоянии , то действие машины определено, и она совершит один из следующих четырех актов: 1 головка стирает символ и записывает в той же ячейке новый символ , 2 головка перемещается в соседнюю слева ячейку 3 головка перемещается в соседнюю справа ячейку 4 машина останавливается. В случаях 1-3 машина переходит в новое внутреннее состояние и готова снова к действию в следующий момент t+1.Первые 3 из возможных актов действия машины могут быть описаны соответственно следующим
Умар.Ш. был тут !!!!!
 
давайте изгоним мат !!!
 
ДОБРОЙ НОЧИ ОТ Ъ
ЛОКИ ИНО
 
ДМК МЭ
 
где инфааа?