19. Понятие информации. Представление информации. Количество информации. Свойства информации.

• ИНФОРМАЦИЯ – это совокупность сведений, уменьшающих неопределенность в выборе различных возможностей. Это такое общее определение, не относящееся к конкретной области. В переводе с латинского информация – это разъяснение, осведомление.

• Информацию можно создавать, передавать, запоминать, искать, принимать, копировать (в какой-то форме), обрабатывать и, наконец, утаивать или разрушать

• Формы представления информации следующие: числовая, текстовая, графическая, звуковая.

• Хранение информации – это запись на какое-то запоминающее устройство, для последующего использования, в любой, необходимый момент (чтобы не создавать заново). Это средство обеспечения ее доступности. Информация записывается в файл. Файл – это место постоянного хранения информации на внешних носителях. Независимо от того, какого вида информацию мы хотим сохранить, в память компьютера информация всегда записывается в числовой форме, в двоичном виде. Для записи в память машины используется два символа «0» и «1», т.е. используется двоичный код. Это простейший язык, алфавит которого состоит из двух символов, они называются битами (величина способная принимать лишь два значения). Бит, принят за минимальную единицу измерения информации. Дальше байт, Кбайт, Мбайт, Гбайт – соответствующие степени двойки (8бит, 2 в 10 степени, 2 в 100 и т.д.).

• Еще одна операция, осуществляемая над информацией – это поиск информации, извлечение хранимой информации.

• Количество информации – это одна из основных характеристик информации, но это субъективная характеристика. Использование терминов «больше информации» или «меньше информации» подразумевает некоторую возможность ее измерения. В тоже время в информатике нельзя провести точную параллель между объемом информации и количеством информации, точнее нельзя установить такую порядковую шкалу. Поэтому информация воспринимается через определенный набор свойств: важность, достоверность, своевременность, доступность и т.д. С точки зрения информатики наиболее важными считаются следующие свойства: объективность, полнота, достоверность, адекватность, доступность и актуальность.

• Объективность и субъективность информации. Более объективной принято считать ту информацию, в которой применяемые методы вносят наименьшие субъективные элементы (фотография и рисунок, вынужденная выборка и т.д.).

• Полнота информации. Полнота информации во многом характеризует качество информации и определяет достаточность данных для принятия решений или для создания новых данных на основе имеющихся.

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

• Адекватность информации – это степень соответствия реальному объективному состоянию дела. Неадекватная информация может образоваться при создании новой информации на основе неполных или недостоверных данных.

• Доступность информации – это мера возможности получить ту или иную информацию.

Основные понятия теории информации и теории кодирования. Кодирование информации. Первая и вторая теорема Шеннона. Системы счисления.

Изучением информатики как таковой (т.е. в виде абстрактного объекта, лишенного конкретного содержания), выявлением общих свойств информации, законов, управляющих ее рождением, развитием и уничтожением, занимается теория информации. Информацию, которая где-то содержится, например, в сообщении, можно рассматривать с различных точек зрения, например, насколько она новая или неожиданная. Теория информации – это одно направление научных исследований, вторым направлением является теория кодирования. Теория кодирования занимается изучением форм, в которые может быть преобразовано содержание любой конкретной информационной единицы (передаваемого сообщения, гранулы знаний и т.п.) Часто эти два направления объединяют в теорию связи. Теория связи – это изучение систем связи с использованием математических моделей их функционирования.

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

КОДИРОВАНИЕ – это процесс представления информации в определенной форме с помощью некоторого алфавита. Математически этот процесс описывается отображением произвольного множества в множество конечных последовательностей (слов) некоторого алфавита. Дискретная информация записывается с помощью некоторого конечного набора знаков, которые условно называются буквами. Буква в данном расширенном понимании – это любой из знаков, которые некоторым соглашением установлены для общения. Эти знаки составляют алфавит кода. КОД – это конечное или счетное множество слов в некотором алфавите, который используется для представления информации.

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

Передача информации подразумевает, что имеется «источник информации» и «получатель информации». Информация от источника к получателю передается посредством какой-нибудь среды, являющейся в таком случае «каналом связи». КАНАЛ СВЯЗИ – это путь, по которому передается информация, он может быть физическим или виртуальным.

Теория связи. Основные понятия теории кодирования. Побуквенное кодирование.

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

В теории связи существует утверждения, что любой сколь угодно зашумленный канал обладает определенной пропускной способностью – скоростью передачи информации, которая никогда не может быть превышена без ошибок, но в принципе достижима с некоторой произвольно малой вероятностью ошибки. Это утверждение является теоремой о канальном кодировании. Впервые она была сформулирована и доказана К.Э.Шенноном. Наиболее широкое применение получили такие коды как, проверка на четность, коды Хэмминга, циклические проверки для обнаружения ошибок, простейшие сверточные коды и т.п.

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

