Урок по информатике на тему "Уточнение понятия алгоритма"

Тема: Уточнение понятия алгоритма.

Цели:

1. Образовательные:

• усвоение определений понятия «алгоритм»;

• формирование навыков работы с машиной Поста;

• формирование навыка использовать имитатор машины Поста для решения возникшей проблемы.

1. Воспитательные:

• воспитание умения находить связь учебной науки с жизненными ситуациями;

• побуждение желания объяснить происходящее;

• воспитание у учащихся творчества.

1. Развивающие:

• развитие логического мышления;

• формирование умений наблюдать.

Задачи урока:

• ознакомление с формальным определением понятия «алгоритм»;

• ознакомление с возможностями и структурой машины Поста;

• ознакомление с системой команд для машины Поста;

• формирование первичных навыков работы с машиной Поста;

• формирование навыка использовать имитатор машины Поста для решения возникшей проблемы.

Тип урока: изучение нового материала.

Оборудование: презентация, проектор.

План урока:

1. Организационный момент (1 мин)

2. Проверка домашнего задания (3мин)

3. Актуализация знаний (4 мин)

4. Изучение нового материала (18 мин)

5. Первичное закрепление (10 мин)

6. Подведение итогов (2 мин)

7. Домашнее задание (2 мин)

Ход урока:

1. Организационный момент. Здравствуйте! Я рада всех вас видеть. Присаживайтесь. Начнём наш урок. Для работы нам понадобятся: тетради, письменные принадлежности и ваша внимательность.

2. Проверка домашнего задания. По вопросам параграфа учащиеся отвечают на вопросы учителя.

3. Что такое динамический HTML? Какие технологии он использует?

• Динамический HTML (DHTML — это технология создания интерактивных сайтов, использующая HTML, CSS, язык программирования (чаще всего JavaScript) и объектную модель документа (англ. DOM — Document Object Model).

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

• Что представляет собой JavaScript-код?

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

• Что такое DOM? Зачем нужна такая структура?

Согласно   объектной   модели   документа   (DOM),   веб-страни­ца — это иерархия (дерево) объектов — рисунков,    блоков, абза­цев, ссылок и т. п. Корень этого дерева — объект document, кото­рый обозначает весь HTML-документ. На рисунке 4.24 показано дерево объектов простого HTML-документа.

• Что такое «ролл-овер»? Приведите примеры, когда этот эффект дей­ствительно полезен.

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

• курсор мыши вошёл в область рисунка (англ. mouse over —
  мышь над объектом);

• курсор мыши вышел из области рисунка (англ. mouse out —
  мышь вне объекта).

• Что такое обработчик события?

Обработчик события — это код на JavaScript, который выпол­няет некоторые действия (меняет рисунок), когда произошло со­бытие, с которым он связан.

• Что означает запись this.src?

• Здесь this означает «этот элемент», т. е. текущий тэг . Тогда this, src — это его атрибут src, так что приведённая строчка меняет рисунок при наведении мыши.

1. Актуализация знаний.

• Дайте определение понятию алгоритм,  исполнитель алгоритма;

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

• Исполнитель алгоритма - это тот объект или субъект, для управления которым составлен алгоритм.

• назовите свойства алгоритма (понятность, точность, конечность, дискретность, результативность);

• назовите способы записи алгоритмов (графический, словесный, в виде программ);

• Назовите типы алгоритмов? Приведите примеры. (линейные, алгоритмы с ветвлениями, алгоритмы с повторениями)

1. Изучение нового материала.

Зачем нужно определение алгоритма?

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

Особый интерес проявляли к алгоритмам математики. Один из древнейших известных алгоритмов — алгоритм Евклида для вычисления наибольшего общего делителя (НОД) двух натураль​ных чисел. Само слово «алгоритм» (от имени математика IX века аль-Хорезми, которого считают основателем алгебры) ввёл в нау​ку в XVII веке немецкий математик Г. В. Лейбниц.

В 1931 г. австрийский математик К. Гёдель доказал теорему о неполноте, смысл которой состоит в том,что в любой достаточ​но сложной формальной системе, основанной на аксиомах (напри​мер, в арифметике, где введены натуральные числа и операции сложения и умножения), есть утверждение, которое невозможно ни доказать, ни опровергнуть в рамках этой системы. Поэтому было высказано предположение о том, что некоторые задачи алгоритмически неразрешимы, т. е. для них в принципе не существует алгоритма решения, и поэтому искать его бессмыслен​но. Чтобы строго доказать или опровергнуть эту гипотезу, нужно было ввести математическое понятие алгоритма.

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

Исследования в этой области, которые начали активно прово​диться в 30-х годах XX века, привели к возникновению , которая занимается:

•​ доказательством алгоритмической неразрешимости задач;

• анализом сложности алгоритмов;

• сравнительной оценкой качества алгоритмов.

Значительный вклад в развитие теории алгоритмов внесли мате​
матики А. Тьюринг (Великобритания), Э. Пост (США), А. Чёрч
(Великобритания), С. Клини (США) и А. А. Марков (СССР).

 Что такое алгоритм?

Первые известные алгоритмы — это правила выполнения арифметических действий с числами. В них чётко определены объекты (числа в десятичной записи) и элементарные шаги (сло​жить, вычесть, перемножить два однозначных числа — вспомни​те таблицы сложения и умножения). Постепенно сложность за​дач, которые решались с помощью алгоритмов, увеличивалась, и понятие «шаг алгоритма» оказалось нечётким, размытым. Напри​мер, можно ли считать элементарным шагом разложение числа на простые множители или сложение многозначных чисел?

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

 Про любой алгоритм можно сказать следующее:

 • алгоритм получает на вход дискретный объект (например, слово);

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

 • если выполнение алгоритма заканчивается, его результат —это объект, построенный на последнем шаге; 

 • если выполнение алгоритма не заканчивается (алгоритм за​цикливается) или        заканчивается аварийно (например, в ре​зультате деления на 0), то результат его     работы при данном входе не определён.

Любой алгоритм рассчитан на определённого исполнителя: он должен использовать только понятные этому исполнителю команды. Задание для исполнителя — это текст на специальном (формальном) языке, который обычно называют программой. Поэтому можно определить алгоритм как программу для некоторого исполнителя.

Напомним,что с точки зрения теории алгоритмов, достаточно рассматривать только алгоритмы, работающие с цепочками символов, которые называют словами (рис. 5.1).

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

Функция, заданная алгоритмом, может быть нигде не опреде​лена. Например, алгоритм

нц пока да

кц

зацикливается при любом входном слове.

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

если а то                                          М:=Ь

М:=а                                                     если а то

иначе                                                    М:=а

М: =Ь                                                    все

все

1. Первичное закрепление.

Вопросы и задания
1. Зачем понадобилось уточнять понятие «алгоритм»?
2. Какие задачи рассматриваются в теории алгоритмов?
3. Почему  можно  ограничиться  алгоритмами  обработки  символьных
строк? Можно ли рассматривать только алгоритмы для преобразова-
ния двоичных кодов?
4. Как БЫ понимаете утверждение «Алгоритм задаёт некоторую функ¬
цию»?
5. Как связаны понятия «алгоритм» и «исполнитель»?
6. Что такое программа?
7. В каком случае говорят, что два алгоритма эквивалентны?
8. Что такое универсальный исполнитель?

1. Подведение итогов. Выставление оценок за работу на уроке.

2. Домашнее задание. п. 34 учить