1

Обмен (прием или передача), обработка и хранение информации — одна из самых важных сторон жизнедеятельности любых живых организмов

Носитель информации — любая материальная среда, служащая для ее хранения или передачи

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

Тема 1. Роль информации в живой природе, жизни человека и общественном развитии.

Технологией называется совокупность знаний о способах и средствах проведения производственных процессов, при которых происходит необходимое качественное изменение обрабатываемых объектов (techno ─ мастерство, log ─ учение, то есть учение о мастерстве, мастерство ─ искусство делать вещи) .

Арифмометр Лейбница

1500 г., Леонардо да Винчи, эскиз суммирующего устройства
1623 г., Вильгельм Шиккард, действующее суммирующее устройство
1641–1645 г.г., Блез Паскаль, суммирующая машина
1671–1674 г.г., Готфрид Лейбниц, арифмометр

Арифмометр В.Т. Однера XIX века и его потомок середины XX века арифмометр «Феликс М»

1801–1808г.г., Жозеф Жаккард, автоматический ткацкий станок
1822 г. Чарльз Бэббидж, описание «разностной» машины
1834 г., Чарльз Бэббидж, эскиз «аналитической» машины
1843 г., Ада Лавлейс, основы программирования, первая в мире программа для аналитической машины Беббиджа (расчет чисел Фиббоначи)
1887 г., Герман Холлерит, первый табулятор
1897 г., Герман Холлерит, основание фирмы Tabulating Machine Company, впоследствии IBM (International Business Machines)

Программа представляет собой план выполнения действий, записанный в специальной, понятной исполнителю действий форме.

Развитие средств механизации и автоматизации обработки информации (с начала XVI века).

Фрагмент машины «Марк-1»

Электромагнитное реле
(принципиальная схема)

Электронная лампа накаливания

Машина ЭНИАК

Лампа накаливания Транзисторы Интегральные схемы

Переход человеческой цивилизации в информационный этап развития (конец XX — начало XXI века)

Базовые понятия информатики:

Информация.
Информационная (математическая) модель.
Алгоритм.
Электронная вычислительная машина (компьютер).

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

К области прикладной информатики относятся следующие разделы и дисциплины:

архитектура компьютеров;
операционные системы;
языки программирования и методы трансляции;
технологии программирования;
информационные системы и технологии;

Информация есть объективное отражение реального мира, атрибут материи, отображающий ее структуру. Эволюционный ряд познания материи, природы, форм проявления материи: вещество — энергия — информация

Общепринятое понятие информации:

Философское понятие информации:

Основоположник кибернетики Норберт Винер говорил об информации так: «Информация есть информация, а не материя и не энергия». То есть, по его мнению, информация относится к фундаментальным понятиям, которые не сводятся к каким-либо другим.

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

В математике и в других науках существуют такие понятия, дать строгое определение которым принципиально невозможно. К ним относятся, например, понятия «множество», «точка» и некоторые другие. Любая попытка каким-либо образом определить их сведется к использованию синонимов, которые в свою очередь окажутся неопределёнными.

В рамках предмета информатика предлагается опираться на следующее объяснение, трактовку понятия информация:

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

В соответствии с приведённой выше трактовкой информации как «отображения в сознании человека» для её появления необходим субъект, получающий информацию — получатель информации.

Очевидно, должен существовать также объект или субъект, передающий её — источник информации. Следует заметить, что источник и получатель информации могут совпадать.

Получателем информации может быть только субъект — одушевлённая сущность — человек. А вот источником информации может быть как субъект, так и любой объект — неодушевленная сущность — техническое устройство, природный или искусственный объект, явление.

Рассматривать случай одновременного нахождения источника и получателя информации в одной и той же точке пространства бессмысленно.

Если имеется разделение во времени, то необходимо организовать хранение информации, а если имеется разделение в пространстве, то её передачу.

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

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

Кроме того, при передаче информации её носитель должен переместиться в пространстве из точки передачи в точку приёма через некоторую материальную среду, которую принято называть каналом связи.

Результатом такого контакта является осознание, выявление человеком смысла принятой информации. Например, один человек слышит произнесённые другим человеком слова и понимает, где и когда должна произойти встреча.

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

Из сказанного выше вытекает, что информация существует только в сознании её получателя и только в процессе её получения, её осознания, выявления её смысла.

Спустя некоторое время принятая информация либо безвозвратно теряется (человек забывает полученные сведения), либо переходит в его знания

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

Итак, выявлены следующие основные аспекты информации:

материальное представление информации в виде носителя, который используется для её хранения и передачи, а также в процессе обработки;
происходящее в сознании человека субъективное, нематериальное понимание, которое включает в себя:

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

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

В теории информации такое отделение основано на использовании дополнительного неопределяемого понятия «сообщение». Это создаёт возможность все материальные аспекты связывать с понятием «сообщение», а все субъективные — с понятием «информация».

Сообщение — это конкретная материальная форма представления информации

Информация — это абстрактный, нематериальный смысл, извлекаемый человеком из сообщения.

Сообщение — материальный носитель информации, информация — нематериальное содержание, смысл сообщения. Сообщение всегда конкретно и материально, информация абстрактна и нематериальна.

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

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

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

Использование понятий «сообщение» и «информация» позволяет строгими научными методами изучать объективные свойства сообщений, совершенно не затрагивая при этом принципиально субъективные аспекты информации

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

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

Термин «данные» в естественных и технических науках имеет используемый точный смысл:

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

Формализованным называется представление, подчиняющееся точно сформулированной, исчерпывающе полной системе правил

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

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

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

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

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

Это значит, что сообщение может быть без потери его смысла, то есть без потери заключенной в нём информации, представлено, зашифровано, закодировано разными способами.

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

В связи с выявленной неоднозначность возникает вопрос о способе, качестве и полноте извлечения информации из сообщения.

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

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

П р и х о д и н е м е д л е н н о

Пример сообщения:

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

использованное правило интерпретации сообщения

Язык интерпретации сообщений

Множество правил

Множество сообщений

Тройка множеств

называется информационной системой

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

Свойства информации:

Объективность
Полнота
Достоверность
Адекватность
Доступность
Актуальность

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

Достоверность — это свойство информации не иметь скрытых ошибок, то есть искажений, о которых получателю ничего не известно.

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

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

Действия над сообщениями

Основные операции:
передача
прием
обработка
xранение

Дополнительные операции :
сбор
формализация
фильтрация
сортировка
архивация
защита

Формализация сообщений представляет собой их приведение к некоторой единой форме для обеспечения возможности сопоставления различных сообщений.

Фильтрация сообщений — это отсеивание помех, шумов, ненужных или пустых сообщений, что повышает их адекватность и достоверность,

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

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

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

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

Передача сообщения всегда связана с необходимостью изменить носитель во времени или в пространстве, Изменение носителя можно понимать как любое изменение его состояния, то есть любое изменение его свойств, характеристик.

Отсюда следует, что передача сообщений с помощью носителя с неизменяющимися свойствами невозможна.

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

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

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

Под состоянием объекта, явления понимается некоторый набор его свойств, характеристик, значений параметров, которые, собственно говоря, и определяют состояние, жёстко связаны с ним.

Например, можно рассматривать следующие состояния человека: «стоит», «идёт», «бежит». Они отличаются друг от друга разными значениями одного параметра скорость тела.

Постоянное, неизменное значение параметра скорость тела или же его изменение в определённых границах означает, что текущее состояние человека не меняется. А изменение скорости с выходом за установленные границы приводит к переходу из одного состояния в другое.

Процессом (лат. processus — продвижение) называется последовательная смена состояний наблюдаемого объекта или явления во времени.

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

Информационным процессом называется изменение со временем содержания информации или представляющего информацию сообщения. К информационным процессам относятся, например, приём, передача и обработка сообщений.

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

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

Можно также выделить группы дискретных и непрерывных процессов.

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

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

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

Дискретное время представляет собой конечную или счётную последовательность временных отсчётов t∈{0, 1, 2,…}, в которые происходит переход дискретного процесса из одного состояния в другое, с ненулевыми промежутками времени между ними.

Моменты времени , в которые заданы или измерены значения параметра сигнала, принято называть отсчётами.

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

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

Для отдельных состояний непрерывных процессов можно говорить только о порядке их следования во времени — предшествующее или последующее состояние. Всегда можно найти два последовательных состояния процесса, которое отделены друга от друга сколь угодно маленьким временным отрезком.

Множество различных состояний непрерывного процесса несчётно (имеет мощность континуума).

Непрерывные процессы происходят в непрерывном времени, которое совпадает с физическим временем.

Изменение во времени значений параметра сигнала A естественно рассматривать как процесс, при этом значения функции f(t) в выбранные моменты времени являются его временными состояниями. Этот процесс может быть непрерывным или дискретным.

Это значит, что значения сигнала A=f(t) могут быть заданы в непрерывном времени, то есть в любой момент времени t из области его определения T0≤ t ≤TN (непрерывный процесс) либо в дискретном времени, то есть только в некоторые выбранные моменты времени t0,t1,…,tN (дискретный процесс).

В первом случае сигнал называется непрерывным, а в втором ̶ дискретным.

Понятия непрерывности и дискретности процесса связаны с множеством, к которому принадлежит аргумент функции . Естественно распространить эти понятия и на множество значений параметра сигнала.

Так, если параметр сигнала A принимает любые значения из некоторого интервала Amin≤A≤Amax, то есть множество E его значений несчётно, то этот сигнал можно рассматривать как непрерывный по значению.

Если все значения параметра A принадлежат конечному множеству E={A0,A1,…AM} — такой сигнал естественно считать дискретным по значению.

непрерывный и по времени и по значению;
дискретный по времени и непрерывный по значениям;
непрерывный по времени, но дискретный по значениям;
дискретный и по времени и по значениям.

Сообщения, основанные на непрерывных сигналах называются непрерывными, сообщения, основанные на дискретных сигналах, называются дискретными.

Информация не обладает ни свойством непрерывности, ни свойством дискретности

Но слуховая система человека способна различать только 512 различных уровней громкости и 2048 различных уровней высоты звука.

Это означает, что любой звуковой сигнал после его приёма и обработки органами слуха человека фактически становится дискретным по значению параметра сообщением. Аналогичными свойствами «естественной дискретности» обладают и другие органы чувств человека.

Однако у органов чувств человека имеются и противоположные свойства, которые приводят к тому, что фактически дискретные сообщения воспринимаются им как непрерывные.

Например, на неспособности зрительной системы человека различать более 24-x последовательно сменяемых в течение одной секунды изображений одного и того же объекта основано кино. Если изображения предъявлять со скоростью, например, 20 кадров в секунду, то они будут восприниматься сознанием человека как отдельные быстросменяемые кадры, а если со скоростью 24 или более — как одно непрерывное, которое создает в сознании впечатление естественного движения объектов съемки.

Остальные преобразования могут быть выполнены без потери информации

Преобразования вида D1→D2 фактически являются разновидностью обработки дискретных сообщений. Эти преобразования в зависимости от используемого способа могут быть проведены как с потерей, так и без потери информации.

Преобразование N1→N2 всегда сопровождается потерей информации. Это принципиальное и неустранимое обстоятельство, вытекающее из самой природы непрерывных сообщений.

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

Развертка сигнала по времени

Квантование сигнала по уровню

Увеличивая значения N и K можно уменьшить потерю информации. Но возможно ли осуществить дискретизацию вообще без её потери?

где ak, ωk и φk — амплитуда, круговая частота и фаза k-ой синусоиды.

Переход от исходной функции к её представлению в виде такой суммы принято назвать преобразованием Фурье, а отдельные слагаемые — гармониками.

Теория рядов Фурье является важным инструментом для решения задач, связанных с преобразованиями сообщений вида D→N. Дело в том, что параметры гармоник (синусоид) — коэффициенты ak и φk находятся по вычисленным или измеренным дискретным отсчётам сигнала с помощью довольно простых соотношений, а частоты ωk однозначно связаны с периодом или длительностью сигнала T – ωk=k× ω1 , ω1=2π/T.,,

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

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

В общем случае суммы в разложении Фурье содержат счётное количество слагаемых, но во многих практически важных частных случаях их количество оказывается конечным и, следовательно, ограниченным. Например, речь человека не содержит частот больших, чем fmax =4000 герц.

Сигналы, создаваемые любыми реальными техническими устройствами, также имеют ограниченный набор гармоник, то есть существует конечная частота fmax такая, что все ωk≤ωmax.

Теорема В.А. Котельникова дает рекомендации по выбору необходимого количества отсчётов для выполнения развёртки сигнала во времени. Но для полной дискретизации необходимо выполнить ещё и квантование сигнала по уровню.

Например, для точной передачи речевого сигнала с максимальной частотой 4 000 Гц при его развертке следует выбрать частоту дискретизации не менее 8 000 отсчётов в секунду (8 килогерц).

Для качественного воспроизведения звукозаписей с помощью компьютера в настоящее время используются частоты дискретизации 44 килогерца и более. Это связано с тем, что слуховая система человека не воспринимает частоты выше, чем 20 000–22 000 герц. Следовательно, частота дискретизации в 44 000 герц сохраняет для человека все слышимые им звуки в неискажённом виде.

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

А при квантовании изображений для естественного восприятия цвета следует выделять не менее чем 224 = 16 777 216 цветовых градации, которые способны распознать органы зрения человека.

НАБОРЫ ЗНАКОВ И АЛФАВИТЫ

Так при квантовании сигнала, за его уровнями закреплены знаки {A0, A1,…,AK}

С учётом того, что параметр изображённого на этих рисунках сигнала может принимать всего десять различных значений можно было бы выбрать какие-либо другие наборы знаков, например, {0, 1, 2, …,9} или {а, б, в, …, и}

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

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

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

Тогда по любому заданному знаку можно однозначно определить соответствующий ему уровень сигнала, и, наоборот, по заданному уровню однозначно определить соответствующий ему знак. В чём недостаток такого подхода?

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

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

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

Алфавит, как правило, задается прямым перечислением всех входящих в него знаков. При этом знаки перечисляются в порядке их следования. Примеры алфавитов:

{а, б, в, г, д, е, ё, ж, з, и, й, к, л, м, н, о, п, р, с, т, у, ф, х, ц, ч, ш, щ, ъ, ы, ь, э, ю, я} — 33 буквы русского языка;
{a, b, c, d, e, f, g, h, i, j, k, l, m, n, o, p, q, r, s, t, u, v, w, x, y, z} — 26 букв английского языка;
{0, 1, 2, …, 9} — 10 цифр арабской десятичной системы счисления;
{·, ─} — два знака азбуки Морзе, которая ранее широко использовалась для радиосвязи и т.д.

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

Так как этот код используется для хранения и обработки данных в компьютерах — вычислительных машинах — его называют ещё и машинным кодом.

По определению любое дискретное сообщение S представляет собой некоторую последовательность квантованных отсчётов, а каждый отсчёт можно обозначить некоторым знаком αj∈A.

Следовательно, дискретное сообщение можно представить, записать в виде последовательности знаков, принадлежащих алфавиту: S=a1,a2,…,am, где aj— очередной знак сообщения, являющийся одним из знаков алфавита aj∈A, j=1,2,…,m; m — количество знаков в сообщении.

В такой записи запятые, которые отделяют знаки последовательности друг от друга, чаще всего пропускаются и тогда сообщение принимает вид S=a1a2…am

Например, последовательность знаков русского алфавита S= и, н, ф, о, р, м, а, ц, и, я или в более кратком виде S= информация — является сообщением, состоящим из m=10 знаков.

А последовательность из m= 8 знаков: 0, 0, 1, 0, 1, 0, 0, 1, 1, или в более наглядном виде «00101001» записана в двоичном алфавите A={0,1}

Количество знаков m, из которых состоит цепочка α называется длиной цепочки. Длину цепочки обозначают |α|. Например, |информация|=10, а |00101001 |=8.

Допускаются цепочки нулевой длины, такие цепочки называются принято называть пустыми. Пустые цепочки обычно обозначаются буквой λ, |λ|=0.

Кодирование сообщений

Исходный алфавит A1, в котором записано сообщение, называется первичным алфавитом. Целевой алфавит A2, в который преобразуется сообщение называется вторичным алфавитом.

Слова записанные в двоичном, шестнадцатеричном и некоторых других алфавитах, принято называть кодом (двоичное слово ─ двоичный код и т.д.).

Дискретное сообщение исходя из технических соображений или из особенностей органов чувств человека, участвующих в приеме или передаче сообщений, разбивают на конечные подпоследовательности знаков, которые принято называть словами. Количество знаков в слове называется длиной слова. Если все слова языка имеют одно и то же количество знаков, то такие слова называются n-разрядными (n ─ длина слова)

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

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

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

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

Кодером называется устройство, обеспечивающее выполнение операции кодирования. Декодером называется устройство, обеспечивающее выполнение операции декодирования.

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

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

Различают два вида сжатия — без потери информации и с потерей информации.

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

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

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

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

Кодирование текстовых данных

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

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

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

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

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

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

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

Определяющие характеристики способов кодирования:

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

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

В 1838 году С. Морзе предложил систему кодирования для первой телеграфной линии, которая строилась между городами Балтимор и Вашингтон (США).

Эта система в нашей стране во время Первой мировой войны 1914–1918 г.г. получила название «морзянки» или «азбуки Морзе». Фактически азбука Морзе была первым цифровым способом передачи сообщений.

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

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

Чтобы при приёме можно было различить два соседних знака, входящих в код одной буквы или цифры, между ними включается пауза с длительностью t передачи точки.

А для разграничения кодов двух соседних букв сообщения делается пауза длительностью 3t. Промежуток между соседними словами задается паузой длительность 6t.

Базовая длительность времени передачи точки t зависит от индивидуального «подчерка» радистов, от их возможностей и опыта. Радист средней квалификации может вести передачу/приём со скоростью 60–100 знаков текста в минуту.

В среднем на код одного знака требуется около 6t. Отсюда базовая единица длительности t равна примерно 0,1–0,15 секунды.

Формирование и передача кодов с неравными длительностями элементарных сигналов с помощью технических средств наталкивается на целый ряд трудностей.

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

Азбука Морзе более века была важнейшей системой кодирования, повсеместно используемой в телеграфной связи, а впоследствии и в радиосвязи. В настоящее время её использование ограничено в основном любительскими сферами.

Это объясняется более простой технической реализацией передачи равномерных кодов. Кроме того, обработка равномерных кодов выполняется значительно проще и быстрее чем обработка неравномерных.

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

К середине XX века в информационных системах разных стран мира использовалось более 60 различных способов кодирования алфавитов естественных языков, так что обмен сообщениями между различными компьютерами был затруднён или вообще невозможен.

В связи с этим остро встала проблема стандартизации способов кодирования текстовых данных. В 1963 году был опубликован первый вариант равномерного алфавитного кода ASCII (от англ. American Standard Code for Information Interchange — американский стандартный код для обмена информацией), который стал логическим развитием кода Бодо.

Однако фактическим международным стандартом это код стал только после 1981 года, когда кодировка ASCII была использована для представления текстов в программах для персональных компьютеров, выпущенных фирмой IBM.

Группа из 8 бит, используемая как единое целое, например, для кодирования одного символа текста, называется байтом (byte ─ BinarY TErm).

Алфавит для представления текстов на естественном языке содержит: 52 латинских буквы, десятичные цифры, знаки препинания, математические знаки, специальные знаки и т.д., всего примерно 150 символов.

Исходя из теоретических соображений, это требует для представления любого знака исходного алфавита при равномерном алфавитном двоичном кодировании log2150 ≈ 7,2 знаков, то есть семи или восьми двоичных цифр.

Первоначально кодировка ASCII была семиразрядной, что позволяло выделить коды максимум 27 = 128 знакам. Но впоследствии было предложено использовать для кодирования одного знака группу из 8 двоичных цифр, что позволяет определить коды для 28 = 256 различных знаков первичного алфавита.

Неиспользованные в базовой части коды входят в расширение таблицы ASCII. Этими кодами в конкретных разновидностях кодировок можно распоряжаться достаточно произвольно. В частности, в разных странах мира такие расширения применяются для кодирования национальных алфавитов.

Для краткости речи расширения кодовой таблицы обычно называют просто кодовой таблицей (а иногда и кодовой страницей), с указанием некоторого дополнительного обозначения, например, говорят: «кодовая таблица Windows 1251», подразумевая под этим соответствующее расширение таблицы ASCII.

1000 10102

К ─ ГОСТ алтерн.
Љ ─ Windows1251

Универсальная кодировка
UNICODE (UNIversal CODE)
1 символ → 16 бит
216=65 536

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

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

Группа байт, совместно используемая для представления каких-либо данных, называется полем. Количество байтов в поле называется длиной поля.

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

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

В общем случае формат понимается как строго определенный, исчерпывающе полный набор правил.

TXT (TeXT — текст) основывается на одной из кодовых таблиц для представления символов и практически не содержит никаких элементов его оформления;
RTF (Rich Text Format — богатый текстовый формат), содержит совокупность стандартных возможностей по оформлению текстов;
DOC (DOCument — документ) содержит подавляющее большинство используемых в современной практике возможностей по оформлению текстов;
PDF (Portable Data Format ─ переместимый формат данных) универсальный формат, воспринимаемый на компьютерах любого типа

Некоторые текстовые форматы:

Понятие формата

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

Однако над числами приходится выполнять разнообразные математические операции — сложение, вычитание, умножение и т. д.

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

Основными разновидностями данных в информатике являются: текстовые, числовые, графические. Представление звуковых данных базируется на числовых, а видеоданных ─ на числовых и графических.

Для обсуждения этих способов потребуются некоторые понятия, связанные с системами счисления.

Каждая система счисления использует для изображения чисел свой собственный набор знаков — алфавит.

Десятичный алфавит: {0,1,2,3,4,5,6,7,8, 9}

Двоичный алфавит: {0,1}

Шестнадцатеричный алфавит: {0,1,2,3,4,5,6,7,8, 9, A, B, C, D, E, F}

Алфавит римской системы счисления: {I,V,X,L,C,D,M}

Примеры алфавитов:

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

Пример: различные изображения числа «девять»: IX, 1001, 11, 10, 9, и т.д.

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

Знаки, входящие в алфавиты систем счисления традиционно называются цифрами. Таким образом, знаки A, B, C, D, E и F, входящие в алфавит шестнадцатеричной системы счисления, считаются цифрами.

В общем случае различают непозиционные, позиционные и смешанные системы счисления.

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

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

При использовании позиционных систем счисления позиции цифр в числе принято называть разрядами: разряд единиц, разряд десятков, разряд сотен и т.д.

Нумерация разрядов для целой части начинается с нуля и производится с возрастанием номеров справа налево, а нумерация для дробной части начинается с минус единицы и осуществляется в порядке убывания номеров слева направо.

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

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

Пример: x=52,128

=5×10+2+

Все входящие в выражение весовые коэффициенты равны pi — основанию системы счисления p в степени, равной номеру разряда i.

Максимальное значение n - разрядных целых чисел в системе счисления с основанием p равно p n –1. Например, максимально возможное 4-х разрядное десятичное число 9999 равно 104–1.

В частности, максимально возможное n – разрядное целое двоичное число равно 2n –1.

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

200510 → 111110101012

2005

→

↓

1

1002

↓

0

→

501

↓

1

→

250

↓

0

→

125

↓

1

→

62

↓

0

→

31

↓

→

1

15

↓

1

→

7

↓

1

→

3

↓

1

→

1

Пример перевода в двоичную систему счисления

Пример перевода в шестнадцатеричную систему счисления

2005

⎜

⎯

⎯

16

1

−

16

⎯

40

2

−

32

⎯

5

85

−

80

⎯

5

⎜

⎯

⎯

16

112

−

⎯

13

7

710 → 7 16

13 10 → D 16

2005 10 → 7D5 16

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

0,625

×

2

⎯

1,250

×

2

⎯

0,500

×

2

⎯

1,000

0,625 10 → 0,101 2

0,625

×

16

⎯

10,000

10 10→ A 16

0,625 10 → 0, A 16

Например, число 23,176 может быть получено как результат округления следующих чисел:

23,17648 ̶ погрешность равна: Δ=|23,176-23,17648|=0,00048
23,17589 ̶ погрешность равна: Δ=|23,176-23,17589|=0,00011
23,1757 ̶ погрешность равна: Δ=|23,176-23,1757|=0,0003
23,17629 ̶ погрешность равна: Δ=|23,176-23,17629|=0,00029

Отсюда Δ≤0,0005 или Δ≤1/2×10-3.

Пусть правильная дробь в системе счисления с основанием q содержит n цифр. Сколько цифр m в дробной части этого числа следует получить при переходе в систему счисления с основанием p?

При переходе из десятичной в двоичную (10→2):

q=10; p=2; m=n×log210, m=3,329 × n

Пример: 2005,62510

→ 111 1101 0101,1012

2005,62510 → 7D5,A16.

Перевод чисел из системы с основанием P в десятичную систему счисления

Записать число в виде разложения по степеням основания исходной системы счисления.
Заменить p-е цифры числа их десятичными эквивалентами.
Выполнить вошедшие в полученное выражение действия.

Пример: 111 1101 0101,1012; p=2

1×20+0×21+1×22+0×23+1×24+0×25+1×26+1×27+1×28+1×29+1×210+1×2–1+0×2–2 +1×2–3

1+22+24+26+27+28+29+210+2–1+2–3 =1+4+16+64+128+256+512+1024+1/2+1/8=2005,62510

Пример: 7D5,A16 ; p=16

5×160+D×161+7×162+A×16–1=5+13×16+7×256+10/16=2005,62510

Нужно осуществить раздельный перевод целой и дробной частей, а затем сложить полученные результаты.

Пример:11111010101,1012

11111010101,101

111 1101 0101, 101

0

0

↓

5

↓

D

↓

7

↓

A

11111010101,1012 → 7D5,A16

Пример: 7D5,A 16

7 D 5, A

↓

0111

↓

1101

↓

0101

↓

1010

011111010101,1010

7D5,A16→11111010101,1012

→11111010101,101

101001011011,00112

111101010111,11112

+

Пример:

02

Перенос (в «уме»):

1

Одноразрядное действие:

1+1= 0 и 1 переноса (в «уме»)

1+1+1= 1 и снова 1 переноса

1

1100110110011,00

1 – 1 = 0

10 – 1 = 1

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

Пример:

1100110110011,00102

101001011011,00112

-

Одноразрядное действие:

0 – 1=

заем

10 – 1 = 1

12

0

0

1

111101010111,11

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

11011,112

Пример:

101,012

×

1101111

1101111

1101111

10010001,10112

Пример:

DA9CD316

15B4F516

+

3+5=8

<16

810→816

816

D+F=

13+15=

28>16

→28-16=12;

1210→C16

C

1

ПЕРЕНОС

С+4=

12+4=

16+4

+1

=17>16

;17-16=

1

1

F05

Второй способ сложения многозначных шестнадцатеричных чисел

DA9CD316

15B4F516

+

Пример:

3+5=8

<16

810→816

816

D+F>16;

F ближе к 1016, не хватает 1;

D-1=C;

1

ПЕРЕНОС

C

F051

Пример:

F051C816

DA9CD316

-

8-3=5

516

С-D=

12-13=

12+16-13=

заем

1510→F16

0

F

15B4

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

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

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

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

Формат с фиксированной точкой

Беззнаковое представление формата с фиксированной точкой

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

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

Диапазон представимых чисел: от 0 до 2N -1, N ─ длина поля в битах.

Следовательно, под дробную часть числа отводится нулевое количество разрядов, поэтому в данном варианте кодирования возможна работа только с целыми числами. Постоянное расположение точки, фиксация её позиции дала название формату — «с фиксированной точкой».

004D;

0000004D;

26710 →

010B; 0000010B

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

→ 4D;

Порядок перехода к беззнаковому формату с фиксированной точкой:

Определение числа по его коду (беззнаковый, фиксированная точка):

Система кодирования со знаком

Код знака числа принято размещать в самом левом разряде поля, который в связи с этим принято называть знаковым битом.

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

Попытка
использования системы кодирования со знаком (прямого двоичного кода со знаковым битом) для представления знаковых целых чисел:

|4|10 → 000 01002;

|127|10 → 111 11112;

+4 → 0|000 01002;

- 4 → 1|000 01002;

+127 → 0|111 11112;

- 127 → 1|111 11112;

Недостатки:

+

+7 → 01112
+6 → 01102
+5 → 01012
+4 → 01002
+3 → 00112
+2 → 00102
+1 → 00012
+0 → 00002
1 → 11112
2 → 11102
3 → 11012
4 → 11002
5 → 10112
6 → 10102
7 → 10012
8 → 10002

При четырех битах всего 16 кодов, диапазон при использовании прямого кода: от – 7 до +7, два кода заняты под нуль 00002 и 10002

При четырех битах всего 16 кодов, диапазон при использовании дополнительного кода: от – 8 до +7, под нуль занят один код 00002, а код 10002 обозначает -8

Для однобайтового поля всего 256 кодов, диапазон целых чисел для беззнакового представления

Для однобайтового кода всего 256 кодов, диапазон целых чисел для однобайтового поля
знакового представления

Рассмотрим пример. Вновь возьмём n=4 и найдем код числа минус семь. В данном случае M=24=100002, прямой код модуля обсуждаемого числа P=1112, и, следовательно, его дополнение до M равно D = 100002 – 1112 = 10012, что совпадает с полученным прямыми рассуждениями дополнительным кодом этого числа.

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

Перевести модуль целого числа в двоичную систему счисления;
Если число отрицательное, то получить дополнительный код, инвертировав прямой код (получится обратный код) и добавив к результату 1;
Записать число в выделенное для него поле.

10000 00002 10016
0100 11012 4D16
1011 00112 B316

Способы получения дополнительного кода

-

-

77; 1) прямой код модуля: 77 → 4D16= 0100 11012;
2) обратный код: 1011 00102;
дополнительный код: 1011 00112;
3) – 77 → 1011 00112 или B316;

Порядок перехода к знаковому формату с фиксированной точкой:

Число: - 7710
Поле 1 байт: 1|011 00112 или B3 16;
Поле 2 байта: 1|111 1111 1011 00112 или FF B316;
Поле 4 байта: 1|111 1111 1111 1111 1111 1111 1011 00112 или FF FF FF B316

1 0000 0000 0000 00002
0100 11012
1111 1111 1011 00112

Дополнительные коды для -77

1 0000 0000 0000 0000 0000 0000 0000 00002
0100 11012
1111 1111 1111 1111 1111 1111 1011 00112

─

─

1 00 0016
4D16
FF B316

─

1 00 00 00 0016
4D16
FF FF FF B316

─

При переходе к более длинному полю свободные слева биты поля заполняются кодом знакового бита 02 (016) для положительных и 12 (F16) ─ для отрицательных

Порядок определения числа по его коду (знаковый, фиксированная точка):

→ +90

→ 0000 0000 0101 10102;

>0;

→ 1111 1111 1110 10002;

<0;

10000-FFE8=0018

→ - 24

Примеры:

В естественных науках часто используются числа вида:- 2,9×10 18 ;0,091 ×10-30. Обычно этот способ используется для задания очень больших или очень маленьких по модулю чисел.

- 2 900 000 000 000 000 000 → - 2,9×1018
0,000 000 000 000 000 000 000 000 000 000 091 → 0,091 ×10-30

Например:

18,456 → 1,8456×10+1

Запись чисел таким способом обладает неоднозначностью:

→ 1845,6 ×10-2

→ 184,56 ×10-1

→ 0,18456 ×10+2

Чтобы избавится от неоднозначности на значение мантиссы m накладывается какое-либо ограничение, например: 0,1 ≤ m< 1 или 1≤ m <10.

ФОРМАТ С ПЛАВАЮЩЕЙ ТОЧКОЙ

Принцип кодирования в формате с плавающей точкой

Код числа вида ± m × q ±p должен содержать:
Код знака числа ± (0 или 1);
Код нормализованной мантиссы 1 ≤ m < 10 ;
Код знака порядка ± (0 или 1);
Код порядка p.

Возможный способ кодирования с помощью восьми десятичных цифр

0

0

Машинный нуль (underflow ─ исчезновение порядка) |x|<10-9

0

Переполнение (overflow ─ переполнение порядка) |x| >9,9999×10+9

При изменении количество разрядов, отводимых на порядок, изменяется диапазон представимых чисел. При изменении количества разрядов, отводимых на мантиссу, изменяется точность представления чисел

1,6×10-4
1,2 ×10-4
2,8 ×10-4

+

8,6×10-4
3,7 ×10-4
12,3 ×10-4

+

→ 1,23×10-3

1,6 ×10-4
1,52 ×10-4
0,08 ×10-4

-

→ 8,0×10-6

1,6×10-4
1,5×10-5

1,6 ×10-4
0,15×10-4
1,75×10-4

+

+

Нормализация результата

Предварительная денормализация операнда

1,6×10-4
1,5×10-3

+

1,6×10-4
15,0×10-4
16,6×10-4

+

→ 1,66×10-3

Диапазон и точность представления чисел в формате с плавающей точной

S=0 для положительных чисел и S=1 ─ для отрицательных
Код машинного порядка Pм равен порядку числа Pи увеличенному на 12710
Код мантиссы равен мантиссе, уменьшенной на единицу

+15,37510

→ 1111,0112

→ 1,111011×10112

S=0;

Pи = 112;

Pм = Pи + 111 11112 = 1000 00102;

M = 1110112

Код числа +15,37510 в формате с плавающей точкой в четырехбайтовом поле 0100 0001 0111 0110 0000 0000 0000 00002 или 41 76 00 0016

Пример:

Пример: С2B7AE0016

→1100 0010 1011 0111 1010 1110 0000 0000

1 10000101 01101111010111

S=1;

Pм = 100001012=8516;

→ Pи =(85-7F)16 = 616 =1102

М = 01101111010111

→ - 1,01101111010111×10+110

→ -1011011,110101112

→ - 5B,D716

= - 91,8398437510

Правила прямого и обратного переходов те же самые, что и при использовании четырехбайтовых полей

Поля длиной 8 байтов ─ длинные вещественные (двойная точность)

Код знака числа S ─ 1 бит (63 бит)
Код машинного порядка Pм ─ 11 бит (52-62 биты)
Код мантиссы M ─ 52 бита (0-51 биты).

Правила прямого и обратного переходов те же самые, что и при использовании четырехбайтовых полей, но машинный порядок отличается от истинного на 102310

+15,37510

→ 1111,0112

→ 1,111011×10112

S=0;

Pи = 112;

Pм = Pи + 11 1111 11112 = 100 0000 00102;

M = 1110112

Пример:

Код числа +15,37510 в формате с плавающей точкой в восьмибайтовом поле 0100 0000 0010 1110 1100 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 00002 или 40 2E C0 00 00 00 00 0016

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

+15,37510

→ 1111,0112

→ 1,111011×10112

S=0;

Pи = 112;

Pм = Pи + 11 1111 1111 11112 = 100 0000 0000 00102;

M = 11110112

Пример:

Код числа +15,37510 в формате с плавающей точкой в десятибайтовом поле 0100 0000 0000 0010 1111 0110 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 00002 или 40 02 F6 00 00 00 00 00 00 0016

Разновидности BCD кодирования

Пример: число: +567 398 104

Текстовый код ASCII: 20 35 36 37 33 39 38 31 30 3416

Неупакованный BCD формат: 00 05 06 07 03 09 08 01 00 0416

Упакованный BCD формат: 05 67 39 81 0416

Знаковый BCD формат (для - 567398104) : 80 00 00 00 00 05 67 39 81 0416

С2ABE45216

Текстовый формат, кодировка Windows1251 → В « д R

Текстовый формат, кодировка КОИ-8 → б └ Д R

КОД:

Текстовый формат, кодировка ГОСТ → ┬ л ф R

Беззнаковый, фиксированная точка → 3 266 045 01010

Знаковый, фиксированная точка → - 1 028 922 28610

Формат с плавающей точкой → - 85,94629110

Кодирование графических данных

Под графическими данными можно понимать рисунок, чертеж, картинку в книге, фотографию, изображения на экране телевизора или в кинозале и т. д.

Основные виды компьютерной графики в настоящее время: растровая, векторная, фрактальная, flash – графика.

Изображение строится из горизонтальных линий — строк. А каждая строка в свою очередь состоит из элементарных мельчайших единиц изображения — точек, которые принято называть пикселями (picsel — PICture'S ELement — элемент картинки).

Основы кодирования растровой графики

← пиксель

Количество строк (например,600)

Количество пикселей в строке (например, 800)

Стандартно используемые разрешения: 800×600, 1024 × 768, 1152 × 864, 1280 × 1024, 1600 × 1200, 1600 × 1280, 1920 × 1200, 1920 × 1600, 2048 × 1536.

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

1. В изображении используется два цвета: белый и черный. Состояние пикселя кодируется одним битом.

Недостаток: получается чрезвычайно контрастное изображение

2. Более реалистический вариант ─ в изображении используются четыре цвета: белый, светло-серый, темно-серый и черный. На один пиксель требуется два бита.

На растр 800×600 требуется 120 000 байтов.

3. Стандартный способ ─ в монохромном изображении используются 256 оттенков серого цвета от белого до черного.

На кодирование одного пикселя требуется один байт, а на весь растр 800×600 ─ 480 000 байтов.

Кодирование цветных пикселей в методе RGB основано на том, что белый цвет можно представить как сумму трех основных цветов: красного (Red), зеленого (Green), синего (Blue), а их смешение в различных пропорциях дает остальные цвета.

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

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

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

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

При этом нулевое значение означает, что в суммарном цвете данный основной цвет отсутствует, а единичное — присутствует.

Можно задать 256 оттенков каждого из основных цветов ─ всего 16 777 216 различных цветов. На кодирование одного пикселя требуется три байта, на растр 800×600 ─ 1 440 000 байтов.

В этом случае для кодирования одного цветного пикселя потребуется три бита — по одному на каждый цвет.

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

На кодирование растра 800×600 необходимо 180 000 байтов.

4. Индексный режим. Для кодирования цвета одного пикселя используется один байт. Базируется на заранее созданной для данного рисунка таблице используемых в нем цветовых оттенков. Затем нужный цвет пикселя выбирается из этой таблицы с помощью номера — индекса, который занимает всего один байт памяти. Для растра 800×600 требуется 480 000 байтов.

Конкретный способ кодирования всей требуемой при записи изображения в память компьютера информации (цвет, яркость, контрастность, разрешение) образует графический формат. Форматы кодирования графической информации, основанные на передаче цвета каждого отдельного пикселя, из которого состоит изображение, относят к группе растровых или BMP (Bit MaP — битовая карта) форматов.

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

а) исходное изображение, б) то же изображение, увеличенное в 8 раз

Некоторые графические векторные форматы

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

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

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

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

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

Заметим, что получающиеся при оцифровывании значения отсчётов в литературе иногда называют сэмплами (англ. sample — образец). Но для обозначения отдельного отсчёта это название некорректно потому, что под термином «сэмпл» в практике оцифровывания звука понимается относительно небольшой звуковой фрагмент, а не отдельный отсчёт.

50 герцам.

Чему равна частота дискретизации в рассматриваемом примере?

При записи звука в мультимедийных технологиях применяются частоты 8, 11, 22, 44 и более килогерц. Для получения высококачественного звука используются частоты до 192 килогерц. Например, частота дискретизации 44 килогерца означает замену одной секунды непрерывного звучания набором из сорока четырех тысяч отдельных отсчетов сигнала.

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

Этот параметр, который принято называть разрядностью преобразования, определяет количество различных уровней сигнала, представимых при его квантовании. Чем больше количество битов, тем более качественно и точно происходит воспроизведение оцифрованного звука. Обычно используются разрядности 8, 16 и 24 бит.

Таким образом, кодирование и обработка звука фактически сводится к кодированию и обработке числовых данных.

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

Формат wav требует очень много памяти. Так, при записи стереофонического звука с частотой дискретизации 44 килогерца и разрядностью 16 бит — параметрами, дающими достаточно хорошее качество звучания — на одну минуту записи требуется около десяти миллионов байтов памяти.

В связи с особенностями программ, осуществляющих кодирование звука, оцифровывание удобнее характеризовать одним параметром, который называется битрейтом (англ. bit rate — битовая скорость).

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

Единицей измерения битрейта является бит в секунду (бит/c или bps — bit per second). Широко используются также кратные единицы — килобиты в секунду (кбит/с, kbit/s или kbps) и мегабиты в секунду (мбит/с, mbit/s или mbps). Во избежание путаницы отметим, что здесь приставки кило- и мега- означают 1 000 и 1 000 000 соответственно.

На самом деле, точное значение стандартного битрейта равно 1411,2 кбит/с, так как частота дискретизации выбирается равной 44 100 герц — немного выше, чем в примере.

Кодирование видеоинформации осуществляется с помощью дискретизации непрерывных изображений. Основано на свойстве человеческого глаза воспринимать быструю смену последовательности картинок с небольшими изменениями одна относительно другой как одну картинку с движением. Этот принцип используется в кино, в мультипликации и анимации. Стандартной частотой дискретизации для видеоизображений является 30 изображений (кадров) в секунду. Кодирование требует не только дискретизации непрерывных движений, но и синхронизации изображения со звуковым сопровождением. В настоящее время для этого используется формат, которой называется avi (Audio-Video Interleaved — чередующееся аудио и видео).

стандарт MPEG-1 описывает форматы записи звука. Например, формат MP-3 при практически том же качестве звука требуется в десять раз меньше памяти, чем при использовании формата WAV.
стандарт MPEG-2 описывает методы сжатия видеозаписей, которые обеспечивают телевизионное качество изображения и стереозвуковое сопровождение и имеют приемлемые требования к памяти.
стандарт MPEG-4 описывает методы сжатия видеозаписей, которые обеспечивают минимальные требования к памяти. Например, с его помощью можно полнометражный цветной фильм со звуковым сопровождением записать на стандартный компакт-диск. Разработан в 1999 году.

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

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

Понятие алгоритма, в отличие от большинства других понятий информатики, имеет довольно длинную историю. Происхождение этого термина обычно связывают с именем узбекского учёного аль-Хорезми, написавшего около 825 года книгу «Об индийском счёте», в которой описаны правила выполнения действий над числами в десятичной позиционной системе счисления.

В настоящее время считается, что именно так появился современный термин алгоритм. Кроме того предполагают, что именно аль-Хорезми впервые использовал цифру 0 (нуль) для обозначения пропущенной позиции в записи числа в позиционной системе счисления. Её индийское название переведено как sifr, отсюда произошли нынешние термины «цифра» и «шифр».

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

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

В 30–50-х годах XX века в связи с формированием теории алгоритмов произошло кардинальное изменение в понимании их роли и значения в научной сфере и обычной жизни человека. В это время термин алгоритм приобрел чёткое научное определение.

В настоящее время понятие алгоритм является сложным и многоплановым, тем не менее, можно выделить три основных аспекта в его использовании:

интуитивный;
теоретический;
фундаментальный.

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

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

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

Заметим однако, что для программистов ещё необходимо чтобы алгоритм обладал некоторой, обсуждаемой далее совокупностью свойств.

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

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

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

Как оказалось, задача доказательства отсутствия решения совершенно отличается от задачи нахождения какого-либо решения.

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

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

А вот внешне аналогичная задача о трисекции угла (о делении произвольного угла на три равные части) при тех же ограничениях решения не имеет, и никогда не будет иметь. Чтобы установить этот факт учёным понадобилось более 2 000 лет.

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

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

В их работах были развиты строгие и точные классические теории алгоритмов: теория рекурсивных функций, теория машин Поста, теория машин Тьюринга, теория нормальных алгоритмов Маркова.

Классические теории алгоритмов иногда объединяют под общим названием логической теории алгоритмов.

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

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

Машина Поста задается:

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

Структура команды машины Поста:

<порядковый номер команды>. <операция> <номер следующей команды>

Пример команды: 5. ⇒ 9
Пятая команда. Шаг вправо, перейти к выполнению команды с номером 9

стереть отметку, если текущая клетка не отмечена;
поставить отметку, если текущая клетка уже отмечена.

Невыполнимые команды:

Требование к программе машины Поста

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

5.

Клетка пуста, переход к 4 команде

⇒ 5

5.

Клетка не пуста, переход к 3 команде

3. ⇐ 2

2. ξ 3

Безрезультатная остановка

V 4
ξ 3
⇐ 6
⇒ 5
Стоп

6. Стоп

Результативная остановка

Пример: изображение числа 2 в машине Поста

1.

2. ⇒ 1
3. ⇐ 4
4. V 5
5. Стоп

Программа для машины Поста прибавления единицы

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

С другой стороны для таких алгоритмов совершенно не нужен такой высокий уровень строгости как у классических теорий.

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

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

Основными особенностями интуитивного представления об алгоритме является неопределённость терминов «исполнитель», «действие», «цель» и т.д. Именно поэтому существует несколько десятков «определений» алгоритма, которые на самом деле являются не более чем «объяснениями на пальцах».

Выдающийся советский математик А.Н. Колмогоров пишет, что «Алгоритм — это всякая система вычислений, выполняемых по строго определённым правилам, которая после какого-либо числа шагов заведомо приводит к решению поставленной задачи».

Создатель одной из классических теорий алгоритмов А.А. Марков приводит следующее объяснение: «Алгоритм — это точное предписание, определяющее вычислительный процесс, идущий от варьируемых исходных данных к искомому результату».

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

Алгоритм — это последовательность действий, либо приводящая к решению задачи, либо поясняющая, почему это решение получить нельзя;

Проанализировав все эти трактовки, можно заметить, что общими для них являются следующие моменты:

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

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

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

Алгоритм есть описание способа решения задачи. Таким образом, исполнение алгоритма есть фактическое решение задачи по заданному в алгоритме способу.

И основным моментом, конечно же, является получение желаемого результата за конечное время. Более того, неявно подразумевается, что это время должно быть разумным, поскольку ждать от исполнителя требуемого результата сотни или даже десятки лет, обычно не может считаться приемлемым.

Алгоритмы являются:

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

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

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

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

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

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

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

А

В

А

В

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

Обсуждая свойство дискретности алгоритма А.Н. Колмогоров пишет, что «алгоритм — это процесс последовательного построения величин, идущий в дискретном времени таким образом, что в начальный момент задается исходная конечная система величин, а в каждый следующий момент система величин получается по определённому закону (программе) из системы величин, имевшихся в предыдущий момент времени».

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

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

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

Это утверждение требует, чтобы общее количество этапов в алгоритме было конечным.

Пример: правило вычисления значения 1+1/4+1/9+…─ задает бесконечное количество этапов, а правило 1+1/4+1/9+1/16+1/25+1/36+1/49+1/64+1/81+1/100 ─ задает конечное количество этапов.

Следовательно, какая-либо последовательная группа этапов алгоритма может выполняться неоднократно, и требование конечности алгоритма исключает случай бесконечного количества выполнений любой группы этапов.

Рассмотрим пример, в котором последовательность предписанных действий необходимо выполнить несколько раз. Врач выписал больному лекарство, которое: 1)следует купить в аптеке и принимать каждый день 2)утром, 3)в обед и 4)вечером, а после выздоровления больному следует 5)пройти контрольное обследование.

Что можно сказать об этом примере?

Явно видна дискретность этого предписания и конечность количества этапов, из которых оно состоит.

Но из пяти этапов первый и пятый должны быть выполнены только один раз, а вот этапы 2, 3 и 4 необходимо выполнять неоднократно, в течении нескольких дней. Про такие этапы программисты говорят, что они образуют цикл.

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

А что если больному лучше не станет? Если врач неправильно поставил диагноз?

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

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

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

Пример неявного задания этапов: 1+1/4+1/9+…+1/100 ─ подразумеваются действия по аналогии.

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

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

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

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

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

Это в свою очередь означает, что алгоритм может содержать только такие действия, которые исполнитель в состоянии выполнить.

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

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

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

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

Алгоритм не содержит ошибок, если он даёт правильные результаты для любых допустимых исходных данных

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

Итак, исполнение алгоритма может завершиться за конечное время с получением требуемого результата только в том случае, если: 1) алгоритм не содержит ошибок, 2) алгоритм применяется к корректным, допустимым входным данным и 3) в алгоритме предусмотрена реакция на возникновение невыполнимых действий.

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

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

Кроме того, алгоритм должен быть задан в форме, которая известна исполнителю. Например, для исполнителя-компьютера алгоритм должен быть в конечном счете задан в двоичном алфавите. Получается, что требование понятности, элементарности относительно, оно всегда зависит от исполнителя алгоритма.

Массовость (универсальность) алгоритма означает, что набор исходных величин алгоритма может выбираться из некоторого, возможно, бесконечного множества наборов.

Для каждого алгоритма существует некоторое множество наборов величин, которые допустимы в качестве исходных данных. Например, в алгоритме деления вещественных чисел делимое может быть любым числом, а делитель не может быть равен нулю.

Интуитивного понятия алгоритма, применяемого совместно с перечисленными требованиями, оказывается достаточно для большинства практических проблем информатики — разработки алгоритмов решения самых разных задач и написания работоспособных программ для компьютера.

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

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

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

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

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

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

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

Способы задания алгоритмов

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

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

Наиболее важные для информатики способы:

словесный;
двоичное кодирование;
графические;
словесно-формульные.

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

Недостаток ─ непосредственное восприятие человеком алгоритма, заданного в двоичном алфавите, затруднено.

Более точно: для исполнения на компьютере алгоритм должен быть представлен в специальной форме, в которой его этапы имеют вид двоичных машинных команд, принадлежащих системе команд процессора этого компьютера.

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

Процессор компьютера ничего кроме машинного языка «не понимает».

Начало

Конец

Основные элементы блок-схем

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

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

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

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

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

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

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

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

Программы, которые осуществляют автоматический перевод, получили название компиляторов (англ. compile — компилятор, переводчик), часто их называют ещё и трансляторами (англ. translator — переводчик).

Автоматическое преобразование на машинный язык программы, которая перед этим сформулирована на алгоритмическом языке, называется трансляцией или компиляцией.

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

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

Подчеркнём, что трансляторы — это специализированные машинные программы, то есть программы, которые уже представлены на машинном языке и потому они могут непосредственно выполняться процессором компьютера.

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

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

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

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

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

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

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

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

В общем случае система любого языка программирования включает в себя как обязательные элементы:

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

Завершая обсуждение способов задания алгоритмов, сравним запись алгоритма на алгоритмическом языке с другими способами задания:

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

Типы алгоритмов

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

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

Семантика (греч. semanticos — обозначающий) языка представляет собой множество правил, объясняющих смысл и свойства конструкций этого языка.

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

Но сами эти правила также необходимо каким-то образом формулировать, причём способ их задания должен обеспечивать однозначность понимания самих правил. Другими словами нужен язык для описания синтаксиса алгоритмических языков. Такие языки существуют и их принято называть метаязыками.

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

В метаязыке БНФ правило, определяющее способ построения конструкции алгоритмического языка, состоит из двух частей, которые отделяются друг от друга знаком . Это знак понимается как «есть по определению». Слева от него в уголковых скобках указывается название определяемой конструкции или понятия, а справа — собственно определение:

<имя понятия> → определение 1 | определение 2 …

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

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

Во всех правилах действует общее соглашение: названия определяемых или уже определённых понятий заключаются в уголковые скобки, а знаки алфавита — не заключаются.

Здесь определяемым является понятие цифра, а справа десять различных вариантов его определения. Понимается этот текст следующим образом: «Цифра есть по определению знак 0, либо знак 1, либо знак 2, либо знак 3 и т.д.».

Таким образом, римские цифры I, V, X, а также «цифры» шестнадцатеричной системы счисления A, B, C, D, F и E с точки зрения этого определения не являются цифрами.

Комментарии

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

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

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

//так выглядит однострочный комментарий и в Паскале и в Си
{ так оформляется многострочный комментарий в Паскале }
(* другой способ оформления многострочного комментария в Паскале *)
/* а это оформление многострочного комментария в Си */

Существует два основных способа включения комментариев: однострочный и многострочный:

Алфавит языка

Алфавит любого языка программирования, как и вообще любой алфавит, представляет собой точно зафиксированное множество знаков

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

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

Это определение понимается следующим образом: основной символ это либо <буква>, либо <цифра>, либо <специальный знак>. Фактически понятие «основной символ» сводится к другим перечисленным справа понятиям, каждый из них, следовательно, должен иметь своё отдельное определение.

