Поиск данных (Умбетова К. Н.)

Текст урока

• Конспект

   Информатика и ИКТ 
  10 класс
  УМК: учебник для  10- 11 классов / И.Г. Семакин,  Е.К.Хеннер. 6-е изд.-М.:БИНОМ. Лаборатория знаний, 2010г Базовый уровень
  1ч на изучение темы
  Тема урока: «Поиск данных».)
  Цели урока:
  - образовательная: изучение понятий «набора данных», «ключа поиска», «структуры данных», изучение алгоритма последовательного поиска и поиска половинным делением, изучение блочного поиска, поиска в иерархической структуре данных.
  - развивающая: развитие познавательного интереса к изучаемому предмету, развитие памяти, внимания, логического мышления. 
  - воспитательная: воспитание информационной культуры, внимания, аккуратности, умения работать в коллективе.
  Тип урока: урок усвоения новых знаний.
  Планируемые результаты:
  учащиеся должны знать:
  что такое «набор данных», «ключ поиска» и «критерий поиска»;
  что такое «структура данных»; какие бывают структуры;
  алгоритм последовательного поиска;
  алгоритм поиска половинным делением;
  что такое блочный поиск;
  как осуществляется поиск в иерархической структуре данных.
  учащиеся должны уметь:
  осуществлять поиск данных в структурированных списках, словарях, справочниках, энциклопедиях;
  осуществлять поиск в иерархической файловой структуре компьютера. 
  Техническое обеспечение урока: компьютер, мультимедиа проектор, учебник по информатике и ИКТ, презентация.
  Учебно-методическое и программное обеспечение урока: 
  1. Семакин И.Г., Хеннер Е.К. Информатика и ИКТ. Базовый уровень. 10-11 класс. – М.: БИНОМ. Лаборатория  знаний, 2011.
  2. Семакин И.Г., Хеннер Е.К., Шеина Т.Ю. Практикум по информатике и ИКТ для 10-11 классов. Базовый уровень.   Информатика. 11 класс. – М.: БИНОМ. Лаборатория  знаний, 2011.
  План урока.
  1. Организационный момент. (2 мин)
  2. Проверка домашнего задания. (8 мин)
  3. Изучение нового материала. (20 мин)
  4. Первичное закрепление изученного материала (10 мин)
  5. Подведение итогов урока. (3 мин)
  6. Домашнее задание. (2мин) 
  Изучаемые вопросы:
  1. Постановка задачи поиска данных.
  2. Организация набора данных.
  3. Последовательный поиск.
  4. Поиск половинным делением.
  5. Блочный поиск.
  6. Поиск в иерархической структуре данных.
  
  Ход урока.
  1. Организационный момент.
  Приветствие учителем учащихся, проверка готовности кабинета и учащихся к уроку, проверка отсутствующих. 
  
  2. Проверка домашнего задания.
  Учитель. На прошлом уроке вы изучили тему: «Автоматическая обработка информации». Ответьте, пожалуйста, на следующие мои вопросы.
  Учитель. Что называется алгоритмом обработки?
  Ученик. Алгоритм обработки – формализованные правила, определяющие последовательность шагов обработки информации.
  Учитель. Назовите виды обра­ботки информации.
  Ученик. Виды обра­ботки информации: 
  1) получение новой информации, новых сведений;
  2) изменение формы представления информации;
  3) систематизация, структурирование данных;
  4) поиск информации.
  Учитель. Что называется систе­мой команд исполнителя алгоритмов?
  Ученик. Совокупность всех команд языка исполнителя называется систе­мой команд исполнителя алгоритмов – СКИ.
  Учитель. Что называется алгоритмической машиной?
  Ученик. Алгоритмическая машина – автоматический исполнитель обработки знаковых последовательностей.
  Учитель. Что представляет собой алгоритм управления работой алгоритмической машины?
  Ученик. Алгоритм управления работой алгоритмической машины представ­ляет собой конечную последовательность команд, посредством выпол­нения которой машина решает задачу обработки информации.
  Учитель. Какими свойствами должен обладать Алгоритм управления алгоритмической машиной?
  Учитель. Какие модели алгоритмических машин существуют в теории алгоритмов?
  Ученик. Машина Тьюринга и машина Поста.
  Ученик. Алгоритм управления такой машиной должен обладать следующими свойствами:
  •   дискретностью (каждый шаг алгоритма выполняется отдельно от других);
  •   понятностью (в алгоритме используются только команды из СКИ);
  • точностью (каждая команда определяет однозначное действие ис­полнителя);
  •  конечностью (за конечное число шагов алгоритма получается ис­комый результат).
  
  3. Изучение нового материала.
  Учитель. Сегодня на уроке  изучим понятия «набора данных», «ключа поиска», «структуры данных», изучим алгоритм последовательного поиска и поиска половинным делением, изучим блочный поиск, поиск в иерархической структуре данных.
  Тема урока «Поиск данных». 
  
  Запись на доске и в тетрадях:
  Число.
  «Поиск данных».
  
  Учитель. Вспомните, как часто приходится вам искать какие-нибудь данные. Та­ких примеров много и в бытовых ситуациях, и в учебном процессе. Напри­мер, в программе телепередач вы ищете время начала трансляции фут­больного матча; в расписании поездов – сведения о поезде, идущем до нужной вам станции. На уроке физики, решая задачу, ищете в таблице удельный вес меди. На уроке английского языка, читая иностранный текст, ищете в словаре перевод слова на русский язык. Работая за компью­тером, вам нередко приходится искать на его дисках файлы с нужными данными или программами.
  1. Постановка задачи поиска данных.
  Во всех компьютерных информационных системах поиск данных явля­ется основным видом обработки информации. При выполнении любого поиска данных имеются три составляющие, которые мы назовем атрибу­тами поиска:
  Первый атрибут: набор данных. Это вся совокупность данных, среди которых осуществляется поиск. Элементы набора данных будем называть записями. Запись может состоять из одного или нескольких полей. На­пример, запись в записной книжке состоит из долей: фамилия, адрес, те­лефон.
  Второй атрибут: ключ поиска. Это то поле записи, по значению которо­го происходит поиск. Например, поле ФАМИЛИЯ, если мы ищем номер телефона определенного человека.
  Третий атрибут: критерий поиска, или условие поиска. Это то условие, которому должно удовлетворять значение ключа поиска в искомой запи­си. Например, если вы ищете телефон Сидорова, то критерий поиска за­ключается в совпадении фамилии Сидоров с фамилией, указанной в оче­редной записи в книжке. 
  
  Запись на доске и в тетрадях:
  Поиск данных:
  1) набор данных: вся совокупность данных, среди которых осуществляется поиск;
  2) ключ поиска: поле записи, по значению которого происходит поиск;
  3) критерий поиска: условие, которому должно удовлетворять значение ключа поиска в искомой записи. 
  
  Учитель. Заметим, что ключей поиска может быть несколько, тогда и критерий поиска будет сложным, учитывающим значения сразу нескольких клю­чей. Например, если в справочнике имеется несколько записей с фамили­ей Сидоров, но у них разные имена, то составной критерий поиска будет включать два условия: ФАМИЛИЯ – Сидоров, ИМЯ – Владимир.
  Как при «ручном» поиске, так и при автоматизированном важнейшей задачей является сокращение времени поиска. Оно зависит от двух обстоятельств:
  1) как организован набор данных в информационном хранилище (в словаре, в справочнике, на дисках компьютера и пр.); 
  2) каким алгоритмом поиска пользуется человек или компьютер.
  2. Организация набора данных. 
  Относительно первого пункта могут быть две ситуации: либо данные никак не организованы (такую  ситуацию   иногда   называют   «кучей»), либо данные структурированы. Под словами «данные структурированы» понимается    наличие   какой-то   упорядоченности данных в их хранилище: в словаре, в расписании, в компьютерной базе данных. 
  Говоря о системах в § 5, мы выделяли важнейшее свойство всякой систе­мы – наличие структуры. Это свойство присуще как материальным систе­мам, так и информационным системам. Названные выше примеры хранилищ информации, а также архивы, библиотеки, каталоги, журналы успеваемости учащихся и многие другие являются системами данных с определенной структурой.
  Структурированные системы данных, хранящиеся на каких-либо носителях, будем называть структурами данных. 
  
  Запись на доске и в тетрадях:
  Структуры данных – структурированные системы данных, хранящиеся на каких-либо носителях. 
  Учитель. Однако бывает и так, что хранимая информация не систематизирована. Представьте себе, что вы записывали адреса и телефоны своих знакомых в записную книжку без алфавитного индекса («лесенки» из букв по краям листов). Записи вели в порядке поступления, а не в алфавитном порядке. А теперь вам нужно найти телефон определенного человека. Что остается делать? Просматривать всю книжку подряд, пока не попадется нужная запись! Хорошо, если повезет и запись окажется в начале книжки. А если в конце? И тут вы поймете, что книжка с алфавитом гораздо удобнее.
  3. Последовательный поиск.
  Ситуацию, описанную выше, назовем поиском в неструктурированном наборе. Разумный алгоритм для такого поиска остается один: последова­тельный перебор всех элементов множества до нахождения нужного. Ко­нечно, можно просматривать множество в случайном порядке (методом случайного перебора), но это может оказаться еще хуже, поскольку неиз­бежны повторные просмотры одних и тех же элементов, что только увели­чит время поиска.
  Опишем алгоритм поиска методом последовательного перебора. Для описания алгоритма воспользуемся известным вам способом блок-схем. В алгоритме учтем два возможных варианта результата: 1) искомые данные найдены; и 2) искомые данные не найдены. Результаты поиска нередко оказываются отрицательными, если в наборе нет искомых данных.
  
  Запись на доске и в тетрадях: 
  
                       Алгоритм поиска последовательным перебором.
  Учитель. Символика блок-схем должна быть вам понятна. Из схемы видно, что если искомый элемент найден, то поиск может закончиться до окончания просмотра всего набора данных. Если же элемент не обнаружен, то поиск закончится только после просмотра всего набора данных.
  Зададимся вопросом: какое среднее число просмотров приходится вы­полнять при использовании метода последовательного перебора? Есть два крайних частных случая:
  •   Искомый элемент оказался первым среди просматриваемых. Тогда просмотр всего один.
  •   Искомый элемент оказался последним в порядке перебора. Тогда число просмотров равно N, где N – размер набора данных. То же будет, если элемент вообще не найден.
  Всякие средние величины принято определять по большому числу про­веденных опытов. На этом принципе основана целая наука под названием математическая статистика. Нетрудно понять, что если число опытов (поисков) будет очень большим, то среднее число просмотров во всех этих опытах окажется приблизительно равным N/2. Эта величина определяет длительность поиска – главную характеристику процесса поиска.
  4. Поиск половинным делением.
  Возьмем для примера игру в угадывание целого числа в определенном диапазоне. Например, от 1 до 128. Один играющий загадывает число, второй пытается его угадать, задавая вопросы, на которые ответом может «да» или «нет». Ключом поиска в этом случае является число, а критерием поиска –  совпадение числа, задуманного первым игроком, с числом, называемым вторым игроком. Если вопросы задавать такие: «Число равно единице?». Ответ: «Нет», вопрос: «Число равно двум?» и т. д., то это будет последовательный перебор. Среднее число вопросов при многократном повторении игры с загадыванием разных чисел из данного диапазона будет равно 128/2 = 64. Однако поиск можно осуществить гораздо быстрее, если учесть упорядоченность натурального ряда чисел, благодаря чему между числами действуют отношения больше/меньше. С подобной ситуацией мы с вами уже встречались в § 4, говоря об измерении информации. Там обсуждался способ угадывания одного значения из четырех (пример с оценками за экзамен) и одного из восьми (пример с книжными полками). Применявшийся метод поиска называется методом половинного деления. Согласно этому методу, вопросы надо задавать так, чтобы каждый ответ уменьшал число неизвестных в два раза. Так же надо искать и одно число из 128. Первый вопрос: «Число меньше 65?» – «Да» – «Число больше 32?» – «Нет» и т. д. Любое число уга­дывается максимум за 7 вопросов. Это связано с тем, что 128 = 27. Снова работает главная формула информатики.
  Метод половинного деления для упорядоченного набора данных работает гораздо быстрее (в среднем), чем метод последовательного перебора.
  Обратите внимание на следующий рисунок, здесь наглядно показан процесс поиска (угадывания) числа «3» из диапазона целых чисел от 1 до 8.
  
  Если максимальное число диапазона N не равно целой степени двойки, то оптимальное количество вопросов не будет постоянной величиной, а будет равно одному из двух значений: X или Х+1, где
  2х <N< 2X+l. Например, если число ищется в диапазоне от 1 до 7, то его можно угадать за 2 или 3 вопроса, поскольку 22 < 7 < 23.
  Число из диапазона от 1 до 200 можно угадать за 7 или 8 вопросов, по­скольку
  27 < 200 < 28.
  Проверьте эти утверждения экспериментально.
  Половинным делением можно искать, например, нужную страницу в толстой книге: открыть книгу посередине, понять, в какой из половин на­ходится искомая страница. Затем открыть середину этой половины и т. д.
  Набор данных может быть упорядочен не только по числовому ключу. Другой вариант упорядочения – по алфавиту. Половинным делением можно осуществлять поиск в орфографическом словаре или в словаре пе­реводов слов с иностранного языка.
  5. Блочный поиск
  Снова вспомним пример с записной книж­кой. Пусть в вашей записной книжке имеется алфавитный индекс в виде вырезанной «лесен­ки» или в виде букв вверху страницы. Несколь­ко страниц, помеченных одной буквой, назовем блоком. Имеется блок «А», блок «Б» и т. д. до блока «Я».
  Индекс — это часть ключа поиска (например, первая буква).
  Записи телефонов и адресов расставлялись в записной книжке по бло­кам в соответствии с первой буквой. Однако внутри блока записи не упо­рядочены в алфавитном порядке следующих букв, как это делается в сло­варях и энциклопедиях. Записи в книжке мы ведем в порядке поступле­ния. При такой организации данных поиск нужного телефона будет происходить блочно-последовательным методом:
  1) с помощью алфавитного индекса выбирается блок с нужной буквой;
  2) внутри блока поиск производится путем последовательного перебора. Большинство книг в начале или в конце текста содержат оглавления: список названий разделов с указанием страниц, с которых они начинают­ся. Разделы – это те же блоки. Поиск нужной информации в книге начи­нается с просмотра оглавления, с дальнейшим переходом к нужному раз­делу, который затем просматривается последовательно. Очевидно, это тот же блочно-последовательный метод поиска.
  Списки с указанием на блоки данных называются списками указателей.
  Разбиение данных на блоки может быть многоуровневым. В толстых словарях блок на букву «А» разбивается, например, на блоки по второй букве: блок от «АБ» до «АЖ», следующий от «АЗ» до «АН» и т. д. Такой порядок называется лексикографическим.
  В поисковом множестве с многоуровневой блочной структурой проис­ходит поиск методом спуска: сначала отыскивается нужный блок первого уровня, затем второго и т. д. Внутри блока последнего уровня может про­исходить либо последовательный поиск (если данных в нем относительно немного), либо оптимизированный поиск типа половинного деления. По­иску методом спуска часто помогают многоуровневые списки указателей.
  6. Поиск в иерархической структуре данных.
  Многоуровневые блочные структуры хранения дан­ных называются иерархическими структурами. По та­кому принципу организовано хранение файлов в фай­ловой системе компьютера. То, что мы называли выше блоками, в файловой системе называется каталогами пли папками, а графическое изображение структуры блоков-папок называется деревом каталогов. Пример отображения на экране компьютера дерева каталогов показан на следующем рисунке. Чтобы найти файл, нужно знать путь к файлу по дереву каталогов. Операционная система поможет найти напрашиваемый вами файл по команде Поиск. Резуль­тат поиска представляется в виде пути к файлу, начи­ная от корневого каталога последовательно по уровням дерева до каталога (папки), непосредственно содержа­вшего ваш файл. Например, при поиске файла с именем kе.ехе будет выдан следующий ответ: E:\GAME\GAMES\ARCON\ke.exe
  Здесь указан полный путь к файлу на логическом диске Е: от корневого каталога до самого файла. Имея такую подсказку, вы легко отыщете нуж­ный файл на диске методом спуска по дереву каталогов. Каталог иерархи­ческой структуры файловой системы компьютера является многоуровне­вым списком указателей. 
  
  4. Первичное закрепление изученного материала. 
  Учитель. Давайте закрепим изученный материал. Ответьте, пожалуйста, на мои вопросы:
  Учитель. Что относится к атрибутам поиска?
  Ученик. К атрибутам поиска относятся: набор данных, ключ поиска, критерий поиска. 
  Учитель. Дайте определение следующим понятиям: набор данных, ключ поиска, критерий поиска. 
  Ученик. Набор данных – это вся совокупность данных, среди которых осуществляется поиск;
  Ключ поиска – это поле записи, по значению которого происходит поиск;
  Критерий поиска – это условие, которому должно удовлетворять значение ключа поиска в искомой записи.
  Набор данных может организоваться как неструктурированный набор или как структура данных.
  Структура данных может быть представлена как линейная упорядоченность по ключу, как блочная одноуровневая структура, как блочная многоуровневая (иерархическая структура).
  Учитель. Какие алгоритмы поиска существуют?
  Ученик. Случайный перебор. Последовательный перебор. Поиск половинным делением. Блочно-последовательный поиск. Использование индексов и списков указателей. Поиск методом спуска по дереву. Использование многоуровневых списков указателей.
  
  5. Подведение итогов урока.
  Учитель. Сегодня на уроке  мы изучили понятия «набора данных», «ключа поиска», «структуры данных», изучим алгоритм последовательного поиска и поиска половинным делением, изучим блочный поиск, поиск в иерархической структуре данных. Есть ли у вас какие-то вопросы ко мне? 
  
  6. Домашнее задание. §11 учебника, устно ответить на вопросы в конце параграфа (1-7).
   

   Read more ...

  Автор(ы): Умбетова К. Н.

  Скачать: Информатика 10кл - Конспект.doc