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

Обновлено: 18.05.2024

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

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

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

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

Для создания алгоритма (программы) необходимо знать:

Полученный алгоритм (программа) должен обладать следующим набором свойств:

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

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

Приведем пример описания алгоритма суммирования двух величин в виде блок-схемы:

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

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

Линейная структура (следование).

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

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

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

Цикл (повторение).

Ц иклы со счётчиком (с параметром) – повторение тела цикла заданное число раз :

Вспомогательный алгоритм (подпрограмма, процедура).

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

Методы разработки сложных алгоритмов.

Существует два метода разработки сложных алгоритмов:

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

В простейшем случае таких объектов два:

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

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

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

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

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

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

В 60 – 70-е годы прошлого века стали появляться языки высокого уровня – формальные языки, позволяющие записывать алгоритмы в привычном для человека виде. Такие языки строились на основе использования определённого набора символов – алфавита и строгих правил построения команд – синтаксиса. Широкое распространение получили процедурные языки высоко уровня. Самые известные процедурные языки - Basic и Pascal . Они развивались длительное время, и последние версии этих языков используются и сейчас ( Qbasic , TurboPascal ). В них широко используются команды (операторы), реализующие типовые алгоритмические структуры. Для ввода и редактирования такой программы используется подобие текстового редактора. Для исполнения такой программы компьютер с помощью специальной программы – транслятора (компилятора или интерпретатора) осуществляет перевод программы с языка высокого уровня в язык машинных команд, при этом компьютер должен проверять программу на наличие ошибок и сообщать о них программисту. Таким образом, для создания компьютерной программы нужны другие компьютерные программы!

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

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

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

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

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

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

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

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

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

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

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

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

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

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

(2) Блок - процесс, предназначенный для описания отдельных действий;

(3) Блок - предопределенный процесс, предназначенный для обращения к вспомогательным алгоритмам (подпрограммам);

(4) Блок - ввода/вывода с неопределенного носителя;

(5) Блок - ввод с клавиатуры;

(6) Блок - вывод на монитор;

(7) Блок - вывод на печатающее устройство;

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

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

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

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

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

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

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

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

Ввод двух чисел а, b .

Вычисляем сумму S = а + b .

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Ввод элементов двумерного массива осуществляется построчно, в свою очередь, ввод каждой строки производится поэлементно, тем самым определяется циклическая конструкция, реализующая вложение циклов. Внешний цикл определяет номер вводимой строки ( i ), внутренний – номер элемента по столбцу ( j ). На рис. 12 представлен алгоритм ввода матрицы A(MxN) .

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

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

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

4. Составление программы (запись алгоритма на языке программирования) и её ввод в память компьютера. Сейчас этот этап принято называть кодированием.

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

6. Вычисление и обработка результатов.

Задачи, которые мы будем рассматривать в данной главе, достаточно чётко поставлены и формализованы. Основное внимание при их решении мы будем уделять этапам 3-6.

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

1. Вставить ключ в замочную скважину.

2. Повернуть ключ несколько раз на 180 градусов против(по) часовой стрелки(е).

3. Вынуть ключ из замочной скважины.

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

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

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

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

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

Пример 2. Простые числа — это натуральные числа, большие единицы, которые имеют только два делителя: единицу и само это число (рис. 2.1).

Во все времена люди хотели найти как можно большее простое число.

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

В 2013 г. открыто простое число, запись которого в десятичной системе счисления состоит из 17 425 170 знаков. На проверку простоты нового числа ушло 39 дней работы персонального компьютера в Университете Центрального Миссури, США.

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

1) выписать подряд все целые числа от 2 до n (2, 3, 4, . n);

2) присвоить переменной р значение 2 (2 — первое простое число);

3) зачеркнуть в списке числа, кратные р: 2р, 3р, 4р, . ;

4) найти первое незачёркнутое число в списке, большее чем р, и присвоить переменной р соответствующее значение;

5) повторять шаги 3 и 4, пока возможно.

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

На практике, алгоритм можно улучшить следующим образом. На шаге 3 числа можно зачёркивать начиная сразу с числа р 2 (р • р), потому что все составные числа меньше него к этому времени уже будут зачёркнуты. И соответственно, останавливать алгоритм можно, когда р 2 станет больше, чем n.

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

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

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

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

Докажите, что рассмотренный в примере 2 метод Эратосфена является алгоритмом.

Не любой расписанный по шагам способ решения задачи является алгоритмом. Убедимся в этом на примере.

Пример 3.

Опишем метод построения перпендикуляра к прямой MN, проходящего через заданную точку А этой прямой, с помощью линейки и циркуля (рис. 2.2):

1) отложить в обе стороны от точки А на прямой MN циркулем отрезки равной длины с концами B и С;

2) увеличить раствор циркуля до радиуса, в полтора-два раза больше длины отрезков АВ и АС;

3) провести указанным раствором циркуля дуги окружностей с центрами в точках B и С так, чтобы они охватили точку А и образовали две точки пересечения друг с другом (D и Е);

4) взять линейку, приложить её к точкам D и E и соединить их отрезком; при правильном построении отрезок пройдёт через точку А и будет являться перпендикуляром к прямой MN.

