Как осуществляется структурирование текста на алгоритмическом языке

Уроки 31 — 32
Алгоритмы, структуры алгоритмов, структурное программирование

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

1. Постановка задачи. 2. Формализация задачи. 3. Построение алгоритма. 4. Составление программы на языке программирования. 5. Отладка и тестирование программы. 6. Проведение расчетов и анализ полученных результатов.

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

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

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

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

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

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

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

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

Понятие алгоритма

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

В наше время понятие алгоритма трактуется шире.

Алгоритм — это последовательность команд управления каким-либо исполнителем.

В школьном курсе информатики с понятием алгоритма, с методами построения алгоритмов ученики впервые знакомятся на примерах учебных исполнителей: Робота, Черепашки, Чертежника и др. В учебнике для 9 класса описан графический исполнитель — ГРИС. Эти исполнители ничего не вычисляют. Они создают рисунки на экране, перемещаются в лабиринтах, перетаскивают предметы с места на место. Таких исполнителей принято называть исполнителями, работающими в обстановке.

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

Данные и величины

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

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

Например, при решении квадратного уравнения: ах 2 + bх + с = 0 исходными данными являются коэффициенты а, b, с; результатами — корни уравнения х₁, х₂; промежуточными данными — дискриминант уравнения: D = b 2 — 4ас.

Для успешного освоения программирования необходимо усвоить следующее правило: всякая величина занимает свое определенное место в памяти компьютера. Иногда говорят — ячейку памяти. Хотя термин «ячейка», с точки зрения архитектуры современных компьютеров, несколько устарел, однако в учебных целях его удобно использовать.

У всякой величины имеются три основных свойства: имя, значение и тип. На уровне команд процессора величина идентифицируется адресом ячейки памяти, в которой она хранится. В алгоритмах и языках программирования величины делятся на константы и переменные. Константа — неизменная величина, и в алгоритме она представляется собственным значением, например: 15, 34.7, ‘k’, true. Переменные величины могут изменять свои значения в ходе выполнения программы и представляются символическими именами — идентификаторами, например: X, S2, cod15. Любая константа или переменная занимают ячейку памяти, а значение этих величин определяется двоичным кодом в этой ячейке.

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

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

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

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

К структурированным величинам относятся массивы, строки, множества и др.

Компьютер — исполнитель алгоритмов.

Как известно, всякий алгоритм (программа) составляется для конкретного исполнителя, в рамках его системы команд. О каком же исполнителе идет речь в теме «Программирование обработки информации»? Ответ очевиден: исполнителем является компьютер. Точнее говоря, исполнителем является комплекс: компьютер + система программирования (СП). Программист составляет программу на том языке, на который ориентирована СП. Схематически это изображено на рис. 3.2, где входным языком исполнителя является язык программирования Паскаль.

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

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

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

Вопросы и задания

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

2. Дайте определение алгоритма.

3. Что такое «система команд исполнителя алгоритмов» (СКИ)?

4. Какими возможностями обладает компьютер как исполнитель алгоритмов?

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

6. Перечислите различные варианты классификации данных.

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

Структура алгоритмов

Базовые алгоритмические структуры

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

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

Следование — это линейная последовательность действий (рис. 3.3).

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

Ветвление — алгоритмическая альтернатива. Управление передается одному из двух блоков в зависимости от истинности или ложности условия. Затем происходит выход на общее продолжение. Вот как изображается ветвление на блок-схеме и АЯ (рис. 3.4).

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

Неполная форма ветвления имеет место, когда на ветви «нет» пусто (рис. 3.5).

Цикл — повторение некоторой группы действий по условию. Различают два типа цикла. Первый — цикл с предусловием: цикл-пока (рис. 3.6).

Пока условие истинно, выполняется серия, образующая тело цикла.

Второй тип циклической структуры — цикл с постусловием: цикл-до (рис. 3.7).

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

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

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

Комбинации базовых структур

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

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

Структурный подход требует соблюдения стандарта в изображении блок-схем алгоритмов. Чертить их нужно так, как это делалось во всех приведенных примерах. Каждая базовая структура должна иметь один вход и один выход. Нестандартно изображенная блок-схема плохо читается, теряется наглядность алгоритма. Несколько примеров структурных блок-схем алгоритмов приведены на рис. 3.8 (вместо «да», «нет» здесь использованы знаки « + » и «-», У — , С — ).

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

1. Вложенные ветвления. Глубина вложенности равна единице.
2. Цикл с вложенным ветвлением.
3. Вложенные циклы-пока. Глубина вложенности — 1.
4. Ветвление с вложенной последовательностью ветвлений на положительной ветви и с вложенным циклом-пока на отрицательной ветви.
5. Следование ветвления и цикла-до.
6. Вложенные циклы. Внешний — цикл-пока, внутренний — цикл-до.

