Что такое структурирование кодирование отбор информации
Процесс кодирования информации
Что такое кодирование информации
Кодирование – это процесс преобразования данных из исходной формы представления в коды.
Код – это набор условных символов для представления информации.
К целям использования кодирования относятся:
Осторожно! Если преподаватель обнаружит плагиат в работе, не избежать крупных проблем (вплоть до отчисления). Если нет возможности написать самому, закажите тут.
Виды кодирования информации, какие бывают способы изменения вида
Перевести в систему кодов можно текст, цвета, графическое изображение, числа, звук, видео и т.д.
Кодирование текстовой информации
Выделяют 3 основных вида кодирования текста:
Поскольку вся информация представлена в памяти компьютера в двоичной системе, для работы с текстом в ЭВМ используют числовой способ кодирования.
Изначально кодирование символов осуществлялось по 7-битному стандарту. В этой системе вычислительная машина записывала в свою память 128 разных состояний. Каждому из них соответствовала определенная буква, знак или символ.
7-битной системы было недостаточно для записи всех мировых языков. По этой причине создатели программ перешли на 8-битный стандарт, который позволил преобразовать 256 разных знаков.
Двоичное кодирование предполагает, что каждый знак соответствует уникальному двоичному коду. В стандартном коде информационного обмена ASCII регламентируется присвоение символу такой последовательности. Первые 33 кода – это операции, такие как пробел, ввод и т.п. Коды 33 – 127 соответствуют буквам латинского алфавита, цифрам, арифметическим символам и знакам препинания. Коды 128 – 255 – это буквы национального алфавита.
Впервые русские буквы были закодированы в стандарте КОИ-8 на вычислительных машинах с операционной системой UNIX. На сегодняшний день более широко используется стандартная кодировка Microsoft Windows с обозначением «Кириллица». Русские буквы для операционной системы MS-DOS преобразуются в стандарте СР866. В устройствах серии Macintosh компании Apple – это кодировка Мас. Еще один стандарт для представления русского алфавита – ISO 8859-5.
Неудобство существования разных кодовых языков состоит в том, что они не адаптированы. Следовательно, текст, созданный в одном стандарте, не будет отображаться в другой кодовой системе. Разработчики нашли решение этой проблемы и предусмотрели автоматическую перекодировку текстовой информации при работе с разными кодовыми стандартами.
Для работы в интернете применяют международную кодировку Unicode. В отличие от 8-битного стандарта, для преобразования символов использует 2 байта, а не 1. Это позволяет закодировать 65536 различных символов.
Кодирование цвета
Для управления яркостью вводят еще один бит, и получается модель IRGB (от английского Intensity – интенсивность). При этом образуются 8 дополнительных кодов, соответственно, цветовая гамма расширяется до 16 оттенков. Добавляются серый, ярко-синий, ярко-зеленый, ярко-голубой, ярко-красный, ярко-лиловый, ярко-желтый, ярко-белый.
Создание более богатой палитры осуществляется в 6-битной системе, называемой RrGgBb. Код 00 означает, что цвет выключен, 01 – это слабый цвет, 10 – обычный оттенок и 11 – интенсивный. В этом случае можно закодировать 64 цвета. Несмотря на это, на экране параллельно могут отражаться до 16 оттенков, поскольку кодирование в кадровом буфере происходит в 4-битной системе. Представление цвета в RrGgBb применяется на видеоадаптерах EGA.
Еще более широкая гамма доступна в видеоинтерфейсе VGA. Благодаря отведению 6 байт на шифровку каждого основного цвета, количество тонов увеличилось до 256 тыс. Из них на экране одновременно отражается максимум 256 оттенков, так как видеобуфер использует 8-битное преображение информации.
В принтерах используется иная цветовая модель – CMYK. Она базируется на голубом, фиолетовом, желтом и черном цветах (Cyan, Magenta, Yellow, Key color – обозначение черного цвета). Так как эти тона получены при вычитании из белого основных цветов, модель называется субстрактивной.
Выбор такой цветовой модели для полиграфии объясняется техническим удобством. Так как печать производится на бумаге, нужно учитывать свойство поверхности отражать. В этом случае проще считать, сколько света отразилось, чем поглотилось.
Кодирование графической информации
Представление графической информации в компьютерах подразделяется на два формата:
Растровый формат можно назвать точечным. Расположенные строго по строкам и столбцам точки имеют отдельные координаты нахождения на дисплее, цвет и уровень интенсивности. Качество изображения напрямую зависит от количества точек – чем их больше, тем картинка качественнее. Растровый способ кодирования подходит для фотографий.
Векторная графика опирается на закодированные геометрические фигуры. В числовой формат приведены размеры объектов, координаты вершин, толщина контуров цвет заливки. Векторное кодирование удобно применять при создании рекламной продукции.
Кодирование числовой информации
Числа в памяти вычислительных машин хранятся в двоичной системе счисления. Выделяют два способа представления чисел:
Целочисленные значения в компьютере представлены с фиксированной запятой.
Целое положительное число переводят в двоичную систему счисления. К полученному коду приписывают 2 нуля слева. Крайний разряд слева в положительном числе равен 0.
Целое отрицательное число преобразуется следующим образом. Число без минуса переводят в двоичную систему, дополняют его нулями слева. Образовавшийся код переводят в обратный, заменяя нули единицами, а единицы – нулями. К полученной комбинации чисел прибавляют 1.
Порядок кодирования действительного или вещественного числа выглядит следующим образом. Число десятичной системы счисления переводят в двоичную. Определяют так называемую мантиссу числа: перемещают запятую в нужную сторону, чтобы слева не было ни одной единицы. Далее определяют значение порядка – количество знаков, на которое перемещена запятая для определения мантиссы.
Кодирование звуковой информации
Звук – это волны с постоянно меняющейся частотой и интенсивностью, вызванные колебанием частиц. Человек распознает звук благодаря меняющемуся давлению акустической волны на препятствия. Громкость звука зависит от акустики звуковой волны, а тон – от частоты.
При оцифровке непрерывная акустическая волна временно превращается в прерывистую. Дискретная форма представляет собой короткие отрезки с неизменным сигналом.
Частота дискретизации – количество измерений громкости в секунду.
Глубина кодирования звука – количество данных, необходимое для преобразования прерывистых уровней громкости звукового сигнала.
От частоты дискретизации глубины кодирования звука зависит точность воспроизведения оригинального звука. Чем выше эти показатели, тем корректнее представление звуковой информации.
Кодирование видеозаписи
Видеофайл состоит из звукового элемента и графического изображения, поэтому эти составляющие подвергаются раздельной кодировке.
Принципы преобразования звука видеозаписи в двоичную систему аналогичны с кодированием обычной звуковой информации.
Последовательность кодирования графики также схожа с переводом обычного изображения в двоичный код. В случае с видео шифруется лишь первый кадр. Последующие изображения преобразуются относительно предыдущей картинки посредством записи изменений.
По завершении процесса кодирования звуковой дорожки и графики получается двоичный код для хранения в памяти ПК и других электронных носителях. Синхронность воспроизведения видеозаписи осуществляется путем разделения этих операций.
Понятие информационного процесса. Сбор и обработка информации.
Урок 2. Информатика 7 класс (ФГОС)
В данный момент вы не можете посмотреть или раздать видеоурок ученикам
Чтобы получить доступ к этому и другим видеоурокам комплекта, вам нужно добавить его в личный кабинет, приобрев в каталоге.
Получите невероятные возможности
Конспект урока «Понятие информационного процесса. Сбор и обработка информации.»
· Определение информационных процессов.
· Виды информационных процессов.
Что же вообще означает слово процесс? Процесс – это последовательность изменений в чём-либо. Например возьмём процесс создания табуретки на уроках технологии. В начале у нас имеется древесина, которая обрабатывается определённым образом. Из неё получаются части табуретки, эти части соединяются воедино. В ходе этого процесса изменяется состояние древесины, а на выходе мы получаем табуретку.
Информационные процессы – это процессы, в ходе которых меняется информация и её состояние. У некоторых из вас мог возникнуть вопрос: «А что вообще может происходить с информацией? Что с ней можно делать?». Давайте посмотрим.
Читая книгу или слушая учителя на уроке – мы воспринимаем информацию и собираем её.
Решая какую-нибудь задачу по математике, мы изменяем информацию, мы рассчитываем какие-то значения по формулам. Мы получаем новую информацию из старой. Обрабатываем её.
Так мы можем выделить четыре основных информационных процесса:
Действия людей над информацией, связанные с её сбором, обработкой, хранением и передачей называются информационной деятельностью.
Сегодня мы подробнее узнаем о сборе информации и её обработке. Начнём со сбора информации. Прежде чем, обработать информацию, сохранить её или передать, нужно сначала её получить. Именно со сбора информации начинается процесс решения любой задачи.
Например, вы хотите подобрать подарок на день рождения другу. Но на основе чего делать выбор? Для того, чтобы выбрать хороший подарок нужно знать, чем увлекается друг и что ему нравится. Даже прежде, чем переходить дорогу на пешеходном переходе необходимо воспринять некоторую информацию. Нам нужно посмотреть на светофор чтобы узнать, какой из сигналов горит, красный или зелёный.
Информация, которую мы собрали может становиться источником других, новых знаний об окружающем нас мире. Так, результаты работы измерительных приборов в физических опытах стали источником знаний о том, что существует электрический ток. И любые прогнозы, будь то прогноз погоды, экономический или спортивный прогнозы так же делаются на основе собранных данных.
Иногда сбор информации может быть связан с некоторыми трудностями. Так, процесс о котором нужно собрать информацию может происходить очень быстро. Тогда со сбором информации помогают специальные автоматизированные измерительные системы. Они позволяют собирать данные очень быстро и с большой точностью. Автоматические измерительные системы часто применяются, когда проведение замеров может быть опасно для жизни. Например, когда нужно узнать какие повреждения получит автомобиль в результате аварии.
Любую получаемую информацию, мы каким-то образом осмысляем и обрабатываем. Важно делать это своевременно. Например из сигналов светофора, и движения автомобилей мы можем сделать вывод, можно или нельзя переходить дорогу. Намного больше информации должны быстро обрабатывать специалисты, которые обслуживают информационные и другие технические системы, нуждающиеся в контроле.
Когда мы принимаем решение о переходе улицы или решаем математическую задачу, когда музыкант играет музыку по нотам, которые находятся перед ним. Во время каждого из этих действий происходит обработка информации. Мы обрабатываем входную информацию: сигналы светофора, условие задачи или ноты и возвращаем результат, который называется выходной информацией. То, есть решение о переходе улицы, решение задачи или музыку.
Обработкой называется целенаправленный процесс изменения содержания или формы представления информации.
Из определения обработки информации понятно, что можно выделить два её типа. Первый тип направлен на изменение содержания и получение новой информации. Второй тип направлен на изменение формы представления информации. Рассмотрим каждый тип обработки подробнее.
Приведём несколько примеров обработки информации, которая связана с изменением её содержания. Это может быть преобразование информации по некоторым правилам, например вычисление по формулам. Исследование некоторых объектов по их моделям. Так мы можем сделать выводы о строении здания, посмотрев на его фотографию. Разные логические рассуждения. Мы можем сделать вывод: если ходить по лужам – можно замочить ноги. Можно привести так же много других примеров.
Пятеро друзей Петя, Вася, Саша, Света и Оля после школы занимаются в разных кружках по интересам: в шахматном клубе, футбольной секции, секции по плаванию, кружке по вязанию, и секции по велоспорту. В каждом кружке занимается кто-то один из ребят, определить, кто из друзей чем увлекается, если:
· Вася и Саша подарили на день рождения футбольный мяч тому, кто занимается в футбольной секции.
· Саша, Света и Петя недавно смотрели шахматную партию с участием того, кто этим увлекается.
· Оле не интересны шахматы.
· Света помогает учиться плавать тому, кто занимается вязанием.
Такую задачу можно решить, рассматривая каждое из условий с помощью таблицы. Назовём её строки, по названиям увлечений ребят. А столбцы обозначим именами ребят. В клетках таблицы будем ставить знак плюс, если человек, именем которого назван столбец увлекается тем, что указано в заголовке строки. А если не увлекается – будем ставить знак минус. Будем рассматривать условия по очерёдности.
4.Обработка информации
Информационный процесс — совокупность последовательных действий (операций), производимых над информацией (в виде данных, фактов, идей, гипотез, теорий и пр.) для получения какого-либо результата (достижения цели).
Можно выделить три основных типа информационных процессов: обработка, хранение и передача информации. Рассмотрим их подробнее.
Обработка информации — это целенаправленный процесс изменения содержания или формы представления информации.
Из курса информатики основной школы вам известно, что существует два различных типа обработки информации:
1) обработка, связанная с получением нового содержания, новой информации;
2) обработка, связанная с изменением формы представления информации, не изменяющая её содержания.
К первому типу обработки информации относятся: преобразование по правилам (в том числе вычисления по формулам), исследование объектов познания по их моделям, логические рассуждения, обобщение и др.
Ко второму типу обработки информации можно отнести:
• кодирование — переход от одной формы представления информации к другой, более удобной для восприятия, хранения, передачи или последующей обработки;
• структурирование — организацию информации по некоторому правилу, связывающему её в единое целое;
• поиск и отбор информации, требуемой для решения некоторой задачи, из информационного массива и др.
При всём многообразии решаемых задач в процессе обработки информации всегда решается некоторая информационная задача, а именно: дан некоторый набор исходных данных — исходной информации, требуется получить некоторые результаты — итоговую информацию. Сам процесс перехода от исходных данных к результату и есть процесс обработки. Тот объект, который осуществляет обработку, может быть назван исполнителем обработки. Для успешного выполнения обработки информации исполнителю должен быть известен способ обработки, т. е. последовательность действий, которую нужно выполнить, чтобы достичь нужного результата. Описание такой последовательности принято называть алгоритмом обработки.
Общая схема процесса обработки информации представлена на рисунке 1.11.
Исполнителем обработки информации может быть человек или компьютер. При этом человек, как правило, является неформальным, творчески действующим исполнителем. Даже для решения самой простой математической задачи разные люди могут использовать разные способы!
Что касается компьютера, то он является формальным исполнителем, действия которого осуществляются автоматически, строго в соответствии с имеющимся алгоритмом обработки информации.
Рассмотрим отдельные процессы обработки информации более подробно.
Кодирование информации
Кодирование информации широко используется в технических средствах работы с информацией (телеграф, радио, компьютеры).
Кодирование — это обработка информации, заключающаяся в её преобразовании в некоторую форму, удобную для хранения, передачи, обработки информации в дальнейшем.
Кодовая таблица — это совокупность используемых кодовых слов и их значений.
1 Также кодом зачастую называют результат кодирования информации.
Ранее мы уже рассмотрели примеры равномерных двоичных кодов — пятиразрядный код Бодо и восьмиразрядный код ASCII.
Самый известный пример неравномерного кода — код (азбука) Морзе, в которой цифры и буквы алфавита представляются последовательностями длинных («тире») и коротких («точек») сигналов, названный в честь американского изобретателя и художника Сэмюэля Морзе (1791-1872). Буквы, встречающиеся в сообщениях чаще, имеют в этом коде более короткий код, чем «редкие» буквы (рис. 1.12).
В азбуке Морзе сигналы отделяются друг от друга паузами — отсутствием сигналов. За единицу «измерения» длительности сигналов принимается длительность сигнала «точка». Длительность тире (длинного сигнала) равна длительности трёх точек (коротких сигналов). Пауза между сигналами одного знака равна одной точке; пауза между знаками в слове — трём точкам; пауза между словами — семи точкам. Фактически пауза является третьим знаком в азбуке Морзе, а сам код — троичным.
Слово WORD, закодированное с помощью азбуки Морзе, на «временной» шкале можно представить так:
Самым знаменитым сообщением, закодированным азбукой Морзе, является сигнал бедствия «SOS». Его запрещено использовать без острой на то необходимости. Передаётся сигнал без межбуквенных пауз:
При использовании неравномерных кодов важно понимать, сколько различных кодовых слов они позволяют построить.
Пример 1. Светодиодная панель содержит восемь излучающих элементов, каждый из которых может светиться или красным, или жёлтым, или синим, или зелёным цветом. Сколько различных сигналов можно передать с помощью панели (все излучающие элементы должны гореть, порядок цветов имеет значение)?
На уроках математики и информатики в основной школе вы изучали элементы комбинаторики, в том числе правило умножения. Согласно ему, если элемент А можно выбрать n способами и при любом выборе А элемент В можно выбрать m способами, то пару (А, В) можно выбрать n • m способами. Это правило справедливо и для произвольного количества независимо выбираемых элементов.
Применим его к решению нашей задачи.
Существует 4 варианта выбора цвета первого элемента, 4 варианта выбора цвета второго элемента; цвета для пары элементов (1, 2) можно выбрать 4 • 4 = 4 2 = 16 способами; цвета для тройки элементов (1, 2, 3) можно выбрать 16 • 4 = 4 3 = 64 способами и т. д. Цвета для восьми элементов (1, 2, 3, 4, 5, 6, 7, 8) можно выбрать 4 8 = 65 536 способами.
Можно ли отнести эту задачу к классу задач на определение максимально возможного количества комбинаций (слов) фиксированной длины определённого алфавита? Обоснуйте свой ответ.
Пример 2.
Выясним, сколько всего различных символов можно закодировать, используя последовательности точек и тире, содержащие не более шести знаков.
Для кодирования различных символов можно использовать последовательности точек и тире, содержащие не более шести знаков, т. е. 1, 2, 3, 4, 5 или 6 знаков.
Последовательностями, содержащими один из двух возможных знаков, можно закодировать два символа: один будет закодирован точкой, второй — тире.
Рассмотрим последовательности, содержащие два знака из двухсимвольного алфавита. Их может быть 2 • 2 = 2 2 = 4.
Последовательностей из трёх знаков, принадлежащих двухсимвольному алфавиту, может быть 4 • 2 = 2 3 = 8.
Рассуждая аналогичным образом, подсчитаем число последовательностей, содержащих 4, 5 и 6 знаков — 16, 32 и 64 соответственно.
Число различных последовательностей, содержащих не более шести знаков двухсимвольного алфавита, будет равно 126 = 2 + 4 + 8 + 16 + 32 + 64.
Пример 3.
Имеющаяся информация должна быть закодирована в четырёхбуквенном алфавите <А, В, С, D>. Выясним, сколько существует различных последовательностей из 7 символов четырёхбуквенного алфавита <А, В, С, D>, которые содержат ровно пять букв А.
Нас интересуют семисимвольные последовательности, любые пять мест в которых будут заняты буквой А, а на двух оставшихся местах могут находиться любые из букв В, С, D.
Так как на 6-м и 7-м местах могут стоять любые из трёх оставшихся букв В, С, D, то всего существует 9 (3 • 3 = 9) разных семибуквенных последовательностей, в которых первые пять позиций заняты буквой А.
Но ведь буквы А могут находиться на любых пяти из имеющихся семи позиций. Например:
А сколько таких вариантов всего? Сколько всего существует способов, которыми мы можем выбрать пять мест из семи для размещения там буквы А?
Для ответа на этот вопрос нужно вспомнить некоторые сведения из изученного в основной школе раздела математики, называемого комбинаторикой.
В комбинаторике набор k элементов, выбранных из данного множества, содержащего n различных элементов, называется сочетанием из n по k.
Для вычисления значения этой величины применяется формула:
4.2. Кодирование информации
Действительно, множество, с которым мы имеем дело, состоит из мест для записи символов в последовательности. Его элементы можно обозначить 1, 2, 3, 4, 5, 6 и 7. Требуется выбрать из этого множества пять мест для размещения буквы А. Число возможных вариантов можно вычислить как число сочетаний из 7 по 5:
Итак, существует 21 вариант выбора в семибуквенной последовательности ровно пяти мест для размещения там буквы А. Для каждого из этих 21 вариантов имеется 9 разных вариантов заполнения двух оставшихся мест.
Всего существует 189 (21 • 9 = 189) различных последовательностей из 7 символов четырёхбуквенного алфавита <А, В, С, D>, которые содержат ровно пять букв А.
Главное условие использования неравномерных кодов — возможность однозначного декодирования записанного с их помощью сообщения. Именно поэтому в технических системах широкое распространение получили префиксные коды: они состоят из слов разной длины, записываемых без разделительного символа. При этом сообщение, закодированное с их помощью, может быть однозначно декодировано.
Префиксный код — код со словом переменной длины, обладающий тем свойством, что никакое его кодовое слово не может быть началом другого (более длинного) кодового слова.
1) код, состоящий из слов 0, 10 и 11, является префиксным;
2) код, состоящий из слов 0, 10, 11 и 100, не является префиксным.
Для того чтобы сообщение, записанное с помощью неравномерного кода, однозначно декодировалось, достаточно, чтобы никакое кодовое слово не было началом другого (более длинного) кодового слова. Это условие ещё называют условием Фано (в честь Роберта Марио Фано, американского учёного, известного по работам в области теории информации).
Обратное условие Фано также является достаточным условием однозначного декодирования неравномерного кода. В нём требуется, чтобы никакой код не был окончанием другого (более длинного) кода.
Для возможности однозначного декодирования достаточно выполнения одного из условий Фано — или прямого, или обратного.
Как вы понимаете смысл этого утверждения? Можно ли на его основе заявлять, что если для некоторого кода условие Фано не выполняется, то однозначное декодирование записанного с его помощью сообщения невозможно?
Пример 4. Двоичные коды для 5 букв латинского алфавита представлены в таблице:
Выясним, какое сообщение (какой набор букв) закодировано с помощью этих кодов двоичной строкой: 0110100011000.
Проанализируем имеющиеся коды: код буквы В (01) является началом кода буквы Е (011); код буквы D (10) является началом кода буквы С (100).
Таким образом, прямое условие Фано для заданных кодов не выполняется. Следовательно, имеющуюся двоичную строку нельзя декодировать однозначно, если начать её декодирование с начала (слева направо).
Начните проводить декодирование двоичной строки 0110100011000 слева направо и убедитесь в справедливости условия Фано.
Для имеющихся кодов выполняется обратное условие Фано: никакой код не является окончанием другого кода. Следовательно, имеющуюся двоичную строку можно декодировать однозначно, если начать её декодирование с конца (справа налево).
Итак, направление однозначного декодирования установлено. Процесс декодирования может быть представлен так:
Если для некоторой последовательности кодов выполняется прямое условие Фано, то её декодирование следует вести слева направо. Если для некоторой последовательности кодов выполняется обратное условие Фано, то её декодирование следует вести справа налево.
Из курса информатики основной школы вам знакомо понятие дерева — иерархической структуры, состоящей из набора вершин и рёбер. Вершина, в которую не входит ни одного ребра, называется корнем; вершины, из которых не выходит ни одного ребра, называются листьями. Дерево, из вершин которого выходит только два ребра, называется двоичным (бинарным) деревом.
Комбинации, соответствующие листьям бинарного дерева, являются кодовыми комбинациями префиксного кода.
Префиксные коды можно наглядно представить с помощью кодовых деревьев.
Пример 5.
Каким кодовым словом может быть закодирована буква Г? Код должен удовлетворять свойству однозначного декодирования. Если можно использовать более одного кодового слова, укажите кратчайшее из них.
Для решения задачи воспользуемся бинарным деревом.
Так как комбинациям префиксного кода должны соответствовать листья бинарного дерева, наше кодовое дерево должно выглядеть так:
Итак, для кодирования буквы Г можно использовать код 111.
Какими кодовыми словами могут быть закодированы буквы Г и Д? Код должен удовлетворять свойству однозначного декодирования. Общая длина кодовых слов для всех пяти букв должна быть минимальной.
Поиск информации
Неоценима роль компьютера в организации важнейшей задачи обработки информации — поиска информации, необходимой человеку для решения стоящей перед ним задачи.
Вспомните, как часто и какую информацию приходится искать вам, членам вашей семьи, вашим друзьям и знакомым. Приведите примеры.
Задача поиска обычно формулируется следующим образом. Имеется некоторое хранилище информации — информационный массив (телефонный справочник, словарь, расписание поездов, диск с файлами и др.). Требуется найти в нём нужную информацию, удовлетворяющую определённым условиям поиска (телефон данной организации, перевод данного слова на английский язык, время отправления данного поезда, файл с рефератом). При этом, как правило, необходимо сократить время поиска, которое зависит от способа организации набора данных и используемого алгоритма поиска.
Алгоритм поиска, в свою очередь, зависит от способа организации информации.
Если данные никак не организованы, то мы имеем дело с неструктурированным набором данных. Для осуществления поиска в таком наборе данных применяется метод последовательного перебора: все элементы, начиная с первого, просматриваются подряд. Поиск завершается в двух случаях:
1) искомый элемент найден, при этом может быть просмотрена как часть имеющегося набора данных, так и весь набор, если искомый элемент оказался последним в наборе;
2) просмотрены все элементы имеющегося набора данных, но искомого элемента среди них не оказалось.
Длительность поиска методом последовательного перебора определяется как N/2, где N — размер набора данных. Действительно, искомый элемент может оказаться первым среди просматриваемых, и в этом случае длительность поиска равна 1. Если искомый элемент окажется последним или его не окажется вообще, то длительность поиска будет равна N. Если провести поиск последовательным перебором достаточно много раз, то окажется, что в среднем на поиск требуемого элемента уходит N/2 просмотров.
Гораздо проще осуществлять поиск в структурированном наборе данных. Структурирование связано с внесением определённого порядка, определённой организации: расположения данных в алфавитном порядке, группировки по некоторым признакам и т. д. Если информация структурирована, то поиск осуществляется быстрее, можно построить оптимальный алгоритм.
Ранее мы уже рассматривали метод половинного деления. Он применяется к наборам данных, элементы которых упорядочены по неубыванию, т. е. каждый последующий элемент не меньше (больше или равен) предыдущего:
Искомый элемент сравнивается с центральным элементом последовательности, номер которого находится как [N/2] + 1. Квадратные скобки здесь обозначают, что от результата деления берётся только целая часть, а дробная часть отбрасывается.
Если искомый элемент больше центрального, то поиск продолжается в правой части последовательности. Если искомый элемент меньше центрального, то — в левой. Если значения искомого элемента и центрального совпадают, то поиск завершается.
Рассмотрим работу этого алгоритма поиска информации на примере.
Пример 6. В последовательности чисел
061 087 154 180 208 230 290 345 367 389 456 478 523 567 590 612
требуется найти число 180.
Просмотр 1. Работаем со всей последовательностью. Определяем центральный элемент (он подчёркнут):
061 087 154 180 208 230 290 345 367 389 456 478 523 567 590 612
Сравниваем искомый элемент с центральным.
По результатам сравнения отбрасываем правую часть последовательности.
Просмотр 2. Работаем с левой частью последовательности. Определяем центральный элемент (он подчёркнут):
061 087 154 180 208 230 290 345
Сравниваем искомый элемент с центральным.
По результатам сравнения отбрасываем правую часть последовательности.
Просмотр 3. Работаем с левой частью последовательности. Определяем центральный элемент (он подчёркнут):
Сравниваем искомый элемент с центральным.
По результатам сравнения отбрасываем левую часть последовательности.
Просмотр 4. Работаем с правой частью последовательности. Определяем центральный элемент (он подчёркнут):
Центральный элемент совпадает с искомым. Поиск завершён.
Как связаны длительность поиска методом половинного деления и длина исходной последовательности данных?
Самое главное
Обработка информации — это целенаправленный процесс изменения содержания или формы представления информации. Существует два различных типа обработки информации:
1) обработка, связанная с получением нового содержания, новой информации;
2) обработка, связанная с изменением формы представления информации, не изменяющая её содержания.
Кодирование — это обработка информации, заключающаяся в её преобразовании в некоторую форму, удобную для хранения, передачи, обработки информации в дальнейшем.
Код — это система (список) условных обозначений (кодовых слов), используемых для представления информации.
Префиксный код — код со словом переменной длины, обладающий тем свойством, что никакое его кодовое слово не может быть началом другого (более длинного) кодового слова. Сообщение, закодированное с помощью префиксного кода, может быть однозначно декодировано.
Задача поиска информации состоит в том, чтобы в некотором хранилище информации (информационном массиве) найти информацию, удовлетворяющую определённым условиям поиска.
Время поиска зависит от способа организации набора данных и используемого алгоритма поиска.
Для осуществления поиска в неструктурированном наборе данных применяется метод последовательного перебора.
Поиск информации в упорядоченном по неубыванию наборе данных может быть осуществлён методом половинного деления.