Основные понятия в программировании

Размещено на http://www.allbest.ru/

§ 1. ИНФОРМАЦИЯ, ЕЕ ВИДЫ И СВОЙСТВА

1.1 различные уровни представлений об информации

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

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

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



Рис. 1.1. Схема передачи информации

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

1.2 непрерывная и дискретная информация

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

В случае когда параметр сигнала принимает последовательное во времени конечное число значений (при этом все они могут быть пронумерованы), сигнал называется дискретным, а сообщение, передаваемое с помощью таких сигналов -дискретным сообщением. Информация, передаваемая источником, в этом случае также называется дискретной. Если же источник вырабатывает непрерывное сообщение (соответственно параметр сигнала - непрерывная функция от времени), соответствующая информация называется непрерывной. Непрерывное сообщение может быть представлено непрерывной функцией, заданной на некотором отрезке [а, b] (см. рис. 1.2). Непрерывное сообщение можно преобразовать в дискретное (такая процедура называется дискретизацией). Для этого из бесконечного множества значений этой функции (параметра сигнала) выбирается их определенное число, которое приближенно может характеризовать остальные значения. Один из способов такого выбора состоит в следующем. Область определения функции разбивается точками x1, x2,... хn, на отрезки равной длины и на каждом из этих отрезков значение функции принимается постоянным и равным, например, среднему значению на этом отрезке; полученная на этом этапе функция называется в математике ступенчатой. Следующий шаг - проецирование значений «ступенек» на ось значений функции (ось ординат). Полученная таким образом последовательность значений функции у1, у2, ... уn. является дискретным представлением непреравной функции, точность которого можно неограниченно улучшать путем уменьшения длин отрезков разбиения области значений аргумента.

Рис. 1.2. Процедура дискретизации непрерывного сообщения

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

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

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

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

1.3 ЕДИНИЦЫ КОЛИЧЕСТВА ИНФОРМАЦИИ: ВЕРОЯТНОСТНЫЙ И ОБЪЕМНЫЙ ПОДХОДЫ

Определить понятие «количество информации» довольно сложно. В решении этой проблемы существуют два основных подхода. Исторически они возникли почти одновременно. В конце 40-х годов XX века один из основоположников кибернетики американский математик Клод Шеннон развил вероятностный подход к измерению количества информации, а работы по созданию ЭВМ привели к «объемному» подходу.

Вероятностный подход

Рассмотрим в качестве примера опыт, связанный с бросанием правильной игральной кости, имеющей N граней (наиболее распространенным является случай шестигранной кости: N = 6). Результаты данного опыта могут быть следующие: выпадение грани с одним из следующих знаков: 1,2,... N.

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

H = f (N), (1.1)

а сама функция f является возрастающей, неотрицательной и определенной (в рассматриваемом нами примере) для N = 1, 2,... 6.

Рассмотрим процедуру бросания кости более подробно:

1) готовимся бросить кость; исход опыта неизвестен, т.е. имеется некоторая неопределенность; обозначим ее H1;

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

3) обозначим неопределенность данного опыта после его осуществления через H2. За количество информации, которое получено в ходе осуществления опыта, примем разность неопределенностей «до» и «после» опыта:

I = H1 - H2 (1.2)

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

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

X=NM. (1.3)

Так, в случае двух бросаний кости с шестью гранями имеем: Х = 62 = 36. Фактически каждый исход Х есть некоторая пара (X1, X2), где X1 и X2 - соответственно исходы первого и второго бросаний (общее число таких пар - X).

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

f(6M) = M • f(6)

Данную формулу можно распространить и на случай любого N:

F(NM) = M • f(N) (1.4)

Прологарифмируем левую и правую части формулы (1.3): ln X = M • ln N, М = ln X/1n M. Подставляем полученное для M значение в формулу (1.4):

Обозначив через К положительную константу , получим: f(X) = К • lп Х, или, с учетом (1.1), H=K • ln N. Обычно принимают К = 1 / ln 2. Таким образом

H = log2 N. (1.5)

Это - формула Хартли.

Важным при введение какой-либо величины является вопрос о том, что принимать за единицу ее измерения. Очевидно, Н будет равно единице при N = 2. Иначе говоря, в качестве единицы принимается количество информации, связанное с проведением опыта, состоящего в получении одного из двух равновероятных исходов (примером такого опыта может служить бросание монеты при котором возможны два исхода: «орел», «решка»). Такая единица количества информации называется «бит».

