что такое алгоритмические средства

Что такое алгоритмические средства

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

А для программных средств выбрано (а точнее, создано) очень удачное слово Software (буквально — «мягкие изделия» ), которое подчёркивает равнозначность программного обеспечения и самой машины и вместе с тем подчёркивает способность программного обеспечения модифицироваться, приспосабливаться, развиваться.

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

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

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

Источник

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

2.3. Обучение алгоритмическому мышлению

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

Обоснуем каждый из этих этапов поподробнее.

2.3.1. Абстрактное мышление

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

Абстрактное мышление позволяет находить главный факт из множества известных фактов, выделить эти факты и явления по их существенному признаку. Очень хорошо об этих способностях написал К.К. Платонов в своей книге: «Занимательная психология» [71]. Автор советует с ней ознакомиться для получения общих сведений о психологии вообще и об абстрактном мышлении в частности.

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

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

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

2.3.2. Разбиение общей задачи на подзадачи

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

Для каждого из них будет свой алгоритм:

Переход со светофором.

Переход улицы без светофора.

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

Итак, мы только что сформулировали основной принцип написания программ [74; 54-55]:

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

2.3.3. Умение планировать этапы и время разработки

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

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

2.3.4. Парадигма и язык программирования

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

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

2.4. Резюме

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

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

Источник

Информационные технологии копия 2

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Рассмотрим некоторые основные конструкции, использующиеся для построения блок-схем (рис. 1).

(1) Блок, характеризующий начало/конец алгоритма (для подпрограмм – вызов/возврат);

(8) Блок – решение (проверка условия или условный блок);

(9) Блок, описывающий блок с параметром;

(10) Блок – границы цикла, описывающий циклические процессы типа: «цикл с предусловием», «цикл с постусловием»;

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

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

Основные алгоритмические конструкции

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

Линейная алгоритмическая конструкция

Линейной называют алгоритмическую конструкцию, реализованную в виде последовательности действий (шагов), в которой каждое действие (шаг) алгоритма выполняется ровно один раз, причем после каждого i- гo действия (шага) выполняется (i+ 1)-е действие (шаг), если i-e действие – не конец алгоритма.

Опишем алгоритм сложения двух чисел на псевдокоде в виде блок-схемы (рис. 2).

Разветвляющаяся алгоритмическая конструкция

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

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

Заданы три числа. Найти значение наименьшего из них Заданные числа обозначим: а, b, с; результирующее наименьшее – min. На рис. 5 представлена блок-схема алгоритма решения данной задачи.

Алгоритмическая конструкция «Цикл»

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

Арифметический цикл

В арифметическом цикле число его шагов (повторений) однозначно определяется правилом изменения параметра, которое задается с помощью начального (N) и конечного (К) значений параметра и шагом (h) его изменения. Т.е., на первом шаге цикла значение параметра равно N, на втором – N + h, на третьем – N + 2h и т.д. На последнем шаге цикла значение параметра не больше К, но такое, что дальнейшее его изменение приведет к значению, большему, чем К.

Вывести 10 раз слово «Привет!».

Параметр цикла обозначим i, он будет отвечать за количество выведенных слов. При i=1 будет выведено первое слово, при i=2 будет выведено второе слова и т. д. Так как требуется вывести 10 слов, то последнее значение параметра i=10. В заданном примере требуется 10 раз повторить одно и то же действие: вывести слово «Привет!». Составим алгоритм, используя арифметический цикл, в котором правило изменения параметра i=1,10, 1. т. е. начальное значение параметра i=1; конечное значение i=10; шаг изменения h=1. На рис. 6 представлена блок-схема алгоритма решения данной задачи.

Цикл с предусловием

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

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

Цикл с постусловием

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

Рекурсивный алгоритм

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

Простые типы данных: переменные и константы

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

Объем памяти для каждого типа определяется таким образом, чтобы в него можно было поместить любое значение из допустимого диапазона значений данного типа. Например, тип «байт» может принимать значения от О до 255, что в двоичном коде (255₍₁₀₎=11111111₍₂₎) соответствует ячейке памяти длиной в 8 бит (или 1 байт).

В описанных выше алгоритмах (примеры 1-3) все данные хранятся в виде переменных. Например, инструкция «Ввод двух чисел а, b » означает введение пользователем значений двух переменных, а инструкция «К=К + 1» означает увеличение значения переменной К на единицу.

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

Все остальные данные в программе, значения которых не изменяются на протяжении ее работы, называют константами или постоянными. Константы, как и переменные, имеют тип. Их можно указывать явно, например, в инструкции «К=К+1» 1 есть константа, или для удобства обозначать идентификаторами: pi=3,1415926536. Только значение pi нельзя изменить, так как это константа, а не переменная.

