Вероятностный, или содержательный подход

Попытаться объяснить данный подход можно, допустив,

что для каждого человека можно условно выделить (напри­мер, в виде окружности) область его знания. Всё, что будет находиться за пределами окружности, можно назвать информа­ционной неопределенностью. Постепенно, в процессе обучения или иной деятельности происходит переход от незнания к зна­нию, т. е. неопределенность уменьшается. Именно такой под­ход к информации как мере уменьшения неопределенности знания позволяет ее количественно оценить (измерить).

Сообщение, уменьшающее неопределенность знания в 2 раза, несет один бит информации.

Например: при подбрасывании монеты может выпасть либо «орел», либо «решка». Это два возможных события. Они равновероятны. Сообщение о том, что произошло одно из двух равновероятных событий (например, выпала «решка»), уменьшает неопределенность нашего знания (перед броском монеты) в два раза.

Математики рассматривают идеальный вариант, что воз­можные события равновероятны. Если даже события неравновероятны, то возможен подсчет вероятности выпадения каждого события.

Под неопределенностью знания здесь понимают количе­ство возможных событий, их может быть больше, чем два.

Например, количество оценок, которые может получить студент на экзамене, равно четырем. Сколько информации содержится в сообщении о том, что он получил «4»? Рассуж­дая, с опорой на приведенное выше определение, можем сказать, что если сообщение об одном из двух возможных событий несет 1 бит информации, то выбор одного из четы­рех возможных событии несет 2 бита информации. Можно прийти к такому выводу, пользуясь методом половинного деления. Сколько вопросов необходимо задать, чтобы выяс­нить необходимое, столько битов и содержит сообщение. Во­просы должны быть сформулированы так, чтобы на них можно было ответить «да» или «нет», тогда каждый из них будет уменьшать количество возможных событий в 2 раза.

Очевидна связь количества возможных равновероятных событий и количества информации:

N=2ⁱ, где N - количество событий, а i-количество информации (в битах)

 

Заполним по формуле таблицу:

 

Количество битов							б
Количество событии

 

Или:

i = log₂N.

Это формула Р. Хартли. Если р = 1/N — вероятность на­ступления каждого из N равновероятных событий, тогда формула Хартли записывается так:

i = log₂(1/p) = log₂p

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

 

Алфавитный подход к измерению информации

Подход основан на подсчете числа символов в сообщении. Этот подход не связывает количество информации с содержа­нием сообщения, позволяет реализовать передачу, хранение и обработку информации с помощью технических устройств, не теряя при этом содержания (смысла) сообщения.