Наглядность структуре описания алгоритма на АЯ придает структуризация внешнего вида текста.

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

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

Для приведенных на рис. 3.8 блок-схем структура текста на АЯ должна быть следующей:

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

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

Вопросы и задания

1. Перечислите основные базовые алгоритмические структуры и покажите способы их отображения на блок-схемах и в АЯ.

2. Какой алгоритм называется структурным?

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

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

5. Для данного натурального числа N требуется вычислить сумму: 1 + 1/2 + 1/3 + . + 1/N. Постройте блок-схемы и напишите на АЯ два варианта алгоритма: с циклом-до и с циклом-пока.

6. Какую структуру будет иметь алгоритм решения следующей задачи? Дано целое положительное число N. Если N — четное, то вычислить N! = 1 • 2 • . • N. Если N — нечетное, то вычислить сумму: 1 + 2 + . + N.

Составьте блок-схему алгоритма решения и опишите его на АЯ.

Паскаль — язык структурного программирования

Программирование для ЭВМ — процесс создания программ управления работой компьютера.

Эволюция программирования

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

Такая команда называется трехадресной. Код 02₁₆ относится к команде сложения. 1-й и 2-й адреса — это адреса ячеек ОЗУ, в которых хранятся слагаемые, 3-й адрес — адрес ячейки, куда заносится сумма. Сама команда хранится в ячейке ОЗУ с адресом 28₁₆.

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

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

ADD а, Ь, с

Слово ADD обозначает команду «сложить», а и b — имена переменных-слагаемых, с — переменная, куда помещается результат.

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

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

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

Языки программирования высокого уровня

Следующим этапом развития программирования стало создание языков программирования высокого уровня — ЯПВУ. Примеры ЯПВУ: Паскаль, Бейсик, Фортран, Си, Java и др. Все названные ЯПВУ относятся к так называемой процедурной парадигме программирования. Поэтому их называют процедурными языками программирования. Программы на таких языках представляют собой последовательности команд, описывающих действия (процедуры) компьютера по обработке информации. Существуют другие парадигмы программирования. Относящиеся к ним языки называют декларативными языками программирования (Пролог, Лисп и др.). Однако мы их рассматривать не будем.

Для каждого языка существует машинно-независимый стандарт. Возможность программирования на данном ЯПВУ зависит от наличия на вашем компьютере транслятора с этого языка. Трансляторы для каждого типа компьютера создают системные программисты.

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

с=а+Ь (на Фортране, Бейсике, Си).

Освоить программирование на языке высокого уровня гораздо проще, чем на ассемблере. Поэтому с появлением ЯПВУ значительно возросло число прикладных программистов, расширилось применение ЭВМ во многих областях.

Большое количество языков программирования появилось в 1960-1970-х годах. В 1965 году в Дартмутском университете был разработан язык Бейсик. По замыслу авторов это простой, легко изучаемый язык, предназначенный для программирования несложных расчетных задач. Наибольшее распространение Бейсик получил с появлением микроЭВМ и персональных компьютеров.

История Паскаля

Язык программирования Паскаль был создан швейцарским профессором Никлаусом Виртом в 1969 году как язык для обучения студентов структурной методике программирования. Язык получил свое название в честь Блеза Паскаля, изобретателя первого вычислительного механического устройства. Позднее фирма Borland International, Inc (США) разработала систему программирования Турбо Паскаль для персональных компьютеров, которая вышла за рамки учебного применения и стала использоваться для научных и производственных целей. В Турбо Паскаль были внесены некоторые дополнения к базовому стандарту Паскаля, описанному Н. Виртом.

Со временем язык развивался. Начиная с версии 5.5, в Турбо Паскаль вводятся средства поддержки объектно- ориентированного программирования (ООП). В дальнейшем это привело к созданию Object Pascal — языка с возможностями объектно-ориентированного программирования. В начале 1990-х годов объединение элементов ООП в Паскале с визуальной технологией программирования привело к созданию системы программирования Delphi.

Структура процедурных языков программирования высокого уровня

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

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

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

Синтаксис — это правописание языковых конструкций (имен, констант, выражений, операторов и пр.).

Семантика — это смысловое содержание языковой конструкции.

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

Структура программы на Паскале

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

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

В Турбо Паскале, в отличие от базового стандарта Паскаля, возможно:
• отсутствие заголовка программы;
• разделы Const, Type, Var, Label могут следовать друг за другом в любом порядке и повторяться в разделе описаний сколько угодно раз.

Вопросы и задания

1. В каком виде составлялись программы для первых компьютеров?

