Главная страница «Первого сентября»Главная страница журнала «Информатика»Содержание №2/2009


Век информатики

Фундаментальные элементы компьютерной науки

Окончание. Начало в № 1/2008

3. Избранные разделы и понятия фундаментальной информатики

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

3.1. Избранные понятия фундаментальной информатики

Знаковая система. Согласно Толковому словарю
А.П. Заморина и А.С. Маркова (М.: Русский язык, 1988), знаковая система — это набор знаков с внутренними отношениями между ними, в употреблении которого может быть обнаружена некоторая регулярность употребления каждого знака. Примерами знаковых систем являются: алфавит какого-либо языка, совокупность цифр системы счисления, азбука Морзе, товарный штрих-код и др. Свойства знаковых систем изучает одна из дисциплин, входящих в информатику как науку, — семиотика.

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

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

Алфавит языка — это конечное упорядоченное множество символов некоторого естественного или формального языка. Например, латинский алфавит, кириллица, алфавит десятичной системы счисления (цифры 0, 1, …, 9), алфавит двоичной системы счисления (цифры 1 и 0).

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

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

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

Эвристика. Это понятие имеет несколько значений. 1) В античной философии — “Искусство нахождения истины”. Система логических приемов и методических правил теоретического исследования. 2) Наука, изучающая продуктивное творческое мышление. 3) Метод обучения, способствующий развитию находчивости, активности. 4) В более узком смысле — система исследования теоретической или практической задачи с целью решить ее, исходя из опыта исследователя.

3.2. Понятие о моделях и моделировании

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

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

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

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

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

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

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

Процесс создания (а иногда и исследования) модели называют моделированием.

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

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

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

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

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

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

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

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

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

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

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

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

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

Например, второй закон Ньютона можно изложить словами, а можно описать математической моделью: F = ma (это модель равноускоренного прямолинейного движения).

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

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

Например, в Вычислительном центре Академии наук под руководством академика Н.Н. Моисеева была разработана математическая модель возможных последствий ядерной войны на планете Земля. На основании этой модели, с использованием мощных компьютеров, были проведены численные эксперименты, которые показали, как наивны надежды некоторых людей пережить возможную катастрофу. Этими экспериментами впервые доказано, что людей погубит не ударная волна, не световое излучение и радиация (от которых можно как-то защититься). Людей погубит... мороз, “ядерная зима”, которая наступит на многие годы в результате подъема в атмосферу огромных облаков сажи и пепла от взрывов и пожаров. Эта сажа будет задерживать солнечные лучи, и температура на Земле резко понизится.

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

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

Фундаментальные понятия этих моделей: объект — нечто, существующее, имеющее название и различимое (например, видеокассета); атрибут (cвойство, характеристика объекта; например, название фильма), значение атрибута (например, “Новые Центурионы”).

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

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

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

Если вы желаете составить более точную информационную модель, можно написать на карточках связный рассказ о видеотеке, что-то вроде: “У меня сто сорок пронумерованных кассет. На кассете № 8 хранится мой лучший фильм “Новые Центурионы” с ... в главной роли...”.

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

Поэтому придумаем для видеотеки набор атрибутов. Для каждой кассеты укажем:

· номер кассеты;

· название видеоматериала;

· фамилию режиссера;

· год создания;

· рубрику (исторический, музыкальный, фантастический);

· уровень (отлично, хорошо, средне и т.п.);

· краткое содержание;

· длительность и т.д.

У конкретной кассеты каждый из этих атрибутов примет то или иное значение. Например, на кассете № 17: фильм “Тайна Голубой долины” (текст), год создания 1992 (дата), длительность 110 минут (число) и т.д.

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

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

· тип видеоматериала (художественный фильм, документальный фильм, клип и т.п.);

· персонажи и исполнители;

· сценарист и т.д. и т.п.

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

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

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

3.3. Выражения

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

Например, выражение “Здравствуй, Мир!” состоит из операндов-слов и орфографических знаков “,”, “пробел” и “!”. Выражение может считаться корректным только при соблюдении синтаксиса, то есть правил записи выражений данного типа. Например, если в выражении “Казнить нельзя, помиловать” переставить или убрать запятую, смысл (значение) выражения либо изменится на противоположный, либо будет утерян.

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

В компьютерных технологиях (начиная от программирования и кончая телекоммуникациями) широко используются четыре типа выражений: арифметическое, символьное (текстовое), условное и логическое. Эти выражения пользователи применяют в электронных таблицах, в информационных системах (при создании баз данных и поиске информации), при работе с сетью Интернет. Важная особенность этих выражений заключается в том, что при выполнении операций над данными вырабатывается уникальное значение выражения, которое является либо действительным числом (для арифметического выражения), либо строкой символов (для символьного выражения), либо логическим (булевым) значением (TRUE или FALSE) — для условного и логического выражения. Например, при выполнении операций в выражении 1 + sin(p/2) вырабатывается значение 2. Это значение может быть присвоено любой вещественной переменной (см. п. 3.5).

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

sin(a + b) – c + 5.

Операндами этого выражения могут быть:

— числовые константы;

— числовые переменные;

функции;

— другие арифметические выражения.

При этом константа — это неизменяемое значение, которое может быть выражено явно (число 5 в приведенном примере) или каким-либо именем, которое обозначает постоянную величину. Иногда явно выраженные константы (числовые или символьные — см. ниже) называют литералами (от англ. literal — буквальный). Число 5 в нашем примере — литерал.

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

