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

3.Как называется блочный символ, представленный на рисунке ?

4.Как называется блочный символ, представленный на рисунке ?

5.Как называется блочный символ, представленный на рисунке ?

Сопоставьте условные обозначения применяемые в блок-схемах и их назначение

а) б) в) г) д)

Укажите соответствие для всех 5 вариантов ответа:

1) блок принятия решения (проверка условия)

2) Блок начала и конца алгоритма

3) блок описания данных

4) блок обработки данных (выполнения действий)

5) блок модификации

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

9. Величины, значения которых меняются в процессе исполнения алгоритма, называются:

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

ЕСЛИ - ТО - ИНАЧЕ - ВСЕ

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

НЦ ПОКА условие

Тело цикла

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

НЦ ДЛЯ i ОТ i1 ДО i2

Тело цикла

13. Дан фрагмент линейного алгоритма:

b:=5+2*a

a:=b/5*a

Чему равно значение переменнойапосле его исполнения?

Выявление ошибок и их устранение называется...

Отдельное указание исполнителю - это...

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

Блок-схема - это...

Какое действие определяет блок комментарии?

20. В блок-схеме начало и конец алгоритма обозначается фи­гурой:

а) б) в) г) д)

21. В блок-схеме действие в алгоритме обозначается фи­гурой:

а) б) в) г) д)

22. В блок-схеме условие обозначается фи­гурой:

а) б) в) г) д)

23. В блок-схеме вывод и ввод данных обозначается фи­гурой:

а) б) в) г) д)

24. Определенность алгоритма означает:

25. Результативность алгоритма означает:

26. Массовость алгоритма означает:

27. Дискретность алгоритма означает:

28. Свойство алгоритма «конечность» означает:

29. Свойство алгоритма «дискретность» означает:

64. Свойство алгоритма «результативность» означает:

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

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

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

Элементы теории алгоритмов

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

Слово «алгоритм» произошло от имени выдающегося средневекового ученогоМухамеда ибн Муса Ал-Хорезми (IXвек н.э.), сокращенноАл-Хорезми . В латинском переводе одного из трудов Ал-Хорезми правила выполнения действий начинались словамиDIXIT ALGORIZMI (Алгоризми сказал), в других латинских переводах автор именовалсяALGORITHMUS (Алгоритмус).

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

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

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

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

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

Основные свойства алгоритма

Массовость.

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

Понятность.

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

Дискретность.

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

Конечность.

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

Определенность.

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

Эффективность.

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

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

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

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

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

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

Тема: Алгоритм. свойства алгоритма

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

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

q Дискретность (прерывность )- алгоритм должен быть разбит на
последовательность выполняемых шагов;

q Определенность (детерминированность, точность) - алгоритм
должен быть однозначно (точно) реализован исполнителем.

q Массовость - составленный алгоритм применим для решения
подобных задач с разными исходными данными.

q Конечность (результативность) - за конечное число шагов
должен быть получен результат;

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

q Понятность – алгоритм должен содержать только те команды,
которые понимает конкретный исполнитель.

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

При всем многообразии алгоритмов решения задач в них можно выделить три основных вида вычислительных процессов:

· линейный;

· ветвящийся;

· циклический.

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

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

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

Ответьте на вопросы теста

1.К основным свойствам алгоритма относятся…

а) краткость, определенность, верность, массовость, формальность

б) дискретность, важность, результативность, верность, формальность

в) достоверность, прерывистость, результативность, обобщенность, формальность

г) опеределенность, важность, результативность, массовость

2. Графическое описание алгоритма-это описание с помощью…

а) ….диаграмм

б)… блок-схем

в) …графиков

г) …всех перечисленных выше способов

3. К какому свойству алгоритма относится определение

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

а) массовость

б) результативность

в) формальность

г) достоверность

4. Описание алгоритма на алгоритмическом языке – это средство для записи алгоритма..

а) … в теоретическом виде

б) … в виде схем

в) … в аналитическом виде

г) … в специальном виде

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

а) результативностью

б) однозначностью

в) дискретностью

г) массовостью

д) все свойства определяют пошаговый характер алгоритма

6. Алгоритм, называется линейным, если...

а) он составлен так, что его выполнение предполагает многократное повторение одних и тех же действий;

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

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

г) он включает в себя вспомогательный алгоритм;

д) его запись представлена в виде одной строки.

7.К основным свойствам алгоритма НЕ относится...

а) корректность;

б) определенность

в) массовость

г) результативность

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

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

Слово «алгоритм» появилось в Средние века, когда ев­ропейцы познакомились со способами выполнения ариф­метических действий в десятичной системе счисления, описанными узбекским математиком Мухаммедом бен Муса аль-Хорезми («аль-Хорезми» - человек из города Хорезми; в настоящее время город Хива в Хорезмской об­ласти Узбекистана). Слово «алгоритм» есть результат ев­ропейского произношения слов «аль-Хорезми».

Алгоритм характеризуется следующими свойствами: дискретностью, массовостью, определенностью, результа­тивностью.

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

Массовость - применимость алгоритма ко всем зада­чам рассматриваемого типа при любых исходных данных.

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

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

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

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

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

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

Блоки, характеризующие нача­ло и конец алгоритма:

Блок, отображающий процесс {оператор), предназначенный для описания отдельных действий:

Блок, описывающий цикл с пара­метром:

Блок ввода/вывода с произвольного носителя информации:

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

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

нп - начало цикла; кп_ - конец цикла; для - цикл с параметром; если - условие; то - результат выполнения условия; иначе - результат невыполнения условия; всё - конец условия; пока - условие цикла.

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

Блок-схема линейного алгоритма нахождения перимет­ра прямоугольного треугольника Р при известных длинах его катетов a, b изображена на рис. 5.1.

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

Различают неполное (если-то) и полное (если-то-иначе) виды ветвления.

Неполное ветвление предполагает нали­чие оператора только на одной ветви (то; Да; Истина), на другой ветви оператор отсутст­вует и управление сразу переходит к точке слияния

Полное ветвление позволяет организовывать две вет­ви в алгоритме (то или иначе; Да илиНет; Истина или Ложь), каждая из которых ведет к общей точке их слия­ния (рис. 5.26).

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

Широкое применение получили три типа циклов: цикл с параметром, цикл с предусловием и цикл с постуслови­ем.

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

Количество шагов цикла с предусловием заранее не определено. В нем сначала проверяется выпол­нение условия. Если оно Истинно (Да), то исполняется тело цикла, после чего вновь проверяется условие. Ука­занные действия проверяются до тех пор, пока условие не примет значение Ложно (Нет).

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

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

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