2. Чем отличались программы на автокодах (ассемблерах) от программ в машинных кодах?

3. Почему ЯПВУ являются машинно-независимыми языками программирования?

4. Что такое трансляция?

5. В какой парадигме программирования реализован язык Паскаль?

6. Что входит в структуру любого процедурного ЯПВУ?

7. Из каких основных разделов состоит программа на Паскале?

Cтруктурирование информации

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

Информация является крупнейшим стратегическим ресурсом современного общества.

Но это только один аспект современной трактовки термина.

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

Слово «информация» произошло от латинского понятия, которое означает разъяснение, высказывание и осведомленность.

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

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

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

Информация = отражение реального мира в виде сигналов и знаков.

Информация существует в виде:

документов;
текстов;
рисунков;
световых сигналов;
энергетических импульсов;
нервных импульсов и так далее.

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

Сведения передаются с помощью сообщений.

Виды сообщений:

Устные.
Письменные: рисунки, знаки.
Жестовые и другие.

Сообщения: дорожные знаки, текст письма, рассказ.

Классификация информации

По способу восприятия информация бывает:

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

По форме представления информацию разделяют на:

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

По назначению информацию делят на:

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

Выделяют такой вид информации, как цифровая информация.

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

Человек работает с аналоговой информацией, а машина — вычислительная техника — с цифровой информацией.

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

Под структурой подразумевают устойчивую картину взаимоотношений элементов целостного объекта информации.

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

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

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

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

Виды связей между понятиями:

смысловые;
ассоциативные;
причинно-следственные и так далее.

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

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

Структурирование информации заключается:

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

Следование принципам структурирования информации приводит к ее успешному сохранению в памяти.

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

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

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

Примечание 1

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

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

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

Группировка опирается на понимание структурной иерархии объектов информации. Здесь важно отделять внешние признаки рассматриваемых понятий от структурных характеристик.

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

Реорганизация включает в себя:

перегруппировку;
распределение элементов;
составление списков, таблиц, схем и так далее.

Примечание 2

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

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

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

Мнемотехникой называют метод эффективного запоминания информации. Он основан на построении ассоциаций.

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

Принципы структурирования

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

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

Структурирование информации проявляется в работе с информацией с помощью:

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

Принципы структурирования информации применимы в сочетании с правилами.

Правило Миллера

Закономерность была обнаружена американским ученым-психологом Дж. Миллером в ходе ряда экспериментов.

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

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

Эффект края

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

Исследованием принципа занимался немецкий ученый Г. Эббингауз в XIX веке.

Эффект Ресторфф

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

Примечание 3

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

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

Типы структур информации

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

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

Методы структурирования

При существующем росте информации от человека требуют совершенствования умений работы с ней.

При работе с информацией важно:

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

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

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

Римская комната или метод Цицерона

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

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

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

Карты памяти или метод Тони Бьюзена

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

Этот метод был предложен в 1974 году, когда опубликовали книгу «Работай головой».

Выделяют области применения карт памяти:

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

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

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

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

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

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

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

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

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

Метод классификации

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

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

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

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

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

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

Связи между объектами называют отношениями.

Симметричную связь обозначают отрезком, а несимметричную — стрелкой.

Задание для самостоятельной работы

Структурируйте тестовую информацию:

Егоров И. учится в 10 классе. Его средний балл составляет 4,34. В 11 классе учится Иванов И.. Его средний балл равен 3,5. Мартынов И. учится в 5 классе, и его средний балл 2,57.

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

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

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

Школьный алгоритмический язык. Урок 1. Структура программы: обзор

При изучении информатики в школах для изучения основ алгоритмизации применяется т. н. Русский алгоритмический язык (школьный алгоритмический язык), использующий понятные школьнику слова на русском языке. Алголо-подобный алгоритмический язык с русским синтаксисом был введён в употребление академиком А. П. Ершовым в середине 1980-х годов в качестве основы для «безмашинного» курса информатики. Впервые был опубликован в учебнике «Основы информатики и вычислительной техники» в 1985 г. Язык также применялся для записи алгоритмов в учебнике А. Г. Кушниренко, Г. В. Лебедева и Р. А. Свореня «Основы информатики и вычислительной техники» для 9-10 классов (1990 г. и последующие переиздания; общий тираж составил 7 млн экземпляров).

Школьный алгоритмический язык.

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

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

1 2 3 4 5 6

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

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

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

В настоящий момент язык переживает своё второе рождение, в связи с разработкой пакета «КуМир» для Windows и Linux. В системе используется несколько исполнителей; основные — это классические «Робот» и «Чертёжник». Пакет включен в дистрибутив ALT Linux Школьный.

