78201

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

Лекция

Информатика, кибернетика и программирование

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

Русский

2015-02-07

242.5 KB

19 чел.

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

Оглавление

[1] Оглавление

[2] Алгоритмизация вычислительных процессов

[2.1] Основные определения и понятия

[2.2] Средства изображения алгоритмов

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

[2.4] Контрольные вопросы.

Урок-лекция №3

Тема: Понятие алгоритма: свойства, способы описания.

Цель: формирование понятия «алгоритм»,  дать описание свойствам алгоритма, определить способы описания.

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

Основные определения и понятия

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

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

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

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

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

Язык программирования - предназначен для реализации программ на ЭВМ.

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

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

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

А:= В+С;     {А, В, С - переменные;}

К:= 2;  

 IF T< 0 THEN . . .

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

Свойства переменной:

1) переменная называется неопределенной до тех пор, пока она не получит значение:

а) вводом извне;

б) занесением константы;

в) занесением значения другой, ранее определенной переменной;

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

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

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

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

Интерпретатор - это программа, которая сразу выполняет переводимые команды.

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

Средства изображения алгоритмов

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

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

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

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

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

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

интервалу. Интервал задается границами А и В.

п.1 Берем первое число. На п.2.

п.2 Сравниваем: выбранное число принадлежит интервалу;

если да, то на п.3, если нет – на п.6.

п.3 Все элементы массива просмотрены? Если да, то на п.5, если нет – то на п.4.

п.4 Выбираем следующий элемент. На п.2.

п.5 Печать сообщения: все элементы принадлежат интервалу. На п.7.

п.6 Печать сообщения: не все элементы принадлежат интервалу. На п.7.

п.7 Конец.

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

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

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

п.1 – вычислить полупериметр треугольника

p=(a+b+c)/2. К п.2.

п.2 – вычислить

К п.3.

п.3 – вывести S , как искомый результат и прекратить вычисления.

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

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

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

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

case

if

for

repeat

while

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

Приведем пример блок-схемы комбинированного алгоритма для расчета суммы положительных S1 и отрицательных S2 чисел из N случайных чисел от -100 до 100.

Соответствующие алгоритму операторы имеют вид:

Begin  

 Randomize;

 Writeln('Введите количество случайных чисел');

  Readln(N);

 S1:=0;

 S2:=0;

 For i:=1 to N do

   begin  

x:=Random(201)-100;

     if x < 0 Then S2:=S2+x  else  S1:=S1+x;

   end;

  Writeln('S1= ',  S1,  '  S2= ', S2);

 Readln

End.

Блок-схемы могут быть традиционные и структурированные. 

Таблица 1 – Основные блоки, используемые при составлении алгоритмов

Название

Обозначение

Назначение

Пуск, Останов

Начало-конец алгоритма

Процесс

Любое вычислительное действие

Решение

Проверка условия

Модификатор

Цикл

Предопределенный процесс

Несколько операций объединенных в одном модуле, подпрограмме

Ввод-вывод

Ввод-вывод данных, носитель данных не определен

Документ

Вывод на печатающее устройство

Соединитель

Используется на линиях разрыва

Комментарий

Комментарий

Рисунок 1-  Блок-схема алгоритма

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

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

Выбираем первый элемент ( i=1) IF A > Xt  или  х. > B  THEN

печать сообщения и переход на конец ELSE

переход к следующему элементу( i = i +1 )

IF массив не кончился ( i <= n ) THEN переход на проверку интервала

ELSE

печать сообщения, что все элементы входят в интервал

Конец

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

Основные элементы МЭСИД


Рассмотрим пример использования диаграмм МЭСИД.

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

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

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

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

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

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

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

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

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

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

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

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

- следования или последовательности операторов;

- развилки или условного оператора;

- повторения или оператора цикла.

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

1) следование

Действия А и В могут быть:

- отдельным оператором;

- вызовом с возвратом некоторой процедуры;

- другой управляющей структурой.

2) развилка

IF P then A else B;

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

IF P then A;

3) повторение

цикл – пока

While P do A;

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

цикл – до

Repeat A until P;

Повторение типа Repeat until всегда выполняется хотя бы 1 раз. Действие А перестает выполняться, как только предикат становится истинным.

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

В зависимости от значения Р выполняется одно из действий А, В, …Z. После чего происходит переход к выполнению следующей управляющей структуры.

Контрольные вопросы.

  1.  Дайте определение алгоритму. Опишите свойства алгоритма.
  2.  Перечислите способы записей алгоритмов.
  3.  Чем отличается компилятор от интерпретатора?
  4.  Что такое подпрограмма?
  5.  Перечислите способы отображения алгоритмов.
  6.  Особенности словесного способа изображения алгоритмов.
  7.  Особенности формульно-словесного способа изображения алгоритмов.
  8.  Особенности изображения алгоритмов с помощью операторных схем (псевдокода).
  9.  Особенности изображения алгоритмов с помощью структурных диаграмм.
  10.  Особенности блок-схемного способа изображения алгоритмов.
  11.  Основные символы, использующиеся при составлении блок-схем.
  12.  Дайте понятие регулярной программы.
  13.  Особенности использования базовых конструкций «следование» и «повторение».
  14.  Особенности использования базовых конструкций «развилка» и «выбор».


 

