Дипломная работа (бакалавр/специалист) на тему Элективный курс по информатике по теме «Функции, вычислимые по Тьюрингу»

Содержание:

Введение 2
Глава 1. Теория алгоритмов и машины Тьюринга 4
1.1. Неформальное определение алгоритма 4
1.2. Машины Тьюринга и вычислимые по Тьюрингу функции 9
1.3. Алгоритмически неразрешимые массовые проблемы 14
1.4. Сложность вычислений и массовых проблем 16
Глава 2. Тренажер машины Тьюринга 21
2.1. Знакомство с тренажером машины Тьюринга 21
2.2. Применение машины Тьюринга к преобразованию слов 23
2.3. Вычисление функций в единичной системе счисления 25
2.4. Вычисление функций в двоичной системе счисления 28
2.5. Проект рабочей программы элективного курса по информатике по теме «Вычислимые по Тьюрингу функции» 29
Заключение 55
Список литературы 57

Введение:

Актуальность темы исследования. Образование, как и любая дру-гая сфера человеческой деятельности в обществе, претерпевает трансфор-мации, связанные с изменениями условий, в образовательной отрасли. Направления этих изменений определяются образовательными концепци-ями и естественным образом являются результатом трансформации соци-альных и технических условий, которые сопровождают образование.
Работа ученика становится все более творческой и самостоятельной в решении проблем. Эпоха сбора бесполезных знаний закончилась, и ожи-дается, что ученик сможет использовать доступные средства информации и эффективно решать проблемы. Это становится возможным благодаря ис-пользованию информационных технологий в школе.
Компьютер занимает важное место в многоязычной теории образо-вания, поскольку он способствует многогранному развитию личности уче-ника, развивая все три типа индивидуальной деятельности. Кроме того, он сочетает в себе множество познавательных, интеллектуальных и культур-ных ценностей. Широкое использование компьютеров в образовании вы-зывает изменения в его структуре и его модернизации, заставляют учителя менять преподавательскую стратегию и методы работы в классе.
Использование компьютеров и информационных технологий — это возможность для образования отходить от трудно понимаемой теории, чтобы обучить способность использовать новую информацию, которая все время появляется, или находить ту информацию, которая необходима. Это касается большинства областей образования, особенно в области есте-ственных и гуманитарных наук, в которых накоплены огромные ресурсы знаний.
В образовании первостепенной целью является подготовка детей и молодежи к жизни в информационном обществе. Наиболее важным навы-ком, приобретенным учащимися во время общего образования в началь-ной школе, является способность использовать современные информаци-онные и коммуникационные технологии, включая поиск и использование информации. В средней школе и старшей школе одной из важных целей общего образования является формирование у учеников взглядов, опреде-ляющих эффективное и качественное функционирования в современном мире.
Конкретные алгоритмы в математике и практике известны давно. В настоящее время, особенно в связи с глобальной компьютеризацией, они прочно вошли в нашу жизнь. Развитие математики и математической логи-ки, а также в немалой степени стремительный прогресс компьютерной тех-ники вызвали к жизни и заставили развиться в 30-60-ые годы прошлого века общую науку об алгоритмах – теорию алгоритмов. Машинам Тьюринга посвящено много книг. Это не удивительно, ведь понятия ре-курсивной функции и машины Тьюринга – наиболее используемые в тео-ретической информатике точные версии интуитивного понятия алгоритма.
Объект исследования. Элективный курс по теории алгоритмов.
Предмет исследования. Решение задач по вычислимым по Тьюрин-гу функциям с применением тренажера «Машина Тьюринга».
Цель исследования. Разработка учебных материалов к элективному курсу по информатике по теме «Функции, вычислимые по Тьюрингу».
Задачи исследования.
1. Подготовка содержания занятий элективного курса по информати-ке (по теории алгоритмов) для учащихся 11 класса.
2. Составление рабочей программы элективного курса по информа-тике и методических указаний к практическим занятиям по изучению тео-рии алгоритмов с применением тренажера машины Тьюринга.
Информационная база исследования. Учебное пособие Игошина В.И. «Теория алгоритмов», а также свободно распространяемая програм-ма «Машина Тьюринга».Актуальность темы исследования. Образование, как и любая дру-гая сфера человеческой деятельности в обществе, претерпевает трансфор-мации, связанные с изменениями условий, в образовательной отрасли. Направления этих изменений определяются образовательными концепци-ями и естественным образом являются результатом трансформации соци-альных и технических условий, которые сопровождают образование.
Работа ученика становится все более творческой и самостоятельной в решении проблем. Эпоха сбора бесполезных знаний закончилась, и ожи-дается, что ученик сможет использовать доступные средства информации и эффективно решать проблемы. Это становится возможным благодаря ис-пользованию информационных технологий в школе.
Компьютер занимает важное место в многоязычной теории образо-вания, поскольку он способствует многогранному развитию личности уче-ника, развивая все три типа индивидуальной деятельности. Кроме того, он сочетает в себе множество познавательных, интеллектуальных и культур-ных ценностей. Широкое использование компьютеров в образовании вы-зывает изменения в его структуре и его модернизации, заставляют учителя менять преподавательскую стратегию и методы работы в классе.
Использование компьютеров и информационных технологий — это возможность для образования отходить от трудно понимаемой теории, чтобы обучить способность использовать новую информацию, которая все время появляется, или находить ту информацию, которая необходима. Это касается большинства областей образования, особенно в области есте-ственных и гуманитарных наук, в которых накоплены огромные ресурсы знаний.
В образовании первостепенной целью является подготовка детей и молодежи к жизни в информационном обществе. Наиболее важным навы-ком, приобретенным учащимися во время общего образования в началь-ной школе, является способность использовать современные информаци-онные и коммуникационные технологии, включая поиск и использование информации. В средней школе и старшей школе одной из важных целей общего образования является формирование у учеников взглядов, опреде-ляющих эффективное и качественное функционирования в современном мире.
Конкретные алгоритмы в математике и практике известны давно. В настоящее время, особенно в связи с глобальной компьютеризацией, они прочно вошли в нашу жизнь. Развитие математики и математической логи-ки, а также в немалой степени стремительный прогресс компьютерной тех-ники вызвали к жизни и заставили развиться в 30-60-ые годы прошлого века общую науку об алгоритмах – теорию алгоритмов. Машинам Тьюринга посвящено много книг. Это не удивительно, ведь понятия ре-курсивной функции и машины Тьюринга – наиболее используемые в тео-ретической информатике точные версии интуитивного понятия алгоритма.
Объект исследования. Элективный курс по теории алгоритмов.
Предмет исследования. Решение задач по вычислимым по Тьюрин-гу функциям с применением тренажера «Машина Тьюринга».
Цель исследования. Разработка учебных материалов к элективному курсу по информатике по теме «Функции, вычислимые по Тьюрингу».
Задачи исследования.
1. Подготовка содержания занятий элективного курса по информати-ке (по теории алгоритмов) для учащихся 11 класса.
2. Составление рабочей программы элективного курса по информа-тике и методических указаний к практическим занятиям по изучению тео-рии алгоритмов с применением тренажера машины Тьюринга.
Информационная база исследования. Учебное пособие Игошина В.И. «Теория алгоритмов», а также свободно распространяемая програм-ма «Машина Тьюринга».

