Информация, представленная в формализованном виде, пригодном для автоматизированной обработки, называется данными.
Человек получает информацию из окружающего мира с помощью органов чувств, анализирует ее и выявляет существенные закономерности с помощью мышления, хранит полученную информацию в памяти. Процесс систематического научного познания окружающего мира приводит к накоплению информации в форме знаний (фактов, научных теорий и т.д.), таким образом, с точки зрения процесса познания информация может рассматриваться как знания.
Формула Шеннона. Информацию, которую получает человек, можно считать мерой уменьшения неопределенности знаний. Подход к информации как к мере уменьшения неопределенности знаний позволяет количественно измерять информацию. Формулу для вычисления количества информации в случае различных вероятностных событий предложил К. Шеннон в 1948 г. Исследуя проблему рациональной передачи информации через зашумленный коммуникационный канал, К. Шеннон предложил революционный вероятностный подход к пониманию коммуникаций и создал первую, истинно математическую, теорию энтропии. Его сенсационные идеи быстро послужили основой для разработки двух основных направлений: теории информации, которая использует понятие вероятности и эргодическую теорию для изучения статистических характеристик данных и коммуникационных систем, и теории кодирования, в которой применяются главным образом алгебраические и геометрические инструменты для разработки эффективных кодов.
Существует множество ситуаций, когда возможные события имеют различные вероятности реализации. Например, если монета несимметрична (одна сторона тяжелее другой), то при ее бросании вероятности выпадения орла и решки будут различаться. В этом случае количество информации определяется по формуле
где I – количество информации;
N – количество возможных событий;
pi – вероятность i-го события.
Например, пусть при бросании несимметричной четырехгранной пирамидки вероятности отдельных событий будут следующими: р1 = 1/2, р2 = 1/4, р3 = 1/8, р4 = 1/8.
Тогда количество информации, которое мы получим после реализации одного из них, можно рассчитать по формуле
I = (1/2 log21/2 + 1/4 log21/4 + 1/8 log21/8 + 1/8 log21/8) = (1/2 + 2/4 + 3/8 + 3/8) бит = 14/8 бит = 1,75 бита.
Этот подход к определению количества информации называется вероятностным.
Количество информации, которое мы получаем, достигает максимального значения, если события равновероятны.
Понятие энтропии как меры случайности введено Шенноном в его статье «A Mathematical Theory of Communication», опубликованной в двух номерах Bell System Technical Journal в 1948 г.
Информационная энтропия – мера хаотичности информации, неопределенность появления какого-либо символа первичного алфавита. При отсутствии информационных потерь информационная энтропия численно равна количеству информации на символ передаваемого сообщения.
Например, в последовательности букв, составляющих какое-либо предложение на русском языке, различные буквы появляются с разной частотой, поэтому неопределенность появления для некоторых букв меньше, чем для других. Если же учесть, что некоторые сочетания букв (в этом случае говорят об энтропии n-го порядка) встречаются очень редко, то неопределенность еще более уменьшается.
Энтропия – это количество информации, приходящейся на одно элементарное сообщение источника, вырабатывающего статистически независимые сообщения.
Определение энтропии Шеннона связано с понятием термодинамической энтропии. Больцман и Гиббс проделали большую работу в области статистической термодинамики, которая способствовала принятию термина «энтропия» в информационной теории. Существует связь между термодинамической и информационной энтропией.
Структура данных
Структура данных определяет их семантику, а также способы организации данных и управления ими. При использовании компьютера для хранения и обработки данных необходимо точно определить тип и структуру данных, а также найти способ наиболее естественного их представления. Компьютер оперирует только с одним видом данных – с отдельными битами, или двоичными цифрами, – и работает с этими данными в соответствии с неизменным набором алгоритмов, которые определяются системой команд центрального процессора. Структура данных, рассматриваемая без учета ее представления в машинной памяти, называется абстрактной, или логической.
Понятие «физическая структура данных» отражает способ физического представления данных в машинной памяти.
Структуры данных, применяемые в алгоритмах, могут быть очень сложными. Под структурой данных в общем случае понимают множество элементов данных и множество связей между ними.
Различают простые (базовые, примитивные) структуры (типы) данных и интегрированные (структурированные, композитные, сложные). Простыми называются такие структуры данных, которые не могут быть расчленены на составные части.
Интегрированными называются такие структуры данных, составными частями которых являются другие структуры данных – простые или, в свою очередь, интегрированные (Гагарина Л.Г., Колдаев В.Д. Алгоритмы и структуры данных: учеб. пособие. М., 2009.).
Важный признак структуры данных – ее изменчивость, т.е. изменение числа элементов и/или связей между элементами структуры. По признаку изменчивости различают следующие структуры:
– простые базовые структуры:
– числовые;
– символьные;
– логические;
– перечисление;
– интервал;
– указатели;
– статические структуры:
– вектор;
– массивы;
– множества;
– записи;
– таблицы;
– полустатические структуры:
– стеки;
– очереди;
– деки;
– строки;
– динамические структуры:
– линейные связные списки;
– разветвленные связные списки;
– графы;
– деревья;
– файловые структуры:
– последовательные;
– прямого доступа;
– комбинированного доступа;
– организованные разделами.
Другой важный признак структуры данных – характер упорядоченности ее элементов.
Структуры данных могут быть линейными и нелинейными. Линейные структуры данных – это те, в которых связи между элементами не зависят от выполнения какого-либо условия (картезианские, строчные, списковые).
Нелинейные структуры данных – это структуры данных, у которых связи между элементами зависят от выполнения определенного условия (деревья, графы, многосвязные списки).
Древовидные структуры – это иерархические структуры, состоящие из вершин и ребер, каждая вершина содержит определенную информацию и ссылку на вершину нижнего уровня.
Графы представляют собой совокупность двух множеств: вершин и ребер. Граф – это сложнейшая нелинейная многосвязная динамическая структура, отображающая свойства и связи сложного объекта.
Модели объектов
При изучении информатики часто необходимо объединять сходные по свойствам сущности (объекты) в различные группы (классы) в зависимости от того, обладают ли они какими-либо общими признаками или свойствами, т. е. можно классифицировать однотипные данные в соответствии с выделенными свойствами, признаками, классами.
Развитие науки невозможно без создания теоретических моделей (теорий, законов, гипотез и пр.), отражающих строение, свойства и поведение реальных объектов. Соответствие теоретических моделей законам реального мира проверяется с помощью опытов и экспериментов. Примеры теоретических моделей: гелиоцентрическая система мира Коперника, модель атома Резерфорда-Бора, модель расширяющейся вселенной, модель генома человека и т.д.
Может оказаться, что у объектов несколько общих свойств, независимых друг от друга, тогда их можно распределить по разным классификационным признакам, т.е. проявляется множественность классификаций для одной и той же группы объектов.
Любая классификация начинается с выделения общих свойств (признаков). Представлена классификация может быть в графической (в виде графов) и в текстовой форме (в виде таблиц или списков).
Объект – простейшая составляющая сложного объединения, обладающая следующими качествами:
– в рамках данной задачи он не имеет внутреннего устройства и рассматривается как единое целое;
– у него имеется набор свойств (атрибутов), которые изменяются в результате внешних воздействий;
– он идентифицирован, т.е. имеет имя (название).
Класс – это множество объектов, обладающих одним или несколькими атрибутами; эти атрибуты называются полем свойств классов.
Система – совокупность взаимодействующих компонентов, каждый из которых в отдельности не обладает свойствами системы в целом, но является ее неотъемлемой частью.
Модель – упрощенное представление о реальном объекте, процессе или явлении.
Моделирование – процесс построения моделей для изучения и исследования объектов, процессов или явлений. Можно моделировать оригинал (прототип) в зависимости от поставленных условий задачи. Моделирование – это метод познания, состоящий в создании и исследовании моделей. Итак, модель – это некий новый объект, который отражает особенности изучаемого объекта, явления или процесса.
Все модели можно разбить на два больших класса: предметные (материальные) и информационные. Предметные модели воспроизводят геометрические, физические и другие свойства объекта в материальной форме (глобус, муляжи, макеты зданий и пр.)- Информационные модели представляют объекты и процессы в образной (рисунки, фотографии и др.) или знаковой форме. Знаковые информационные модели строятся с помощью различных языков (знаковых систем).
Состояние прототипа – это совокупность свойств его составных частей, а также его собственных. Состояние – моментальная фотография прототипа для выбранного момента времени, с течением времени состояние может меняться, тогда говорят о существовании процесса. Различают модели состояния –-структурные модели (чертеж, схема, блок-схема алгоритма) – и модели процессов – функциональные модели (макет, демонстрирующий работу чего-либо).
Имитационное моделирование – метод исследования, основанный на том, что изучаемый прототип заменяется его имитатором (натурной или информационной моделью), с которым и проводятся эксперименты с целью получения информации об особенностях прототипа. В качестве имитатора могут выступать и математические модели, реализованные на компьютере. В настоящее время имитационное моделирование является важнейшим методом исследования и прогнозирования в науке (прогноз погоды, экономические прогнозы и т.д.).
Типы моделей:
– предметные (натурные):
– подобия;
– тренажеры;
– эрзацы;
– информационные:
– непрерывные;
– знаковые.
Примерами натурных моделей подобия являются игрушка, манекен, фотография и т.п. Модели-эрзацы – протезы, заменяющие настоящие органы и частично выполняющие функции последних. Материальные модели – предметные, физические.
Информационные модели – совокупность информации, характеризующая свойства и состояние объекта, процесса, явления, а также его взаимосвязь с внешним миром. Информационные модели подразделяются на знаковые (дискретные, представленные посредством некоторого алфавита и языка) и непрерывные (например, математическая функция и ее график).
Формализованные языки имеют фиксированный набор лексических единиц (слов) и жесткий синтаксис фраз. Этим обеспечивается однозначность понимания смысла фраз и исполнения содержащихся в них указаний. Примером моделей, представленных посредством формализованных языков, может служить математическое описание существующих в природе или человеческом обществе явления, процесса (запись шахматной партии, нотная запись звуков и т.д.).
Построение знаковой модели является обязательным этапом решения практической задачи с помощью компьютера. В дальнейшем, говоря о моделях в информатике, будем подразумевать именно информационные знаковые модели.
Классификация моделей
Признаки, по которым классифицируются модели:
– область использования;
– учет в модели временного фактора;
– отрасль знаний;
– способ представления моделей.
Классификация по области использования:
– учебные модели – наглядные пособия, различные тренажеры, обучающие программы;
– научно-технические модели (создаются для исследования процессов и явлений);
– игровые модели – военные, экономические, спортивные и деловые игры;
– имитационные модели – не просто отражают реальность, а имитируют ее. Эксперимент либо многократно повторяется, либо проводится одновременно со многими другими похожими объектами, но поставленными в разные условия.
В классификации с учетом реального времени модели разделяются на:
– статические (одномоментный срез информации по объекту);
– динамические (позволяющие увидеть изменения объекта во времени).
Классификация по способу представления:
– вербальная модель – информационная модель в мысленной или разговорной форме (идея, возникающая у изобретателя; музыкальная тема; рифма, прозвучавшая в сознании автора, и т.д.);
– знаковая модель – информационная модель, выраженная специальными знаками, т.е. средствами любого формального языка (рисунки, тексты, графики, схемы).
По форме представления можно выделить следующие виды информационных моделей:
– геометрические – графические формы и объемные конструкции;
– математические – математические формулы, отображающие различные параметры объекта или процесса;
– словесные – устные или письменные описания с использованием иллюстраций;
– структурные – схемы, графики, таблицы;
– логические – модели, в которых представлены различные варианты выбора действий на основе умозаключений и анализа условий;
– специальные – ноты, химические знаки;
– компьютерные и некомпьютерные.
Этапы моделирования:
1. Постановка задачи. Описание задачи. Определение целей моделирования. Анализ объекта моделирования.
2. Разработка модели. Формирование представления об элементарных объектах.
3. Выбор наиболее существенной информации при создании информационной модели.
4. Компьютерный эксперимент. Тестирование. Проверка правильности модели.
5. Анализ результатов моделирования. Принятие решения, которое должно быть выработано на основе всестороннего анализа полученных результатов.
6. Принятие решений. Достижение конечной пели моделирования.