Система «КуМир» разработана в НИИСИ РАН по заказу Российской академии наук и распространяется свободно на условиях лицензии GNU GPL 2.0.

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

Пример алгоритма

1 2 3 4 5 6 7 8 9 10

алг Сумма квадратов (арг цел n, рез цел S)  дано | n > 0  надо | S = 1*1 + 2*2 + 3*3 + . + n*n нач цел i  ввод n; S:=0  нц для i от 1 до n S:=S+i*i  кц  вывод "S vertical-align: top;">кон

Как осуществляется структурирование текста на алгоритмическом языке

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

Следование — это линейная последовательность действий (рис. 3.3).

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

Ветвление — алгоритмическая альтернатива. Управление передается одному из двух блоков в зависимости от истинности или ложности условия. Затем происходит выход на общее продолжение. Вот как изображается ветвление на блок-схеме и АЯ (рис. 3.4).

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

Неполная форма ветвления имеет место, когда на ветви «нет» пусто (рис. 3.5).

Рис. 3.5. Неполное ветвление

Цикл — повторение некоторой группы действий по условию. Различают два типа цикла. Первый — цикл с предусловием: цикл-пока (рис. 3.6).

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

Пока условие истинно, выполняется серия, образующая тело цикла.

Второй тип циклической структуры — цикл с постусловием: цикл-до (рис. 3.7).

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

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

Комбинации базовых структур

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

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

Вложенные ветвления. Глубина вложенности равна единице.
Цикл с вложенным ветвлением.
Вложенные циклы-пока. Глубина вложенности — 1.
Ветвление с вложенной последовательностью ветвлений на положительной ветви и с вложенным циклом-пока на отрицательной ветви.
Следование ветвления и цикла-до.
Вложенные циклы. Внешний — цикл-пока, внутренний — цикл-до.

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

Рис. 3.8. Структурные схемы алгоритмов

Для приведенных на рис. 3.8 блок-схем структура текста на АЯ должна быть следующей:

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

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

Как осуществляется структурирование текста на алгоритмическом языке

Copy raw contents

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

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

Постановка задачи.
Формализация задачи.
Построение алгоритма.
Составление программы на языке программирования.
Отладка и тестирование программы.
Использование программы.

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

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

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

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

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

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

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

Одним из фундаментальных понятий в информатике является понятие алгоритма. Происхождение самого термина «алгоритм» связано с математикой. Это слово происходит от Algorithmi — латинского написания имени Мухаммеда альХорезми (787 — 850), выдающегося математика средневекового Востока. В XII в. был выполнен латинский перевод его математического трактата, из которого европейцы узнали о десятичной позиционной системе счисления и правилах арифметики многозначных чисел. Именно эти правила в то время называли алгоритмами. Сложение, вычитание, умножение столбиком, деление уголком многозначных чисел — вот первые алгоритмы в математике.

В наше время понятие алгоритма трактуется шире. Алгоритм — это последовательность команд управления каким-либо исполнителем.

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

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

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

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

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

Например, при решении квадратного уравнения ах 2 + Ьх + с = 0 исходными данными являются коэффициенты а, Ь, с; результатами — корни уравнения х1, х2; промежуточным данным — дискриминант уравнения D = b 2 — 4ас.

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

У всякой величины имеются три основных свойства: имя, значение и тип (на самом деле многие современные языки, такие как PHP или JS, обходятся без явного указания типа, интерпретируя тип переменной в зависимости от контекста операции). На уровне команд процессора величина идентифицируется при помощи адреса ячейки памяти, в которой она хранится. В алгоритмах и языках программирования величины делятся на константы и переменные. Константа — неизменная величина, и в алгоритме она представляется собственным значением, например: 15, 34.7, k, true и т.д. Переменные величины могут изменять свои значения в ходе выполнения программы и представляются символическими именами — идентификаторами, например: X, S2, cod15. Любая константа, как и переменная, занимает ячейку памяти, а значение этих величин определяется двоичным кодом в этой ячейке.

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

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

Типы констант определяются по контексту (т.е. по форме записи в тексте), а типы переменных устанавливаются в описаниях переменных (не во всех языках; Python, например, не имеет явного определения типа, тип переменной определяетя при первом присваивании).

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

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

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

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

Определенность (детерминнированность) — предполагает получение однозначного результата вычислительного процecca при заданных исходных данных. Благодаря этому свойству процесс выполнения алгоритма носит механический характер.

Результативность (конечность) — алгоритм должен приводить к решению задачи за конечное число шагов.

Формы записи алгоритмов

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

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

Пример: написать алгоритм «Одеться по погоде». Если на улице температура ниже 0, то необходимо надеть шубу, иначе – куртку.

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

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

Словесный способ не имеет широкого распространения, так как такие описания:

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