Структурированные данные и алгоритмы их обработки

Одномерный массив (шкаф ящиков в один ряд) предполагает наличие у каждого элемента только одного индекса. Примерами одномерных массивов служат арифметическая (а_i) и геометрическая (b_i) последовательности, определяющие конечные ряды чисел. Количество элементов массива называют размерностью. При определении одномерного массива его размерность записывается в круглых скобках, рядом с его именем. Например, если сказано: «задан массив A (10)», это означает, что даны элементы: a ₁ , a ₂ , …, a ₁₀ . Рассмотрим алгоритмы обработки элементов одномерных массивов.

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

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

Обозначим индекс наибольшего элемента т. Будем считать, что первый элемент массива является наибольшим (т = 1). Сравним поочередно наибольший с остальными элементами массива. Если оказывается, что текущий элемент массива а _i (тот, c которым идет сравнение) больше выбранного нами наибольшего а_т, то считаем его наибольшим (т=i) (рис.10).

Рассмотрим двумерный массив (шкаф с множеством ящиков, положение которых определяется двумя координатами – по горизонтали и по вертикали). В математике двумерный массив (таблица чисел) называется матрицей. Каждый ее элемент имеет два индекса а _ij , первый индекс i определяет номер строки, в которой находится элемент (координата по горизонтали), а второй j – номер столбца (координата по вертикали). Двумерный массив характеризуется двумя размерностями N и М, определяющими число строк и столбцов соответственно (рис. 11).

Задана матрица символов (100х100), представляющая собой карту ночного неба; звездам на карте соответствует символы «*». Определить: сколько звезд на карте?

Алгоритм решения задачи достаточно прост, необходимо перебрать все элементы матрицы и посчитать, сколько среди них символов «*». Обозначим К переменную – счетчик. На рис 13. представлена блок-схема решения этой задачи.

Источник

Что такое алгоритмические средства

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

Введение в моделирование и алгоритмизацию

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

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

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

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

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

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

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

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

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

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

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

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

Существуют общепринятые и широко используемые типы:

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

Компьютер и моделирование

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

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

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

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

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

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

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

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

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

Фундаментальные понятия этих моделей :

объект (нечто, существующее и различимое; например, книга),

атрибут (свойство, характеристика объекта; например, название книги или издание),

значение атрибута (например, “Информатика”).

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

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

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

У конкретной книги каждый из этих атрибутов примет то или иное значение. Например, для книги № 10: название “Анализ финансовых операций” (текст), год издания 1998 (дата) и т. д.

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

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

Для пояснения понятия “алгоритм” важное значение имеет определение понятия “исполнитель алгоритма”. Алгоритм формулируется в расчете на конкретного исполнителя, например человека, особую машину — автомат и т. д.

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

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

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

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

СРЕДСТВА ЗАПИСИ АЛГОРИТМОВ

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

Рассмотрим основные средства, используемые для записи алгоритмов.

Словесная запись алгоритма

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

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

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

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

Пример структурной схемы алгоритма Евклида

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

Переход по стрелке со знаком “+” происходит, если условие соблюдено, а переход по стрелке “-”, если условие не соблюдено.

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

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

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

алгоритм алгоритм Евклида;

пока первое число не равно второму

иначе определить большее из двух чисел;

заменить большее число на разность большего и меньшего чисел

взять первое число в качестве ответа

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

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

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

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

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

Универсальные языки высокого уровня обеспечивают создание различных программ (задач), например Алгол, Си, ПЛ/1 и т.д..

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

Фирма Microsoft использует Visual Basic для расширения функций своих программных продуктов. Уже в пакете Microsoft Office для Windows 3-х пользователям и программистам предлагались диалекты Word Basic и Access Basic, а ныне в Microsoft Office предусмотрен универсальный язык Visual Basic for Applications (VBA — Visual Basic для приложений). Ранее этот язык использовался только в Excel 5.0. С помощью VBA можно создавать собственные программные модули, собственные интерфейсы для офисных приложений Word, Excel, Access.

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

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

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

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

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

Несмотря на существование множества языков программирования, все они, как правило, содержат

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

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

Значение переменной величины может быть изменено с помощью команды присваивания. Например, команда x:=1 означает, что переменной x присваивается значение 1, а команда y:=y+1 — что переменной y присваивается значение, которое на 1 больше ее прежнего значения.

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

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

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

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

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

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

В том случае, когда условие соблюдено, продолжение исполнения алгоритма происходит по стрелке “+”, в противном случае — по стрелке “—”.

Команда повторения (цикл)

Рассмотрим два типа команды повторения.

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

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

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

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

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

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

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

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

Существует несколько методов проектирования:

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

Источник