Длина кода – это число генерируемых в процессе операции кодирования символов. Обычно число вводимых в кодер символов фиксировано; число выводимых может быть фиксированным, либо переменным, в зависимости от типа используемого кодера, который может формировать код фиксированной или переменной длины.

Код фиксированной или постоянной длины – это код, ставящий в соответствие определенному количеству символов источника определенное количество выходных символов. Как правило, это блочный код. Блочный код – это код с исправлением ошибок или код с обнаружением ошибок, в котором за одну операцию на вход кодера поступает фиксированное число (например, k) знаков, а на выходе генерируется кодовое слово, состоящее из большего числа знаков (например, n). Этот код иногда называют (n,k) – кодом, т.е. с длиной блока k и длиной кодового слова n. В теории кодирования блок – это упорядоченный набор символов, имеющих обычно фиксированную длину, можно, в общем случае, считать синонимом терминов слово и цепочка, но обязательно фиксированная длина. Декодер за одну операцию принимает n знаков и выдает k знаков. Поскольку кодовые слова длиннее входных слов, число одновременно принимаемых слов не так велико. Кодовые слова формируются фактически путем выбора из множества слов соответствующей длины, а именно способ выбора придает коду те или иные конкретные свойства.

Кодирование информации позволяет декодеру с большой вероятностью успеха исправить любые ошибки, возникающие в канале при искажении сигнала помехой. Коды с исправлением ошибок применяются в системах с прямым исправлением, не зависимо от того блочный это код или сверточный. Кодами с исправлением ошибок являются коды Хемминга, симплексные коды, код Голея, коды Рида-Соломона и коды Боуза-Чоудхури-Хокенгема. Методы повышения надежности за счет введения избыточности широко применяются как в различных технических устройствах, так и в повседневной жизни. Например, многие естественные языки обладают избыточностью (русский, японский, английский), за счет чего мы можем понять речь даже при сильном искажении. В технике, например, могут установить два – три одинаковых устройства при выходе из строя одного его можно заменить другим. Или с помощью одного устройства выполняются дважды одни и те же вычисления, и если результаты этих вычислений совпадают, то принимается решение о том, что вычисления выполнены без ошибок. Если же результаты этих вычислений не совпадают, значит, в процессе вычисления произошла ошибка. Вычисления повторяются. Это примеры повышения надежности при наличии избыточности.

Поскольку ошибки можно устранять путем их обнаружения и запроса повторной передачи, в число систем с исправлением ошибок иногда включают системы с переспросом, в которых используются коды с обнаружением ошибок. Коды с обнаружением ошибок обычно бывают блочными, и, как правило, применяются в системах с переспросом. Для обнаружения ошибок наиболее часто используются циклические, избыточные коды. Простая разновидность такого кода – код с контролем по четности (чаще всего используется в технике). (Исправление ошибок переспросом – исправление посредством обнаружения их приемником, когда последний реагирует на любую ошибку в принятом блоке путем отправления передатчику запроса на повторную передачу блока. Исправление переспросом в отличие от прямого исправления ошибок требует наличия обратного канала.) Примером такого кода служат линейные коды – это коды, кодирование и декодирование в которых может быть сведено к линейным операциям.

Циклический, избыточный код – это разновидность полиномиального кода (семейство линейных кодов с исправлением или обнаружением ошибок, алгоритмы кодирования и декодирования которых могут быть выражены соответствующим образом в терминах полиномов над базовым полем, следовательно, могут быть реализованы в понятиях регистров сдвига с комбинационной линейной логикой, Р151). В принципе, каждый блок можно считать полиномом. Этот полином А умножается в кодере на порождающий полином (формально заданный степенной ряд, то есть сумма множества степенных выражений независимых переменных Р150) G, в результате чего формируется полином AG. В процессе передачи или записи этого полинома к нему добавляется полином ошибки E:

AG + E.

В декодере эта последовательность делится на тот же самый порождающий полином G. Остаток деления проверяется. Если он отличен от нуля, то регистрируется ошибка, и предпринимаются необходимые действия (В 011).

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

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

Для представления чисел используются непозиционные и позиционные системы счисления.

В непозиционных системах каждая цифра имеет свой вес и ее значение не зависит от положения в числе – от позиции. Пример – римская система. Скажем, число 76 в этой системе выглядит так:

LXXVI, где L=50, X=10, V=5, I=1.

Как видно цифрами здесь служат латинские символы.

В позиционных системах значения цифр зависят от их положения (позиции) в числе.

Так, например, человек привык пользоваться десятичной позиционной системой — числа записываются с помощью 10 цифр. Самая правая цифра обозначает единицы, левее — десятки, ещё левее — сотни и т.д.

