Задачи обработки информации

Тема урока: Задачи обработки информации. Кодирование информации. Подсчет количества слов фиксированной длины в определенном алфавите.

Цель урока:

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

Планируемые образовательные результаты:

·        предметные: понимание сущности понятий «информационный процесс», «обработка информации», «кодирование», «префиксный код»; понимание сущности метода половинного деления; наличие представлений о задачах обработки информации, об общей схеме процесса обработки информации; умение строить неравномерные коды, допускающие однозначное декодирование сообщений, используя условие Фано; наличие знаний о постановках задач поиска и сортировки, их роли при решении задач анализа данных;

·        метапредметные: способность выходить за рамки учебного предмета и осуществлять целенаправленный поиск возможностей для широкого переноса средств и способов действия; искать и находить обобщённые способы решения задач, в том числе, осуществлять развёрнутый информационный поиск и ставить на его основе новые (учебные и познавательные) задачи;

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

Решаемые учебные задачи:

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

2) расширить и обобщить представления учащихся о задачах обработки информации;

3) расширить представление учащихся о кодировании как процессе обработки информации, о способах кодирования информации;

4) сформировать представления учащихся о префиксных кодах;

5) расширить представления учащихся о задачах поиска информации, о методе половинного деления.

Основные понятия: информационный процесс, обработка информации, кодирование, код, кодовая таблица, префиксный код, поиск информации, метод половинного деления.

Электронное приложение к учебнику:

·        презентация «Обработка информации»

Дополнительные интернет-ресурсы:

·        РЭШ(https://resh.edu.ru). Урок 4. Обработка информации. Передача и хранение информации.

Ход урока:

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

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

  Опрос учеников по вопросам No1–5, 7, 10, 11, 13, 14 к §3.

   Из курса информатики основной школы вам известно, что существует два различных типа обработки информации: 1) обработка, связанная с получением нового содержания, новой информации; 2) обработка, связанная с изменением формы представления информации, не изменяющая её содержания.

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

  При всем многообразии решаемых задач в процессе обработки информации всегда решается некоторая информационная задача.

Исполнитель – человек или компьютер, который осуществляет обработку информации.

Алгоритм – последовательность действий, которую нужно выполнить, чтобы достичь нужного результата.

Кодирование — обработка информации, заключающаяся в её преобразовании в некоторую форму, удобную для хранения, передачи, обработки информации в дальнейшем.

Код — система условных обозначений (кодовых слов), используемых для представления информации.

Кодовая таблица — совокупность используемых кодовых слов и их значений.

   Ранее мы рассмотрели примеры равномерных двоичных кодов. Назовите их (пятиразрядный код Бодо, восьмиразрядный код ASCII).

   Самый известный пример неравномерного кода – азбука Морзе (сообщение учащегося).

   При использовании неравномерных кодов важно понимать, сколько различных кодовых слов они позволяют построить (рассматриваются примеры 1-3 учебника).

   Главное условие неравномерных кодов – возможность однозначного декодирования сообщения. Именно поэтому в технических системах широкое распространение получили префиксные коды: они состоят из слов различной длины, записываемых без разделительного символа.

   Пре́фиксный код — код со словом переменной длины, обладающий тем свойством, что никакое его кодовое слово не может быть началом другого (более длинного) кодового слова.

   Для того чтобы сообщение, записанное с помощью неравномерного кода, однозначно декодировалось, достаточно, чтобы никакое кодовое слово не было началом другого (более длинного) кодового слова. Это условие еще называют условием Фано. Обратное условие Фано также является достаточным условием однозначного декодирования неравномерного кода. В нем требуется, чтобы никакой код не был окончанием другого.

   Другой  важнейшей  задачей  обработки  информации  является  поиск информации.

   Рассмотрим  два  основных  алгоритма поиска,  применяемых  в  зависимости  от  способа  организации  информации: метод последовательного перебора, метод половинного деления.

   Метод перебора иллюстрируется решением следующей проблемы: «Закрывая спортивный магазин, продавец обнаружил отдельно стоящую кроссовку. В магазине осталось только девять коробок с обувью той же модели и того же размера. Помогите продавцу найти пару для этой кроссовки».

   Метод половинного деления иллюстрируется решением следующей задачи:  «У плотника в Бобровой деревне 9 складов, пронумерованных от 1 до 9. Плотник не может вспомнить, сколько складов уже заполнил, но помнит, что заполнял их в порядке возрастания номеров. Помогите плотнику найти первый из незаполненных складов за меньшее число ходов».

IV. Закрепление изученного материала

   Выполнение задания №13 к §4.

   В ходе обсуждения вырабатывается общая стратегия решения, сводящаяся к применению метода половинного деления, знакомого учащимся ранее. Алгоритм оптимального поиска для набора данных, элементы которого упорядочены по неубыванию, т. е. каждый последующий элемент не меньше (больше или равен) предыдущего, —a1≤ a2≤ a3≤ ... ≤ aN:1) искомый элемент   сравнивается   с   центральным   элементом последовательности,   номер   которого   находится   как   [N/2]+1 (квадратные  скобки  здесь  обозначают,  что  от  результата  деления берётся только целая часть, а дробная часть отбрасывается); 2) если искомый элемент больше центрального, то поиск продолжается в правой части последовательности. Если он меньше центрального, то — в левой. Если значения искомого элемента и центрального совпадают, то поиск завершается.

   На  основе метода  половинного  деления обучающиеся  формулируют алгоритм поиска первого пустого склада.

1. Найдём  номер  центрального  склада  по  формуле  [N/2]+1  (от результата деления берётся только целая часть), где N–количество складов.

2. Если склад под этим номером занят, то поиск продолжается в правой части последовательности. Если пустой, то — в левой.

3. Поиск  завершается,  когда  найдена  граница  между  занятыми  и пустыми складами. Рассмотрим «крайние» случаи: 1) пустой склад первый; 2) пустой склад последний (под № 31).

Решение оформляется в виде таблицы.

Общий  случай  поиска  в  диапазоне  можно  представить следующим образом.

1. Определяем  два  элемента: левый  (L)–точно  заполненный  в  нашем случае L= 0, правый (R) –точно пустой –R= 32.

2. Номер центрального склада С= (L+ R) div 2.

3. Если склад C–пустой, то из рассмотрения следует убрать все номера больше C,  т.е.  смещается  правая  граница R= C.  Если  склад  полный,  то смещаем левую границу L= C.

4. Если  разница R–L>1  переходим  к  пункту  2.Если R–L= 1,  то последний заполненный склад —L, первый пустой —R.

V. Итоги урока

Наш урок подошел к концу. Что нового вы сегодня узнали на уроке и чему научились?

VI. Домашнее задание: §4, вопросы и задания № 1–4, 6–10, 12, 13 к параграфу. Дополнительное  задание  для  учеников,  планирующих  сдавать  ЕГЭ  по информатике: №5, 11 к параграфу.