Почему этот способ построения перпендикуляра к прямой не является алгоритмом? Какое свойство алгоритмов здесь нарушено?

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

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

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

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

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

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

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

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

Из курса информатики основной школы вам известны разные способы записи одного и того же алгоритма:

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

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

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

Пусть задумано число X ∈ [А, В]. Представим в виде блок- схемы алгоритм решения этой задачи — известный вам метод половинного деления (рис. 2.3).

Подсчитайте, какое наибольшее число шагов может понадобиться для угадывания по этому алгоритму числа X ∈ [0, 100].

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

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

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

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

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

Сложность алгоритма — количество элементарных шагов (действий) в вычислительном процессе этого алгоритма.

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

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

Для решения задачи могут быть разработаны алгоритмы, имеющие разную сложность. Лучшим среди них считается алгоритм, имеющий наименьшую сложность.

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

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

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

1. Запишем n в двоичной системе счисления.

2. Заменим в этой записи каждую единицу парой букв КХ, а каждый ноль — буквой К.

3. Вычеркнем крайнюю левую пару КХ.

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

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

1. 100 = 1100100₂.
2. Строим последовательность: КХКХКККХКК.
3. Вычёркиваем крайнюю левую пару КХ: КХКККХКК.
4. Вычисляем искомое значение:
К: возвести х в квадрат (х 2 );
X: умножить результат на х (x 3 );
К: возвести результат в квадрат (х 6 );
К: возвести результат в квадрат (х 12 );
К: возвести результат в квадрат (х 24 );
X: умножить результат на х (х 25 );
К: возвести результат в квадрат (х 50 );
К: возвести результат в квадрат (х 100 ).

Самое главное

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

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

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

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

Для учеников 1-11 классов и дошкольников
Бесплатные сертификаты учителям и участникам

Лекция № 6: Алгоритмизация и программирование

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

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

Название "алгоритм" произошло от латинской формы имени величайшего среднеазиатского математика Мухаммеда ибн Муса ал-Хорезми (Alhorithmi), жившего в 783—850 гг.

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

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

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

Исполнителя хаpактеpизуют:

1. Сpеда (или обстановка) — это "место обитания" исполнителя. Напpимеp, для исполнителя человека – это общество или природа, для робота – помещение, в котором он функционирует.

2. Система команд . Каждый исполнитель может выполнять команды только из некотоpого стpого заданного списка — системы команд исполнителя. Для каждой команды должны быть заданы условия пpименимости (в каких состояниях сpеды может быть выполнена команда) и описаны pезультаты выполнения команды . Напpимеp, команда Pобота "идти" может быть выполнена, если перед Pоботом нет стены или иных препятствий. Человек-водитель может вести общественный транспорт только в соответствии с дорожными знаками и отсутствии препятствий на дорогах.

3. После вызова команды исполнитель совеpшает соответствующее элементаpное действие .

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

В информатике универсальным исполнителем алгоритмов является компьютер.

Свойства алгоритмов

Основные свойства алгоритмов следующие:

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

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

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

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

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

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

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

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

Например. Записать алгоритм нахождения наибольшего общего делителя (НОД) двух натуральных чисел ( алгоритм Эвклида ).

Алгоритм может быть следующим:

задать два числа;

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

определить большее из чисел;

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

повторить алгоритм с шага 2.

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

125-75 = 50; а=50, б=75

НОД=25; 125/25=5, 75/25=3

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

Недостатки словесного способа

словесный алгоритм строго не формализуем;

создается многословность записи;

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

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

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

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

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

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

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

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

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

3. Запись алгоритма в виде псевдокода

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

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

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

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

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

Примером псевдокода является школьный алгоритмический язык в русской нотации ( школьный АЯ ), описанный в учебнике А.Г. Кушниренко и др. "Основы информатики и вычислительной техники", 1991.

Наприемр

Основные служебные слова

алг название алгоритма (аргументы и результаты)

дано условия применимости алгоритма

надо цель выполнения алгоритма

нач описание промежуточных величин

| последовательность команд (тело алгоритма)

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

4. Программная форма представления алгоритма

Это тексты на языке программирования

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

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

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

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

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

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

Структура ветвление существует в четырех основных вариантах:

если условие

то действия

2. если—то—иначе

если условие

то действия 1

иначе действия 2

при условие 1: действия 1

при условие 2: действия 2

при условие N: действия N

4. выбор—иначе

при условие 1: действия 1

при условие 2: действия 2

при условие N: действия N

иначе действия N+1

Примеры структуры ветвление

то y := sin(x)

то a := 2*a; b := 1

иначе b := 2*b

при n = 1: y := sin(x)

при n = 2: y := cos(x)

при n = 3: y := 0

при a > 5: i := i+1

при a = 0: j := j+1

иначе i := 10; j:=0

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

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

нц пока условие

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

нц для i от i1 до i2

Примеры структуры цикл

нц пока i

нц для i от 1 до 5

Вложенные циклы

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

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

Вычислить сумму элементов заданной матрицы А(5,3).

нц для i от 1 до 5

нц для j от 1 до 3

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

Читайте также: