Свойства энтропии

1. Как следует из ( 0 .8), E=0 только в том случае, есликакая-либоизp(A_j)=1. Однако, при этом из (1.4 п.1.2.2.) следует, что все остальные

p(A_i)=0 (ij), т.е. реализуется ситуация, когда один из исходов являетсядостоверным(а событие перестает быть случайным). Во всех остальных случаях, очевидно, что E > 0.

2. Из аддитивности неопределенностей следует, что и энтропия, как мера неопределенности, должна обладать аддитивностью, т.е. для двух независимыхопытовAиB

E(AB)=E(A)+E(B) (0.9), т.е.

энтропия сложногоопыта, состоящего из нескольких независимых, равнасуммеэнтропий отдельных опытов.

3. Пусть имеется два опыта с одинаковым числом исходов n, но в одном случае они равновероятны, а в другом – нет. Каково соотношение энтропий опытов?

Примем без доказательства следующее утверждение:

(0.10)

при прочих равных условиях наибольшуюэнтропию имеет опыт сравновероятнымиисходами.

(При необходимости доказательство можно найти, например, в книгах:Яглом А.М., Яглом И.М. [1_11, с.40–43]; Бриллюэн Л.[1_3, с.34–36].)

Другими словами, энтропия максимальнав опытах, где все исходыравновероятны. Здесь усматривается аналогия (имеющая глубинный смысл!) с понятием энтропии, используемой в физике. Впервые понятие энтропии было введено в 1865 г. немецким физиком Рудольфом Клаузиусом как функции состояния термодинамической системы, определяющей направленность самопроизвольных процессов в системе. Клаузиус сформулировалIIначало термодинамики. В частности, он показал, что максимума энтропия достигает при полной разупорядоченности в системе, чему соответствует состояние равновесия. Другими словами, в физике энтропия оказываетсямерой беспорядка в системе. Позднее (в 1872 г.) Людвиг Больцман, развивая статистическую теорию, связал энтропию системы с вероятностью ее состояния, дал статистическое (вероятностное) толкованиеII-му началу термодинамики и, в частности, показал, что вероятность максимальна у полностью разупорядоченной (равновесной) системы, причем, энтропия и термодинамическая вероятность оказались связанными логарифмической зависимостью! Сходство понятий и соотношений между ними в теории информации и статистической термодинамике, как оказалось позднее, имеет глубокий смысл. (Подробнее об этом можно причитать в книгах Л.Бриллюэна [1_3] и Р.Л.Стратоновича [1_8].)

Что дает понятие энтропии для решения практических задач? Рассмотрим одну из них.

Пусть имеются два ящика, в каждом из которых по 12 шаров. В первом– 3 белых, 3 черных и 6 красных;во втором– каждого цвета по 4. Опыты состоят в вытаскивании по одному шару из каждого ящика. Что можно сказать относительно неопределенностей этих опытов? Согласно ( 0 .8) находим энтропии обоих опытов:

Ясно, что E₂>E₁, т.е. во втором опыте неопределенность исхода выше, что, кстати, иллюстрирует справедливость формулы ( 0 .10).

75.1 Подходы к организации эвм. Эвм, управляемые данными. Эвм, управляемые запросами.

15.9. Концепция ВС[выч. систем] с управлением потоком данных

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

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

В таких условиях актуальными являются исследования но­вых путей построения высокопроизводительных ВС, одними из которых являются ВС с управлением потоком данных (опе­рандов), или, другими словами, потоковые ВС.

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

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

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

Следуя(55], рассмотрим в качестве примера вычисле­ние на потоковой ВС корней квадратного уравнения

ах^—Ьх+с=0 (при Ь"—4ас>0;

ж) ,2 ==(Ь ±У^ —4ас)/2а.

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

Процесс решения можно представить следующей последова­тельностью операций:

К0:А\:=2^а,

Kl'•Bl:=b^^[:2(возведение в степень);

K2:C:=i^c,

КЗ;С\:==С^а,

K4:D:=BI-CI,

K5'•DI'.==SQRT(D)(извлечение квадратного корня);

K6:B2:=b+Dl,

K7:B3:=b-D\,

KS:XI:=B2/AI,

К9-.Х2:==ВЗ/А1.

На рис. 15.18 показан граф потока данных, управляющих решением рассматриваемой задачи. Большими кружками обоз­начены операционные устройства, а маленькими — метки го­товности данных. В начальном состоянии процесса готовы все входные данные. Вершины графа активизируются в произвольном порядке при готовности их операндов. Тем не менее в конце концов получается один и тот же результат.

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

Возникает вопрос, как данные и соответствующие команды находят друг друга? Для ответа на него обратимся к рис. 15.19[след.стр.], поясняющему идею процессора, управляемого потоком данных [31, 34]. «Потоковая программа» размещается в массиве ячеек команд. Команда наряду с кодом операции содержит поля, куда заносятся готовые операнды, и поле, содержащее адреса ко­манд, в которые должен быть направлен в качестве операнда результат операции. Кроме того, каждой команде поставлен в соответствие двухразрядный тег (располагаемый в управляю­щем устройстве), разряды которого устанавливаются в 1 при занесении в тело команды соответствующих операндов. В со­стоянии тега 11 (оба операнда готовы) инициируется запрос к операционному коммутатору на передачу готовой команды в соответствующее коду операции (и тегу операнда, определяю­щему тип данных) о щионное устройство. Результат выполнения команды наднепосредственно адресуемыми операндами направляется через командный коммутатор согласно указан­ным в команде адресам в ячейки команд и помещается в их поля операндов. Далее указанная процедура циклически повторяется, причем управление этим процессом полностью децентрализовано и не нуждается в счетчике команд.

75.2 Объектно-ориентированное программирование. Понятие класса, Инкапсуляция. Наследование. Полиморфизм.

Ооп: абстрагирование, инкапсуляция, наследование, полиморфизм.

Объектно-ориентированное программирование (ООП) - парадигма программирования, в которой основными концепциями являются понятия объектов и классов.

Объектно-ориентированное программирование в настоящее время является абсолютным лидером в области прикладного программирования (языки Java, C#, C и др.).

Абстракция данных 

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

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

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

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

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

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

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

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

Примеры блочных кодов: коды Хемминга, коды БЧХ, коды Рида-Соломона.Декодирование сверточных кодов производится, как правило, с помощью алгоритма Витерби.