Функция — это переменная величина, значение которой зависит от значений других величин (аргументов). Функция имеет имя и аргументы, которые обычно записываются через запятую (или через точку с запятой) в круглых скобках — следом за именем функции. Аргументом функции может быть любой операнд. Если функция используется как операнд, она всегда должна возвращать (принимать) уникальное значение (арифметическое, символьное или логическое). Например, функция СТЕПЕНЬ(A2;2,3) в MS Excel возвращает значение ячейки A2, возведенное в степень 2,3. Бывают функции без аргументов (например, СЛЧИС() в MS Excel). В программировании встречаются функции, которые не возвращают никакого значения (они просто выполняют какую-то операцию).

Знаками арифметических операций служат “+” (сложение), “–” (вычитание), “*” (умножение), “/” (деление). Возведение в степень обычно обозначается “**” или “^”. Установлен приоритет (последовательность) выполнения операций в арифметическом выражении: сначала выполняется возведение в степень, затем умножение и (или) деление, затем сложение и (или) вычитание. Последовательность выполнения операций может быть изменена с помощью круглых скобок (первыми выполняются операции в самых внутренних скобках). Результат арифметического выражения — число. Например, 28/2 + 5 = 19, а 28/(2 + 5) = 4.

Символьное выражение. Операндами этого выражения являются строки символов одной из кодовых таблиц. Например, “Лунная”+“ радуга” — это символьное (текстовое) выражение, операнды которого — строки символов “Лунная” и “ радуга”. Для символьного выражения определена только одна операция — конкатенация (сложение строк). Знаком этой операции обычно служит знак “+”, однако в MS Excel знак конкатенации — “&” (амперсанд). Результатом символьного выражения является новая строка символов, в нашем примере — “Лунная радуга”. В зависимости от соглашений языка программирования или приложения строки символов обычно окаймляются прямыми кавычками (как в нашем примере) или апострофами (‘). Следует заметить, что в нашем примере всюду указаны символьные литералы, однако значение строки символов может быть присвоено и символьной переменной (как число — числовой переменной).

Примечание. Обратите внимание, что символ “пробел” — равноправный элемент символьной строки, и там, где он необходим, опускать его нельзя (“ радуга”, но не “радуга”).

Условные и логические выражения рассмотрены в следующем пункте.

3.4. Алгебра логики

Алгебра логики — это один из разделов математической логики, разработанный в XIX веке английским математиком Дж. Булем (отцом известной писательницы Э.Л. Войнич, автора романа “Овод”). В основе алгебры логики лежит исчисление высказываний (т.e. законченных по смыслу предложений), каждое из которых может быть либо истинным (TRUE), либо ложным (FALSE). Например, высказывание “Воробей — птица” является истинным, а высказывание “5 > 12” — ложным. Из таких элементарных высказываний с помощью “логических связок” AND (И), OR (ИЛИ) и др. складываются сложные высказывания, каждое из которых тоже может быть истинным или ложным. Например, сложные высказывания

“Воробей — птица” AND 5 < 12

“Воробей — птица” OR 5 > 12

истинны, а высказывание

“Воробей — хищник” AND 5 < 12

ложно.

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

Условное выражение — это высказывание о значениях операндов, и это высказывание может быть истинным или ложным. Например, если переменная a в момент высказывания имеет значение 6, то высказывание 2 < a является истинным, а высказывание a > 15 — ложным. Результатом условного выражения является логическое (булево) данное, которое может принимать только два значения — “Истина” или “Ложь” (в других формулировках — TRUE или FALSE, “Да” или “Нет”, 1 или 0). Операндами условного выражения могут быть числовые или текстовые константы (строки символов), переменные числового или текстового типа, функции, соединенные между собой знаками операций отношения:

= равно;

<> не равно;

> больше;

< меньше;

<= меньше или равно;

>= больше или равно.

Условное выражение является частным случаем логического выражения.

Логическое выражение — это составное высказывание о значениях нескольких условных выражений. Операндами логического выражения могут быть условные выражения, соединенные между собой знаками логических операций AND или OR (“И” или “Или”). Логическое выражение (так же, как и условное) может принимать только булево значение (“Истина” или “Ложь”). Например, рассмотрим выражения:

d > 5 AND a < 2

d > 5 OR a < 2

Первое высказывание является истинным, если одновременно d > 5 и a < 2 (например, при d = 6 и a = 1), а второе высказывание будет истинным, если истинно хотя бы одно из составляющих его высказываний (например, при d = 6 и любом значении a).

В математике логические операции AND и OR имеют названия:

AND — Конъюнкция (И);

OR — Дизъюнкция (ИЛИ).

Кроме широко распространенных операций AND и OR, существуют следующие логические операции:

XOR — Дизъюнкция II (“исключающее ИЛИ”);

EQV — Эквивалентность;

IMP — Импликация.

Пусть A — первое условное выражение в логической операции, а B — второе. Тогда сводную таблицу значений логического выражения A^B (так называемую таб­лицу истинности), где “^” — обобщенный знак логической операции, можно записать следующим образом (T — “Истина”, F — “Ложь”):

A

B

AND

OR

XOR

EQV

IMP

T

T

T

T

F

T

T

T

F

F

T

T

F

F

F

T

F

T

T

F

T

F

F

F

F

F

T

T

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

Существует унарная логическая операция NOT (отрицание, НЕ), выполняемая над одним выражением. Например, выражение NOT(a > b) истинно, если выражение a > b — ложно, т.е. если a меньше или равно b.

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

((a > b) OR (b > c)) AND NOT ((a > 0) OR (c > a))

устанавливается следующий порядок операций:

Алгебра логики (ее называют также булевой алгеб­рой) широко используется и в математике, и в информационной технологии: в языках программирования, в языках запросов информационных систем, в электронных таб­лицах, даже в языке командных файлов MS-DOS. Для определенности мы привели лишь один из вариантов начертания знаков отношения и логических операций (используемый в MS Access). В отличие от знаков арифметических операций (+, –, *, /) здесь нет стандарта, и в разных случаях (в математике, в языках программирования, в языках запросов) эти знаки могут записываться по-разному. Например, вместо “=” часто пишут “==”, вместо “<>” — сочетание “!=”, вместо AND — “&”, или “&&”, или “and” и т.д. Для понимания принципов это не имеет значения.

Применение алгебры логики. В традиционных курсах информатики алгебра логики излагалась лишь в разделе “Логические основы ЭВМ” и в разделе “Программирование”. Например, как уже говорилось, логические операции — это основа работы процессора, и над парой двоичных кодов процессор может выполнить операции: конъюнкцию (логическое умножение), — например, 1 AND 1 = 1, 0 AND 1 = 0 и т.д.; дизъюнкцию (логическое сложение), — например, 1 OR 1 = 1, 0 OR 1 = 1 и т.д.; исключающее “ИЛИ” (логическое сравнение), — например, 1 XOR 1 = 1,
0 XOR 1 = 0 и т.д. (см. таблицу истинности). По сути, это профессиональные аспекты алгебры логики, и для обычного пользователя они слишком абстрактны и туманны.

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

Пример 1. В ячейке D3 электронной таблицы (MS Excel) мы можем записать выражение, результатом которого является уровень инфляции за текущий месяц (в процентах). В других ячейках, используя аппарат алгеб­ры логики, можно “вычислять” текстовую характеристику инфляции. Например, если D3 < 3 (т.е. значение этого выражения — “Истина”), “инфляция низкая”; если И(D3 >= 3; D3 < 10), “инфляция умеренная” (т.е. значение D3 больше или равно 3 И меньше 10) и т.д.

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

Пол = М AND Дата_рожд. < 01.01.1975.

Система выберет из базы данных людей, для которых это логическое выражение имеет значение TRUE (“Истина”).

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

3.5. Операция присваивания

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

c = a > 5.

В левой части формулы указана логическая (булева) переменная c, которая примет значение TRUE, если значение a больше 5, и FALSE, если a равно или меньше 5.

Вы знаете, что минимальный элемент оперативной памяти (элемент байта) называется битом. Именем (или адресом) бита как переменной можно считать номер разряда байта, в котором этот бит находится (0, 1, ..., 7). Область определения бита — лишь два значения: 0 и 1. Эти же значения являются областью определения логических (или булевых) переменных, которые используются в алгебре логики, рассмотренной в предыдущем пункте.

С другой стороны, минимально адресуемая ячейка оперативной памяти компьютера — байт. Именем (адресом) байта можно считать его порядковый номер в сегменте памяти (0, 1, ... — верхняя граница зависит от способа сегментации памяти и для нас несущественна). Содержимое (значение!) байта можно трактовать по-разному, однако под определенным углом зрения можно сказать, что область определения байта — либо множество целых положительных чисел от 0 до 255, либо множество целых чисел от –128 до +127.

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

В электронных таблицах именем переменной можно считать адрес ячейки, составляемый из обозначения столбца и номера строки, на пересечении которых эта ячейка находится (B2, G14 и т.п.). А вот множество допустимых значений этой “переменной” определяется либо по умолчанию (например, все действительные числа (в допустимом для компьютера диапазоне) или произвольный текст), либо по нашему произволу (числа, текст, даты или время в заданном формате, денежные единицы).

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

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

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

Никогда не смешивайте имя (name) переменной с названием (подписью, заголовком — caption, title), которое часто используется совместно с именем. Например, в заголовке столбца реляционной таблицы или в форме можно указать название (подпись) Текущая дата, в то время как имя этого столбца — Текдата. Компьютер работает исключительно с формализованными уникальными именами, а всякие названия для него — пустой звук.

Операция изменения значения переменной называется присваиванием. Например, если в ячейке электронной таблицы D12 записана формула =С6+5, то мы говорим, что ячейке D12 присваивается значение, которое будет получено в результате сложения значения ячейки C6 с числом 5.

В качестве знака операции присваивания обычно используются “=” или “:=”. Следует отличать знак присваивания от знака отношения “равно” (например, a = b). В качестве последнего используются “=” или “==”. В некоторых языках знаки присваивания и отношения совпадают (что иногда служит источником ошибок).

3.6. Алгоритмы

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

Алгоритмы широко используются во всех сферах человеческой жизни и деятельности — в быту, технике, математике, компьютерных технологиях. Например, результатами исполнения алгоритмов “бытовой сферы” (или “интуитивных”) являются: звонок из кабины междугородного телефона, приготовленное по рецепту блюдо, сборка автомобиля. Математические алгоритмы: вычисление квадратного корня, нахождение наибольшего общего делителя двух чисел и т.п.

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

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

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

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

Предписания, входящие в состав алгоритма, можно разделить на два принципиально разных типа: предписание “Исполнить” и предписание “Проверить”. Например, в блоке 1 рис. 2 (с. 22) содержится предписание “Исполнить” (т.е. вычислить значение дискриминанта — арифметическое выражение с присваиванием), а в блоке 2 — предписание “Проверить” (т.е. проверить значение дискриминанта).

Результатом выполнения предписания “Исполнить” всегда является некоторое значение числового, текстового или иного типа. Например, результатом вычисления дискриминанта является некое действительное (вещественное) число, а результатом соединения двух слов “Лунная” и “ радуга” является строка символов “Лунная радуга”. Предписание типа “Исполнить” может иметь и другой результат. Например, при работе с процессором MS Word вы можете выдать предписание “Напечатать номер страницы в правом нижнем углу”, и результат исполнения этого предписания нельзя отнести ни к числовому, ни к текстовому типу.

Результатом выполнения предписания “Проверить” всегда является одно из двух возможных (логических) значений: “Истина” или “Ложь”, TRUE или FALSE, “Да” или “Нет”. После исполнения такого предписания следующее предписание (типа “Исполнить” или “Проверить”) выбирается в зависимости от полученного при проверке результата (см. блок 2 на рис. 2).

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

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

Основные типы циклов: 1) повторение последовательности команд заданное количество раз (цикл со счетчиком); 2) циклическое выполнение блока команд, пока выполняется (или не выполняется) некоторое условие. Типичная конструкция цикла типа (1) — (FOR... NEXT, ДЛЯ... СЛЕДУЮЩИЙ); примером цикла (2) является конструкция DO WHILE... LOOP (ДЕЛАТЬ ПОКА), записываемая в разных вариантах и по разным правилам синтаксиса.

Если после исполнения очередного предписания в алгоритме выбор следующего предписания зависит от результатов этого исполнения (“Истина” или “Ложь”), такой алгоритм (или участок алгоритма) называется разветвляющимся. Во многих языках типичной командой ветвления является конструкция IF... THEN... ELSE (ЕСЛИ... ТОГДА... ИНАЧЕ), записываемая в разных вариантах и по разным правилам синтаксиса.

В программировании и компьютерных технологиях широко используются вспомогательные алгоритмы, под которыми понимают функции, процедуры или операции, возвращающие какой-либо результат или решающие какую-либо стандартную задачу. Например, почти в любой программе, среди прочих предписаний, можно указать обращение к функции: D = SIN(A*T). Это вспомогательный алгоритм, и в результате его исполнения переменная D примет значение синуса произведения значений переменных A и T. В программе на языке С можно записать функцию putch(zn), и в результате ее исполнения на экран в текущую позицию курсора поступит символ, код которого ранее был присвоен переменной zn. В программе MS Excel щелчком на кнопке панели инструментов можно упорядочить значения ячеек выделенного столбца электронной таблицы и т.п.

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

4. Системы счисления

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

В непозиционной системе счисления значение каждой цифры числа не зависит от ее положения в изображении числа. Например, в римской системе счисления (единственной непозиционной системе, которая иногда употребляется ныне) знак-цифра I обозначает единицы и только единицы, “цифра” V представляет пятерку, “цифра” X — десяток и т.д. Таким образом, XXV = 10 + 10 + 5 = 25, XVIII = 10 + 5 + 1 + 1 + 1 = 18, XI = 10 + 1 = 11, IX = 10 – 1 = 9, XIV = 10 + 5 – 1 =
= 14 и т.п. Непозиционные системы крайне неудобны для представления больших и дробных чисел, для умножения и деления.

В математике и компьютерной технологии используются только позиционные системы счисления. Хорошо знакомая всем десятичная система счисления располагает только десятью арабскими цифрами — 0, 1, 2, ..., 9, — однако это не мешает нам представить с их помощью любое мыслимое число, которое можно изобразить на бумаге. Десятичная система является позиционной, а это означает, что значение каждой цифры числа, представленного в такой системе, определяется ее местом (позицией) в числе. Например, в числе 459 цифра 9 представляет единицы, цифра 5 — десятки, а цифра 4 — сотни. Таким образом, число 459 — это девять единиц, пять десятков и четыре сотни. В числе 495 та же девятка уже представляет десятки, а 5 — единицы (пять единиц, девять десятков и четыре сотни).

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

Основанием десятичной системы является десяток, и поэтому число 459 можно представить суммой

459 = 102 + 5 · 101 + 9 · 100.

Компьютер распознает только две цифры: 0 и 1. В этом случае мы можем говорить о двоичной системе счисления. Эта система тоже является позиционной, но по основанию 2. В двоичной системе каждое число также является суммой произведений цифр числа на степень основания, начиная со степени 0.

Например, число 110 в двоичной системе счисления можно прочитать справа налево так: ноль единиц, одна двойка (21) и одна четверка (22). Просуммировав эти степени, получим, что 110 в двоичной системе является числом 6 в десятичной системе счисления.

Число 1011 можно прочесть так: одна единица, одна двойка, ноль четверок, одна восьмерка, — т.е. 1 + 2 + 0 + 8 = 11; число 1111 = 1 + 2 + 4 + 8 = 15.

В компьютерных технологиях широко используются двоичная и шестнадцатеричная системы счисления (ранее не менее широко применялась и восьмеричная система). В шестнадцатеричной системе — 16 “цифр” (0, 1, ..., 15), а в восьмеричной системе — 8 цифр (0, 1, ..., 7). Между этими системами существует очень простая связь, которую сначала покажем в таблице:

Число

Цифра

Триада

Тетрада

0

0

000

0000

1

1

001

0001

2

2

010

0010

3

3

011

0011

4

4

100

0100

5

5

101

0101

6

6

110

0110

7

7

111

0111

8

8

1000

9

9

1001

10

A

1010

11

B

1011

12

C

1100

13

D

1101

14

E

1110

15

F

1111

Каждая цифра восьмеричного числа (от 0 до 7) может быть представлена двоичной триадой (000, ..., 111). Для обозначения шести старших цифр шестнадцатеричной системы используются латинские буквы A = 10, B = 11, ..., F = 15, и каждая из цифр этой системы может быть представлена двоичной тетрадой (0000, ..., 1111).

Чтобы перевести произвольное двоичное число в восьмеричную или шестнадцатеричную систему счисления, достаточно: 1) разбить его справа налево на триады (тетрады), дополнив старшую триаду (тетраду) нулями (если необходимо); 2) заменить эти триады (тетрады) соответствующими цифрами.

Например:

11010001011101 = 011.010.001.011.101 = 321358

11010001011101 = 0011.0100.0101.1101 = 345D16

Для перевода целого десятичного числа в систему счисления с произвольным основанием используется следующий алгоритм:

1) делим число на основание (базу) системы. В остатке получится младшая цифра искомого числа;

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

Эти операции повторяем до тех пор, пока частное не примет значение, которое меньше основания. Это значение — старшая цифра искомого числа.

На рисунке в качестве примера показан перевод числа 142 в восьмеричную систему счисления: 14210 = 2168.

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

2168 = 010 001 110 = 100011102

и получают двоичное число.

В свою очередь, двоичное число легко разбить на тетрады (справа налево) и получить шестнадцатеричное число:

2168 = 1000 1110 = 8E16

Таким образом: 14210 = 2168 = 8E16.

Обратный перевод в десятичное число выполняется по тривиальному алгоритму, например:

2168 = 2 ґ 82 + 1 ґ 81 + 6 ґ 80 = 14210.

8E = 8 ґ 161 + 14 ґ 160 = 14210.

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

1) для записи относительных или абсолютных адресов оперативной памяти; например, FA1C или A0D34A;

2) для изучения содержимого файла.

В последнем случае файл выдают на экран (например, клавишей F3 в Norton Commander) и переключаются на отображение в шестнадцатеричной системе. Каждый байт будет представлен двузначным шестнадцатеричным числом (от 00 до FF). Например, символ “Возврат каретки” будет отображен числом 0D (1310), а “Новая строка” — числом 0A (1010).

5. Понятие о программировании для ЭВМ

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

Программа-компилятор (от англ. compile — составлять, собирать) переводит исходный текст в машинный код и записывает его на диск в форме исполняемого (загрузочного) файла с расширением exe. После этого программа выполняется независимо от исходного текста. Раньше компиляторы называли трансляторами.

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

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

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

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

Процедурное программирование. Рассмотрим простейший пример — решение квадратного уравнения.

Исходные данные. Значения переменных a > 0, b 0, c 0.

Задача. Вычислить действительные корни уравнения ax2 + bx + c = 0.

Схема алгоритма показана на рис. 2.

В блоке 1 компьютер вычисляет значение дискриминанта d по заданным значениям a, b и c. В блоке 2 это значение проверяется: если оно меньше нуля, компьютер выдает нам сообщение “Решения нет” (блок 4); если d больше или равен нулю, вычисляются квадратный корень из дискриминанта, а затем — значения двух корней (x1 и x2). В частном случае, если d = 0, получаются два равных корня (x1 = x2 = –b/2a). Ниже показан пример записи этого алгоритма на языке BASIC (в среде QBASIC).

Рис. 2. Блок-схема алгоритма решения квадратного уравнения

REM Решение квадратного уравнения

CLS

10 INPUT "Введите a, b, c ", a, b, c

20 d = b * b - 4 * a * c

30 IF d >= 0 THEN

40 ds = SQR(d)

50 x1 = (-b + ds) / (2 * a)

60 x2 = (-b - ds) / (2 * a)

70 PRINT "x1 = "; x1; " x2 = "; x2

80 ELSE PRINT "Решения нет"

90 END IF

100 END

Для решения той же задачи с помощью электронных таблиц MS Excel запишем в ячейки A1, B1 и C1 соответственно a = 2, b = 6 и c = –20, а в ячейку D1формулу расчета дискриминанта: =B1*B1-4*A1*C1 .
В ячейку E1 запишем условную функцию =ЕСЛИ(D1<0;" "; КОРЕНЬ(D1)). Таким образом, если дискриминант меньше нуля, ячейка E1 принимает текстовое (символьное) значение (конкретно — пробел), а в остальных случаях — числовое значение.

Рис. 3. Решение квадратного уравнения в электронной таблице

В ячейки B3 и B4 запишем формулы расчета корней, одна из которых показана на рис. 3 (вычисление корня x1). Функция ЕТЕКСТ возвращает логическое значение “Истина”, если ее аргумент (в данном случае — E1) принимает текстовое значение (пробел). В результате в ячейке B3 появится либо значение корня x1 (переведенное в текстовую форму), либо символьная строка "Решения нет". Аналогичная формула (для x2) записана в ячейку B4.

Объектно-ориентированное программирова­ние (ООП). Приложения графической среды Windows составляются, как правило, на объектно-ориентированных языках. ООП — это современная технология программирования, основанная на идее объекта как некоей самодостаточной сущности, которая объединяет в себе структуры данных (свойства, атрибуты) и поведение (способность совершать какие-то действия). Объектами могут быть документы определенного типа, окна, элементы окон (поля ввода, списки, флажки, радиокнопки) и т.д. Основным понятием ООП является класс как модель набора объектов определенного типа, для которой формально определены структуры данных и поведение (метод класса). В момент исполнения приложения класс сам по себе не существует, — существуют конкретные экземпляры данного класса, поведение которых определяется событиями на компьютере и сообщениями, поступающими от других объектов. Например, в традиционном программировании мы явно присваиваем некоей переменной значение цвета “Синий”, а в ООП — просто приказываем (или “просим”) объект перекраситься в синий цвет.

Среди важнейших понятий ООП: 1) полиморфизм (способность различных объектов по-разному реагировать на одни и те же события); 2) наследование (возможность создания производных классов на основе базового класса с наследованием данных и поведения базового класса); 3) инкапсуляция (сокрытие деталей реализации алгоритма класса от программиста).

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

