Формальные признаки алгоритмов
Различные определения алгоритма в явной или неявной форме содержат следующий ряд общих требований:
– дискретность – алгоритм должен представлять процесс решения задачи как последовательное выполнение некоторых простых шагов. При этом для выполнения каждого шага алгоритма требуется конечный отрезок времени, т.е. преобразование исходных данных в результат осуществляется во времени дискретно;
– детерминированность – определенность. В каждый момент времени следующий шаг работы однозначно определяется состоянием системы. Таким образом, алгоритм выдает один и тот же результат (ответ) для одних и тех же исходных данных. В современной трактовке у разных реализаций одного и того же алгоритма должен быть изоморфный граф. С другой стороны, существуют вероятностные алгоритмы, в которых следующий шаг работы зависит от текущего состояния системы и генерируемого случайного числа. Однако при включении метода генерации случайных чисел в список исходных данных вероятностный алгоритм становится подвидом обычного;
– понятность – алгоритм для исполнителя должен включать только те команды, которые ему (исполнителю) доступны, которые входят в его систему команд;
– завершаемость (конечность) – при корректно заданных исходных данных алгоритм должен завершать работу и выдавать результат за конечное число шагов. С другой стороны, вероятностный алгоритм может и никогда не выдать результат, но вероятность этого равна 0;
– массовость – алгоритм должен быть применим к разным наборам исходных данных;
– результативность – завершение алгоритма определенными результатами:
– алгоритм содержит ошибки, если приводит к получению неправильных результатов либо не дает результатов вовсе;
– алгоритм не содержит ошибок, если он дает правильные результаты для любых допустимых исходных данных.
Алгоритмизация – процесс разработки алгоритма (плана действий) для решения задачи. Алгоритм – это формальное описание способа решения задачи путем разбиения ее на конечную по времени, последовательность действий (элементарных операций). Под словом «формальное» подразумевается, что описание должно быть абсолютно полным и учитывать все возможные ситуации, которые могут встретиться по ходу решения задачи. Под элементарной операцией понимается действие, которое по заранее определенным критериям (например, очевидности) не имеет смысла детализировать.
Алгоритм на выбранном языке программирования записывается с помощью команд описания данных, вычисления значений и управления последовательностью выполнения программы.
Алгоритмический язык – формальный язык, используемый для записи, реализации и изучения алгоритмов. Всякий язык программирования является алгоритмическим языком, но не всякий алгоритмический язык пригоден для использования в качестве языка программирования. В узком смысле слова алгоритмическим языком также называют семейство языков программирования Алгол.
При преподавании информатики в школах для изучения основ алгоритмизации применяется так называемый школьный алгоритмический язык (учебный алгоритмический язык), использующий понятные школьнику слова на русском языке. В отличие от большинства языков программирования, алгоритмический язык не привязан к архитектуре компьютера, не содержит деталей, связанных с устройством машины.
Использование таких алгоритмических конструкций, как ветвление и цикл, подразумевает использование логических выражений, построение которых невозможно без понятия высказывания, логического значения, логических операций и кванторов.
В математической логике наряду с логическими операциями используются и кванторы. Квантор (от лат. quantum – сколько) – логическая операция, дающая количественную характеристику области предметов, к которой относится выражение, получаемое в результате ее применения.
В обычном языке носителями таких характеристик служат такие слова, как «все», «каждый», «некоторый», «любой», «всякий», «бесконечно много», «существует», «имеется», «единственный», «несколько», «конечное число», а также все количественные числительные. В формализованных языках, составной частью которых является исчисление предикатов, для выражения всех подобных характеристик оказывается достаточным кванторов двух видов: квантора общности и квантора существования.
Кванторы позволяют из конкретной высказывательной формы получить высказывательную форму с меньшим числом параметров, в частности из одноместной высказывательной формы получить высказывание.
Алгоритм, представленный в форме, пригодной для восприятия и выполнения компьютером, называется программой. Для записи алгоритмов в такой форме существуют различные языки программирования. Алгоритмические конструкции в языке программирования записываются с помощью соответствующих операторов. Информация, подаваемая на вход программе, называется данными. Одной из задач информатики является нахождение форм представления информации, удобных для компьютерной обработки. Информатика как точная наука работает с формальными (описанными математически строго) структурами данных. Примерами структур данных являются числа, логические значения, последовательности, таблицы, строки, списки, деревья, графы и т.п. Перечисленные структуры данных существуют независимо от их реализации в программировании. С этими структурами работали математики и в XVIII, и в XIX вв., когда еще не придумали вычислительные машины и никто не знал, что наступит эра информатизации. Удачный выбор структуры данных для представления информации может существенно повысить эффективность решения задачи. Реализация этих структур в языке программирования производится через соответствующие типы данных. Разработка программ в настоящее время – это достаточно сложный процесс, она требует и знания систем программирования, и владения технологией программирования, и сознательного использования одной из парадигм программирования, в частности объектно-ориентированного программирования.
Понятие алгоритма, являющееся фундаментальным понятием математики и информатики, возникло задолго до появления вычислительных машин. Первоначально под словом «алгоритм» понимали способ выполнения арифметических действий над десятичными числами. В дальнейшем это понятие стали использовать для обозначения любой последовательности действий, приводящей к решению поставленной задачи. Само же слово «алгоритм» появилось в Средние века, когда европейцы познакомились со способами выполнения арифметических действий, описанными узбекским математиком Мухаммедом бен Муса аль-Хорезми. Слово «алгоритм» – европеизированное произношение слов «аль-Хорезми».
В своем нынешнем смысле слово «алгоритм» часто ассоциировалось с алгоритмом Евклида, который представляет собой
процесс нахождения наибольшего общего делителя (НОД) двух чисел.
Приведем современное описание алгоритма Евклида с использованием блок-схемы.
Стрелка , используемая при описании данного алгоритма, обозначает операцию замещения, или присваивания. Разумеется, в книге Евклида «Начала» этот алгоритм сформулирован не совсем так (а записан совсем не так). В данном случае мы продемонстрировали современную формулировку этого алгоритма и одну из распространенных наглядных форм записи алгоритмов.
Любой алгоритм существует не сам по себе, а предназначен для определенного исполнителя. Алгоритм описывается в командах исполнителя, который этот алгоритм будет выполнять. Объекты, над которыми исполнитель может совершать действия, образуют так называемую среду исполнителя, а множество команд, которые исполнитель может выполнять, – систему команд исполнителя (СКИ).
Таким образом, алгоритм можно рассматривать как последовательность команд управления работой исполнителя (предписание исполнителю на выполнение последовательности действий).
Алгоритмы подразделяются на:
– линейные (действия выполняются одно за другим);
– разветвленные (есть условие и существует хотя бы два пути выполнения алгоритма);
– циклические (многократное повторение некоторой группы шагов).
Источник
Алгоритм и его формальное исполнение
Цель урока: дать понятие об алгоритме, его свойствах, видах и о способах записи алгоритмов.
Обучающие:
– дать понятие об алгоритме;
– формировать представление: о линейном, разветвляющем и циклическом алгоритмах, о способах записи алгоритмов.
Формировать умение:
– выполнять и составлять алгоритмы в виде блок-схем.
Развивающие
– развитие алгоритмического мышления, познавательных интересов, навыков работы на компьютере;
– развивать память и внимание через активное использование информации;
– развивать умение анализировать;
– развивать рациональное мышление.
Воспитательные:
– воспитание творческого подхода к работе и желания экспериментировать;
– формирование коммуникативных компетенций учащихся через работу в группах;
– воспитание уважения к мнению других, умения слушать;
– воспитание информационной культуры учащихся, внимательности, аккуратности, дисциплинированности, усидчивости;
– формирование и развитие информационного видения окружающего мира.
Тип урока: Изучение нового материала.
Формы работы учащихся: беседа, работа в группах (парах).
Необходимое техническое оборудование.
- Организационный момент. (1 мин.)
- Актуализация опорных знаний. (5 мин.)
- Изучение нового материала (15 мин.)
- Практическая работа в группах (закрепление материала). (10 мин.)
- Домашнее задание. (2 мин.)
- Вопросы учеников. (5 мин.)
- Подведение итогов. (2 мин.)
I. Организационный момент.
Приветствие, проверка присутствующих. Объяснение хода урока.
II. Актуализация знаний.
Для решения большинства задач существует множество готовых программ. Но для того чтобы лучше понимать все происходящее с компьютером и уверенно принимать правильные решения, рядовому пользователю необходимо обладать определенной компьютерной грамотностью.
Следует отметить, что большинство редакторов (например, Microsoft Office Word, Excel) имеют встроенные средства программирования, освоив которые можно значительно расширить свои возможности.
III. Теоретическая часть.
Один из важнейших этапов решения задач на ЭВМ – составление алгоритма. О том, что такое алгоритмы, какими общими свойствами они обладают и как исполняются, мы и поговорим на этом уроке.
В 1983 году отмечалось 1200-летие со дня рождения одного из величайших ученых Средней Азии и средневекового Востока Мухамада ибн Мусы аль-Хорезми. Он написал ряд трактатов по арифметике и алгебре, в том числе книгу «Арифметика индусскими цифрами» – о счете с помощью десяти цифр и правилах арифметических действий с числами.
Имя ученого аль-Хорезми превратилось в понятие algorithmi, первоначально обозначавшее десятичную систему исчисления и правила арифметических действий в этой системе. Отсюда и возник современный научный термин «алгоритм».
Вы постоянно сталкиваетесь с этим понятием в различных сферах деятельности человека (кулинарные книги, инструкции по использованию различных приборов, правила решения математических задач. ). Обычно мы выполняем привычные действия не задумываясь, механически.
Алгоритм – описание последовательности действий (план), строгое исполнение которых приводит к решению поставленной задачи за конечное число шагов. (Слайд 3) Приложение
Существует несколько форм представления алгоритмов: (Слайд 4)
- На естественном языке (словесная форма).
- На языке блок-схем.
- На алгоритмическом языке – программа.
Например, вы хорошо знаете, как открывать ключом дверь. Однако, чтобы научить этому малыша, придется четко разъяснить и сами эти действия и порядок их выполнения: (Слайд 5)
- Достать ключ из кармана.
- Вставить ключ в замочную скважину.
- Повернуть ключ два раза против часовой стрелки.
- Вынуть ключ.
В повседневной жизни алгоритм часто записывается в виде предложений, расположенных в порядке выполнения. Запись алгоритма с помощью слов называется словесным представлением алгоритма.
Составьте алгоритм задачи “Слепить снеговика”. Такого как на картинке. Пронумеруйте шаги так чтобы выполнив их последовательно мы слепили снеговика. (Слайд 6)
Перед вами 6 рисунков – столько , сколько шагов в алгоритме. Пронумеруйте рисунки – шаги алгоритма. (Слайд 7)
Если вы внимательно оглянитесь вокруг, то обнаружите множество алгоритмов которые мы с вами постоянно выполняем. Мир алгоритмов очень разнообразен. Несмотря на это, удается выделить общие свойства, которыми обладает любой алгоритм.
Свойства алгоритмов: (Слайд 8)
- Дискретность (алгоритм должен состоять из конкретных действий, следующих в определенном порядке);
- Детерминированность (любое действие должно быть строго и недвусмысленно определено в каждом случае);
- Конечность (каждое действие и алгоритм в целом должны иметь возможность завершения);
- Массовость (один и тот же алгоритм можно использовать с разными исходными данными);
- Результативность (отсутствие ошибок, алгоритм должен приводить к правильному результату для всех допустимых входных значениях).
В алгоритме команды записаны одна за другой в определенном порядке. Исполняются они не обязательно в том же порядке. В зависимости от того, каков порядок исполнения команд, можно выделить три типа алгоритмов: линейный, разветвляющий, циклический. (Слайд9) и вспомогательные.
Виды алгоритмов: (Слайд 10)
- Линейный алгоритм (описание действий, которые выполняются однократно в заданном порядке);
- Циклический алгоритм (описание действий, которые должны повторятся указанное число раз или пока не выполнено задание);
- Разветвляющий алгоритм (алгоритм, в котором в зависимости от условия выполняется либо одна, либо другая последовательность действий).
Для более наглядного представления алгоритма широко используется графическая форма – блок-схема, (Слайд 12) которая составляется из стандартных графических объектов.. Каждое графически обозначенное предложение алгоритма называется блоком. В блок записывается только одна команда. Блоки (шаги) алгоритма соединены стрелочками.
Примеры записи алгоритмов в виде блок-схемы:
Линейный алгоритм. (Слайд 13)
Вычислить площадь прямоугольника со сторонами А, В. (Слайд 14)
Разветвляющий алгоритм. (Слайд15)
Циклический алгоритм. (Слайд 17, 18)
Стадии создания алгоритма: (Слайд 19)
- Алгоритм должен быть представлен в форме, понятной человеку, который его разрабатывает.
- Алгоритм должен быть представлен в форме, понятной тому объекту (в том числе и человеку), который будет выполнять описанные в алгоритме действия.
Объект, который будет выполнять алгоритм, обычно называют исполнителем. (Слайд 20)
Исполнитель – объект, который выполняет алгоритм.
Идеальными исполнителями являются машины, роботы, компьютеры.
Компьютер – автоматический исполнитель алгоритмов.
Алгоритм, записанный на “понятном” компьютеру языке программирования, называется программой.
Закрепление: ответить на вопросы теста http://school-collection.edu.ru/catalog/res/ef6533fd-06d1-4b38-9498-ac58430f845e/view/
Ответить на вопросы теста.
- Что такое алгоритм? Приведите примеры алгоритмов.
- Какие свойства алгоритмов вы знаете?
- Какие виды алгоритмов вы знаете?
- Какие способы записи алгоритмов вы знаете?
- Что такое исполнитель алгоритмов?
- Что такое программа?
IV. Домашнее задание.
Ответить на вопросы кроссворда: http://school-collection.edu.ru/catalog/rubr/a30a9550-6a62-11da-8cd6-0800200c9a66/63387/?interface=pupil&class=51
V. Вопросы учеников.
Ответы на вопросы учащихся.
Подведение итога урока. Выставление оценок.
На уроке мы познакомились с тем, что такое алгоритм, какими свойствами он обладает и как его можно записать.
Н.Д. Угринович. Базовый учебник “Информатика и ИКТ”. 9-й класс. БИНОМ. 2011 г.
Источник
