 |
|
Информационные модели. Объекты информации. Дискретное представление информации.
Информационная модель — модель объекта, представленная в виде информации, описывающей существенные для данного рассмотрения параметры и переменные величины объекта, связи между ними, входы и выходы объекта и позволяющая путём подачи на модель информации об изменениях входных величин моделировать возможные состояния объекта. Информационные модели нельзя потрогать или увидеть, они не имеют материального воплощения, потому что строятся только на информации. Информационная модель — совокупность информации, характеризующая существенные свойства и состояния объекта, процесса, явления, а также взаимосвязь с внешним миром.
Информационные модели делятся на:
Описательные информационные модели - это модели, созданные на естественном языке (т.е. на любом языке общения между людьми: английском, русском, китайском и т.п.) в устной или письменной форме.
Формальные информационные модели - это модели, созданные на формальном языке (т.е. научном, профессиональном или специализированном). Примеры: формулы, таблицы, карты, графы, схемы и т.д.
Объект информации - это объективно существующий результат информационной деятельности, информационный продукт. Информационный продукт – совокупность данных, сформированная производителем для реального или потенциального распространения. Объекты информации – это какие-либо документы и ресурсы. Все объекты информации существуют на определенных носителях. Носители информации дают возможность ее записывать, хранить и распространять. Человечество прошло долгий путь развития носителей информации. Сначала это был камень (стены пещер, каменные стелы, отдельные камни и т.д.), глина (глиняные таблички, черепки керамических сосудов – остраконы), реже – металл, дерево и пр. Большой шаг вперед был сделан с началом применения материалов-предшественников бумаги – папируса, затем пергамена (слово «пергамен» в качестве обозначения писчего материала правильнее, чем «пергамент»). Подлинную революцию носителей информации произвело открытие и распространение бумаги. Началась эра бумажных носителей информации. Хотя бумажные носители по-прежнему очень распространены, в эру бурного развития вычислительной техники и телекоммуникаций огромное значение приобрели оптические, магнитные, магнитно-оптические носители информации (CD, DVD, HDD, винчестеры, флэш-носители и т. д.). Немалое значение имеют и различные фото- и киноматериалы.
В компьютере для представления информации используется двоичное кодирование, так как удалось создать надежно работающие технические устройства, которые могут со стопроцентной надежностью сохранять и распознавать не более двух различных состояний (цифр): электромагнитные реле (замкнуто/разомкнуто); участок поверхности магнитного носителя информации (намагничен/размагничен); участок поверхности лазерного диска (отражает/не отражает); триггер (может устойчиво находиться в одном из двух состояний, поэтому широко используется в оперативной памяти компьютера). Все виды информации в компьютере кодируются на машинном языке, в виде логических последовательностей нулей и единиц. Цифры двоичного кода можно рассматривать как два равновероятных состояния (события). При записи двоичной цифры реализуется выбор одного из двух возможных состояний (одной из двух цифр) и, следовательно, она несет количество информации, равное 1 биту. Даже сама единица измерения количества информации бит (bit) получила свое название от английского словосочетания BInary digiT (двоичная цифра). Важно, что каждая цифра машинного двоичного кода несет информацию в 1 бит. Таким образом, две цифры несут информацию в 2 бита, три цифры — в 3 бита и так далее. Количество информации в битах равно количеству цифр двоичного машинного кода.
5. Определение алгоритма. Виды алгоритмов. Свойства алгоритмов.
Алгоритм – это конечная последовательность указаний на языке понятном исполнителю, задающая процесс решения задач определенного типа и ведущая к получению результата, однозначно определяемого допустимыми исходными данными.
Виды алгоритмов:
- Линейный(набор команд (указаний), выполняемых последовательно во времени друг за другом);
- Разветвляющий(алгоритм, содержащий хотя бы одно условие, в результате проверки которого ЭВМ обеспечивает переход на один из двух возможных шагов);
- Циклический(алгоритм, предусматривающий многократное повторение одного и того же действия (одних и тех же операций) над новыми исходными данными);
Свойства алгоритма:
- Дискретность(в данном случае, разделенность на части) и упорядоченность
Алгоритм должен состоять из отдельных действий, которые выполняются последовательно друг за другом.
- Детерминированность (однозначная определенность)
Многократное применение одного алгоритма к одному и тому же набору исходных данных всегда дает один и тот же результат.
- Формальность
Алгоритм не должен допускать неоднозначности толкования действий для исполнителя.
- Результативность и конечность
Работа алгоритма должна завершаться за определенное число шагов, при этом задача должна быть решена.
- Массовость
Определенный алгоритм должен быть применим ко всем однотипным задачам.
6. Основные алгоритмические структуры. Блок-схемы алгоритмов.
В рамках структурного программирования задачи, имеющие алгоритмическое решение, могут быть описаны с использованием следующих алгоритмических структур:
Следование. Предполагает последовательное выполнение команд сверху вниз. Если алгоритм состоит только из структур следования, то он является линейным.
Ветвление. Выполнение программы идет по одной из двух, нескольких или множества ветвей. Выбор ветви зависит от условия на входе ветвления и поступивших сюда данных.
Цикл. Предполагает возможность многократного повторения определенных действий. Количество повторений зависит от условия цикла.
Функция (подпрограмма). Команды, отделенные от основной программы, выполняются лишь в случае их вызова из основной программы (из любого ее места). Одна и та же функция может вызываться из основной программы сколь угодно раз.
Алгоритм можно описать разными способами: словами, на языке программирования, а также с помощью блок-схем.
На языке блок-схем каждый шаг алгоритма описывается с помощью соответствующей фигуры, а последовательность выполнения шагов определяется линиями-связями. Блок схемы читаются сверху вниз и слева направо. Блок-схемы полезны тем, что обеспечивают легкую «читаемость» алгоритма. Однако это не всегда так: стоит попытаться нарисовать блок-схему для более-менее сложного алгоритма, как она разрастается до невероятных размеров и теряет все свое наглядное преимущество. Поэтому блок-схемы хороши в структурном программировании для описания коротких алгоритмов.
Язык блок-схем прост (хотя существуют его расширенные варианты):
Прямоугольник – выполнение действия (например, c = a + b)
Ромб – проверка условия (например, a > b). Если условие выполняется, то алгоритм идет по линии «да», если не выполняется – то по линии «нет».
Скругленный прямоугольник – начало и конец алгоритма
Скошенный прямоугольник – ввод-вывод данных (например, получение значения переменной, вывод результата на экран монитора).
7. Абстрактная машина Тьюринга. Алгоритмы Маркова.
В 1936 г. Аланом Тьюрингом для уточнения понятия алгоритма был предложен абстрактный универсальный исполнитель. Его абстрактность заключается в том, что он представляет собой логическую вычислительную конструкцию, а не реальную вычислительную машину. Термин «универсальный исполнитель» говорит о том, что данный исполнитель может имитировать любой другой исполнитель. Например, операции, которые выполняют реальные вычислительные машины можно имитировать на универсальном исполнителе. В последствие, придуманная Тьюрингом вычислительная конструкция была названа машиной Тьюринга. Машина Тьюринга состоит из бесконечной в обе стороны ленты, разделенной на ячейки, и автомата (головки), которая управляется программой.
Программы для машин Тьюринга записываются в виде таблицы, где первые столбец и строка содержат буквы внешнего алфавита и возможные внутренние состояния автомата (внутренний алфавит). Содержимое таблицы представляет собой команды для машины Тьюринга. Буква, которую считывает головка в ячейке (над которой она находится в данный момент), и внутренне состояние головки определяют, какую команду нужно выполнить. Команда определяется пересечением символов внешнего и внутреннего алфавитов в таблице.
Автомат машины Тьюринга в процессе своей работы может выполнять следующие действия:
- Записывать символ внешнего алфавита в ячейку (в том числе и пустой), заменяя находившийся в ней (в том числе и пустой).
- Передвигаться на одну ячейку влево или вправо.
- Менять свое внутреннее состояние.
В середине прошлого века выдающийся русский математик А.А. Марков ввел понятие нормального алгоритма (алгорифма) с целью уточнения понятия "алгоритм". Идеи алгоритмов маркова положены в основу большой группы языков программирования, получивших название языки логического программирования. Для определения нормального алгоритма Маркова вводится произвольный алфавит - конечное непустое множество символов, при помощи которых описывается алгоритм и данные. В алфавит также включается пустой символ, который мы будем обозначать греческой буквой λ. Под словом понимается любая последовательность непустых символов алфавита либо пустой символ, который обозначает пустое слово. Всякий НАМ определяется конечным упорядоченным множеством пар слов алфавита, называемых подстановками . В паре слов подстановки левое (первое) слово непустое, а правое (второе) слово может быть пустым символом. Для наглядности левое и правое слово разделяются стрелкой. Например,
В качестве данных алгоритма берется любая непустая строка символов. Работа НАМ состоит из последовательности совершенно однотипных шагов. Шаг работы алгоритма может быть описан следующим образом:
В упорядоченной последовательности подстановок ищем самую первую подстановку, левое слово которой входит в строку данных.
В строке данных ищем самое первое (левое) вхождение левого слова найденной подстановки.
Это вхождение в строке данных заменяем на правое слово найденной подстановки (преобразование данных).
Шаг работы алгоритма повторяется до тех пор, пока
- либо не возникнет ситуация, когда шаг не сможет быть выполнен из-за того, что ни одна подстановка не подходит ( левое слово любой подстановки уже не входит в строку данных ) - правило остановки;
- либо не будет установлено, что процесс подстановок не может остановиться.
В первом случае строка данных, получившаяся при остановке алгоритма, является выходной (результатом) и алгоритм применим к входным данным, а во втором случае алгоритм не применим к входным данным.