Конспект урока информатики в 10 классе по теме «Обработка информации и алгоритмы»
Конспект урока информатики в 10 классе по теме «Обработка информации и алгоритмы»
Составитель: Грехова Екатерина Александровна, I квалификационная категория, МАОУ г. Владимира «Средняя общеобразовательная школа №14», учитель математики и информатики.
Цели урока:
Образовательные:
1) способствовать углублению представлений учащихся об алгоритмах обработки информации;
2) ввести понятие алгоритмической машины, рассказать о моделях алгоритмических машин Тьюринга и Поста;
3) способствовать формированию умения составлять
Развивающие:
1) способствовать развитию логического мышления;
2) способствовать развитию кругозора учащихся;
3) способствовать развитию интереса к изучаемому предмету.
Воспитательные:
1) способствовать формированию коммуникативных умений учащихся;
2) способствовать развитию информационно-познавательной компетенции учащихся.
Оборудование: компьютеры для учащихся с установленной на них машиной Поста.
Ход урока:
1.Организационный момент.
2. Постановка целей и задач урока
«Сами машины — это пустые перчатки, Но их надевает
Р. Брэдбери.
В 1931 году австрийский математик А. Гедель доказал Теорему о неполноте. Поэтому было высказано предположение о том, что некоторые задачи Алгоритмически неразрешимы, то есть для них в принципе не существует алгоритма решения, и поэтому искать его бессмысленно. Исследования, которые начали проводить в этой области в 30-х годах 20-го века привели к возникновению Теории алгоритмов.
В настоящее время, Теория алгоритмов занимается : доказательством алгоритмической неразрешимости задач; анализом сложности алгоритмов; сравнительной оценкой качества алгоритмов.
Появляется новый термин «универсальный исполнитель». Универсальным исполнителем называют исполнителя, для которого можно построить алгоритм, эквивалентный любому алгоритму для любого другого исполнителя.
Сегодня мы познакомимся с моделями «универсальных исполнителей» и на одном из них напишем программу.
3. Актуализация опорных знаний
Давайте вспомним, что понимают под обработкой информации?
Обработка информации — это процесс изменения формы представления информации или ее содержания.
Кто может быть исполнителем обработки информации?
Исполнителем обработки информации может быть человек или автомат .
Какие варианты обработки информации Вам известны?
Существуют следующие варианты обработки информации: получение новой информации, изменение формы представления информации, систематизация/структурирование данных, поиск информации.
Что такое алгоритм?
Алгоритм — это определенная последовательность логических действий для решения поставленной задачи.
Приведите примеры алгоритмов.
Примеры алгоритмов:
А) алгоритм нахождения корней квадратного уравнения с помощью теоремы Виета;
Б) алгоритм Евклида.
Какими свойствами обладает алгоритм?
Свойства алгоритмов:
Дискретность и упорядоченность. Алгоритм должен состоять из отдельных действий, которые выполняются последовательно друг за другом.
Детерминированность . Многократное применение одного алгоритма к одному и тому же набору исходных данных всегда дает один и тот же результат.
Формальность. Алгоритм не должен допускать неоднозначности толкования действий для исполнителя.
Результативность и конечность. Работа алгоритма должна завершаться за определенное число шагов, при этом задача должна быть решена.
Массовость. Определенный алгоритм должен быть применим ко всем однотипным задачам.
4. Объяснение нового материала
В 30-х годах ХХ века возникает новая наука — теория алгоритмов. Вопрос, на который ищет ответ эта наука: для всякой ли задачи обработки информации может быть построен алгоритм решения? Но чтобы ответить на этот вопрос, надо сначала договориться об исполнителе, на которого должен быть ориентирован алгоритм.
В 1936 году английский ученый Алан Тьюринг и английский математик и логик польского происхождения Эмиль Пост независимо друг от друга предложили модели таких исполнителей — алгоритмические машины.
Алгоритмическая машина — это автоматический исполнитель обработки знаковых последовательностей.
Послушаем сообщения о жизни Эмиля Поста и Алана Тьюринга .
Сравнительная характеристика машины Поста и машины Тьюринга:
Машина Тьюринга | Машина Поста | |
Описание машины | Абстрактная вычислительная машина | |
Состав машины | Счетная лента , Читающая и пишущая головка, Лентопротяжный механизм, Операционное исполнительное устройство | 1. бесконечная лента, разделенная на одинаковые ячейки 2. читающая, пишущая и перемещающаяся головка |
Внешний и внутренний алфавит | Двузначный или трехзначный | |
Выполняемые действия | 1) записывать новый символ в обозреваемую ячейку; 2) выполнять сдвиг по ленте на одну ячейку вправо/влево или оставаться неподвижным; 3) переходить в новое состояние; 4) прекращать работу . | V j — поставить метку, перейти к j-й строке программы. X j — стереть метку, перейти к j-й строке программы. -> j — сдвинуться вправо, перейти к j-й строке программы. ? j1; j2 — если в ячейке нет метки, то перейти к j1-й строке программы, иначе перейти к j2-й строке программы. ! — конец программы . |
Запись программы для машины | Записывается в таблице | Состоит из пронумерованных строк |
Машина Поста проще, чем машина Тьюринга, поэтому мы с Вами будем выполнять практические работы с помощью компьютерной модели машины Поста.
5. Практическая работа
Задача: Машина Поста состоит из ленты, разбитой на ячейки, и каретки, которая может считывать содержимое обозреваемой ячейки, стирать метки и ставить метки. Создайте компьютерную модель машины Поста, вычитающей два числа . Каретка вначале стоит на правой крайней позиции вычитаемого числа.
Указание:
Будем представлять натуральное число P набором из P+1 единиц и разделять числа нулем. Исходное положение каретки помечено символом «v»
V | |
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