Графический способ записи алгоритмов

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

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

Название символа	Обозначение и пример заполнения	Пояснение
Процесс	Вычислительное действие или последовательность действий
Решение	Проверка условий
Модификация	Начало цикла
Предопределенный процесс	Вычисления по подпрограмме, стандартной подпрограмме
Ввод-вывод	Ввод-вывод в общем виде
Пуск-останов	Начало, конец алгоритма, вход и выход в подпрограмму
Документ	Вывод результатов на печать

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

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

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

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

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

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

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

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

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

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

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

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

Программный способ записи алгоритмов

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

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

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

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

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

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

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

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

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

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

Общие принципы построения алгоритмов

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

Принцип поэтапной детализации алгоритма (другое название — «проектирование сверху-вниз»). Этот принцип предполагает первоначальную разработку алгоритма в виде укрупненных блоков (разбиение задачи на подзадачи) и их постепенную детализацию.

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

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

Определение сложности работы алгоритмов

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

Память или время

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

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

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

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

При сравнении различных алгоритмов важно знать, как их сложность зависит от объёма входных данных. Допустим, при сортировке одним методом обработка тысячи чисел занимает 1 с., а обработка миллиона чисел – 10 с., при использовании другого алгоритма может потребоваться 2 с. и 5 с. соответственно. В таких условиях нельзя однозначно сказать, какой алгоритм лучше.

В общем случае сложность алгоритма можно оценить по порядку величины. Алгоритм имеет сложность O(f(n)) , если при увеличении размерности входных данных N, время выполнения алгоритма возрастает с той же скоростью, что и функция f(N) . Рассмотрим код, который для матрицы A[NxN] находит максимальный элемент в каждой строке.

В этом алгоритме переменная i меняется от 1 до N. При каждом изменении i, переменная j тоже меняется от 1 до N. Во время каждой из N итераций внешнего цикла, внутренний цикл тоже выполняется N раз. Общее количество итераций внутреннего цикла равно N*N. Это определяет сложность алгоритма O(N 2 ).

Оценивая порядок сложности алгоритма, необходимо использовать только ту часть, которая возрастает быстрее всего. Предположим, что рабочий цикл описывается выражением N 3 +N. В таком случае его сложность будет равна O(N 3 ). Рассмотрение быстро растущей части функции позволяет оценить поведение алгоритма при увеличении N. Например, при N=100, то разница между N 3 +N=1000100 и N=1000000 равна всего лишь 100, что составляет 0,01%.

При вычислении O можно не учитывать постоянные множители в выражениях. Алгоритм с рабочим шагом 3N 3 рассматривается, как O(N 3 ). Это делает зависимость отношения O(N) от изменения размера задачи более очевидной.

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

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

В качестве примера рассмотрим две процедуры: Slow со сложностью O(N 3 ) и Fast со сложностью O(N 2 ).

Если во внутренних циклах процедуры Fast происходит вызов процедуры Slow, то сложности процедур перемножаются. В данном случае сложность алгоритма составляет O(N 2 )*O(N 3 )=O(N 5 ).

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

Следующий фрагмент имеет именно такую сложность:

Сложность рекурсивных алгоритмов

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

Рассмотрим рекурсивную реализацию вычисления факториала:

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

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

Рассмотрим такую процедуру:

Поскольку процедура вызывается дважды, можно было бы предположить, что её рабочий цикл будет равен O(2N)=O(N). Но на самом деле ситуация гораздо сложнее. Если внимательно исследовать этот алгоритм, то станет очевидно, что его сложность равна O(2 (N+1) -1)=O(2 N ).

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

Объёмная сложность рекурсивных алгоритмов

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

Средний и наихудший случай

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

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

С другой стороны, искомый элемент может находится в списке на первой позиции. Алгоритму придётся сделать всего один шаг. Такой случай называется наилучшим и его сложность можно оценить, как O(1).

Оба эти случая маловероятны. Нас больше всего интересует ожидаемый вариант. Если элемента списка изначально беспорядочно смешаны, то искомый элемент может оказаться в любом месте списка. В среднем потребуется сделать N/2 сравнений, чтобы найти требуемый элемент. Значит сложность этого алгоритма в среднем составляет O(N/2)=O(N).

В данном случае средняя и ожидаемая сложность совпадают, но для многих алгоритмов наихудший случай сильно отличается от ожидаемого. Например, алгоритм быстрой сортировки в наихудшем случае имеет сложность порядка O(N 2 ), в то время как ожидаемое поведение описывается оценкой O(N*log(N)), что много быстрее.

Общие функции оценки сложности

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

C – константа (время выполнения алгоритма не зависит от входных параметров, линейные алгоритмы)
log(log(N))
log(N) — (поиск в сортированном массиве)
N C , 0
N — линейная сложность (поиск в не сортированном массиве)
N*log(N)
N C , C>1
C N , C>1
N!

Если мы хотим оценить сложность алгоритма, уравнение сложности которого содержит несколько этих функций, то уравнение можно сократить до функции, расположенной ниже в таблице. Например, O(log(N)+N!)=O(N!).

Если алгоритм вызывается редко и для небольших объёмов данных, то приемлемой можно считать сложность O(N 2 ), если же алгоритм работает в реальном времени, то не всегда достаточно производительности O(N).

Обычно алгоритмы со сложностью N*log(N) работают с хорошей скоростью. Алгоритмы со сложностью N C можно использовать только при небольших значениях C. Вычислительная сложность алгоритмов, порядок которых определяется функциями C N и N! очень велика, поэтому такие алгоритмы могут использоваться только для обработки небольшого объёма данных.

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

Школьный алгоритмический язык. Урок 1. Структура программы: обзор

Школьный алгоритмический язык.

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

Основные элементы алгоритмического языка

Структура ветвление – это алгоритм, содержащий одно или несколько условий и соответственно 2е и более ветви

если-то (неполное ветвление) если-то-иначе

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

Цикл – многократное посторенние одного или нескольких действий (тел цикла)

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

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

Цикл Пока – действия повторяются до тех пор, покавыполняется определённое условие

Блок-схема цикла с предусловием

Цикл Пока не – действия повторяются до тех пор, пока невыполнится определённое условие

Блок-схема цикла с постусловием

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

Основные элементы алгоритмического языка

Алгоритмический язык – это структурно-стилизованный способ описания алгоритма

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

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

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

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

Базовые типы объектов алгоритмов и, соответственно программ – этоданные: Имеется тpи основных вида данных: константы, переменные и массивы.

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

числовые: 7.5, 12;

логические: true(истина), false(ложь);

строковые: «abcde», «информатика».

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

Тип указывает какой способ записи информации используется и сколько памяти необходимо для её хранения.

Имя (идентификатор) последовательность символов для обозначения объектов программы (переменных, массивов, функций и дp.) – поясняет значение объекта. Имена устанавливает автор алгоритма. Они могут состоять из латинских букв и цифр. Первым символом в идентификаторе должна стоять латинская буква. Иногда длина идентификатора ограничена. Рекомендуется выбирать мнемонические имена, отражающие физическую суть соответствующего объекта задачи (SUMMA, FIO, PI). Общепринято для обозначения счётчиков использовать однобуквенные имена: I, J, K, L, M, N.

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

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

Двумерный массив – для индексации указывают два индекса – сначала № строки (i), затем № столбца (j)

Возможны не только числовые массивы, но и символьные (напр. список фамилий). В качестве индексов могут использоваться не только константы, но и переменные и даже выражения А(I+2); X(I, J+3). Массив относится к составным (конструируемым) типам данных.

В любом алгоритме (программе) всегда присутствует раздел операторов. Всегда имеется одна точка входа (НАЧАЛО) и одна (в некоторых языках программирования – несколько) точка выхода (КОНЕЦ). В остальном разделы в составе алгоритма могут отличаться в зависимости от используемого языка. В разных языках программирования используются разные записи программы: в одних каждое действие записывается в отдельной строке, в других – через двоеточие и т.д. В некоторых версиях языка Basic, строки нумеруются.

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

Различают простые и составные операторы. Простые: оператор присваивания, оператор перехода, операторы ввода и вывода данных.

Составные: условные операторы, операторы цикла и др.

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

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

Операции. Существуют следующие типы операций:

— арифметические операции: сложение, обозначается символом “+”; вычитание, обозначается символом “-”; умножение, обозначается символом “*”; деление, обозначается символом “/” и дp. ;

— логические операции: операции “логическое и”, “логическое или”, “логическое не” и др.;

— операции отношения: меньше, обозначается символом “”; меньше или равно, обозначается символами “=”; равно, обозначается символом “=”; не равно, обозначается символами “<>”.

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

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

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

Различают выражения арифметические, логические и строковые (текстовые).

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

1. Нельзя опускать знак умножения между сомножителями и ставить рядом два знака операций.

2. Индексы элементов массивов записываются в скобках.

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

4. Операции одного старшинства выполняются слева направо.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2. Если программа большая и повторная компиляция всего исходного текста занимает много времени, разделение ее на части экономит время компиляции.

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

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

Первая программа была написана Адой Лавлейс.

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

1. наиболее распространенная классификация всех языков программирования – языки низкого, высокого и сверхвысокогоуровня.

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

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

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

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

