По теоретическому материалу 2 семестра

Вид материала

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

Содержание 14.Понятие алгоритма. Свойства и виды алгоритмов. Способы задания алгоритмов. Механический алгоритм Вероятностный (стохастический) алгоритм Эвристический алгоритм Свойства алгоритма 15.Элементы блок схем. Алгоритмические структуры (линейная, ветвление, цикл). Линейная алгоритмическая структура. Алгоритмическая структура «ветвление». Алгоритмическая структура «цикл».

Подобный материал:

• Все задания находятся на сайте школы, 20.04kb.
• Автор программы: Кутлалиев А. Х. ( akutlaliev@hse ru ) Рекомендована секцией умс, 226.67kb.
• Темы лекций второго семестра Программа экзамена второго семестра Тема, 71.64kb.
• Молекулярная биология, 75.71kb.
• Матричная структура фист осень 2011/12, 105.89kb.
• Матричная структура фист осень 2011/12, 104.73kb.
• Программа по курсу общей физики для Радиофизического факультета, 140.36kb.
• Программа вступительных испытаний по теоретическому курсу «физическая культура» Специальность, 32.94kb.
• Рабочий план II курса весеннего семестра фбпэ факультета на 200, 698.38kb.
• Учебно-методический комплекс по дисциплине «отечественная история» Архангельск, 277.43kb.

14.Понятие алгоритма. Свойства и виды алгоритмов. Способы задания алгоритмов.

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

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

(Algorithmi (Аль-Хорезми) - среднеазиатский математик XI в., впервые описавший правила выполнения четырёх арифметических действий).

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

Исполнитель алгоритма - человек или устройство (в частности, процессор ЭВМ), умеющий выполнять определённый набор действий. Такой набор действий - система команд исполнителя.

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

• механические алгоритмы, или детерминированные, жесткие (например, алгоритм работы машины, двигателя и т. п.);
  
• гибкие алгоритмы, например стохастические, т. е. вероятностные и эвристические.
  

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

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

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

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

понятность для исполнителя – содержание предписания о выполнении только таких действий, которые входят в систему команд исполнителя;

дискретность (прерывность) – выполнение команд алгоритма последовательно, с точной фиксацией моментов окончания выполнения одной команды и начала выполнения следующей;

определённость - каждое правило алгоритма должно быть чётким и однозначным;

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

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

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

• словесный;
  
• графический;
  
• табличный;
  
• программный.
  

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

Графический способ записи - в виде блок-схем. Блок-схема - последовательность блоков, соединенных линиями передачи (ветвями).

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

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

15.Элементы блок схем. Алгоритмические структуры (линейная, ветвление, цикл).

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

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

Символ ''Решение" представляет собой ромб. Используется для отображения выбора направления вычислений в зависимости от результатов (исходов) проверки некоторого условия. Условие записывается внутри ромба. В качестве признаков условия используются слова "Да", "Нет" и математические символы: =, ≠, >, < , и т. п.
Признаки проставляются над выходящими линиями потока или справа от них. Если число исходов проверки условий больше трех, то признаки условия проставляются в разрыве линии потока.

"Ввод-вывод" представляет собой параллелограмм. Используется для отображения ввода или вывода и сопровождающих их преобразований данных к виду, пригодному для переработки или регистрации. Внутри символа может также размещаться запись формульно-словесного типа. Например, ' Ввод X" или "Вывод У".

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

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

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



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

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

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



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

Алгоритм, в котором серия команд выполняется многократно, называется циклическим алгоритмом.