лекция. Лекция_ Основы алгоритмизации. Лекция. Основы алгоритмизации
 Скачать 0.68 Mb.
|
|
ГБПОУ "Краевой политехнический колледж" г.Чернушка, Пермский край ЛЕКЦИЯ. ОСНОВЫ АЛГОРИТМИЗАЦИИ Алгоритм – это конечная последовательность чётко определённых действий (инструкций, команд, правил), необходимых для решения задачи. Существуют параллельные алгоритмы, действия в которых могут выполняться параллельно, независимо друг от друга. Основные признаки алгоритма 1. Наличие исходных данных на входе алгоритма. 2. Наличие определённого результата на выходе алгоритма. 3. Массовость (общность() – алгоритм должен позволять решать задачу с произвольным набором исходных данных, а не только к какими-то конкретными наборами исходных данных. 4. Детерминированность (повторяемость) – при одних и тех же исходных данных на входе алгоритм должен приводить к одному и тому же результату на выходе. 5. Однозначность (определённость) – инструкции алгоритма должны быть понятны и однозначно истолкованы для исполнителя. 6. Конечность (дискретность) – алгоритм должен приводить к решению задачи за конечное число шагов. 7. Корректность – алгоритм должен приводить к корректному решению задачи. Исполнитель алгоритма Исполнитель алгоритма – это система, способная выполнить действия, определяемые алгоритмом. Исполнителем алгоритма могут быть: человек (биологическая система), компьютер (техническая система), иные системы. Исполнитель характеризуется системой команд. Система команд – это совокупность команд, которые может выполнять исполнитель. Получив команду, исполнитель выполняет соответствующее полученной команде элементарное действие. Чтобы исполнитель был способен выполнить алгоритм, алгоритм должен быть описан в системе команд исполнителя. Исполнитель выполняет алгоритм формально, не размышляя над выполняемыми командами, а строго следуя пошаговым инструкциям алгоритма. Способы описания алгоритмов Алгоритм может быть описан следующими способами: словесное описание алгоритма на естественном языке; описание алгоритма псевдокодом. Псевдокод – частично формализованный естественный язык с элементами языка программирования и общепринятыми математическими обозначениями; графическое описание алгоритма блок-схемами; описание на языке программирования (алгоритмическом, логическом или объектно-ориентированном). Графическое описание алгоритма Блок-схема – это подробное графическое представление логической структуры программы или алгоритма с помощью стандартных блоков (условных символов), соединённых линиями. Правила выполнения блок-схем определяются стандартом ГОСТ 19.701–90 (ISO 5807-85) «Схемы алгоритмов, программ, данных и систем. Обозначения условные и правила выполнения», который определяет внешний вид графических блоков и их назначение. Стандарт подразделяет символы в четыре группы: символы данных; символы процесса; символы линий; специальные символы. Каждый символ имеет определённую форму. Внутри символа может помещаться текст, поясняющий его функцию. Основные символы
Базовые структуры алгоритмов Структура любого алгоритма может быть построена комбинацией базовых структур: линейный алгоритм (следование); разветвляющийся алгоритм (ветвление, развилка); циклический алгоритм (повтор, цикл). Базовые структуры имеют по одному входу и одному выходу. Линейный алгоритм Линейный алгоритм (рис. 1) – это последовательность действий, каждое из которых выполняется один раз и имеет по одному входу и одному выходу.  Рисунок 1 – Структура линейного алгоритма Примеры:   Разветвляющийся алгоритм Разветвляющийся алгоритм – это алгоритм, в котором в зависимости от результата проверки некоторого условия осуществляется выбор одного из альтернативных путей (ветви) выполнения алгоритма. Различают полное и неполное ветвления. Полное ветвление (рис. 2 а, б) предполагает выполнение действий в обеих ветвях алгоритма, неполное ветвление (рисунок 3 а, б) – только в одной ветви алгоритма.  Рисунок 2 – Структура полного ветвления  Рисунок 3 – Структура неполного ветвления Примеры:  Циклический алгоритм Циклический алгоритм – это алгоритм, в котором осуществляется многократное выполнение некоторой последовательности действий. Совокупность действий, повторяющихся на каждом шагу цикла, называется телом цикла. Циклические алгоритмы по способу выхода из цикла подразделяются на арифметические и итерационные. У арифметических циклов количество повторений известно заранее или может быть вычислено. У итерационных циклов количество повторений заранее не известно. Выход из итерационного цикла происходит в результате достижения требуемой точности приближённых вычислений. Циклический алгоритм типа «до» С постусловием (рис. 4) условие цикла проверяется после выполнения действия.  Рисунок 4 – Структура цикла с постусловием (цикл «до») Циклический алгоритм типа «пока» С предусловие (рис. 5) условие цикла проверяется перед выполнением действия. Тело цикла выполняется до тех пор, пока выполняется условие «пока».  Рисунок 5 – Структура цикла с предусловием (цикл «пока») Циклический алгоритм типа «для» Тело цикла выполняется для всех значений параметра заголовка цикла (рис. 6). Запись «I=i1, iN, k» означает, что параметр I изменяется от i1 до iN с шагом k.  Рисунок 6 – Структура цикла с предусловием (цикл «пока») Вложенные циклы Цикл называется вложенным (рис .7), если он размещён внутри другого цикла. Внутренний цикл вызывается при проходе внешнего цикла. После завершения внутреннего цикла вызывается внешний цикл.  Рисунок 7 – Структура вложенного цикла ВОПРОСЫ ДЛЯ САМОПРОВЕРКИ Уважаемые студенты! Это вопросы и задания для самопроверки. Знания, полученные при их выполнении, пригодятся Вам при итоговом тестировании по курсу «Информатика и ИКТ». Вопросы вы можете задать на форуме курса. Что такое алгоритм? Перечислите и объясните признаки алгоритма. Что делает исполнитель? Кто или что может быть исполнителем? Перечислите способы описания алгоритма. Что такое блок-схема? Перечислите и объясните символы, используемые в блок-схеме. Что такое линейный алгоритм? Приведите пример линейного алгоритма. Что такое разветвляющийся алгоритм? Перечислите виды разветвляющегося алгоритма. Приведите пример разветвляющегося алгоритма. Что такое циклический алгоритм? Перечислите виды циклических алгоритмов. Приведите пример циклического алгоритма. Информатика и ИКТ Страница |