К языкам сверхвысокого уровня можно отнести лишь Алгол-68 и APL. Повышение уровня этих языков произошло за счет введения сверхмощных операций и операторов.

2. Другая классификация делит языки на вычислительные и языки символьной обработки. К первому типу относят Фортран, Паскаль, Алгол, Бейсик, Си, ко второму типу — Лисп, Пролог, Снобол и др.

3. Языки программирования делят на процедурные, объектно-ориентированныеидекларативные

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

Среди процедурных языков выделяют в свою очередь структурные и операционные языки. В структурных языках одним оператором записываются целые алгоритмические структуры: ветвления, циклы и т.д. В операционных языках для этого используются несколько операций. Широко распространены следующие структурные языки: Паскаль, Си, Ада, ПЛ/1. Среди операционных известны Фортран, Бейсик, Фокал.

Одним из первых процедурных языков программированиявысокого уровня является Фортран(Formula Translation), созданный в середине 50-х годов. Благодаря своей простоте и тому, что на этом языке накоплены большие библиотеки программ, Фортран и в наши дни остается одним из самых распространенных. Он используется для инженерных и научных расчетов, для решения задач физики и других наук с развитым математическим аппаратом. В 2000 г. вышла версия Фортран F2k (стандартная версия HPF (High Performance Fortran) для параллельных суперкомпьютеров

Для решения учётно-экономических задач и управленческих задач был создан язык программирования – Кобол (Common business oriented language)

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

Алгол (Algorithmiclanguage) разработан группой зарубежных специалистов в 1960 г., явился результатом международного сотрудничества конца 50-х гг. (Алгол-60). Алгол предназначался для записи алгоритмов, построенных в виде последовательности процедур, применяемых при решении поставленных задач. В нем впервые введены понятия «блочная структура программы», «динамическое распределение памяти». Внутри блока в Алголе можно вводить локальные обозначения, которые не зависят от остальной части программы. Несмотря на свое интернациональное происхождение, Алгол-60 получил меньшее распространение, чем Фортран. В 1968 г. в результате дальнейшего развития и усовершенствования Алгола-60 была создана версия Алгол-68. Это многоцелевой универсальный расширенный язык программирования. Последнее свойство позволяло с помощью одной и той же программы транслятора осуществлять трансляцию с различных расширенных версий языка без дополнительных затрат на приспособление этого языка к различным категориям пользователей, на получение проблемно-ориентированных диалектов языка. По своим возможностям Алгол-68 и сегодня опережает многие языки программирования, но для него нет хороших компиляторов. В нашей стране в те годы под руководством академика Андрея Петровича Ершова был создан транслятор Альфа, который представлял достаточно удачную русифицированную версию Алгола.

В середине 60-х гг. сотрудники математического факультета Дартмутского колледжа Томас Курц и Джон Кемени создали специализированный язык программирования, который состоял из простых английских слов. Новый язык назвали универсальным символическим кодом для начинающих (Beginners All-purpose Symbolic Instruction Code) или сокращенно BASIC (Бейсик). 1964 г. считают годом рождения этого языка. Он получил самое широкое распространение при работе на персональных компьютерах в режиме интерактивного диалога. Популярность Бейсика объясняется как простотой его освоения, так и наличием достаточно мощных универсальных средств, пригодных для решения научных, технических и экономических задач, а также задач бытового характера, игровых и т.д. Существует множество версий языка, зачастую мало совместимых друг с другом. Спустя много лет после изобретения Бейсика, он и сегодня самый простой для освоения из десятков языков общецелевого программирования.

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

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

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

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

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

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

Расширение областей применения ЭВМ влечет за собой создание языков, ориентированных на новые сферы применения: Снобол– алгоритмический язык для обработки текстовой информации, Лисп— алгоритмический язык для обработки символов. Лисп находит широкое применение в исследованиях по созданию искусственного интеллекта.

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

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

Основными концепциями ООП являются понятия объектов и классов (либо, в менее известном варианте языков с прототипированием — прототипов).

· Система состоит из объектов

· Объекты некоторым образом взаимодействуют между собой

· Каждый объект характеризуется своим состоянием и поведением

· Состояние объекта задаётся значением полей данных

· Поведение объекта задаётся методами

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

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

Прототип — это образцовый объект, по образу и подобию которого создаются другие объекты.

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

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

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

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

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

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

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

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

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

В логических языках программа вообще не описывает действий. Она задает данные и соотношения между ними. После этого системе можно задавать вопросы. Машина перебирает известные и заданные в программе данные и находит ответ на вопрос. Логическое программирование основано на теории математической логики. Порядок перебора не описывается в программе, а неявно задается самим языком. Классическим языком логического программирования считается Prolog (PROgramming in LOGic – программирование в терминах логики). Этот язык программирования разрабатывался для задач анализа и понимания естественных языков на основе языка формальной логики и методов автоматического доказательства теорем. Prolog является по сути универсальной машиной вывода, работающей в предположении замкнутости мира фактов. Построение логической программы вообще не требует алгоритмического мышления, программа описывает статические отношения объектов, а динамика находится в механизме перебора и скрыта от программиста.

Языки описания сценариевпредназначаются не для написания приложения с нуля, а для комбинирования компонентов, набор которых создается заранее при помощи других языков. Развитие и рост популярности Internet также способствовали распространению языков описания сценариев. Так, для написания сценариев широко употребляется язык Perl, а среди разработчиков Web-страниц популярен JavaScript.

Языки программирования баз данных предназначены для обработки больших массивов информации и выборки записей по определённым признакам. В каждой СУБД имеется свой универсальный язык, ориентированный на её особенности. Для управления реляционной базой данных был создан структурированный язык SQL (Structured Query Language).

Basic

Beginner’s All-purpose Symbolic Instruction Code – универсальный язык символических инструкций для начинающих.

Программа на языке Basic состоит из последовательности строк. Каждая строка содержит номер и один или несколько операторов.

Алфавит языка включает:

— десятичные цифры от 0 до 9

— cтрочные и прописные буквы от A до Z (используются для операторов, идентификаторов и различных операций.

— cтрочные и прописные буквы кириллицы от А до Я (используются только в комментариях без кавычек и в символьных константах)

— знаки и символы + — = * ( ) < >$ % @ # & : ; пробел

Константы (арифметические, символьные, логические)

— целая константа в диапазоне от -32768 до +32767 (не сдержит десятичной точки)

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

— форма с фиксированной точкой (естественная форма)

3.2 0.615 -37.149 276.00 +1.54

— форма с плавающей точкой

— 4.32*10 -4 записывается как — 4.32Е – 4

0.761*10 6 записывается как 0.761Е + 6

Диапазон допустимых значений от -Е + 38 до +Е + 38

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

Идентификаторы – могут содержать латинские буквы, цифры и некоторые символы. В конце идентификатора может быть суффикс –

для имён объектов символьного типа $ (name$ s5$ FIO$)

для целых чисел % (N% i%)

для вещественных чисел – буква или цифра в конце имени (X a PLAN Sum2)

Объявление объектов программы – для выделения места в памяти. Простые переменные можно объявлять в любой строке до первого использования. Для объявления массива используется оператор DIM

20 DIM FIO$ (20) ‘ Список группы

30 DIM STUD$ (20), OCEN% (20, 5) ‘ Информация о студентах

Операции– для вычислительного процесса

— арифметические операции (в порядке убывания приоритета)

^ возведение в степень

MOD получение остатка от деления

— операции отношения:

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

Если отношение ложно, результат операции «О», если истинно «-1».

Операции отношения используются при сравнении данных: двух чисел либо двух строк. Сравнить число со строкой нельзя.

— — логические операции

NOT логическое отрицание

AND и, логическое умножение

OR или, логическое сложение

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

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

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

Похожие публикации:

Как оптимизировать css код
Как отключить кэширование css на сайте
Что выбрать arduino или raspberry
Что лучше css v34 или css v91

Как осуществляется структурирование текста на алгоритмическом языке

Уроки 31 — 32Алгоритмы, структуры алгоритмов, структурное программирование

Понятие алгоритма

Данные и величины

Вопросы и задания

Структура алгоритмов

Базовые алгоритмические структуры

Комбинации базовых структур

Вопросы и задания

Паскаль — язык структурного программирования

Эволюция программирования

Языки программирования высокого уровня

История Паскаля

Структура процедурных языков программирования высокого уровня

Структура программы на Паскале

Вопросы и задания

Cтруктурирование информации

Классификация информации

Принципы структурирования

Правило Миллера

Эффект края

Эффект Ресторфф

Типы структур информации

Методы структурирования

Римская комната или метод Цицерона

Карты памяти или метод Тони Бьюзена

Метод классификации

Задание для самостоятельной работы

Школьный алгоритмический язык. Урок 1. Структура программы: обзор

Школьный алгоритмический язык.

Комментарии

Пример алгоритма

Как осуществляется структурирование текста на алгоритмическом языке

Комбинации базовых структур

Как осуществляется структурирование текста на алгоритмическом языке

Школьный алгоритмический язык. Урок 1. Структура программы: обзор

Школьный алгоритмический язык.

Комментарии

Основные элементы алгоритмического языка

Добавить комментарий Отменить ответ

Уроки 31 — 32
Алгоритмы, структуры алгоритмов, структурное программирование