В любой позиционной системе число может быть представлено в виде многочлена.

20, 21. Теория автоматов. Абстрактный автомат. Цифровые автоматы. Вычисляемые функции. Формальная теория вычислимости (частично-рекурсивные функции), регистровые машины (машина Тьюринга) и нормальные алгоритмы Маркова.

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

Теорию алгоритмов мы с вами рассмотрим только с точки зрения теоретического изучения алгоритмов и их разрешимости. Все алгоритмические языки и языки программирования относятся к формальным языкам

Что такое формальный язык? Это конечное или бесконечное подмножество множества * всех -слов образованных из некоторого конечного набора символов .

Изучением формальных языков занимается теория формальных языков (F118). В частности эта наука занимается изучением структуры и способов представления бесконечных классов формальных языков. В основе таких исследований лежат методы формальной логики (F119). Это наука о методах анализа высказываний и доказательств, в которой рассматриваются абстрактные символы и сформированные из них выражения, но не придается никакого значения семантике этих абстракций (можно посмотреть символьная логика S417). Формальные языки описываются главным образом с помощью грамматик (G044), L-систем (L152) и автоматов (А189). Изучение формальных языков начато Н.Хомским в 1956 году в связи с попытками формализации методов исследования естественных языков. В дальнейшем теория формальных языков применялась или развивалась в связи с синтаксическим анализом языков программирования (P050), проблемами эффективной вычислимости (E023) и сложности вычислений (С214), теорией полугрупп (S074). Наиболее распространенными предметами исследований являются: разрешимость задачи определения свойств языков, характеристика классов языков с точки зрения их замкнутости (C137), а также выявление различных способов описания классов языков с помощью, например, языка Дика (D320). Так же изучаются такие проблемы, как являются ли контекстные языки (С283) замкнутыми относительно операции образования дополнения, а также разрешима ли задача определения эквивалентности детерминированных автоматов с магазинной памятью (P346). Так же в предмет теории формальных языков входит изучение бесконечных строк, деревьев и графов. Сделаем некоторые пояснения.

Слово – есть конечная последовательность символов, взятых из некоторого множества символов . Можно говорить о слове в рамках алфавита  или о -слове. Элементы этого множества  называются так же буквами. Общепринятыми обозначениями являются также следующие:

!w! – длина слова w;

w - I-тый символ слова w;

• - пустое слово, единственное слово длины ;

* - множество всех -слов;

Множество* является бесконечным, если  не является пустым, в последнем случае

* = {}.