<буква>→ a | b | c | d | e | f | g | h | i | j | k | l | m | n | o | p | q | r | s | t | u | v | w | x | y | z | A | B | C | D | E | F | G | H | I | J | K | L | M | N | O | P | Q | R | S | T | U | V | W | X | Y | Z

<специальный знак>→<знак арифметической операции>|<знак отношения>| <разделитель>|<ключевое слово>

<знак арифметической операции>→ + | - | * | /

<знак отношения >→ = | < | <= | > | >= | <>

разделитель>→ ⎵ (знак пробела) | . | , | ; | : | ( | ) | [ | ] | { | } | ↑ | ‘ | :=

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

Имя (идентификатор)

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

В качестве имён могут использоваться, например, такие последовательности знаков: a, i, counter, z56yfw9q% .

Более конкретные правила образования имен регламентируются в описании языков, и в различных языках и информационных системах эти правила различны. В основном эти правила уточняют приведённое выше общее определение имени. Подробнее о выборе имен см. параграф 7.4.

Данные

В алгоритмах и программах всегда используются какие-либо данные: исходные данные вводятся, затем они как-то обрабатываются и возникают некоторые промежуточные данные, выходные данные — результаты — выводятся: отображаются на дисплее, печатаются на бумаге и т.д.

К данным в алгоритмах и программах относятся:

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

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

В таких случаях целесообразно закрепить за значением какое-либо имя и указывать это имя везде, где требуется использовать значение. Например, чтобы каждый раз не записывать число 3.1415926, следует закрепить за ним имя, скажем, pi и указывать его вместо числа. Такие имена принято называть константами.

В информатике для выполнения действий с такими величинами вводится понятие переменной.

Переменной называется программная конструкция, которая может: 1) принимать значение, 2) сохранять его сколько угодно долго без изменения, 3) при необходимости это значение может быть изменено требуемым образом.

Переменные в алгоритмах рассматриваются как некоторые носители значений, как своеобразные сейфы для их хранения.

Чтобы запомнить некоторое значение его закрепляют за выбранной для этой цели переменной — кладут в «сейф».

Переменная сохраняет значение в неизменном состоянии столько, сколько это требуется алгоритму.

Единственный способ сохранить в алгоритме некоторое значение, а потом его как-то использовать в вычислениях состоит в его закреплении за некоторой переменной в качестве текущего значения. Про такое действие говорят: присваивание значения переменной.

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

Переменные в алгоритмах обозначаются именами, характеризуются типом и имеют, либо не имеют текущего значения

Переменные, не имеющие текущего значения, называются неопределенными, и их использование в алгоритмах существенно ограниченно

Однако с точки зрения программиста данные в алгоритмах и программах всегда наделены некоторым смыслом, определённым образом интерпретируются (англ. interpretation — толкование, объяснение). Скажем, одно и то же число может рассматриваться и как вес товара и как расстояние до некоторой точки.

Любая конкретная интерпретация двоичного кода определяется формой и структурой его представления в программе, которые выбраны программистом. А этот выбор, в конечном счёте, зависит от решаемой задачи и удобства выполнения действий над данными, которые, как видно из примера, могут иметь самую разную природу.

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

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

Тип представляет собой важнейшую характеристику данных, используемых в алгоритмах или программах. Тип определяет: 1)множество допустимых значений переменой, 2)множество операций, которые могут выполняться над этими значениями, 3)структуру значения (скаляр, вектор и т.д.), а также 4) способ машинного представления значения.

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

Над данными разных типов допускается выполнение различных операций. Например, действия сложение и умножение допустимы над числовыми данными, а действия отрицание, конъюнкция и дизъюнкция — над логическими. При этом логические значения складываться и умножаться не могут, а для чисел не определены логические операции.

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

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

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

Тип boolean (char, bool)

Два логических значения false и true. Причем, falseМашинное представление ─ нулевое и единичное значение бита: false кодируется 0, true ─ 1. Операции: ¬, ∨, ∧, =, < и т.д.

В качестве машинного представления этих значений можно было бы использовать состояние одного бита: нулевое значение бита естественно считать кодом значения false, а единичное — кодом значения true. Однако минимальной доступной процессору самостоятельной единицей памяти является байт. В качестве кода значения false выбрано нулевое значение байта 0000 00002, а кодом значения true считается любой ненулевой восьмибитный код.

Тип integer, int

В информатике считается, что данные целого типа всегда задаются абсолютно точно.

Как правило, в алгоритмических языках предусматривается не один целый тип, а семейство целочисленных типов, которые отличаются друг от друга форматом и длиной поля в машинном представлении, и, как следствие, различными диапазонами возможных значений. Эти диапазоны всегда являются подмножествами математического множества Ζ.

Так у целого типа с названиями byte (Паскаль), unsigned char (Си) длина поля равна одному байту, а значение представлено в беззнаковом формате с фиксированной точкой, поэтому множество возможных значений принадлежит интервалу [0, 255].

У стандартного целого типа integer (Паскаль), int (Си) длина поля равна двум байтам и используется знаковое представление формата с фиксированной точкой, отсюда диапазон значений [–32768, 32767].

Над данными целых типов определены арифметические операции сложения ( + ), вычитания ( - ), умножения ( * ), целочисленного деления (div — Паскаль, / — Cи) и остатка от деления (mod — Паскаль, % — Cи).

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

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

Важнейшим для информатики является представление о вещественных данных как о результатах всевозможных измерений или же математических операций над измеренными значениями. В связи с этим вещественные данные считаются принципиально приближенными, неточными. Именно поэтому множество R* вещественных чисел информатики не содержит целых, которые по своей природе являются точными: множество Ζ не пересекается с множеством R*.

Тип real, float

Для значений этого типа выделяются поля длиной 4 байта, точность значений равна 7–8-ми десятичным цифрам, а их модули принадлежат диапазону (1,4×10–45; 3,4× 1038).

Примеры записи вещественных чисел: 7.3 → 7,3; -5.0→ –5,0; 19E6 → 19×106, -1.34E-20 → –1,34×10-20.

Для данных вещественного типа определены все четыре арифметические операции. Результат получается вещественного типа.

Для вещественных типов определены все операции сравнения, но их использование имеет одну особенность.

Несмотря на то, что для вещественных данных разрешается использование операций сравнения «равно» и «не равно», делать это не рекомендуется.

Применение отношений «равно» и «не равно» для вещественных данных некорректно, так как сравнение приближенных чисел в отношении «равно» обычно даёт результат false, а сравнение в отношении «не равно», как правило, имеет результат true.

Кроме того, вместо сравнения вещественных переменных на равенство более корректной является проверка их близости. Например, вместо равенства x=y лучше использовать неравенство вида |x-y|

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

Возьмём, например, отношение 5<>5.0 (Паскаль), 5!=5.0 (Си). обсуждаемое соотношение должно всегда иметь значение false, но скрытые детали реализации трансляторов могут дать любой результат вычислений, что влечёт за собой неоднозначность алгоритма, поэтому таких операций следует всемерно избегать.

п

Множество значений определяется кодовой таблицей и возможностями клавиатуры. Операции: +, =, <, и т.д. Машинное представление: текстовый формат ASCII, Unicode.

Структурированные типы данных

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

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

представлен тремя составляющими его значение координатами x1, x2 и x3.

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

Эта запись означает, что на заданное число необходимо умножить все координаты вектора .

А можно, например, выяснить знак у какой-то конкретной координаты вектора, тогда с помощью номера указывается только требуемая координата: x3>0, и действие сравнения с нулём выполняется только над ней.

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

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

Различают простые (скалярные, неструктурированные) и сложные (составные, структурированные) типы данных.

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

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

Значение скалярного типа представлено ровно одним компонентом (время, температура), значение структурированного типа представлено более чем одним компонентом (вектор, матрица).

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

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

Например, имена x и A обозначают весь вектор и всю матрицу соответственно.

Для выделения отдельного компонента массива в квадратных скобках справа от названия указывается его номер или несколько номеров через запятую: w[5]; w[i+2]; A[1,2].

В языке Си, а также во многих родственных языках при указании отдельного элемента матрицы необходимо каждый индекс записывать в отдельной паре квадратных скобок: элементу матрицы A23 соответствует обозначение A[2][3].

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

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

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

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

В рассматриваемом примере чтобы указать какой месяц входит в дату, применяется составное имя Дата.Месяц, а имя Дата.Год служит для указания на входящий в дату год. Для первой строки таблицы имени Дата соответствует полное значение «9 Мая 1945», а составное имя Дата.Месяц имеет своим значением «Мая».

Описания

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

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

Для переменных и функций тип должен указываться явно. Для такого рода указаний в алгоритмах используются конструкции, которые называются описаниями. В важных частных случаях описание связывает имя константы и её значение, а также имя переменной или функции и её тип.

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

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

<описание константы> const <имя>=<непосредственное значение> (Паскаль)

<описание константы> const <тип><имя>=<непосредствен. значение>(Си).

