Рабочие листы
к вашим урокам
Скачать
Тема урока: «Уточнение понятия алгоритма. Универсальные исполнители» Цели: образовательная: дать представление об основных понятиях формального алгоритма:входной алфавит, слово, алфавит состояний, начальное состояние, пассивное состояние, «пусто»; развивающая: совершенствование умственной и познавательной деятельности учащихся, развитие мышления учащихся; воспитательная: сознательное усвоение материала учащимися; Ход урока: 1. Организационный момент 2. Изучение нового материала Работа с презентацией Уточнённое понятие алгоритма: Алгоритм - это организованная последовательность действий, понятных для некоторого исполнителя, ведущая к решению поставленной задачи. Исполнитель алгоритма - это тот объект или субъект, для управления которым составлен алгоритм.назовите свойства алгоритма (понятность, точность, конечность, дискретность, результативность);назовите способы записи алгоритмов (графический, словесный, в виде программ);Назовите типы алгоритмов? Приведите примеры. (линейные, алгоритмы с ветвлениями, алгоритмы с повторениями) Алгоритм – это конечная система правил, сформулированная на языке исполнителя, которая определяет последовательность перехода от допустимых исходных данных к конечному результату и которая обладает свойствами дискретности, детерминированности, результативности, конечности и массовости). Определения алгоритма, которые мы с вами рассматривали не являются строгими, так как в них используются не определяемые точно термины, например «правило». Однако математики достаточно долго пользовались интуитивным понятием алгоритма. В рамках подобного определения были сформулированы и успешно применялись на практике алгоритмы для решения таких задач, как нахождение корней квадратного и кубических уравнений, решение систем линейных уравнений (метод Гаусса) и др. Постепенно математики подходили к постановке и решению все более сложных задач. Так, например, Г. Лейбниц в XVII веке пытался построить общий алгоритм решения любых математических задач. В XX веке эта идея прибрела более конкретную форму: построить алгоритм проверки правильности любой теоремы при любой системе аксиом. Построить такие алгоритмы не удавалось, и математики выдвинули предположение: а вдруг для того или иного класса задач в принципе невозможно построить алгоритм решения. Следовательно, если алгоритма не существует, то они ищут то, чего нет. На основе этого предположения возникло понятие алгоритмически неразрешимой задачи – задачи, для которой невозможно построить процедуру решения задачи. Надо было научиться математически строго доказывать факт отсутствия соответствующего алгоритма. А это возможно только в том случае, если существует строгое определение алгоритма. Поэтому возникла проблема: построить формальное определение алгоритма, аналогичное известному интуитивному понятию. Попытки выработать формальное определение алгоритма привели в 20-30 –х годах XX века к возникновению теории алгоритмов. В первой половине XX века разные математики (А. Тьюринг, Э. Пост, А.Н. Колмагоров, А.А.Марков идр.) предложили несколько подходов к формальному определению алгоритма: нормальный алгоритм Маркова, машина Тьюринга, машина Поста и т. д. В дальнейшем было показано, что все эти определения эквивалентны. Мы рассмотрим формальное определение алгоритма, введенное А. Тьюрингом. Тьюринг признан одним из основателей информатики и теории искусственного интеллекта, его считают первым теоретиком современного программирования и, наконец, первым в мире хакером. Между прочим, его «хакерская деятельность» внесла во время второй мировой войны существенный вклад в победу союзных войск над германским флотом, а один из коллег Тьюринга однажды сказал: «Я не берусь утверждать, что мы выиграли войну благодаря Тьюрингу. Однако без него могли бы её и проиграть». Для уточнения понятия алгоритма была предложена абстрактная вычислительная конструкция, которая позже была названа машиной. Тьюринг описал свою машину в 1936 году. Целью создания такой абстрактной воображаемой машины было получение возможности доказательства существования или не существования алгоритмов решения различных задач. Руководствуясь этой целью, Тьюринг искал как можно более простую, «бедную» алгоритмическую схему, лишь бы она была универсальной. Прежде чем мы начнем знакомиться с машиной Тьюринга, необходимо сделать замечания относительно объектов, с которыми работают алгоритмы. Замечание. Алгоритм имеет дело не с объектами реального мира, а с некоторыми изображениями этих объектов (объектами работы алгоритмов могут быть только слова).Любой алфавит можно заменить другим (закодировать). Будем считать, что алгоритмы работают со словами, и мы формально описываем объекты – слова, над которыми работают алгоритмы, в некотором алфавите. Описание машины Тьюринга Машина Тьюринга – это строгое математическое построение, математический аппарат, созданный для решения определённых задач. Этот математический аппарат был назван «машиной» по той причине, что по описанию он похож на вычислительную машину. Принципиальное отличие машины Тьюринга от вычислительной машины заключается в том, что у машины Тьюринга запоминающее устройство есть бесконечная лента: у реальных вычислительных машин устройство может быть сколь угодно большим, но не бесконечным. В каждой машине Тьюринга есть две части: Неограниченная в обе стороны лента, разделённая на ячейки;Автомат (головка для считывания/записи, управляемая программой) 1 1 1 * 1 1 С каждой машиной Тьюринга связаны два конечных алфавита: алфавитвходных символов А={а0,а1,а2,…,ам}алфавит состояний Q={q0,q1,q2,…,qм} буква а0 -признак того, что ячейка пуста состояние q1 – начальное состояние q0 – пассивное (если машина попала в это состояние, то она закончила свою работу). Автомат каждый раз видит только одну ячейку. В зависимости от того, какую букву он видит, а так же в зависимости от своего состояния qi, автомат может выполнять следующие действия: записать новую букву в обозреваемую ячейку;выполнить сдвиг по ленте на одну ячейку вправо/влево или остаться на месте;перейти в новое состояние.
6 671 964 материала в базе
Настоящий материал опубликован пользователем Брух Таисия Викторовна. Инфоурок является информационным посредником и предоставляет пользователям возможность размещать на сайте методические материалы. Всю ответственность за опубликованные материалы, содержащиеся в них сведения, а также за соблюдение авторских прав несут пользователи, загрузившие материал на сайт
Если Вы считаете, что материал нарушает авторские права либо по каким-то другим причинам должен быть удален с сайта, Вы можете оставить жалобу на материал.
Удалить материалВаша скидка на курсы
40%Курс профессиональной переподготовки
500/1000 ч.
Курс повышения квалификации
36/72 ч.
Курс профессиональной переподготовки
300/600 ч.
Курс профессиональной переподготовки
300 ч. — 1200 ч.
Мини-курс
6 ч.
Мини-курс
3 ч.
Мини-курс
4 ч.
Оставьте свой комментарий
Авторизуйтесь, чтобы задавать вопросы.