Заключение:

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

Фрагмент текста работы:

Глава 1. Теория алгоритмов и машины Тьюринга
1.1. Неформальное определение алгоритма

Слово «алгоритм» является производным от имени выдающегося узбекского математика Мухаммеда Аль-Хорезми (Хорезма- историче-ская область современного Туркменистана). Мухаммеду Аль-Хорезми как и другим выдающимся учёным того времени было поручено зада-ние: перевести греческие труды в области математики. Аль-Хорезми также занимался астрономией, географией и многими другими науками. Но главная заслуга учёного состоит в том, что благодаря его труду За-падная Европа познакомилась с десятичной позиционной системой счисления. Арабский оригинал этой книги не сохранился, зато дошли до нашего времени латинские переводы его работы. Имя автора на латини-це читает, как «Алгоризми» впоследствии « Алгоритм». Данным словом какое -то время называли индийский позиционный счёт. Сегодня слово «алгоритм» обрело новый лексический смысл. Сами того не подозревая, мы периодически сталкиваемся с огромным количеством алгоритмов. Мнение о том, что алгоритм – это только математически-информационный термин является ошибочным. Даже процесс чаепития можно считать агоритмом, состоящем из определённых действий: кипя-чения воды, заварки чая, чайной церемонии, его употребления [15. c.23].
Таким образом, алгоритм — свод правил, четко и однозначно опре-деляющих процесс выполнения заданной работы в виде конечной по-следовательности действий или операций путем преобразования допу-стимых исходных данных в желаемый результат за конечное число ша-гов.
Основные свойства алгоритмов [10. c.31]:
1. Массовость. Алгоритм содержит в себе входные данные – аргу-менты, известные при постановке задачи. В примере с чаепитием вход-ными данными могут быть: вода, чай, сахар, сервис… Результат работы алгоритма — получение новых данных, в данном случае результатом яв-ляется чаепитие. Алгоритм преобразует исходную информацию в нуж-ную пользователю. Входные данные могут различаться, т.е. алгоритм применяют для целого класса задач одного типа. Это свойство алгорит-ма получило название массовость.
2. Понятность. Алгоритм состоит только из тех элементов, которые необходимы при в пределах условий решаемой задачи, и не содержит ничего лишнего, не нужного исполнителю.
3. Дискретность. Алгоритм делится на определённые блоки- более простые действия (алгоритм имеет дискретную структуру). Выполнение каждого из блоков выполняется последовательно и приводит к конечно-му результату.
4. Конечность. Процесс работы алгоритма заканчивается после выполнения определённого количества шагов.
5. Определенность Каждый этап алгоритма, должен представлять собой точность и не двусмысленность. Именно благодаря данному свой-ству выполнение алгоритма можно доверить компьютеру.
6. Эффективность. Каждый этап алгоритма, должен представлять собой точность и не двусмысленность. Именно благодаря данному свой-ству выполнение алгоритма можно доверить компьютеру каждый этап алгоритма, должен представлять собой точность и не двусмысленность. Именно благодаря данному свойству выполнение алгоритма можно до-верить компьютеру каждый этап алгоритма, должен представлять собой точность и не двусмысленность. Именно благодаря данному свойству выполнение алгоритма можно доверить компьютеру.
В современной теории алгоритмов не малое место отводят маши-нам вычислительных преобразований, так как именно они являются средством выполнения алгоритмических вычисления. Благодаря их со-зданию стала возможна алгоритмизация сложных задач и их быстрое решение. Машины вычислительных преобразований — механическое или электромеханическое устройство преобразующее входящую информа-цию в необходимый результат. В математике долгое время отсутствова-ла надобность в создании чёткой теории алгоритмов, однако появление большого количества неразрешимых заставило ведущие умы XX в. со-здать формальную чётко сформулированную науку — науку направлен-ную на поиск нужного алгоритма для любой задачи [7. c.15].
Построение такого формального подхода было начато с формали-зации объектов (операндов) алгоритма. За их основу было принято брать любые предметы окружающего мира: например, числа, показания приборов, фиксирующих параметры процессов, таблицы, пути в лаби-ринте и т.п. Все эти операнды алгоритма- записываются в виде опреде-лённого языка. Тогда получается, что исполнитель по средством алго-ритма преобразует слова в произвольном алфавите в слова, на том же языке, но имеющие совсем иной смысл.
Значительный вклад в теорию алгоритмов вложил в 1936 году ан-глийский математик А.Тьюринг, который формально описал конструк-цию некоторой абстрактной машины (машины Тьюринга). Основной те-зис учёного — «Всякий алгоритм может быть реализован соответствую-щей машиной Тьюринга» [1. c.104].
Не малых успехов в данном направлении добился и американский математик Э. Пост, который предложил иную преобразующую машину -машину Поста. Большой вклад в развитие теории алгоритмов внёс в1954 году советский математик А.А. Марков, разработавший теорию классов алгоритмов, названных им нормальными алгорифмами. Мака-ров также высказал свой основной тезис о том, что любой алгоритм нормализуем. Эти алгоритмические подходы схожи в том смысле, что алгоритмы, описываемые в одной из схем, могут быть также описаны и в другой. В последнее время эти теории алгоритмов объединяют под названием логические [1. c.105].
В современной теории алгоритмов не малое место отводят маши-нам вычислительных преобразований, как как именно они являются средством выполнения алгоритмических вычисления. Благодаря их со-зданию стала возможна алгоритмизация сложных задач и их быстрое решение. Машины вычислительных преобразований-механическое или электромеханическое устройство преобразующее входящую информа-цию в необходимый результат.
Способы представления алгоритмов [4. c.50]:
Словесный способ. Его смысл состоит в описании алгоритма на одном из языков при помощи терминов и общеупотребительных слов. Такой способ используется крайне редко так как он громоздок и неудо-бен, отнимает много времени и усилий.
Символический способ заключается в описании алгоритма при по-мощи определённого набора символов и обозначений. Данный способ также имеет недостатки так как он не обладает наглядностью. Символи-ческие сокращения целых выражений и действий делают алгоритм менее читабельным.
Графический способ пожалуй самый удобный способ представле-ния алгоритмо в- он представляет собой алгоритма в виде блок-схемы. Блоки в графическом способе соединяются стрелочками. Способ удобен и нагляден. При представлении задачи графическим способом применя-ют такие основные виды блоков (рисунок 1.1).

