Конспект урока информатики в 10 классе по теме «Обработка информации и алгоритмы»

Составитель: Грехова Екатерина Александровна, I квалификационная категория, МАОУ г.Владимира «Средняя общеобразовательная школа №14», учитель математики и информатики.

Цели урока:

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

1) способствовать углублению представлений учащихся об алгоритмах обработки информации;

2) ввести понятие алгоритмической машины, рассказать о моделях алгоритмических машин Тьюринга и Поста;

3) способствовать формированию умения составлять программу на компьютерной модели машины Поста.

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

1) способствовать развитию логического мышления;

2) способствовать развитию кругозора учащихся;

3) способствовать развитию интереса к изучаемому предмету.

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

1) способствовать формированию коммуникативных умений учащихся;

2) способствовать развитию информационно-познавательной компетенции учащихся.

Оборудование: компьютеры для учащихся с установленной на них машиной Поста.

Ход урока:

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

2. Постановка целей и задач урока

«Сами машины - это пустые перчатки,
но их надевает человеческая рука,
которая может быть хорошей или плохой»

Р.Брэдбери.

В 1931 году австрийский математик А.Гедель  доказал теорему о неполноте. Поэтому было высказано предположение о том, что некоторые задачи алгоритмически неразрешимы, то есть для них в принципе не существует алгоритма решения, и поэтому искать его бессмысленно. Исследования, которые начали проводить в этой области в 30-х годах 20-го века привели к возникновению теории алгоритмов. В настоящее время, теория алгоритмов занимается: доказательством алгоритмической неразрешимости задач; анализом сложности алгоритмов; сравнительной оценкой качества алгоритмов.

Появляется новый термин «универсальный исполнитель». Универсальным исполнителем называют исполнителя, для которого можно построить алгоритм, эквивалентный любому алгоритму для любого другого исполнителя.

Сегодня мы познакомимся с моделями «универсальных исполнителей» и на одном из них напишем программу.

3. Актуализация опорных знаний

Давайте вспомним, что понимают под обработкой информации?

Обработка информации – это процесс изменения формы представления информации или её содержания.

Кто может быть исполнителем обработки информации?

Исполнителем обработки информации может быть человек или автомат (компьютер).

Какие варианты обработки информации Вам известны?

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

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

Алгоритм – это определенная последовательность логических действий для решения поставленной задачи.

Приведите примеры алгоритмов.

Примеры алгоритмов:

а) алгоритм нахождения корней квадратного уравнения с помощью теоремы Виета;

б) алгоритм Евклида.

Какими свойствами обладает алгоритм?

Свойства алгоритмов:

• Дискретность (разделенность на части) и упорядоченность. Алгоритм должен состоять из отдельных действий, которые выполняются последовательно друг за другом.

• Детерминированность (однозначная определенность). Многократное применение одного алгоритма к одному и тому же набору исходных данных всегда дает один и тот же результат.

• Формальность. Алгоритм не должен допускать неоднозначности толкования действий для исполнителя.

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

• Массовость. Определенный алгоритм должен быть применим ко всем однотипным задачам.

4. Объяснение нового материала

В 30-х годах ХХ века возникает новая наука – теория алгоритмов. Вопрос, на который ищет ответ эта наука: для всякой ли задачи обработки информации может быть построен алгоритм решения? Но чтобы ответить на этот вопрос, надо сначала договориться об исполнителе, на которого должен быть ориентирован алгоритм.

В 1936 году английский ученый Алан Тьюринг и английский математик и логик польского происхождения Эмиль Пост независимо друг от друга предложили модели таких исполнителей – алгоритмические машины.

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

Послушаем сообщения о жизни Эмиля Поста и Алана Тьюринга (заранее готовят два ученика, материал есть в конце учебника).

Сравнительная характеристика машины Поста и машины Тьюринга:

Название машины

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

Машина Поста

Описание машины

абстрактная вычислительная машина

Состав машины

1. счетная лента (разделенной на ячейки и ограниченной слева, но не справа),

2. читающая и пишущая головка,

3. лентопротяжный механизм,

4. операционное исполнительное устройство

1. бесконечная лента, разделенная на одинаковые ячейки

2. читающая, пишущая и перемещающаяся головка

Алфавит

Внешний и внутренний алфавит (конечное множество состояний каретки)

двузначный или трехзначный

Выполняемые действия

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

2) выполнять сдвиг по ленте на одну ячейку вправо/влево или оставаться неподвижным;

3) переходить в новое состояние;

4) прекращать работу (останавливаться).

V j - поставить метку, перейти к j-й строке программы.

X j - стереть метку, перейти к j-й строке программы.

<- j - сдвинуться влево, перейти к j-й строке программы.

-> j - сдвинуться вправо, перейти к j-й строке программы.

? j1; j2 - если в ячейке нет метки, то перейти к j1-й строке программы, иначе перейти к j2-й строке программы.

! – конец программы (стоп).

Запись программы для машины

записывается в таблице

состоит из пронумерованных строк

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

5. Практическая работа

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

Указание:

Будем представлять натуральное (целое неотрицательное) число P набором из P+1 единиц и разделять числа нулём. Исходное положение каретки помечено символом «v»

v

0

0

1

1

1

1

1

0

1

1

1

0

0

0

Р

Q

Программа вычитания состоит из последовательного затирания крайних левых меток у Q и правых у P:

1. Х - стираем левый символ у Q

2. →

3. ? 4, 5

4. Stop - стоп если затерли Q=0

5. ←

6. ? 5, 7 - цикл поиска P

7. Х - стираем правый символ у P

8. →

9. ? 8, 1 - ищем Q

Отметим, что номер команды перехода не указывается, если переход происходит на следующую по порядку строку (для наглядности текста). В 6-ой строке возможно зацикливание, если Q > P. Проверьте работу программы.

6. Постановка домашнего задания

прочитать стр.46-49, устно вопр.1, 2, 4, 5 стр.49, письм.вопр.3, 6 стр.4

7. Подведение итогов урока

В чем различие между машинами Поста и Тьюринга?

Какие действия выполняет машина Поста?

Какие трудности у Вас возникли при написании программы вычитания двух чисел на машине Поста?

Выставление оценок активным учащимся.

Используемые материалы:

Информатика и ИКТ. Базовый уровень: учебник для 10-11 классов/ И.Г.Семакин, Е.К.Хеннер - М.: Бином. Лаборатория знаний, 2012