Что значит формальный алгоритм
Алгоритм и его формальное исполнение
Цель урока: дать понятие об алгоритме, его свойствах, видах и о способах записи алгоритмов.
Обучающие:
– дать понятие об алгоритме;
– формировать представление: о линейном, разветвляющем и циклическом алгоритмах, о способах записи алгоритмов.
Формировать умение:
– выполнять и составлять алгоритмы в виде блок-схем.
Развивающие
– развитие алгоритмического мышления, познавательных интересов, навыков работы на компьютере;
– развивать память и внимание через активное использование информации;
– развивать умение анализировать;
– развивать рациональное мышление.
Воспитательные:
– воспитание творческого подхода к работе и желания экспериментировать;
– формирование коммуникативных компетенций учащихся через работу в группах;
– воспитание уважения к мнению других, умения слушать;
– воспитание информационной культуры учащихся, внимательности, аккуратности, дисциплинированности, усидчивости;
– формирование и развитие информационного видения окружающего мира.
Тип урока: Изучение нового материала.
Формы работы учащихся: беседа, работа в группах (парах).
Необходимое техническое оборудование.
I. Организационный момент.
Приветствие, проверка присутствующих. Объяснение хода урока.
II. Актуализация знаний.
Для решения большинства задач существует множество готовых программ. Но для того чтобы лучше понимать все происходящее с компьютером и уверенно принимать правильные решения, рядовому пользователю необходимо обладать определенной компьютерной грамотностью.
Следует отметить, что большинство редакторов (например, Microsoft Office Word, Excel) имеют встроенные средства программирования, освоив которые можно значительно расширить свои возможности.
III. Теоретическая часть.
Один из важнейших этапов решения задач на ЭВМ – составление алгоритма. О том, что такое алгоритмы, какими общими свойствами они обладают и как исполняются, мы и поговорим на этом уроке.
В 1983 году отмечалось 1200-летие со дня рождения одного из величайших ученых Средней Азии и средневекового Востока Мухамада ибн Мусы аль-Хорезми. Он написал ряд трактатов по арифметике и алгебре, в том числе книгу «Арифметика индусскими цифрами» – о счете с помощью десяти цифр и правилах арифметических действий с числами.
Имя ученого аль-Хорезми превратилось в понятие algorithmi, первоначально обозначавшее десятичную систему исчисления и правила арифметических действий в этой системе. Отсюда и возник современный научный термин «алгоритм».
Вы постоянно сталкиваетесь с этим понятием в различных сферах деятельности человека (кулинарные книги, инструкции по использованию различных приборов, правила решения математических задач. ). Обычно мы выполняем привычные действия не задумываясь, механически.
Алгоритм – описание последовательности действий (план), строгое исполнение которых приводит к решению поставленной задачи за конечное число шагов. (Слайд 3) Приложение
Существует несколько форм представления алгоритмов: (Слайд 4)
Например, вы хорошо знаете, как открывать ключом дверь. Однако, чтобы научить этому малыша, придется четко разъяснить и сами эти действия и порядок их выполнения: (Слайд 5)
В повседневной жизни алгоритм часто записывается в виде предложений, расположенных в порядке выполнения. Запись алгоритма с помощью слов называется словесным представлением алгоритма.
Составьте алгоритм задачи “Слепить снеговика”. Такого как на картинке. Пронумеруйте шаги так чтобы выполнив их последовательно мы слепили снеговика. (Слайд 6)
Если вы внимательно оглянитесь вокруг, то обнаружите множество алгоритмов которые мы с вами постоянно выполняем. Мир алгоритмов очень разнообразен. Несмотря на это, удается выделить общие свойства, которыми обладает любой алгоритм.
Свойства алгоритмов: (Слайд 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 г.
Формальные признаки алгоритмов
Различные определения алгоритма в явной или неявной форме содержат следующий ряд общих требований:
– дискретность – алгоритм должен представлять процесс решения задачи как последовательное выполнение некоторых простых шагов. При этом для выполнения каждого шага алгоритма требуется конечный отрезок времени, т.е. преобразование исходных данных в результат осуществляется во времени дискретно;
– детерминированность – определенность. В каждый момент времени следующий шаг работы однозначно определяется состоянием системы. Таким образом, алгоритм выдает один и тот же результат (ответ) для одних и тех же исходных данных. В современной трактовке у разных реализаций одного и того же алгоритма должен быть изоморфный граф. С другой стороны, существуют вероятностные алгоритмы, в которых следующий шаг работы зависит от текущего состояния системы и генерируемого случайного числа. Однако при включении метода генерации случайных чисел в список исходных данных вероятностный алгоритм становится подвидом обычного;
– понятность – алгоритм для исполнителя должен включать только те команды, которые ему (исполнителю) доступны, которые входят в его систему команд;
– завершаемость (конечность) – при корректно заданных исходных данных алгоритм должен завершать работу и выдавать результат за конечное число шагов. С другой стороны, вероятностный алгоритм может и никогда не выдать результат, но вероятность этого равна 0;
– массовость – алгоритм должен быть применим к разным наборам исходных данных;
– результативность – завершение алгоритма определенными результатами:
– алгоритм содержит ошибки, если приводит к получению неправильных результатов либо не дает результатов вовсе;
– алгоритм не содержит ошибок, если он дает правильные результаты для любых допустимых исходных данных.
Алгоритмизация – процесс разработки алгоритма (плана действий) для решения задачи. Алгоритм – это формальное описание способа решения задачи путем разбиения ее на конечную по времени, последовательность действий (элементарных операций). Под словом «формальное» подразумевается, что описание должно быть абсолютно полным и учитывать все возможные ситуации, которые могут встретиться по ходу решения задачи. Под элементарной операцией понимается действие, которое по заранее определенным критериям (например, очевидности) не имеет смысла детализировать.
Алгоритм на выбранном языке программирования записывается с помощью команд описания данных, вычисления значений и управления последовательностью выполнения программы.
Алгоритмический язык – формальный язык, используемый для записи, реализации и изучения алгоритмов. Всякий язык программирования является алгоритмическим языком, но не всякий алгоритмический язык пригоден для использования в качестве языка программирования. В узком смысле слова алгоритмическим языком также называют семейство языков программирования Алгол.
При преподавании информатики в школах для изучения основ алгоритмизации применяется так называемый школьный алгоритмический язык (учебный алгоритмический язык), использующий понятные школьнику слова на русском языке. В отличие от большинства языков программирования, алгоритмический язык не привязан к архитектуре компьютера, не содержит деталей, связанных с устройством машины.
Использование таких алгоритмических конструкций, как ветвление и цикл, подразумевает использование логических выражений, построение которых невозможно без понятия высказывания, логического значения, логических операций и кванторов.
В математической логике наряду с логическими операциями используются и кванторы. Квантор (от лат. quantum – сколько) – логическая операция, дающая количественную характеристику области предметов, к которой относится выражение, получаемое в результате ее применения.
В обычном языке носителями таких характеристик служат такие слова, как «все», «каждый», «некоторый», «любой», «всякий», «бесконечно много», «существует», «имеется», «единственный», «несколько», «конечное число», а также все количественные числительные. В формализованных языках, составной частью которых является исчисление предикатов, для выражения всех подобных характеристик оказывается достаточным кванторов двух видов: квантора общности и квантора существования.
Кванторы позволяют из конкретной высказывательной формы получить высказывательную форму с меньшим числом параметров, в частности из одноместной высказывательной формы получить высказывание.
Алгоритм, представленный в форме, пригодной для восприятия и выполнения компьютером, называется программой. Для записи алгоритмов в такой форме существуют различные языки программирования. Алгоритмические конструкции в языке программирования записываются с помощью соответствующих операторов. Информация, подаваемая на вход программе, называется данными. Одной из задач информатики является нахождение форм представления информации, удобных для компьютерной обработки. Информатика как точная наука работает с формальными (описанными математически строго) структурами данных. Примерами структур данных являются числа, логические значения, последовательности, таблицы, строки, списки, деревья, графы и т.п. Перечисленные структуры данных существуют независимо от их реализации в программировании. С этими структурами работали математики и в XVIII, и в XIX вв., когда еще не придумали вычислительные машины и никто не знал, что наступит эра информатизации. Удачный выбор структуры данных для представления информации может существенно повысить эффективность решения задачи. Реализация этих структур в языке программирования производится через соответствующие типы данных. Разработка программ в настоящее время – это достаточно сложный процесс, она требует и знания систем программирования, и владения технологией программирования, и сознательного использования одной из парадигм программирования, в частности объектно-ориентированного программирования.
Понятие алгоритма, являющееся фундаментальным понятием математики и информатики, возникло задолго до появления вычислительных машин. Первоначально под словом «алгоритм» понимали способ выполнения арифметических действий над десятичными числами. В дальнейшем это понятие стали использовать для обозначения любой последовательности действий, приводящей к решению поставленной задачи. Само же слово «алгоритм» появилось в Средние века, когда европейцы познакомились со способами выполнения арифметических действий, описанными узбекским математиком Мухаммедом бен Муса аль-Хорезми. Слово «алгоритм» – европеизированное произношение слов «аль-Хорезми».
В своем нынешнем смысле слово «алгоритм» часто ассоциировалось с алгоритмом Евклида, который представляет собой
процесс нахождения наибольшего общего делителя (НОД) двух чисел.
Приведем современное описание алгоритма Евклида с использованием блок-схемы.
Любой алгоритм существует не сам по себе, а предназначен для определенного исполнителя. Алгоритм описывается в командах исполнителя, который этот алгоритм будет выполнять. Объекты, над которыми исполнитель может совершать действия, образуют так называемую среду исполнителя, а множество команд, которые исполнитель может выполнять, – систему команд исполнителя (СКИ).
Таким образом, алгоритм можно рассматривать как последовательность команд управления работой исполнителя (предписание исполнителю на выполнение последовательности действий).
Алгоритмы подразделяются на:
– линейные (действия выполняются одно за другим);
– разветвленные (есть условие и существует хотя бы два пути выполнения алгоритма);
– циклические (многократное повторение некоторой группы шагов).
Алгоритм и его формальное исполнение. Свойства алгоритма и его исполнители
Свойства алгоритма и его исполнители
Дискретность. Разделение алгоритма на последовательность законченных действий – шагов. Каждое действие должно быть закончено прежде, чем исполнитель приступит к выполнению следующего шага.
Результативность. Получение из исходных данных результата за конечное число шагов.
Понятность . Алгоритм не должен содержать предписаний, смысл которых может восприниматься неоднозначно.
Массовость. Возможность применения алгоритма к большому количеству различных исходных данных.
Детерминированность. Выполнение команд алгоритма в строго определенной последовательности.
Точность. Запись алгоритма должна быть такой, чтобы на каждом шаге его выполнения было известно, какую команду нужно выполнять следующей.
Конечность. Завершение работы алгоритма за конечное число шагов.Вопрос о рассмотрении бесконечных алгоритмов остается за рамками теории алгоритмов.
Способы описания алгоритма
Словесный способ Алгоритм представляет собой описание на естественном языкепоследовательных этапов обработки данных.
Графический способ Изображение алгоритма в виде последовательности связанных между собой функциональных блоков.
Программный способ (алгоритмический ) Алгоритм, предназначенный для записи на компьютере, должен быть записан на понятном ему языке. Такой язык называется языком программирования, а запись алгоритма на этом языке – программа.
Линейный (последовательный) алгоритм — описание действий, которые выполняются однократно в заданном порядке
Разветвляющийся алгоритм — алгоритм, в котором в зависимости от условия выполняется либо одна, либо другая последовательность действий
Циклический алгоритм — описание действий, которые должны повторяться указанное число раз или пока не выполнено заданное условие.
Курс повышения квалификации
Дистанционное обучение как современный формат преподавания
Курс повышения квалификации
Педагогическая деятельность в контексте профессионального стандарта педагога и ФГОС
Курс повышения квалификации
Современные педтехнологии в деятельности учителя
Ищем педагогов в команду «Инфоурок»
Номер материала: ДБ-1072198
Не нашли то что искали?
Вам будут интересны эти курсы:
Оставьте свой комментарий
Авторизуйтесь, чтобы задавать вопросы.
Учителя о ЕГЭ: секреты успешной подготовки
Время чтения: 11 минут
Рособрнадзор разрешил провести ВПР по некоторым предметам на компьютерах
Время чтения: 0 минут
В России утвердили новый порядок формирования федерального перечня учебников
Время чтения: 1 минута
Поставщики интернета для школ будут работать с российским оборудованием
Время чтения: 1 минута
АСИ организует конкурс лучших управленческих практик в сфере детского образования
Время чтения: 2 минуты
В Минпросвещения рассказали о формате обучения школьников после праздников
Время чтения: 1 минута
Учителя о ЕГЭ: секреты успешной подготовки
Время чтения: 11 минут
Подарочные сертификаты
Ответственность за разрешение любых спорных моментов, касающихся самих материалов и их содержания, берут на себя пользователи, разместившие материал на сайте. Однако администрация сайта готова оказать всяческую поддержку в решении любых вопросов, связанных с работой и содержанием сайта. Если Вы заметили, что на данном сайте незаконно используются материалы, сообщите об этом администрации сайта через форму обратной связи.
Все материалы, размещенные на сайте, созданы авторами сайта либо размещены пользователями сайта и представлены на сайте исключительно для ознакомления. Авторские права на материалы принадлежат их законным авторам. Частичное или полное копирование материалов сайта без письменного разрешения администрации сайта запрещено! Мнение администрации может не совпадать с точкой зрения авторов.
ФОРМАЛЬНОЕ ОПРЕДЕЛЕНИЕ АЛГОРИТМА
Построим контекстно свободный язык L2, который будем называть алгоритмическим. Для этого воспользуемся нотацией Бекуса. Предложение языка L2 будем обозначать метасимволом (запись первичного алгоритма):
Для того чтобы L2 был полностью определен, необходимо задать с помощью метаформул значения метасимволов:
Мы этого не будем делать, определяя тем самым не один язык, а класс языков. В качестве L2 может быть принят любой из конкретных языков этого класса. Заметим только, что разделители должны быть выбраны так, чтобы они однозначно разделяли приказы на соответствующие части, а разделитель III должен быть отличим от разделителя VI, а также от любой отсылки и метки.
Для того, чтобы наделить запись первичного алгоритма смыслом, зададим следующее правило.
П р а в и л о выполнения первичного алгоритма.
1) Просматривая запись первичного алгоритма с начала, найти первый приказ; перейти к п.2.
2) Если рассматриваемый приказ является безусловным, перейти к п.3, иначе к п.5.
3) Применить операцию, соответствующую знаку действия данного приказа, к операнду; найти отсылку в данном приказе; перейти к п.4.
6) Найти первую отсылку данного приказа; перейти к п.4.
7) Найти вторую отсылку данного приказа; перейти к п.4.
Заметим, что правило выполнения зависит от языка L2 и от заранее выбранного набора операций. Это правило является алгоритмом в интуитивном смысле слова, однако сформулированным настолько точно, что при его выполнении не может возникнуть никаких неясностей.
Запись первичного алгоритма, рассматриваемая вместе с правилом его выполнения, называется первичным алгоритмом.
Применение правила выполнения первичного алгоритма к совокупности, образованной из записи первичного алгоритма и записи операнда, порождает процесс, называемый алгоритмическим. Этот процесс может либо заканчиваться при выполнении п.2 правила, и тогда полученный операнд называется искомым результатом, либо обрываться из-за невыполнимости какого-либо другого пункта правила (безрезультатно остановиться), либо продолжаться неограниченно (не останавливаться).
Следует обратить внимание на то, что алгоритмический процесс представляет собой процесс совместного преобразования совокупности записей алгоритма и операнда. Частной особенностью этого преобразования является неизменность символьной конструкции, являющейся записью алгоритма.
Натуральные алгоритмы. Натуральными алгоритмами называются первичные алгоритмы, для выполнения которых требуется только знание натуральных операций и, может быть, линеаризации и делинеаризации. Приведем одно из семейств натуральных алгоритмов.
Алгоритмический язык L1 конкретизируем следующим образом:
Смысл знаков действий и знаков условий разъясняет табл.3.2.
Приказы алгоритмического языка могут иметь вид
Знаки натуральных операций
Для построения грамматик языков L1 и L2 достаточно знания операции конкатенации. Таким образом, построенный нами класс первичных (натуральных) алгоритмов, использующих только натуральные операции, линеаризацию и делинеаризацию, определен математически вполне строго.
Первый пункт общего определения алгоритма гласит:
Но общее понятие алгоритма существенно шире. Его второй пункт гласит:
Наконец, третий пункт общего определения гласит:
Таким образом, каждый алгоритм в широком формальном смысле, если он не первичный, имеет свой алгоритм выполнения. Если бы не были определены первичные алгоритмы, то невозможно было бы дать строгое определение и остальных алгоритмов, так как невозможно было бы указать ни одного алгоритма выполнения. Но после того, как построен хотя бы один алгоритм выполнения, можно строить многие другие, уже не привлекая первичных алгоритмов.
Одноместным называется n-местный алгоритм, для которого n=1. Первичные алгоритмы тоже будем называть одноместными.
Алгоритм в широком формальном смысле называется применимым к данному конкретному операнду (набору операндов), если алгоритм его выполнения применим к соответствующей символьной конструкции, объединяющей записи алгоритма и операнда ( операндов ). В противном случае говорят, что алгоритм в широком формальном смысле неприменим а данному операнду (набору операндов).
Два алгоритма называются функционально эквивалентными, если их языки операндов совпадают между собой и если всегда для одного и того же исходного данного оба алгоритма либо дают один и тот же результат, либо оба к нему неприменимы.
Т е о р е м а. Для всякого семейства первичных алгоритмов (определяемого двумя языками L1 и L2 и правилом выполнения) существует алгоритм в широком формальном смысле, который эквивалентен правилу их выполнения и имеет запись, графически тождественную с записью этого правила.
Такой алгоритм естественно назвать алгоритмом выполнения для данного семейства первичных алгоритмов. Приведенная теорема, хотя и не позволяет при определении понятия алгоритма отказаться от определения первичных алгоритмов, все же «уравнивает в правах» первичные алгоритмы с непервичными.
При соблюдении вышеуказанных предосторожностей можно следующим образом описать связь между алгоритмом, отвечающими ему языками и алгоритмом выполнения.
Для каждого семейства алгоритмов, определяемого некоторым алгоритмом выполнения W, множество L3=
Рассмотрим два семейства алгоритмов, у которых эквивалентны алгоритмы выполнения. Ясно, что эти семейства имеют одни и те же языки операндов, искомых результатов и алгоритмический. Возьмем два алгоритма, принадлежащих разным семействам, но имеющих одну и ту же запись. Такие алгоритмы эквивалентны, но при выполнении порождают неодинаковые процессы.
О п р е д е л е н и е. Два алгоритма, которые имеют одинаковые записи и эквивалентны, являются одним и тем же алгоритмом (или экземплярами одного и того же алгоритма).
Теперь нетрудно уточнить приведенное выше общее определение алгоритма (вернее, дополнить его).
Алгоритм — это совокупность записи алгоритма и отображения, индуцируемого его алгоритмом выполнения.