Развитием идей ООП, связанным с необходимостью ускорить и упростить разработку приложений, является так называемое визуальное программирование — “сборка” приложения или его фрагмента (например, формы) непосредственно на экране с применением технологии “Drag-and-Drop” и готовых блоков-объектов (например, полей ввода, флажков, радиокнопок, списков), перемещаемых указателем мыши. При этом программный код, соответствующий приложению или его фрагменту, генерируется автоматически. Инструментальные средства визуального программирования встраиваются в соответствующую среду разработки (например, в языки 4GL, Visual Basic) или соответствующую СУБД (например, в MS Access). Визуальное программирование играет важную роль в технологиях быстрой разработки приложений (RAD — Rapid Applications Development).

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

1. Существуют машинно-ориентированные языки и языки, условно не зависящие от аппаратной платформы. При программировании на машинном языке команды записывались непосредственно в кодах компьютера. Например, команда сложения двух чисел могла выглядеть примерно так: 14 0127 2677 3656. Число 14, указанное в начале команды, — это код операции, означающий: “Сложить два неких числа и сумму записать в память” (четырехзначные числа — это адреса ячеек памяти). В настоящее время на машинном языке не программируют, однако по-прежнему широко используются машинно-ориентированные языки (языки ассемблера, псевдокоды, языки символического кодирования). В этих языках для представления кодов операций, адресов ячеек, регистров и т.п. применяются их символические обозначения. Например, вместо команды 14 (“Сложить”) может быть записана аббревиатура A (Add). Языки, условно не зависящие от аппаратной платформы, часто называют алгоритмическими языками, или языками высокого уровня. К ним относятся BASIC, FORTRAN, Pascal, C и многие другие.

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

2. Ранее алгоритмические языки классифицировали по назначению и предметной области. Например, считалось, что BASIC удобен для начинающих, FORTRAN — для математических расчетов, COBOL — для коммерческих расчетов, C — для системного программирования и т.д. Однако бурное развитие информационной технологии привело к сглаживанию возможностей языков, и теперь многие из них могут считаться универсальными.

3. Многие специалисты классифицируют языки по поколениям, используя формулу nGL (n = 1, 2, ..., 5), GL = Generation Language: 1GL — машинные языки (например, система команд ЭВМ “Минск-1”); 2GL — машинно-ориентированные языки (ассемблер, псевдокод, язык символического кодирования); 3GL — процедурные языки высокого уровня (BASIC, Pascal, C и т.д.); 4GL, — как правило, объектно-ориентированные языки разработки приложений СУБД, включающие подмножества языков 3GL (например, C, Pascal), собственные операторы и функции, обращения к языкам запросов (типа SQL) и т.п.; 5GL — языки искусственного интеллекта (например, Prolog).

К отдельному классу языков можно отнести различные командные языки баз данных (например, Clipper) и языки запросов (например, SQL — см. ниже).

Ныне наиболее употребительными можно считать объектно-ориентированные диалекты BASIC, Pascal, C++, Java.

В наше время нельзя говорить о языке вне его связи с конкретной реализацией на компьютере, вне связи со средой программирования (или системой программирования, СП). “Официальное” изложение семантики и синтаксиса конкретного языка обычно занимает не более 10–15 страниц, однако в реальных программах мы видим множество функций, процедур, директив, которые даже не предусмотрены в исходной версии. Кроме того, в наше время существует множество “комбинированных” языков, которые включают в себя различные подмножества “классических” алгоритмических языков (например, языки 4GL).

Система программирования — это инструментальный комплекс программ, предназначенный для создания, модификации и отладки программ на том или ином языке (например, QBASIC, Turbo Pascal и др.). Основные элементы процедурной СП: средства управления файлами, текстовый редактор для создания и редактирования исходных текстов, компилятор или интерпретатор, инструментальные средства отладки, средства создания сложных программ (“проектов”) и перекрывающихся модулей (оверлеев) и др.

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

6. Структуры данных в компьютерных технологиях

6.1. Структура и структурирование

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

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

1) Линейная (одномерная, векторная) структура — это просто список некоторых однородных объектов, формально не связанных между собой. Например: список студентов в группе, список домов в микрорайоне, список книг на полке, ряд чисел с результатами измерения какого-либо параметра.

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

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

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

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

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

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

Структурирование информации в каком-либо документе — это введение некоторых соглашений о способах представления и организации данных. В структурированной информации все элементы данных представляются в заранее обусловленных форматах, например: 1) для символьного данного указывается его длина в символах кодовой таблицы; 2) для числового данного — тип числа (целое или с плавающей точкой), длина в байтах (2, 4 и т.п.), диапазон допустимых значений; 3) для даты — представление даты (ДД.ММ.ГГГГ или ММ-ДД-ГГ и т.д.). Кроме того, при структурировании информации указываются способы объединения элементов данных, например: элементы данных об экземпляре объекта (лице, товаре и т.п.) объединяются в строку, строки в таблицу, таблицы в базу данных (файл базы данных). Пример структурированной информации — таблица реляционной базы данных, пример неструктурированной информации — газетная статья.

Принципиальное различие между структурированной и неструктурированной информацией заключается в следующем: только в структурированных документах или базах данных возможен строгий поиск данных по заданным пользователем критериям. Например, указав определенную дату (разумеется, в обусловленном формате), мы можем быть уверены, что система, скажем, создаст полную выборку всех событий за эту дату, зарегистрированных в системе (не упустив ни одного и не показав ни одного лишнего события). Во всех языках имеется множество омонимов, т.е. слов, звучащих и пишущихся одинаково, но обозначающих совершенно разные понятия, — например, “Рак” (созвездие, членистоногое, болезнь). Структурированная система запишет это слово соответственно в графы “Созвездия”, “Животные”, “Болезни” и никогда не ошибется в выборе.

Имманентным (т.е. присущим самой природе) свойством неструктурированной (документальной) системы является ее способность в ответ на запрос, с одной стороны, выдавать пользователю ненужную информацию (например, спутав термины “Рак”), а с другой — не выдавать нужные (например, если автор документа назвал рака омаром).

В зависимости от подхода один и тот же документ иногда можно считать неструктурированным и структурированным. Например, обычный текстовый файл обычно считается неструктурированным документом. Однако если ввести соглашение: каждая строка файла содержит одинаковое число полей переменной длины, разделенных каким-либо разделителем (например, запятой), — файл становится структурированным. Число запятых в каждой строке должно быть одинаковым: если в каком-то поле нет данных, запятая все равно ставится. Уровень структурированности такого файла можно повысить, если ввести соглашения о типе поля, — например, текстовое (от 0 до 255 символов), поле типа даты в заранее обусловленном формате (например, ММ-ДД-ГГ — месяц, день, год) и число (например, –24,89; 14,47 и и т.п.). Разумеется, в каждой строке поле с одним и тем же номером (например, пятое от начала) должно иметь один и тот же тип.

6.2. Адресация в компьютерных технологиях

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

Например, минимально адресуемый элемент оперативной памяти — байт (в ПК) или ячейка той или иной разрядности (в больших ЭВМ). Для указания на конкретный байт (ячейку) используют его (ее) порядковый номер (начиная с 0). Такой адрес может быть относительным (например, номер байта в каком-то сегменте) или абсолютным (если адресное пространство непрерывно). Адрес байта (ячейки) обычно записывают в шестнадцатеричной системе счисления (например, 0F1E).

Минимально адресуемая область памяти на диске — сектор. При этом адрес блока данных, записанных на жестком диске, можно указать в абсолютной форме (цилиндр, головка, дорожка, сектор) или логическими ссылками (имя файла, смещение искомого блока относительно начала файла). Наиболее распространенный формат логического адреса файла на диске: <логический диск>:\<каталоги>\<имя файла>. Например, адрес C:\SIMP\SET\REM.EXE указывает на файл REM.EXE, расположенный в подкаталоге SET каталога SIMP, зарегистрированного в корневом каталоге логического диска C:. При поиске такого файла, используя таблицу размещения файлов — FAT, программы преобразуют его логический адрес в физический (истинный) адрес на диске.

Адрес ячейки в электронной таблице составляется из обозначения столбца и номера строки, на пересечении которых находится эта ячейка. Например: B10, A6, K123 и т.д.

Каждый компьютер в сети Интернет имеет физический адрес (IP-адрес), например: 128.29.15.124, однако на практике используются логические, доменные адреса, например: www.microsoft.com. При поиске нужного компьютера (по адресу) Интернет преобразует его доменный адрес в физический.

Для указания на ресурс Интернета (web-сервер, сайт, страницу) применяется URL (Uniform Resource Locator — унифицированный указатель на ресурс, адрес ресурса Интернета). URL записывается в формате: <протокол>://<сервер (компьютер)><локальный адрес>. Например: http://www.sirena.ru/info, ftp://ftp.citforum.ru/pub/bach.zip. В частном случае адрес ресурса может совпадать с физическим (доменным) адресом компьютера-сервера. Например, доменный адрес web-сервера Microsoft (www.microsoft.com) совпадает с URL-адресом общего ресурса Microsoft.

В больших машинах, если их операционная система использует виртуальную память, применяются так называемые “виртуальные адреса”, т.е. адреса несуществующих ячеек. Дело в том, что система виртуальной памяти увеличивает доступное программам оперативное запоминающее устройство (ОЗУ) за счет использования рабочих областей на диске. Поэтому, если в машине физический объем ОЗУ равен, скажем,
1 миллиону ячеек, программист может указать адрес, например, 2,4 миллиона, и программа будет работать так, как будто в ОЗУ действительно имеется ячейка с адресом 2,4 миллиона.

6.3. Файловые системы

В зависимости от подхода термин “файловая система” можно толковать по-разному.

1. С точки зрения профессионала, файловая система — это таблица размещения файлов (FAT), создаваемая при форматировании жесткого или гибкого диска (см. п. 1.5 в № 1/2009).

Основные файловые системы современных ПК:
1) в MS-DOS и Windows — FAT (File Allocation Table); 2) в Windows старших версий — VFAT (Virtual File Allocation Table, совместимая с FAT); 3) в Windows NT — NTFS (New Technology File System); 4) в OS/2 — HPFS (High Performance File System — высокопроизводительная файловая система).

2. С точки зрения пользователя, в MS-DOS файловую систему компьютера образуют логические диски, каталоги и файлы. Файловую систему Microsoft Windows образуют папки (логический диск в этой системе тоже считается папкой), в которых располагаются служебные файлы, программы и документы, причем последние делятся на документы зарегистрированных и незарегистрированных типов. Файловая система MS-DOS из среды Windows является “классической” иерархической структурой, воспринятой от знаменитой операционной системы UNIX. Управление файловой системой — создание папок и ярлыков, копирование и перемещение папок и файлов, удаление и переименование.

3. Этот термин часто употребляется применительно к упрощенным СУБД (например, построенным на базе модели FMS (File Management System)) — системы управления файлами. Такая система представляет собой совокупность файлов, которые содержат базу данных, но управляются с помощью нестандартных (часто изобретенных программистом) механизмов манипулирования данными.