Рисунок 1.1. Пример алгоритма в графическом виде [3. c.140]
Справа указан алгоритм сложения двух чисел в виде блок-схемы.
Основные ресурсы: – время (время выполнения -временная слож-ность) и – объем памяти (ёмкостная сложность). Не сложно определить, что время более важный показатель в теории определения уровня слож-ности. Уровень сложности задачи может меняться. Он зависит от вход-ных данных (операндов задачи). Бывает два вида сложности:
1) в худшем случае
2) сложность в среднем случае.
Наиболее особое внимание уделяют сложности в худшем случае. Чаще всего оценивают порядок роста сложности при n¥: T = O (f (n)). Фактическая сложность (время выполнения алгоритма в единицу време-ни) зависит не только от конструкции алгоритма, но и от многих инди-видуальных показателей компьютера, таких как: производительность процессора, его тактовая чистота, старое оборудование.
Порядок увеличения сложности определяет количество решаемых задач. Теорема Блюма об ускорении гласит: «Существует такая алго-ритмически разрешимая задача Z, что любой алгоритм A, позволяющий решить задачу Z, можно ускорить следующим образом: создадим дру-гой алгоритм A¢, также решающий Z и такой, что TA’ (n) £ log TA(n) для почти всех n». Такой способ анализа алгоритмов не очень удобен [8. c.12].
В современной теории алгоритмов принято считать, что разумней вместо «сложности задачи» использовать классы сложности. Пусть f(n) — некоторая функция, отображающая N в N. Класс сложности C(f(n)) — это множество всех задач, для которых существует хотя бы один алгоритм, сложность которого не превышает O(f(n)). Специалисты по теории сложности считают, что это определение не совсем полное, и что в идеа-ле необходимо уточнить: Что мы имеем в виду под «алгоритмом»? Ка-кая сложность (временная, емкостная или какая-нибудь еще) конкретно интересует [8. c.13]. Многие исследователи делают заключение, что им хотелось бы отметить, что если бы человек так и не научился алгорит-мизировать свои действия: мы бы так и не смогли решить задачи повы-шенной сложности, в науке и технике проявился застой а многие изобре-тения и открытия попросту не были воплощены в жизнь.