Что нужно для обработки информации
Что нужно для обработки информации
Обработка (преобразование) информации — это процесс изменения формы представления информации или её содержания. Обрабатывать можно информацию любого вида, и правила обработки могут быть самыми разнообразными.
В результате обработки имеющейся (входной) информации мы получаем новую (выходную) информацию.
Во многих задачах бывает заранее известно правило, по которому следует осуществлять преобразование входной информации в выходную. Это правило может быть представлено в виде формулы или подробного плана действий.
Обработка информации — это решение информационной задачи, или процесс перехода от исходных данных к результату.
Процесс обработки информации не всегда связан с получением каких-то новых сведений. Например, при переводе текста с одного языка на другой. Обработка информации, связанная с изменением её формы, но не изменяющая содержания, происходит при систематизации информации, поиске информации, кодировании информации.
Обработка информации – это:
· представление и преобразование информации из одного вида в другой в соответствии с формальными правилами;
· процесс интерпретации (осмысления) данных;
· процесс преобразования к виду, удобному для передачи или восприятия (кодирование, декодирование и т.д.);
· процесс преднамеренного искажения или изменения структуры данных, изменение числовых значений данных и т.д.
Обработка информации заключается в различных преобразованиях самой информации или формы ее представления:
— извлечение новой информации из данной путем логических рассуждений, например, раскрытие преступления по собранным уликам
— изменение формы представления информации, например, перевод текста с одного языка на другой или шифровка (кодирование) текста;
— сортировка информации, например, упорядочение списка фамилий по алфавиту;
— поиск информации, например, поиск телефона в телефонной книге или поиск иностранного слова в словаре.
Под обработкой информации в информатике понимают любое преобразование информации из одного вида в другой, производимое по строгим формальным правилам. Примерами таких преобразований могут служить: замена одной буквы на другую в тексте; замена нулей на единицы, а единиц на нули в последовательности битов; сложение двух чисел, когда из информации, представляющей слагаемые, получается результат – сумма.
Слова «Обработка информации», таким образом, вовсе не подразумевают восприятие информации или ее осмысление. Компьютер – всего лишь машина и способна только к технической, машинной обработке информации.
Конечно, технические преобразования информации обычно производятся с целью достижения некоторого осмысленного эффекта. Например, если в тексте восклицательный знак заменить на вопросительный, то это будет соответствовать и некоторому смысловому изменению. Однако сама замена восклицательного знака на вопросительный носит технический характер и может быть произведена в любом тексте:
Это правда! à Это правда?
Обработка информации на ЭВМ обычно состоит в выполнении огромного количества такого рода элементарных, технических операций.
Но всегда ли нам известно, как, по каким правилам входная информация преобразовывается в выходную?
Такую систему, в которой наблюдателю доступны лишь входные и выходные величины, а её структура и внутренние процессы неизвестны, называют «чёрным ящиком».
Что представляют собой обработка, сбор и передача информации?
Содержание:
Обработка информации — это набор операций над информацией, которые осуществляют при помощи специальных технических и программных инструментов. В результате обработки информации она видоизменяется. Обработка информации являются частью информационных процессов, куда входят:
Сбор информации
По большому счету, жизнедеятельность каждого человека — это постоянный сбор информации о жизни, профессии, окружающих людях, других странах и т. д. В более узких смыслах сбор информации — это систематический мониторинг хранилищ информации: баз данных, справочников, библиотек и др.
Человек осуществляет сбор информации следующими методами:
Простой пример из жизни — вы решили поехать на выходные к другу в соседний город. Для того чтобы это сделать, вам необходимо будет просмотреть план проезда и расписание транспорта из вашего города в соседний. Для этого вы возьмете в руки телефон или сядете за компьютер, соберете всю необходимую информацию. Ваши родители, узнав о вашей поездке, попросят контакты вашего друга, проверят маршрут вашего передвижения, узнают адрес, где вы планируете находиться и др. И вы, и ваши родители произведете сбор информации при помощи технических средств. Сбор нужной информации — это умение, без которого очень трудно жить в современном мире.
Хранение информации
Информация хранится в цифровых и в нецифровых носителях. Носитель — это некий объект или среда, где сохраняется собранная информация.
Нецифровые носители — это:
Любое место или материал, где можно записать какую-то информацию может стать носителем. Самый распространенный нецифровой носитель современного мира — это бумага.
Цифровые носители — это:
Цифровые носители являются более компактными носителями информации, поэтому чаще всего применяются в жизнедеятельности человека. Такие носители помогают хранить информацию любых объемов, чего не скажешь о нецифровых носителях.
Вернемся к нашему примеру. После того как вы собрали информацию о проезде к другу в соседний город, вам нужно как-то сохранить эту информацию. Скорее всего вы ее запомните и отправите на хранение в мозг, плюс, сделаете скриншот расписания автобусов, чтобы сохранить на цифровом носителе.
Передача информации
Передача информации может быть открытой, закодированной или зашифрованной. Типичные примеры передачи информации:
Передача сигнала между источником и приемником называется канал связи, который тоже может быть открытым или защищенным.
Вернемся к нашему примеру. Вы сделали скрин расписания автобусов в соседний город, а родители захотели с ним ознакомиться. Вы открываете привычный мессенджер и скидываете скриншот им на телефон. Между вами и родителями произошла передача информации, где ваш телефон — это источник, а телефон родителей — приемник. Канал связи в мессенджере между вашими телефонами защищен сквозным шифрованием. Это значит, что даже если хакер в момент передачи перехватит ваш скрин, он не сможет его расшифровать и понять куда и во сколько вы едете.
Обработка информации
Обработка информации несет в себе цели:
Любое преобразование информации будет считаться ее обработкой, например:
Вернемся к нашему примеру. Вы скинули скрин родителям, но ваша мама пишет, что не может разобрать и понять что там изображено, поэтому просит вас скинуть в другом формате. Вы можете;
Все ваши действия — это и есть обработка информации.
Компьютерная грамотность с Надеждой
Заполняем пробелы — расширяем горизонты!
Как работает ПК: Обработка информации на компьютере
Мы давно уже привыкли к персональным компьютерам (сокращенно ПК). Включаем их и работаем, ни мало не задумываясь над тем, как они устроены и как происходит обработка информации на компьютере.
Все это благодаря тому, что разработчики ПК и программного обеспечения к ним научились создавать надежные продукты, которые не дают нам повода лишний раз задуматься над устройством компьютера или обслуживающих его программ.
Случай на экзамене
Профессор. Как работает трансформатор?
Студент. У-у-у-у-у-у-у-у-у-у-у-у-у-у…
Вероятно, читателям блога небезынтересно узнать о принципах работы компьютера и программного обеспечения.
Обработка информации на компьютере: основные этапы
Компьютер изначально был задуман для автоматизации процессов обработки информации. Он устроен соответствующим образом, чтобы иметь все возможности для успешного выполнения своего предназначения.
Для того чтобы обрабатывать в компьютере информацию, с ней необходимо делать следующие основные операции:
1) вводить информацию в компьютер:
Эта операция нужна для того, чтобы компьютеру было что обрабатывать. Без возможности ввода информации в компьютер он становится как бы вещью в себе.
2) хранить введенную информацию в компьютере:
Очевидно, что если дать возможность вводить информацию в компьютер, то надо также иметь возможность эту информацию в нем хранить, и затем использовать в процессе обработки.
3) обрабатывать введенную информацию:
Здесь надо понимать, что для обработки введенной информации нужны определенные алгоритмы обработки, иначе ни о какой обработке информации речи быть не может. Компьютер должен быть снабжен такими алгоритмами и должен уметь их применять к вводимой информации с тем, чтобы «правильно» преобразовывать ее в выходные данные.
4) хранить обработанную информацию
Так же как и с хранением введенной информации, в компьютере должны храниться результаты его работы, результаты обработки входных данных с тем, чтобы в дальнейшем ими можно было бы воспользоваться.
5) выводить информацию из компьютера
Эта операция позволяет вывести результаты обработки информации в удобочитаемом для пользователей виде. Именно эта операция дает возможность воспользоваться результатами обработки информации на компьютере. Иначе эти результаты обработки так и остались бы внутри компьютера, что сделало бы их получение совершенно бессмысленным.
Что такое обработка информации на компьютере
Самое важное умение компьютера – это обработка информации. Прелесть компьютера как раз и состоит в том, что он может информацию преобразовывать. Все устройство компьютера обусловлено требованием обработки информации в кратчайшие сроки, наиболее быстрым способом.
Под обработкой информации на компьютере можно понимать любые действия, которые преобразуют информацию из одного состояния в другое.
Соответственно, компьютер имеет специальное устройство, называемое процессором, которое предназначено исключительно для чрезвычайно быстрой обработки данных, со скоростями, доходящими до миллиардов операций в секунду.
Оперативная память (ОЗУ)
Требуемые для обработки данные процессор получает (берет) из оперативной памяти.
Оперативная память — это устройство, которое предназначено для ВРЕМЕННОГО хранения как входных, так и выходных данных.
Там же в оперативной памяти находится и место для хранения промежуточных данных, формируемых в процессе обработки информации. Таким образом, процессор как получает данные из оперативной памяти, так и записывает обработанные данные в эту память. Там информация хранится временно, до тех пор, пока она находится в обработке.
Наконец, для ввода и вывода данных к компьютеру подключаются внешние устройства ввода-вывода, которые позволяют ВВОДИТЬ информацию, подлежащую обработке, и ВЫВОДИТЬ результаты этой обработки.
Внешний винчестер, внешнее DVD-устройство, флешка, клавиатура, мышь
Процессор и оперативная память работают с одинаково большой скоростью. Как уже говорилось выше, скорость обработки информации может составлять многие миллионы и миллиарды операций в секунду. Никакое внешнее устройство ввода и вывода информации не может работать на таких скоростях.
Поэтому для их подключения в компьютере предусмотрены специальные контроллеры устройств ввода-вывода. Их задача состоит в том, чтобы согласовать высокие скорости работы процессора и оперативной памяти с относительно низкими скоростями ввода и вывода информации.
Эти контроллеры подразделяются на специализированные, к которым могут быть подключены только специальные устройства, и универсальные. Примером специализированного устройства контроллера служит, например, видеокарта, которая предназначена для подключения к компьютеру монитора.
Контроллеры могут быть и универсальными, в этом случае – это так называемые порты ввода-вывода, К портам ввода-вывода могут подключаться разнообразные устройства (клавиатуры, манипуляторы «мышь», принтеры, сканеры и т.п.).
Нашли ошибку? Выделите фрагмент текста и нажмите Ctrl+Enter.
Обработка информации
Обработка информации — процесс планомерного изменения содержания или формы представления информации.
Обработка информации производится в соответствии с определенными правилами некоторым субъектом или объектом (например, человеком или автоматическим устройством). Будем его называть исполнителем обработки информации.
Исполнитель обработки, взаимодействуя с внешней средой, получает из нее входную информацию, которая подвергается обработке. Результатом обработки является выходная информация, передаваемая внешней среде. Таким образом, внешняя среда выступает в качестве источника входной информации и потребителя выходной информации.
Обработка информации происходит по определенным правилам, известным исполнителю. Правила обработки, представляющие собой описание последовательности отдельных шагов обработки, называются алгоритмом обработки информации.
Исполнитель обработки должен иметь в своем составе обрабатывающий блок, который назовем процессором, и блок памяти, в котором сохраняются как обрабатываемая информация, так и правила обработки (алгоритм). Все сказанное схематически представлено на рисунке.
Схема обработки информации
Пример. Ученик, решая задачу на уроке, осуществляет обработку информации. Внешней средой для него является обстановка урока. Входной информацией — условие задачи, которое сообщает учитель, ведущий урок. Ученик запоминает условие задачи. Для облегчения запоминания он может использовать записи в тетрадь — внешнюю память. Из объяснения учителя он узнал (запомнил) способ решения задачи. Процессор — это мыслительный аппарат ученика, применяя который для решения задачи, он получает ответ — выходную информацию.
Схема, представленная на рисунке, — это общая схема обработки информации, не зависящая от того, кто (или что) является исполнителем обработки: живой организм или техническая система. Именно такая схема реализована техническими средствами в компьютере. Поэтому можно сказать, что компьютер является технической моделью “живой” системы обработки информации. В его состав входят все основные компоненты системы обработки: процессор, память, устройства ввода, устройства вывода (см. “Устройство компьютера” 2).
Входная информация, представленная в символьной форме (знаки, буквы, цифры, сигналы), называется входными данными. В результате обработки исполнителем получаются выходные данные. Входные и выходные данные могут представлять собой множество величин — отдельных элементов данных. Если обработка заключается в математических вычислениях, то входные и выходные данные — это множества чисел. На следующем рисунке X: <x1, x2, …, xn> обозначает множество входных данных, а Y: <y1, y2, …, ym> — множество выходных данных:
Схема обработки данных
Обработка заключается в преобразовании множества X в множество Y:
Здесь Р обозначает правила обработки, которыми пользуется исполнитель. Если исполнителем обработки информации является человек, то правила обработки, по которым он действует, не всегда формальны и однозначны. Человек часто действует творчески, не формально. Даже одинаковые математические задачи он может решать разными способами. Работа журналиста, ученого, переводчика и других специалистов — это творческая работа с информацией, которая выполняется ими не по формальным правилам.
Для обозначения формализованных правил, определяющих последовательность шагов обработки информации, в информатике используется понятие алгоритма (см. “Алгоритм” 2). С понятием алгоритма в математике ассоциируется известный способ вычисления наибольшего общего делителя (НОД) двух натуральных чисел, который называют алгоритм Евклида. В словесной форме его можно описать так:
1. Если два числа равны между собой, то за НОД принять их общее значение, иначе перейти к выполнению пункта 2.
2. Если числа разные, то большее из них заменить на разность большего и меньшего из чисел. Вернуться к выполнению пункта 1.
Здесь входными данными являются два натуральных числа — х1 и х2. Результат Y — их наибольший общий делитель. Правило (Р) есть алгоритм Евклида:
Такой формализованный алгоритм легко запрограммировать для современного компьютера. Компьютер является универсальным исполнителем обработки данных. Формализованный алгоритм обработки представляется в виде программы, размещаемой в памяти компьютера. Для компьютера правила обработки (Р) — это программа.
Методические рекомендации
Объясняя тему “Обработка информации”, следует приводить примеры обработки, как связанные с получением новой информации, так и связанные с изменением формы представления информации.
Первый тип обработки: обработка, связанная с получением новой информации, нового содержания знаний. К этому типу обработки относится решение математических задач. К этому же типу обработки информации относится решение различных задач путем применения логических рассуждений. Например, следователь по некоторому набору улик находит преступника; человек, анализируя сложившиеся обстоятельства, принимает решение о своих дальнейших действиях; ученый разгадывает тайну древних рукописей и т.п.
Второй тип обработки: обработка, связанная с изменением формы, но не изменяющая содержания. К этому типу обработки информации относится, например, перевод текста с одного языка на другой: изменяется форма, но должно сохраниться содержание. Важным видом обработки для информатики является кодирование. Кодирование — это преобразование информации в символьную форму, удобную для ее хранения, передачи, обработки (см. “Кодирование” ).
Структурирование данных также может быть отнесено ко второму типу обработки. Структурирование связано с внесением определенного порядка, определенной организации в хранилище информации. Расположение данных в алфавитном порядке, группировка по некоторым признакам классификации, использование табличного или графового представления — все это примеры структурирования.
Особым видом обработки информации является поиск. Задача поиска обычно формулируется так: имеется некоторое хранилище информации — информационный массив (телефонный справочник, словарь, расписание поездов и пр.), требуется найти в нем нужную информацию, удовлетворяющую определенным условиям поиска (телефон данной организации, перевод данного слова на английский язык, время отправления данного поезда). Алгоритм поиска зависит от способа организации информации. Если информация структурирована, то поиск осуществляется быстрее, его можно оптимизировать (см. “Поиск данных”).
В пропедевтическом курсе информатики популярны задачи “черного ящика”. Исполнитель обработки рассматривается как “черный ящик”, т.е. система, внутренняя организация и механизм работы которой нам не известен. Задача состоит в том, чтобы угадать правило обработки данных (Р), которое реализует исполнитель.
Исполнитель обработки вычисляет среднее значение входных величин: Y = (X1 + X2)/2
На входе — слово на русском языке, на выходе — число гласных букв.
Наиболее глубокое освоение вопросов обработки информации происходит при изучении алгоритмов работы с величинами и программирования (в основной и старшей школе). Исполнителем обработки информации в таком случае является компьютер, а все возможности по обработке заложены в языке программирования. Программирование есть описание правил обработки входных данных с целью получения выходных данных.
Следует предлагать ученикам два типа задач:
— прямая задача: составить алгоритм (программу) для решения поставленной задачи;
— обратная задача: дан алгоритм, требуется определить результат его выполнения путем трассировки алгоритма.
При решении обратной задачи ученик ставит себя в положение исполнителя обработки, шаг за шагом выполняя алгоритм. Результаты выполнения на каждом шаге должны отражаться в трассировочной таблице.
Учитель информатики
Сайт учителя информатики. Технологические карты уроков, Подготовка к ОГЭ и ЕГЭ, полезный материал и многое другое.
Обработка информации
§ 4. Обработка информации
Информатика. 10 класса. Босова Л.Л. Оглавление
Информационный процесс — совокупность последовательных действий (операций), производимых над информацией (в виде данных, фактов, идей, гипотез, теорий и пр.) для получения какого-либо результата (достижения цели).
Можно выделить три основных типа информационных процессов: обработка, хранение и передача информации. Рассмотрим их подробнее.
Обработка информации — это целенаправленный процесс изменения содержания или формы представления информации.
Хранение информации – это один из главных информационных процессов, с которым неразрывно связано понятие устройства хранения информации, или запоминающего устройства. Разные устройства могут использовать различные способы хранения информации.
Передача информации — физический процесс, посредством которого осуществляется перемещение информации в пространстве. Записали информацию на диск и перенесли в другую комнату.
Данный процесс характеризуется наличием следующих компонентов:
Источник информации.
Приёмник информации.
Носитель информации.
Среда передачи.
4.1. Задачи обработки информации
Из курса информатики основной школы вам известно, что существует два различных типа обработки информации: 1) обработка, связанная с получением нового содержания, новой информации; 2) обработка, связанная с изменением формы представления информации, не изменяющая её содержания.
К первому типу обработки информации относятся: преобразование по правилам (в том числе вычисления по формулам), исследование объектов познания по их моделям, логические рассуждения, обобщение и др.
Ко второму типу обработки информации можно отнести: • кодирование — переход от одной формы представления информации к другой, более удобной для восприятия, хранения, передачи или последующей обработки; • структурирование — организацию информации по некоторому правилу, связывающему её в единое целое; • поиск и отбор информации, требуемой для решения некоторой задачи, из информационного массива и др.
При всём многообразии решаемых задач в процессе обработки информации всегда решается некоторая информационная задача, а именно: дан некоторый набор исходных данных — исходной информации, требуется получить некоторые результаты — итоговую информацию. Сам процесс перехода от исходных данных к результату и есть процесс обработки. Тот объект, который осуществляет обработку, может быть назван исполнителем обработки. Для успешного выполнения обработки информации исполнителю должен быть известен способ обработки, т. е. последовательность действий, которую нужно выполнить, чтобы достичь нужного результата. Описание такой последовательности принято называть алгоритмом обработки.
Общая схема процесса обработки информации представлена на рисунке 1.11.
Рис. 1.11. Общая схема процесса обработки информации
Исполнителем обработки информации может быть человек или компьютер. При этом человек, как правило, является неформальным, творчески действующим исполнителем. Даже для решения самой простой математической задачи разные люди могут использовать разные способы!
Что касается компьютера, то он является формальным исполнителем, действия которого осуществляются автоматически, строго в соответствии с имеющимся алгоритмом обработки информации.
Рассмотрим отдельные процессы обработки информации более подробно.
4.2. Кодирование информации
Кодирование информации широко используется в технических средствах работы с информацией (телеграф, радио, компьютеры).
Кодирование — это обработка информации, заключающаяся в её преобразовании в некоторую форму, удобную для хранения, передачи, обработки информации в дальнейшем.
Кодовая таблица — это совокупность используемых кодовых слов и их значений.
1) Также кодом зачастую называют результат кодирования информации.
Ранее мы уже рассмотрели примеры равномерных двоичных кодов — пятиразрядный код Бодо и восьмиразрядный код ASCII.
Самый известный пример неравномерного кода — код (азбука) Морзе, в которой цифры и буквы алфавита представляются последовательностями длинных («тире») и коротких («точек») сигналов, названный в честь американского изобретателя и художника Сэмюэля Морзе (1791-1872). Буквы, встречающиеся в сообщениях чаще, имеют в этом коде более короткий код, чем «редкие» буквы (рис. 1.12).
Рис. 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.
Для вычисления значения этой величины применяется формула:
Здесь n! = 1 • 2 • … • n.
Действительно, множество, с которым мы имеем дело, состоит из мест для записи символов в последовательности. Его элементы можно обозначить 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. Для кодирования некоторой последовательности, состоящей из букв А, Б, В и Г, решили использовать неравномерный двоичный код, позволяющий однозначно декодировать полученную двоичную последовательность. Для букв А, Б и В использовали такие кодовые слова: А — О, Б — 10, В — 110.
Каким кодовым словом может быть закодирована буква Г? Код должен удовлетворять свойству однозначного декодирования. Если можно использовать более одного кодового слова, укажите кратчайшее из них.
Для решения задачи воспользуемся бинарным деревом.
Отметим вершины, соответствующие используемым кодовым словам: А — 0, Б — 10, В — 110:
Так как комбинациям префиксного кода должны соответствовать листья бинарного дерева, наше кодовое дерево должно выглядеть так:
Итак, для кодирования буквы Г можно использовать код 111.
Усложним условие задачи. Теперь кодируемая последовательность состоит из букв А, Б, В, Г и Д. Кодовые слова для букв А, Б и В определены: А — О, Б — 10, В — 110.
Какими кодовыми словами могут быть закодированы буквы Г и Д? Код должен удовлетворять свойству однозначного декодирования. Общая длина кодовых слов для всех пяти букв должна быть минимальной.
4.3. Поиск информации
Неоценима роль компьютера в организации важнейшей задачи обработки информации — поиска информации, необходимой человеку для решения стоящей перед ним задачи.
Вспомните, как часто и какую информацию приходится искать вам, членам вашей семьи, вашим друзьям и знакомым. Приведите примеры.
Задача поиска обычно формулируется следующим образом. Имеется некоторое хранилище информации — информационный массив (телефонный справочник, словарь, расписание поездов, диск с файлами и др.). Требуется найти в нём нужную информацию, удовлетворяющую определённым условиям поиска (телефон данной организации, перевод данного слова на английский язык, время отправления данного поезда, файл с рефератом). При этом, как правило, необходимо сократить время поиска, которое зависит от способа организации набора данных и используемого алгоритма поиска.
Алгоритм поиска, в свою очередь, зависит от способа организации информации.
Если данные никак не организованы, то мы имеем дело с неструктурированным набором данных. Для осуществления поиска в таком наборе данных применяется метод последовательного перебора: все элементы, начиная с первого, просматриваются подряд. Поиск завершается в двух случаях:
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. Работаем с левой частью последовательности. Определяем центральный элемент (он подчёркнут):
061 087 154 180
Сравниваем искомый элемент с центральным.
По результатам сравнения отбрасываем левую часть последовательности.
Просмотр 4. Работаем с правой частью последовательности. Определяем центральный элемент (он подчёркнут):
Центральный элемент совпадает с искомым. Поиск завершён.
Как связаны длительность поиска методом половинного деления и длина исходной последовательности данных?
САМОЕ ГЛАВНОЕ
Обработка информации — это целенаправленный процесс изменения содержания или формы представления информации. Существует два различных типа обработки информации:
1) обработка, связанная с получением нового содержания, новой информации;
2) обработка, связанная с изменением формы представления информации, не изменяющая её содержания.
Кодирование — это обработка информации, заключающаяся в её преобразовании в некоторую форму, удобную для хранения, передачи, обработки информации в дальнейшем.
Код — это система (список) условных обозначений (кодовых слов), используемых для представления информации.
Префиксный код — код со словом переменной длины, обладающий тем свойством, что никакое его кодовое слово не может быть началом другого (более длинного) кодового слова. Сообщение, закодированное с помощью префиксного кода, может быть однозначно декодировано.
Задача поиска информации состоит в том, чтобы в некотором хранилище информации (информационном массиве) найти информацию, удовлетворяющую определённым условиям поиска.
Время поиска зависит от способа организации набора данных и используемого алгоритма поиска.
Для осуществления поиска в неструктурированном наборе данных применяется метод последовательного перебора.
Поиск информации в упорядоченном по неубыванию наборе данных может быть осуществлён методом половинного деления.
Вопросы и задания
1. Приведите примеры процессов обработки информации, которые чаще всего вам приходится выполнять в жизни. Для каждого примера определите исходные данные, алгоритм (правила) обработки и получаемые результаты. К каким типам обработки информации относятся эти процессы?
2. Поясните суть понятий «кодирование», «код», «кодовая таблица».
3. Светодиодная панель содержит шесть излучающих элементов, каждый из которых может светиться или красным, или жёлтым, или зелёным цветом. Сколько различных сигналов можно передать с помощью панели (все излучающие элементы должны гореть, порядок цветов имеет значение)?
4. Автомобильный номер состоит из нескольких букв (количество букв одинаковое во всех номерах), за которыми следуют три цифры. При этом используются 10 цифр и только 5 букв: А, В, С, D и F. Требуется не менее 100 тысяч различных номеров. Какое наименьшее количество букв должно быть в автомобильном номере?
5. Сколько существует различных последовательностей из 6 символов четырёхбуквенного алфавита <А, В, С, D>, которые содержат не менее двух букв А (т. е. две и более буквы А)?
6. Сравните равномерные и неравномерные коды. Каковы их основные достоинства и недостатки?
7. Какие коды называют префиксными? Почему они так важны? В чём суть прямого и обратного условий Фано?
8. Двоичные коды для 5 букв латинского алфавита представлены в таблице:
Из четырёх сообщений, закодированных этими кодами, только одно пришло без ошибки. Найдите его:
1) 110100000100110011;
2) 111010000010010011;
3) 110100001001100111;
4) 110110000100110010.
9. Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г и Д, используется неравномерный двоичный код, позволяющий однозначно декодировать полученную двоичную последовательность. При этом используются следующие коды: А — 1110, Б — 0, В — 10, Г — 110. Каким кодовым словом может быть закодирована буква Д? Код должен удовлетворять свойству однозначного декодирования. Если можно использовать более одного кодового слова, укажите кратчайшее из них.
10. Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г и Д, используется неравномерный троичный код, позволяющий однозначно декодировать полученную троичную последовательность. Вот этот код: А — 0, Б — 11, В — 20, Г — 21, Д — 22. Можно ли сократить для одной из букв длину кодового слова так, чтобы закодированную последовательность по-прежнему можно было декодировать однозначно? Коды остальных букв меняться не должны.
11. Для передачи закодированных сообщений используется таблица кодовых слов из четырёх букв. Причем используются только буквы А, Р и У. Сколько различных кодовых слов может быть в такой таблице, если ни в одном слове нет трёх одинаковых букв, идущих подряд?
12. Методом половинного деления в последовательности чисел
061 087 154 180 208 230 290 345 367 389 456 478 523 567 590 612
требуется найти число 590. Опишите процесс поиска.
13. В Международном конкурсе по информатике «Бобёр» школьникам была предложена задача «Склад», подготовленная специалистами из Японии. Вот её условие.
Плотник в Бобровой Деревне использует 31 склад, пронумерованный от 1 до 31. Однажды он забыл, сколько складов уже заполнил, но помнит, что заполнял их в порядке возрастания номеров.
Чтобы уменьшить количество открывания дверей, он действует следующим образом:
Сначала открывает склад со средним номером — склад № 16. Затем:
• если склад № 16 пуст, он решает искать первый незаполненный склад в промежутке от № 1 до № 15, открывает опять средний склад — склад № 8 — и повторяет процедуру;
• если склад № 16 заполнен, то нужный склад он ищет между № 17 и № 31, открывает средний склад — склад № 24 — и повторяет процедуру.
После всех действий плотник обнаружил, что заполнены были склады от № 1 до № 15 включительно. Сколько дверей ему пришлось открыть?
Решите эту задачу. Какой из рассмотренных нами методов поиска был использован героем этой задачи?