А также другие работы, которые могут Вас заинтересовать

34378. Платёжный баланс, его роль, содержание и прогнозирование 60.5 KB
  Процентные ставки на международных рынках являются важным фактором определяющим чистые процентные поступления на текущий счет а вместе с процентными ставками на внутреннем рынке они заметно влияют на объем и направление потоков капитала. При прогнозировании важно учитывать сочетание прогнозного результата по текущему счету с допустимыми значениями притока капитала для покрытия дефицита. При прогнозировании финансового счета необходимо различать три основные категории: прямые инвестиции перемещения средне и долгосрочного капитала и...
34379. Прогнозирование валютного курса 38 KB
  Если большое количество стран конкурирует в экспортировании товаров и услуг тогда величина экспорта будет очень чувствительна даже к небольшим изменениям обменного курса. Это не изменит курса обмена. Процесс формирования валютного курса можно подразделить на два этапа: определение валютного курса который отражает реальную стоимость национальной валюты по аналогии с себестоимостью товара формирование рыночного валютного курса который отражает цену национальной валюты образующиеся на основе реального валютного курса под воздействием...
34380. Прогнозирование развития рынка ценных бумаг 57 KB
  Cpitl mrket это составная часть финансового рынка на котором осуществляются операции куплипродажи ценных бумаг. Финансовый рынок состоит из: Денежный рынок который в свою очередь состоит из: учётный рынокдоля денежного рынка где осуществляется перераспределение краткосрочных денежных средств между кредитными институтами путем куплипродажи векселей и ценных бумаг. Основа рынка учетные и переучетные операции банков межбанковскийсегмент рынка ссудных капиталов где временно свободные денежные ресурсы кредитных учреждений...
34381. Трудовые ресурсы (ТС), их состав. Рынок труда. Проблема занятости 50.5 KB
  Критериями для выделения из общей численности населения трудовых ресурсов являются границы трудоспособного возраста которые устанавливаются государством и зависят от общественного строя продолжительности жизни людей других социальноэкономических факторов и принятых в связи с этим официальных государственных актов. В состав трудовых ресурсов включаются: трудоспособное население в трудоспособном возрасте; работающие подростки до 16 лет; население старше рабочего возраста принимающее участие в общественном производстве. В зависимости от...
34382. Прогнозирование ТС и их использования. Сводный баланс ТС, его содержание и методика разработки 73.5 KB
  Сводный баланс ТС его содержание и методика разработки Прогнозирование трудовых ресурсов является составной частью процесса разработки демографических прогнозов служащих для решения следующих задач: определение перспективной численности населения и его половозрастной структуры; оценка численности населения трудоспособного возраста основного источника трудовых ресурсов; обоснование перспектив социальноэкономического развития; разработка концепции демографического развития согласованной с концепцией...
34383. Социальная политика. Показатели, характеризующие уровень жизни населения 77.5 KB
  Показатели характеризующие уровень жизни населения Социальная политика государства это комплекс организационных экономических и других мероприятий по улучшению материального благосостояния духовному и физическому развитию населения оказанию поддержки инвалидам и малообеспеченным членам общества. Учитывая комплексный характер определения социальная политика ее обычно расчленяют на следующие составные части: политика доходов населения; социальная защита граждан; развитие системы здравоохранения образования культуры...
34384. Социальные нормы и нормативы. Минимальный потребительский бюджет и минимальная заработная плата 61.5 KB
  Минимальный потребительский бюджет и минимальная заработная плата Переход к рыночной модели хозяйствования неизбежно привносит в жизнь общества хронические болезни капиталистической системы: безработицу резкое имущественное расслоение бедность многочисленных слоев населения. Необходимость проведения активной социальной политики направленной на поддержание уровня жизни населения и обеспечение социальной защиты наиболее нуждающихся граждан обусловливает широкое использование в прогнозировании и планировании социальных нормативов. Это...
34385. Баланс денежных доходов и расходов населения, его роль и методика разработки 72 KB
  Политика доходов была направлена на сохранение в условиях инфляции определенного уровня заработной платы низкооплачиваемым слоям населения и реальной стоимости социальных выплат путем их периодических централизованных повышений или индексаций. Их успешная реализация стала важным этапом в обеспечении устойчивого экономического роста и повышении уровня жизни населения. Реальные денежные доходы населения повысились на 72 их рост по отношению к 1990 г.
34386. Прогнозирование и планирование оплаты труда 66 KB
  Основная цель оплаты труда обеспечить объективно необходимое воспроизводство рабочей силы в соответствии с ее стоимостью и повысить уровень мотивации исполнителей к эффективному труду. Фонд оплаты труда по народному хозяйству это сумма денежных средств предназначенных для распределения между рабочими и служащими в зависимости от количества и качества затраченного труда. Источниками фонда оплаты труда является национальный доход который распределяется на фонд потребления и фонд накопления.