Все N исходов рассмотренного выше опыта являются равновероятными и поэтому можно считать, что на «долю» каждого исхода приходится одна N-я часть общей неопределенности опыта: (log2 N)1N. При этом вероятность i-го исхода Рi равняется, очевидно, 1/N.

Таким образом,

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

Объемный подход

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

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

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

1.4 СВОЙСТВА ИНФОРМАЦИИ

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

Рассмотрим некоторый набор свойств информации:

* запоминаемость;

* передаваемость;

* преобразуемость;

* воспроизводимость;

* стираемость.

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

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

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

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

§ 2. АЛГОРИТМ И ЕГО СВОЙСТВА

2.1 РАЗЛИЧНЫЕ ПОДХОДЫ К ПОНЯТИЮ «АЛГОРИТМ»

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

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

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

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

2.2 понятие исполнителя алгоритма

Понятие исполнителя невозможно определить с помощью какой-либо формализации. Исполнителем может быть человек, группа людей, робот, станок, компьютер, язык программирования и т.д. Важнейшим свойством, характеризующим любого из этих исполнителей, является то, что исполнитель умеет выполнять некоторые команды. Так, исполнитель-человек умеет выполнять такие команды как «встать», «сесть», «включить компьютер» и т.д., а исполнитель-язык программирования Паскаль - команды WRITE, END, READ и другие аналогичные. Вся совокупность команд, которые данный исполнитель умеет выполнять, называется системой команд исполнителя (СКИ).

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

Рис. 2.1. Исполнитель-робот

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

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

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

2.3 графическое представление алгоритмов

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

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

Рис.2.2. Три типа вершин графа

На рис. 2.2 изображены «функциональная» (a) вершина (имеющая один вход и один выход); «предикатная» (б) вершина, имеющая один вход и два выхода (в этом случае функция Р передает управление по одной из ветвей в зависимости от значения Р (Т, т.е. true, означает «истина», F, т.е. false - «ложь»); «объединяющая» (в) вершина (вершина «слияния»), обеспечивающая передачу управления от одного из двух входов к выходу. Иногда вместо Т пишут «да» (либо знак +), вместо F- «нет» (либо знак -).

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

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

Рис. 2.3. Структура «следование»

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

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

Эта структура называется также «ЕСЛИ - ТО - ИНАЧЕ», или «развилка». Каждый из путей (ТО или ИНАЧЕ) ведет к общей точке слияния, так что выполнение программы продолжается независимо от того, какой путь был выбран.

Рис. 2.4. Структура «ветвление»

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

Рис. 2.5. Структура «неполное ветвление»

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

Цикл начинается с проверки логического выражения. Если оно истинно, то выполняется «a», затем все повторяется снова, пока логическое выражение сохраняет значение «истина». Как только оно становится ложным, выполнение операций «а» прекращается и управление передается по программе дальше.

Рис. 2.6. Структура цикла «пока»

Рис. 2.7. Структура цикла «до»

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

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

1) возможность создания программы несколькими программистами;

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

3) упрощение отладки программы - поиска и устранения в ней ошибок;

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

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

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

Рис.2.8. Некоторые дополнительные конструкции для изображения блок-схем алгоритмов

2.4. СВОЙСТВА АЛГОРИТМОВ

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

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

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

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

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

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

§ 3. ПРОГРАММИРОВАНИЕ

3.1 классификация языков программирования

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

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

Принципиально иное направление в программировании связано с методологиями (иногда говорят «парадигмами») непроцедурного программирования. К ним можно отнести объектно-ориентированное и декларативное программирование. Объектно-ориентированный язык создает окружение в виде множества независимых объектов. Каждый объект ведет себя подобно отдельному компьютеру, их можно использовать для решения задач как «черные ящики», не вникая во внутренние механизмы их функционирования. Из языков объектного программирования, популярных среди профессионалов, следует назвать прежде всего Си++, для более широкого круга программистов предпочтительны среды типа Delphi и Visual Basic.

Рис. 3.1. Классификация языков программирования

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

3.2 ПОНЯТИЕ О ЯЗЫКАХ ПРОГРАММИРОВАНИЯ ВЫСОКОГО УРОВНЯ

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

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

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

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

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

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

Языки программирования, имитирующие естественные языки, обладающие укрупненными командами, ориентированными на решение прикладных содержательных задач, называют языками «высокого уровня». В настоящее время насчитывается несколько сотен таких языков, а если считать и их диалекты, то это число возрастет до нескольких тысяч. Языки программирования высокого уровня существенно отличаются от машинно-ориентированных (низкого уровня) языков. Во-первых, машинная программа в конечном счете записывается с помощью лишь двух символов 0 и 1. Во-вторых, каждая ЭВМ имеет ограниченный набор машинных операций, ориентированных на структуру процессора. Как правило, этот набор состоит из сравнительно небольшого числа простейших операций, типа: переслать число в ячейку; считать число из ячейки; увеличить содержимое ячейки на +1 и т.п. Команда на машинном языке содержит очень ограниченный объем информации, поэтому она обычно определяет простейший обмен содержимого ячеек памяти, элементарные арифметические и логические операции. Команда содержит код и адреса ячеек, с содержимым которой выполняется закодированное действие.

Языки программирования высокого уровня имеют следующие достоинства:

* алфавит языка значительно шире машинного, что делает его гораздо более выразительным и существенно повышает наглядность и понятность текста;

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

* конструкции команд (операторов) отражают содержательные виды обработки данных и задаются в удобном для человека виде;

* используется аппарат переменных и действия с ними;

* поддерживается широкий набор типов данных.

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

3.3. ВВЕДЕНИЕ В ПАСКАЛЬ

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

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

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

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

Программа I

program KvadUravn; (заголовок программы)

var (список переменных)

а,b,с: real; (коэффициенты уравнения)

d,xlx2: real; (вспомогательные переменные)

begin (начало программы)

writein; (пропуск строки на экране)

writein('введи a,b,c'); read(а,Ь,с); (ввод данных)

d:=b*b-4*a*c; (дискриминант)

if d<0 then (если d<0, то)

write('корней нет') (печатать)

else (иначе)

begin (начало серии команд)

xl:=(-b+sqrt(d))/(2*a);

x2:=(-b-sqrt(d))/(2*а); (вычисляем корни)

write('х1=',х1,' х2=',х2) (печать корней)

end (конец серии)

end. (конец программы)

Схематически программа представляется в виде последовательности восьми разделов:

1) заголовок программы;

2) описание внешних модулей, процедур и функций;

3)описание меток;

4) описание констант;

5) описание типов переменных;

6) описание переменных;

7) описание функций и процедур;

8) раздел операторов.

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

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

3.4. ОСНОВНЫЕ КОНСТРУКЦИИ ЯЗЫКА

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

Реализация последовательности действий (т.е. структуры следования) выполняется с помощью составного оператора:

begin <последовательность операторов> end

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

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

Структура и действие условного оператора таковы:

If <логическое выраженне>

then <оператор 1>

else <оператор 2>

Условный оператор может быть неполным, т.е. не содержать часть «else <оператор 2>». В этом случае, если значение логического выражения равно false, условный оператор не вызывает никаких действий.

Оператор варианта имеет следующую форму:

case <выражение> of

<список констант 1> : <оператор 1>;

<список констант 2> : <оператор 2>;

…………………………

<список констант N> : <оператор N>

end.

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

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

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

Цикл с предусловием является наиболее мощным в Паскале. Другие операторы цикла можно выразить через него. Его форма такова:

while - <логическое выражение> do <оператор>

Действие: вычисляется значение логического выражения. Если оно равно true, то выполняется оператор, после чего снова вычисляется значение логического выражения, в противном случае действие заканчивается.

Оператор цикла с постусловием имеет форму:

repeat <последовательность операторов>

until <логическое выражение>

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

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

Форма 1:

for <параметр>:= <выражение 1> to <выражение 2> do <оператор>

Форма 2:

for <параметр>:=<выражение 1> downto <выражение 2> do <оператор>

3.5. СТРУКТУРЫ ДАННЫХ

Мы уже познакомились с простыми типами real, integer, boolean, byte, char.

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

Описание перечисляемого типа выполняется в разделе типов по схеме:

type <имя типа> = <список имен>

Примеры:

type operator = (plus,minus,multi, divide);

color = (white,red,blue,yelow,purple,green);

В списке должно быть не более 256 имен.

Поскольку перечисляемый тип относится к ординальным, то к его элементам можно применять функции ord(x), pred(x), succ(x) и операции отношения. Отметим, что данные этого типа не подлежат вводу и выводу с помощью функций ввода/вывода и могут использоваться внутри программы для повышения ее читабельности и понятности.

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

type days=(mon,tue,wed,thu,fri,sat,sun);

workday s=mon.. fri;

index=1..30;

letter='a'..'z';

Можно задать интервал и в разделе переменных:

var a:1..100;b:-25..25;

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

3.6. ПРОЦЕДУРЫ И ФУНКЦИИ

Описание и вызов. В Паскале подпрограммы называются процедурами и функциями и описываются в разделе с тем же названием.

Процедура имеет такую же структуру, как и программа, но с двумя отличиями:

* заголовок процедуры имеет другой синтаксис и включает служебное слово procedure;

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

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

procedure <имя> (<список описаний формальных параметров>) Описание формальных параметров может иметь вид

<список имен>: <тип> или var <список имен>: <тип>

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

Оператор вызова процедуры имеет вид

<имя процедуры> (<список выражений>);

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

Параметры-переменные следует использовать для представления результатов процедуры.

Функция - это подпрограмма, определяющая единственное скалярное, вещественное или строковое значение. Отличия подпрограммы-функции от процедуры:

* заголовок функции начинается со служебного слова function и заканчивается указанием типа значения функции:

function <имя> (список описаний формальных параметров): <тип>;

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

* обращение к функции - не оператор, а выражение вида

<имя функции> (<список фактических параметров>).

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

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

Бывают случаи, когда одни и те же подпрограммы могут использоваться в различных программах одного и даже нескольких пользователей. В подобных ситуациях целесообразно создавать внешние подпрограммы, которые можно в необходимый момент подключать в любые программы. Как правило, внешние подпрограммы объединяют в отдельные пакеты, так называемые, библиотеки внешних подпрограмм. Могут создаваться личные библиотеки, специализированные библиотеки коллективного пользования и др. С одной из таких библиотек - встроенной библиотекой стандартных подпрограмм - пользователи имеют дело практически всегда. В состав этой библиотеки входят процедуры и функции вычисления значений ряда элементарных функций: синуса, косинуса, экспоненты и т.д., процедуры и функции обработки символьных величин, процедуры ввода-вывода и др. (список их приведен в конце § 3). Встроенная библиотека подключается к любой программе автоматически при компиляции. Поэтому откомпилированный файл с расширением .corn (иногда называемый «комовским»), как правило, занимает в 8 -10 раз больше места в памяти, чем исходный текст.

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

Модули используют в более поздних версиях Паскаля для создания библиотек и разделения больших программ на логически связанные независимые друг от друга составные части. В состав модуля входят следующие разделы: заголовок, интерфейс, реализация, инициализация. Заголовок необходим для ссылок на модуль. Интерфейс содержит объявления, включая процедуры и функции, представленные списком заголовков и доступные пользователям в теле основной программы. Раздел «реализация» содержит тела процедур и функций, перечисленных в интерфейсной части модуля. Раздел «инициализация» содержит операторы, необходимые для инициализации модуля. Таким образом модуль - это набор констант, типов данных, переменных, процедур и функций. Каждый модуль компилируется отдельно; результат компилляции - файл с расширением .tpu (Turbo Pascal Unit). Каждый элемент модуля можно использовать в программе пользователя без дополнительного объявления, для чего достаточно записать имя используемого модуля в директиве Uses в начале программы после его заголовка.

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

uses <имя модуля>

Программист может сам создать модуль. Ниже приведен пример с соответствующими комментариями.

3.7. работа с файлами

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

Файлы позволяют решить две проблемы:

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

2) взаимодействие программ с внешними устройствами ввода-вывода: дисплеем, принтером, АСП и т.п.

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

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

type <имя файлового типа> = file of <тип компонентов>

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

Описание файловой переменной задается обычным способом в разделе описаний. Например:

var f: intfile; или var f: file of integer;

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

assign (<имя файловой переменной>,'<имя устройства>')

Как правило, файлы для хранения данных связаны с устройством внешней памяти на магнитных носителях (дисковод) и носят название внешние файлы. Если, например, файл с именем primer, dat логически связан с дисководом А:, то все данные, помещаемые в файл, будут храниться на этом дисковом накопителе, a установка «окна» между программой и файлом будет определяться через файловую переменную f оператором

assign (f, 'primer.dat')

Если внешним устройством является принтер, то связь осуществляется оператором assign(f, '1st:'). Здесь 1st - логическое имя печатающего устройства. Ниже приведены логические имена внешних устройств ввода-вывода:

con - консоль; trm - терминал; kbd - клавиатура; 1st - принтер; aux - буфер сети;

usr-драйвер пользователя.

После осуществления связи файловая переменная f отождествляется с соответствующим файлом.

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

Чтение и запись данных осуществляется известными командами read/write, только в начале списка помещается имя файловой переменной:

read (f, <список ввода>); readln (f, <список ввода>);

write(f, <список вывода>); writeln(f, <список вывода>).

Закрытие файла осуществляется командой close(f).

3.8 РАБОТА С ГРАФИКОЙ

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

Модуль представляет собой мощную библиотеку графических подпрограмм универсального назначения, рассчитанную на работу с наиболее распространенными графическими адаптерами CGA, EGA, VGA, SVGA IBM-совместимых персональных компьютеров.

Подключение модуля Graph, tpu к программе выполняется директивой

uses graph;

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

Некоторые сведения о драйверах н определяемых ими режимах

Адаптер	Драйвер	Режим (Номер, имя)	Разрешимость	Число страниц
EGA	EGA	OEgalo	640х200	4
		1 Egahi	640х350	2
VGA	VGA	OVgalo	640х200	4
		IVgalo	640х350	2
		2Vgalo	640х480	1

Процедура инициализации в Турбо-Паскале имеет три аргумента:

Initgraph(<драйвep>, <режим>, '<путь к драйверу>').

Она может быть выполнена так:

uses graph;

var gd, gm: integer; {переменные gd и gm определяют драйвер и режим}

begin

gd:=vga; gm:=vgahi;

initgraph(gd,gm.'d:\tp55);

Первые две команды можно заменить одной:

gd:=detect

Целая константа detect=0 в модуле Graph автоматически распознает драйвер и устанавливает режим максимального разрешения для данной машины.

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

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

Для формирования палитры используется система смешения красного, зеленого и синего цветов и изменения яркости луча. Цвет задается номером из списка цветов палитры в интервале 0 .. 15.

Процедуры sе1со1ог(<цвет>) и setbkcolor(<цвет>) устанавливают текущий цвет рисунка и цвет фона. При инициализации графики по умолчанию устанавливается черный фон и белый цвет рисунка.

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

Основные процедуры модуля Graph

Заголовок процедуры	Геометрический смысл
putpixel(x,y,c)	Построить точку (х,у) цветом с
setlinestyle(a,b,t)	Установить стиль, образей и толщину линий
line(xl,yl,x2,y2)	Соединить две точки отрезком
rectangle(xl,yl.x2.y2)	Построить прямоугольник с заданными концами диагонали и
	сторонами, параллельными осям координат
circle(x,y,r)	Построить окружность с центром (х,у) и радиусом г
arc(x,y,a,b,r)	Построить дугу окружности: a,b - начальный и конечный угол в
	Градусах
ellipse(x,y,a,b,rx,ry)	Построить эллиптическую дугу: rx, rу - полуоси эллипса
setfillstyle(t,c)	Установить стиль закраски и ее цвет
fillellipse(x,y,rx,ry)	Построить закрашенный эллипс, используя цвет рисунка
floodfill(x,y,cg)	Закрасить фигуру до границы с цветом cg; (x,y) - внутренняя
	точка фигуры
bar(xl,yl,x2,y2)	Построить столбец, используя тип и цвет закраски
pieslice(x,y,a,b.r)	Построить и закрасить сектор круга
sector(x,y.a,b,rx,ry)	Построить и закрасить эллиптический сектор
settextsiyle(f,n,d)	Установить шрифт, направление вывода и размер символа текста '
outtextxy(x,y,st)	Вывести строку st, начиная с точки (х,у)
outtext(st)	Вывести строку, начиная с точки расположения текущего указателя

§ 4. базы данных и системы управления базами данных

4.1 ПОНЯТИЕ ИНФОРМАЦИОННОЙ СИСТЕМЫ

информация программирование алгоритм база

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

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

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

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

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

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

Предположим мы хотим собрать информацию про альбомы музыкальных групп. Пусть имеется информация о некоторых альбомах: 1965, Led Zeppelin 4, Lp, Help!, Atlantic, 1971. Lp(England), EMI. 1970, Flash Gordon, Parlophone, 1980, Led Zeppelin 3, Soundtrack, Lp, Atlantic. Этот список мало о чем говорит. Извлечь какую-либо информацию из этого набора данных практически невозможно.

...