6.4. Документы

Общие положения. Объектами обработки большинства приложений среды Windows являются файлы, многие из которых выполняют служебные функции и не представляют интереса для пользователя, а многие служат интеллектуальными продуктами, ради которых, собственно, вы и работаете с компьютером. Для таких файлов в ИТ принят единый термин: “документы”. Вот наиболее распространенные ныне документы, с которыми работают сотни миллионов пользователей во всем мире:

— текстовые файлы;

— текстовые документы;

— электронные таблицы;

— файлы презентаций;

— графические изображения растрового формата типа продуктов Paint и Adobe Photoshop и векторного формата типа продуктов CorelDRAW!;

— файлы баз данных (современная БД обычно располагается в одном файле);

— страницы Web и их “спутники”, графические файлы JPG (со статическими (неподвижными) изображениями) и GIF (продукты пакета 3D-Studio), которые могут хранить анимированные изображения.

Каждый документ имеет своего “родителя”, т.е. приложение, которое его создает и обрабатывает (при этом, разумеется, Microsoft не единственный производитель таких приложений). Некоторые документы могут отображаться разными приложениями (например, графические файлы — “вьюерами”), а некоторые приложения могут создавать и обрабатывать разные документы (например, MS Word — файлы форматов DOC, RTF и др.).

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

Например, основные структурные элементы текстового документа:

— документ в целом;

— разделы документа;

— разделы с заголовками (главы, параграфы, пункты, подпункты);

— страницы;

— абзацы;

— колонтитулы;

— сноски;

— примечания;

— графические объекты;

— таблицы и др.

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

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

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

Наконец, особо сложную логическую структуру имеет сеть Интернет, хотя на практике пользователю нужно знать простейшую вещь: URL-адрес нужной страницы. В целом же мы можем найти в Интернете и сетевые, и иерархические, и табличные, и линейные структуры данных (хост-компьютер — сайт — страница), причем сами страницы имеют самую разнообразную организацию (если попытаться сравнивать их с текстовыми документами), и в качестве основных элементов web-страниц нам уместно различать:

— текстовую часть страницы;

— неподвижные изображения;

— интерактивные формы, обеспечивающие двустороннюю связь абонента Интернета с сервером (например, заполнение и отправка анкет, заказов, каких-либо документов);

— активные элементы страницы, обслуживающие воспроизведение звука, анимацию изображений, демонстрацию видеофильмов (видеоклипов) и кинофильмов;

— гиперссылки (как текстовые, так и графические).

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

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

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

“Классическим” примером разницы между логическим и физическим представлением данных служит гиперссылка: на экране вы видите обыкновенный текст (или картинку), выделенный цветом или подчеркнутый, — например, “см. статью Н.Сергеева”, — а физически с этим текстом связан (встроен в него) невидимый для пользователя адрес другого документа (необязательно web-страницы), причем адрес может иметь очень сложную и неудобочитаемую структуру.

6.5. Общее понятие о кодировании информации

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

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

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

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

Наконец, в компьютерных технологиях, помимо прочих систем и способов кодирования, фундаментальный характер имеют: 1) кодирование текстовой (символьной или алфавитно-цифровой) информации; 2) кодирование числовой информации; 3) кодирование изображений. Для кодирования текстовой информации используются кодовые таблицы символов. При кодировании числовой информации различают несколько способов представления числа в памяти компьютера: целые числа (один, два, четыре байта), числа с плавающей точкой (короткие, длинные) и т.п. Следует отличать числа от цифр-символов. Например, цифра “8” принадлежит к текстовой информации и кодируется в таблице ASCII десятичным числом 56, занимающим один байт. Однако число “8” может быть представлено и половиной байта (например, 00001000), и двумя, и даже десятью байтами.

При кодировании изображений различают, с одной стороны, два способа представления изображения — растром (по точкам) и набором математических формул (векторное изображение), а с другой – механизмы создания цветной палитры изображения. Каждый цвет (или оттенок серого как частный случай цвета) представлен целым числом, которое, в зависимости от палитры видеоадаптера или другого устройства отображения (например, принтера), может занимать разное количество бит (например, 2, 4, 8 и т.п.). Для представления цвета фона и цвета символа в стандартном текстовом режиме современных видеоадаптеров используются обычно 4 бита, позволяющих закодировать 16 основных цветов (черный, белый, синий и т.п.). Основной физический механизм образования изображения на экране современного монитора — технология RGB (Red — красный, Green — зеленый, Blue — синий), в которой каждый цвет (оттенок цвета) — это результат смешения в определенных пропорциях трех основных цветов: красного, синего и зеленого.

Кроме того, в компьютерной технологии разработаны различные стандарты кодирования и сжатия (компрессии) звуков и изображений в аудио- и видеофайлах. Например, при кодировании музыки с целью ее воспроизведения с помощью звуковых плат и синтезаторов (имитирующих звучание различных музыкальных инструментов) используется стандарт MIDI (Musical Instrument Digital Interface — цифровой интерфейс музыкальных инструментов).

Коротко о главном в этой статье

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

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

3. Описаны принципы программного управления персональным компьютером — базовая система ввода-вывода (BIOS); общие принципы работы операционных систем.

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

5. На конкретном примере дано понятие о программировании для ЭВМ; изложены принципы объектно-ориентированного программирования как основы создания современных программных продуктов.

6. Подробно рассмотрены структуры данных в компьютерных технологиях; адресация объектов в ИТ; файловые системы с точки зрения пользователя и специалистов по ИТ, а также файловые системы как “суррогат” СУБД.

7. Дано общее представление о кодировании информации.

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

Юр. Ал. Шафрин

TopList