Алфавит любого языка включает в себя конечный набор символов. Исходя из вероятностного подхода к определению количества информации, появление символов алфавита в тексте можно рассматривать как различные возможные со­бытия. Количество таких событий (символов) N называют мощностью алфавита. Тогда количество информации (, ко­торое несет каждый из N символов, согласно вероятностно­му подходу определяется из формулы:

2ⁱ = N.

Количество символов в тексте из k символов:

I= k? i

Алфавитный подход является объективным способом из­мерения информации и используется в технических устрой­ствах.

 

Переход к более крупным единицам измерения

Ограничения на максимальную мощность алфавита не су­ществует, но есть алфавит, который можно считать доста­точным (на современном этапе) для работы с информацией, как для человека, так и для технических устройств. Он включает в себя: латинский алфавит, алфавит языка стра­ны, числа, спецсимволы — всего около 200 знаков. По при­веденной выше таблице можно сделать вывод, что 7 битов информации недостаточно, требуется 8 битов, чтобы закоди­ровать любой символ такого алфавита, 256 = 2⁸. 8 бит об­разуют 1 байт. То есть для кодирования символа компьютер­ного алфавита используется 1 байт. Укрупнение единиц из­мерения информации аналогично применяемому в физике — используют приставки «кило», «мега», «гига». При этом следует помнить, что основание не 10, а 2.

1 Кб (кило­байт) = 2¹⁰ байт = 1024 байт,

1 Мб(мегабайт) = 2¹⁰ Кб = 2²⁰ байт и т. д.

Умение оценивать количество информации в сообще­нии поможет определить скорость информационного пото­ка по каналам связи. Максимальную скорость передачи информации по каналу связи называют пропускной спо­собностью канала связи. Самым совершенным средством связи на сегодня являются оптические световоды. Инфор­мация передается в виде световых импульсов, посылае­мых лазерным излучателем. У этих средств связи высокая помехоустойчивость и пропускная способность более 100Мбит/с.

 

Понятие алгоритма: свойства алгоритмов, исполнители алгоритмов. Автоматическое исполнение алгоритма. Основные алгоритмические структуры.

 

Понятие алгоритма

Исторический обзор. Первым дошедшим до нас алгорит­мом в его интуитивном понимании — конечной последовательности элементарных действии, решающих поставлен­ную задачу, — считается предложенный Евклидом в III веке до нашей эры алгоритм нахождения наибольшего общего де­лителя двух чисел (алгоритм Евклида). Вплоть до начала XX века само слово «алгоритм» употреблялось в устойчивом сочетании «алгоритм Евклида». Для описания пошагового решения других математических задач использовалось сло­во «метод».

Слово «алгоритм», «algorithm» происходит от имени вы­дающегося ученого IX века Мухаммеда ибн Муса ал-Хорезми (в переводе с арабского Мухаммед, сын Мусы из Хорезма). По латинскому переводу его труда (XII век) Западная Европа познакомилась с десятичной позиционной системой счисления и правилами (algorismi) выполнения в ней арифметических действий.

 

Формализация понятия алгоритма. Во всех сферах своей деятельности, в частности, в сфере обработки информации, человек сталкивается с различными методами решения задач. Они определяют порядок выполнения действий для получения желаемого результата — мы можем трактовать это как первоначальное или интуитивное определение алгоритма.

Определение 1. Алгоритм — это заданное на некотором языке конечное предписание, задающее конечную последовательность выполнимых элементарных операций для решения задачи, общее для класса возможных исходных данных.

Варианты словесного определения алгоритма, принадле­жащие российским ученым-математикам А. Н. Колмогорову и А. А. Маркову:

Определение 2 (Колмогоров). Алгоритм — это всякая система вычислений, выполняемых по строго определенным правилам, которая после какого-либо числа шагов заведомо приводит к решению поставленной задачи.

Определение 3 (Марков). Алгоритм — это точное предписание, определяющее вычислительный процесс, идущий от варьируемых исходных данных к искомому результату.

 

Свойства алгоритмов

• Дискретность. Алгоритм состоит из последовательных команд, только выполнив одну команду, исполнитель может приступить к выполнению следующей. То есть структура алгоритма является дискретной (прерывной).
• Конечность. Алгоритм содержит конечное количество элементарных выполнимых предписаний, т. е. удовлетворяет требованию конечности записи. Исполнитель алгоритма должен выполнять конечное количество шагов при решении задачи, т. е. алгоритм удовлетворяет требованию конечности действий.
• Точность (определенность). Каждая команда алгоритма должна определять однозначное действие исполни­теля. Этим свойством часто не обладают предписания и инструкции, которые составляются для людей.
• Понятность. Каждая команда алгоритма должна быть понятна исполнителю. Алгоритм не рассчитан на при­нятие самостоятельных решений исполнителем, не предусмотренных составителем алгоритма.
• Универсальность (массовость). Алгоритм должен быть единым для всех допустимых исходных данных. Разработка алгоритма — процесс творческий, но требующий значительных затрат времени и умственных усилий, поэтому желательно, чтобы он обеспечивал решение за­дач данного типа. Это свойство не является обязатель­ным; не менее важными являются алгоритмы уникальные, разработанные для решения одной задачи.

Алгоритм предполагает наличие исполнителя — человека или технического устройства (автомат, робот, компьютер) со строго определенным набором возможных команд. Совокупность команд, которые могут быть выполнены исполнителем, называется системой команд исполнителя (СКИ). Исполнитель может исполнять команды из СКИ и ничего более.