Множество  называется алфавитом языка. Указанное подмножество множества * называют языком над алфавитом  или -языком. Таким образом в теории формальных языков (F118) под языком понимается просто совокупность строк без всякой связи с их возможной семантикой. (несмотря на существенную роль, которую играют бесконечные языки, их исследование ограничено классом рекурсивно перечислимых языков

Несмотря на существенную роль, которую играют бесконечные языки, их исследование ограничено классом рекурсивно-перечислимых языков (R066). Говорят, что подмножество А множества В является рекурсивно перечислимым по отношению к В, если существует эффективная процедура, которая выдаст для данного элемента b из В положительный ответ тогда и только тогда, когда b является элементом А. Если b не является элементом А, то в общем случае процедура никогда не закончится. Это более слабое понятие, чем рекурсивное множество, т.е. множество определенное общей рекурсивной функцией (R068). Множество может быть рекурсивно перечислимым, не будучи рекурсивным. (Так множество программ на языке АДА, выполнение которых заканчивается для данного входа является рекурсивно перечислимым, по отношению к классу всех программ на языке Ада, но не является рекурсивным.)

Средствами описания формальных языков являются грамматики, автоматы и L-системы.

Начнем с автоматов. Автомат – это общее название устройств, которые осуществляют «механическую» обработку входных цепочек символов с целью определения, принадлежат ли они некоторому множеству цепочек, т.е. формальному языку (F117), или для порождения выходных цепочек символов. В утверждение «автомат А распознает (или воспринимает) язык L» может быть заложен один из двух смыслов:

• для любой входной цепочки символов w автомат А останавливается и указывает, что он принимает или отвергает w, в зависимости от того, выполняется или нет условие wL;

• А восстанавливается, если wL, в противном случае автомат не останавливается.

Абстрактный автомат задается как совокупность таких объектов:

• конечное множество Z={z₁ , z₂ , … z_n} входных сигналов (входной алфавит),

• конечное множество W={w₁ , w₂ , … w_g} выходных сигналов (выходной алфавит),

• произвольного множества A={a₁ , a₂ , … a_m} состояние автомата (алфавит внутренних состояний),

• элемент a₀ множества А, называемого начальным состояния автомата,

• функцией  (a,z) переходов автомата

• функцией  (a,z) выходов автомата.

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

В 30-ых, 40-вых годах XX столетия было дано достаточно много определений понятия алгоритм. Одно из первых было дано английским математиком А.Тьюрингом, который в 1936 году описал схему некоторой гипотетической (абстрактной) машины и предложил называть алгоритмом то, что умеет делать такая машина. По этому определению, то, что не может быть сделано машиной Тьюринга, это уже не алгоритм. Иначе говоря, Тьюринг формализовал правила выполнения действий при помощи описания работы некоторой конструкции.

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

-процедура должна состоять из конечного множества «простых» команд, порядок выполнения которых должен быть определен (т.е. быть программой).

-если были заданы значения х (входные данные) из области определения функции f (данной процедуры), то через конечное число шагов вычисления должны закончиться и дать в результате f(x); если значения не принадлежат области определения f, то процедура не должна приводить к какому-либо результату, т.е. если входные данные не являются данными из области определения, это не должно приводить к ошибке, а эта ситуация должна быть предусмотрена в алгоритме, и просто не должно быть результата, значит алгоритм должен производить контроль входных данных.

За исключением простейших случаев, доказать эффективность (корректность) алгоритма, или даже описать результат действия алгоритма довольно трудно. В таком случае ограничиваются проверкой правильности алгоритма (практической). Такая проверка позволяет удостовериться, что алгоритм обеспечивает выполнение требуемых вычислений. Делается тестирование программы в различных условиях постановки задачи для приобретения уверенности в том, что алгоритм нормально работает во всех контрольных примерах. Если тестовый набор подобран достаточно хорошо, то после проверки можно полагаться на достоверность алгоритма.

В теории алгоритмов существует такая проблема: определить можно ли найти решение данной задачи за конечное число шагов. Это называется вопрос алгоритмической разрешимости задачи. Установлено, что существуют такие классы задач, для решения которых нет и не может быть установлен универсальный прием – алгоритм решения (хотя при определенных ограничениях на данные, решение может быть найдено). Такие задачи называются алгоритмически неразрешимыми.

Алгоритмический процесс должен быть конечным, т.е. за определенное число шагов должен быть получен результат или доказано, алгоритм не применим к данному множеству исходных данных. Значит должна быть доказана применимость или неприменимость алгоритма. Нужно отметить, что в данном случае речь идет не о конкретном, фиксированном, а лишь о конечном числе шагов алгоритмического процесса и об отсутствии препятствий для выполнения каждого шага. Т.е. алгоритм неприменим к определенным исходным данным, если какой-то его шаг по какой-то причине нельзя выполнить, или будет требоваться бесконечное число шагов алгоритма.

Например:

1. Если задан алгоритм перевода неправильной дроби в десятичную. Процесс деления 10 на 3 может продолжаться до бесконечности, значит, стандартный алгоритм не применим, но если поставить задачу иначе и предусмотреть прерывание алгоритма на каком-то шаге, например, выполнение с заданной точностью, то алгоритм будет результативным.

2. Когда алгоритмический процесс обрывается безрезультатно, например, возникает деление на 0. Алгоритм следующий:

   • исходные данные умножить на 3;

   • к полученному результату прибавить 2;

   • определить остаток Х от деления полученной суммы на 4;

   • разделить исходные данные на Х.

Если исходное данное , например, 4к+2, где к=0;1;2;…, то , к примеру при к=2, Х=0 и получаем деление на 0, алгоритм обрывается без результата на п.4 не выполним, т.е. в данном случае алгоритм приводит к результату, если исходные данные определены на множестве вещественных чисел, исключая целые вида 4к+2.

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

Итак, когда решение какой-то задачи может быть достигнуто при использовании какого-то алгоритма, то этот алгоритм называется разрешающим или эффективным алгоритмом.(S222) Термин разрешимость применяется по отношению к функции (предикату) P(x), заданному на множестве натуральных чисел, если его характеристическая функция (C076) C_p является вычислимой (о вычислимости по Тьюрингу позже), причем:

C_p (x)=1, если P(x) выполняется;

C_p (x)=0, если P(x) не выполняется;

Предложенная Тьюрингом машина является полностью абстрактной, и никогда не была реализована (как известно ее и нельзя реализовать это будет ясно при рассмотрении).

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

Исходя из этого Тьюринг искал как можно более простую, бедную алгоритмическую схему, лишь бы она была универсальной. Принципиальное отличие машины Тьюринга от вычислительной машины состоит в том, что ее запоминающее устройство представляет собой бесконечную ленту, тогда как у вычислительной машины может быть очень большое, но уж во всяком случае не бесконечное запоминающее устройство. Машину Тьюринга нельзя реализовать именно из-за ее бесконечной ленты.