Пусть, например, имеются описания:

Теперь в любом месте алгоритма имя pi представляет число 3.1425926. Удобство применения констант в алгоритмах в том, что для любого непосредственного значения можно подобрать краткое и запоминающееся имя, которое в любом месте представляет это значение, причём изменить указанное в описании значение константы невозможно.

Заметим, что в этих определениях предполагается, что существуют и определения понятий <непосредственное значение>, <имя>, <тип>. Если их нет, то определение <описание константы> окажется некорректным.

const pi=3.1415926 // Па, const float pi=3.1425926 // Си.

Эта формула понимается следующим образом: «Описание простого типа есть по определению конструкция, состоящая из одного имени или перечисленных через запятую имён переменных, относящихся к одному и тому же типу, за которым через двоеточие указывается имя типа».

Описания простых переменных в Cи определяются немного по-другому:

<описание простого типа> <имя типа> <список имен через запятую>

И в Паскале и в Cи несколько подряд расположенных описаний отделяются друг от друга точкой с запятой.

y: real; b: char; i, j, n, counter: integer; // Па
float y; char a; int i, j, n, counter; // Cи

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

После квадратных скобок следует ключевое слово of (из) и завершается описание указанием типа элементов.

x,у: array[1..3] of real; w: array[1..9] of real; A, В, С: array[1..3, 1..3] of integer // Па

В языке Си описание массива состоит из имени типа элементов массива, за которым расположено имя массива. Далее для вектора в квадратных скобах указывается количество компонент вектора, а для матрицы записываются две пары таких скобок, в первой паре задается количество строк, а во второй — количество столбцов матрицы.

float x[3], w[9]; int A[3][3]; // Cи

Внимание! Нумерация элементов массивов в языке Cи всегда начинается с нуля.

Выражения

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

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

Для наиболее часто используемых на практике элементарных функций в алгоритмических языках определены имена, типы аргументов и результатов, а также способы вычисления их значений. Такие функции принято называть стандартными. Например, для вычисления квадратного корня из некоторого числа можно применить стандартную функцию с названием sqrt (англ. square — квадрат).

Например: sqrt — это имя функции, а sqrt(4.8) — это указатель функции.

Про результат, получающийся при вычислении значения функции, говорят: функция возвращает результат.

Выражения в алгоритмических языках являются практически полным аналогом хорошо известных арифметических и алгебраических выражений. Выражением называется текст, задающий правило вычисления значения

В выражения могут входить: непосредственные значения, константы, переменные и указатели функций, соединённые знаками различных операций.

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

Но в любом случае эти правила обеспечивают стандартный математический порядок старшинства — сначала выполняются действия умножения и деления, а потом умножения и сложения.

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

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

Пусть требуется записать в программе выражение соответствующее дроби:

При записи выражений необходимо также следить за типами, входящих в выражение операндов: они должны обеспечивать возможность выполнения вычислений. Например, запись 'a'+4 является ошибочной, так как невозможно сложить букву с целым числом.

Поскольку «многоэтажные» конструкции в алгоритмических языках запрещены, соответствующее обсуждаемой дроби выражение должно быть записано в одну строчку: a+b/c+d.

Но эта запись ошибочна, так как с учётом старшинства операций получим, что эта строка задаёт такие вычисления:

Необходимый порядок действий можно задать только применив круглые скобки: (a+b)/(c-d).

Примеры отношений: k > i–1, j<=3, x >= sqrt(r*r – y*y)

При записи в алгоритмических языках неравенств вида 0

Ошибка здесь в том, что отношение может включать только два выражения и только один знак отношения

Неравенства вида следует трактовать как два неравенства x>0 и x≤1, которые должны выполняться одновременно, то есть, связаны логической операцией конъюнкция: x>0 ∧ x≤1.

Правильный вариант записи: (x>0) and (x<=1) //Па (x>0) && (x<=1) //Cи

Операторы и управляющие конструкции

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

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

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

В различные алгоритмические языки включены разные наборы операторов. Но этот набор всегда подбирается таким образом, чтобы с их помощью можно было построить любые возникающие при решении практических и теоретических задач алгоритмы.

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

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

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

Присваивание

Присваивание нового значения выполняется независимо от того, определена или нет переменная, которой производится присваивание.

Если переменная была определена, то есть у неё было старое значение, то оно безвозвратно теряется, и установить каким оно было невозможно.

Синтаксис оператора присваивания в простейшем случае определяется следующим образом:

<оператор присваивания> → <Имя> := <Выражение > (Паскаль)
<оператор присваивания> → <Имя> = <Выражение > (Си)

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

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

Заметим, что присваивание может изображаться и другими знаками, в частности, в языке Бейсик для этого используется ключевое слово Let, а в языках ассемблера — mov (от англ. move — движение, передача в другие руки).

Примеры присваиваний:

counter:=0; X:=10.3;Y:= 2.0*X+1.0; n:=4; n:=n+1; w[n+2]:=0.8; //Па

counter=0; X=10.3;Y= 2.0*X+1.0; n=4; n=n+1; w[n+2]=0.8; //Си

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

До начала действия переменная из левой части имеет старое значение или не имеет никакого;
После завершения действия она всегда имеет новое текущее значение.

X

10.3

X

X:=10.3
X=10.3

Неопределенное значение

Старое значение

Новое значение

4

n

Старое значение

5

n

n:=n+1n=n+1

Новое значение

Действие, задаваемое оператором n:=n+1// Па, n=n+1; // Си, состоит в увеличении текущего значения переменной n на единицу. Такой оператор и аналогичные ему встречаются в алгоритмах очень часто, поэтому в языке Cи имеется короткая эквивалентная форма его записи n++;

w[1] w[2] w[3] w[4] w[5] w[6] w[7] w[8] w[9]

w[n+2]:=0.8w[n+2]=0.8

Выполнение действия существенно зависит от текущего значения n. Так при n=5 значение индексного выражения определяет, что получить значение 0.8 должен седьмой элемент массива w.

0.8

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

X : real: C : char; I,J : integer;

X:=0.8;

C:=‘&’;

I:=6;

X:=‘&’;

C:=6;

I:=‘&’;

X:=C+I;

J:=2*J+I

Действие n:=6 n=6

Сравнение n=6 n==6

4

n

Результат

6

n

4

n

Результат

false, 0

4

n

В операции сравнения левая и правая части равноправны, а в действии присваивания ─ не равноправны. В присваивании выражение слева писать нельзя, а в сравнении ─ можно.

n:=6;

n=6;

6:=n;

y:=2*x+1;

2*x+1:=y;

n:=5; j:=8; n:=j;

n:=5; j:=8; j:=n

6=n;

y=2*x+1;

2*x+1=y;

n:=5; j:=8; n=j;

n:=5; j:=8; j=n

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

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

Первая группа действий называется вводом исходных данных, а вторая — выводом результатов. А когда безразлично, о чем идёт речь используется термин обмен.

Эти процедуры как раз и связаны и с аппаратурой компьютера и с языковыми конструкциями программы.

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

read(список вводимых величин) // Па, scan(список вводимых величин) // Cи

а для вывода процедуры —

write(список выводимых величин) // Па, print(список выводимых величин) // Cи

в которых вводимые/выводимые величины представлены в виде списка, состоящего из имён этих величин, перечисляемых через запятую.

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

Структура программы — алгоритма, заданного на алгоритмическом языке, — в значительной мере зависит от используемого языка.

Общая структура программы

Программа на языке Паскаль в простейшем случае имеет вид:

var O1; O2;…;Om begin S1; S2; …; Sn end. // Па

То есть она содержит последовательность описаний O1;O2;…;Om используемых в программе переменных, и последовательность операторов S1;S2; …;Sn, которые задают нужные действия, здесь О и S — условные обозначения описания и оператора соответственно.

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

То есть она состоит из заключённой в фигурные скобки одной последовательности, которая включает в себя и описания, и операторы.

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

В простейшем варианте написания программы на языке Cи перед фигурными скобками указывается имя main (англ. — главный) и пара круглых скобок, конструкции, являющейся частным случаем так называемого заголовка функции, который состоит из имени и заключаемого в круглые скобки списка параметров

Попутно отметим, что пара ключевых слов begin end в Паскале и пара фигурных скобок { } в Си называется операторными скобками, а конструкции begin S1; S2; …; Sn end и { S1; S2; …; Sn; } — составным оператором.

Важно! Заключение последовательности операторов в операторные скобки превращает эту последовательность с точки зрения синтаксических правил языка в один оператор

S1; S2; S3; … ;SN

S1

S2

S3

SN

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

Пример. Обмен значениями двух переменных

Буквальная реализация условия задачи

5

n

8

m

n:=m
n=m

8

8

n

8

m

m:=n
m=n

5

n

8

m

m:=n
m=n

5

5

n

5

m

n:=m
n=m

5

8

k

5

8

5

k=n;
k=n;

n:=m;
n=m;

m:=k;
m=k;