- •1. Языки программирования. Структурная технология программирования. Реализация основных алгоритмических структур на процедурном языке программирования.
- •2.Базовые алгоритмические структуры: процедуры и функции, рекурсивные функции и процедуры.
- •3.Составные структуры данных: определение новых типов данных, одномерные и двухмерные массивы, строки, множества, записи, файлы.
- •1. Массивы
- •3. Множества
- •4. Записи
- •5. Файлы
- •4. Динамические структуры данных: списки, стеки, очереди.
- •5. Понятие о логическом программировании. Структура программы в Прологе. Предикаты, правила, факты.
- •10) Информация, ее виды и свойства. Измерение информации.
- •11) Кодирование информации. Условие Фано. Коды Шеннона-Фано и Хаффмана.
- •12) Достоверность передачи информации. Коды Хемминга.
- •Кодирование с выявлением ошибок (коды с проверкой на четность).
- •3. Кодирование с исправлением ошибок (самокорректирующиеся коды).
- •13) Понятие о конечных автоматах. Эквивалентность и произведение конечных автоматов.
- •Алгоритмы и их свойства. Существование алгоритмически неразрешимых проблем. Машина Поста.
- •Формализация понятия алгоритма . Машина Тьюринга.
- •Формализация понятия алгоритма. Нормальные алгоритмы Маркова.
- •Формализация понятия алгоритма. Рекурсивные функции.
- •18. Формальная грамматика. Метаязыки. Форма Бэкуса-Наура. Синтаксические диаграммы.
- •Инструментальное программное обеспечение
- •Системы программирования
- •Виды инструментального по
- •Определение
10) Информация, ее виды и свойства. Измерение информации.
Инф-цию наряду с веществом и энергией рассм-ют в качестве важнейшей сущности мира, в кот. мы живем. Но как таково это понятие не определено. В простейшем бытовом понимании с термином "инфц-ия" обычно ассоциир-ся некот-е сведения, данные, знания и т.п. Информация передается в виде сообщений (носитель +код(спец набор некоторых символов алфавита)), опре-дел-их форму и представ-е передав-ой инф-ции. Приме-рами сообщений явл-ся: музыкальное произвед-е; теле-передача; команды регулировщика на перекрестке; текст, т.д. При этом предпол-ся, что имеются "источник инф-ции" и "получатель инф-ции".
Одно сообщ-е несет разную инф-ю для разных людей, т.к. ч-ку свойств-но субъект-е воспр-е инф-и ч/з некот. набор ее св-тв: важность, достовер-ть, своеврем-ность, доступ-ть и т.д. Т.о, инф-ция-интерпретация сообщ-ия.
Потенциальная информация - это разнообразие объекта «самого по себе», это его структура, организация, сложность.
Актуальная («действительная») информация - это разнообразие, переданное (данному) приемнику (или данным приемникам), отраженное им.
Под инф-ей в киберн-ке (науки об общих закономерностях в управлении и связи в различных системах: искусственных, биологических, социальных) поним-ся любая совокуп-ть сиг-налов, кот. некот-я система воспринимает от окруж.среды (входная инф-ция X), вы-дает в окруж.среду (выходная инф-ция Y), а также хранит в себе (внутр-я, внутрисистемая инф-ция Z).
Свойства информации:
запоминаемость;
передаваемость;
преобразуемость;
воспроизводимость;
стираемость
Передаваемость– способность информации к копированию, т.е. к тому, что она может быть «запомнена» другой макроскопической системой и при этом останется тождественной самой себе.
Воспроизв-сть характ-ет неиссяк-сть и неистощимость инф-ции т.е.что при копир-ии инф-ция ост-тся тождеств-й самой себе.
Фундаментальное св-во инф-ции – преобразуем-ть - инф-ция может менять способ и форму существ-я. Копируемость есть разновид-ть преобраз-я инф-ции, при кот. ее кол-во не меняется. В общем случае кол-во инф-ции в проц-сах преобраз-я меняется, но возрастать не может. Св-во стираемости инф-ции также не явл-ся независ-м. Оно связано с таким преобраз-ем инф-ции (передачей), при кот.ее кол-тво уменьш-ся и стан-ся = 0
Чтобы сообщение было передано от источника к получателю, необходима некоторая материальная субстанция – носитель информации. Сообщение, передаваемое с помощью носителя, назовем сигналом. В общем случае сигнал – это изменяющийся во времени физический процесс. Такой процесс может содержать различные хар-ки (например, при передаче электрических сигналов могут изменяться напряжение и сила тока). Та из характеристик, которая используется для представления сообщений, называется параметром сигнала.
В случае, когда пар-р сигнала принимает послед-ное во времени конечное число значений (при этом все они могут быть пронумерованы), сигнал называется дискретным, а сообщение, передаваемое с помощью таких сигналов – дискретным сообщением. Информация, передаваемая источником, в этом случае также называется дискретной. Если же источник вырабатывает непрерывное сообщение (соответ. пар-р сигнала – непрерывная фун-я от времени), соотв-щая информация называется непрерывной. Пример дискретного сообщения – процесс чтения книги, информация в которой представлена текстом, т.е. дискретной последовательностью отдельных значков (букв). Примером непрерывного сообщения служит человеческая речь, передаваемая модулированной звуковой волной; параметром сигнала в этом случае является давление, создаваемое этой волной в точке нахождения приемника – человеческого уха.
Соответствие между сообщением и содержащейся в нем информацией называется правилом интерпретации сообщения.
α
N I , α – правило интерпретации (язык), N – сообщение, I – информация.
Измерение информации
Кибернетический подход (вероятностный)
Объемный подход
Вероятностный подход
Основой вероятностного подхода к оценке количества информации является понятие энтропии – меры неопределенности наших знаний о состоянии некоторой системы. Энтропия тем больше, чем больше множество возможных исходов. В свою очередь исходы характеризуются вероятностью их появления - частостью появления каждого исхода в большом количестве повторений опыта.
Вероятность и энтропия связаны логарифмической зависимостью: Н = - Log 2 P
Разность величин неопределенности состояния системы до опыта H’ и после опыта H характеризует полученную нами информацию I(Х): I(Х) = Н – Н’
Т.о, информация есть уменьшение энтропии системы в результате получения некоторых сведений о ней.
Часто до опыта Н’=0, и принято считать, что энтропия отождествляется кол-ву информации.
Согласно развитой теории, в случае равновероятных N событий энтропия H вычисляется по формуле Хартли H = log2 N (где N - число равновероятных исходов (событий)).
За единицу измерения количества информации принят 1 бит, количество информации получаемое при выборе одного из двух равновероятных исходов опыта :
log22=1 (бит)
Таким образом, количество информации измеряется в двоичных единицах - битах.
В
случае, когда вероятности Pi N событий
неодинаковы, имеет место формула
Шеннона
,
где N
– количество возможных символов в
сообщении (исходов опыта). Pi
– вероятность появления определенной
буквы (исхода).
В
случае равновероятных событий
,
формула Шеннона переходит в формулу
Хартли.
Объемный подход.
Объем данных в сообщении измеряется кол-вом символов (разрядов) в этом сообщении. В различных системах счисления один разряд имеет различный вес и соответственно меняется единица измерения данных: в двоичной системе счисления единица измерения - бит;
8 бит = 1 байт
1024 Б = 1 килобайт
1024 К = 1 мегабайт
1024 М = 1 гигабайт
