©Максимовская М.А., учитель информатики ЦО 109, 2010 г. - презентация

1 ©Максимовская М.А., учитель информатики ЦО 109, 2010 г.

2 «алгоритм» Слово «алгоритм» возникло в Европе после перевода на латынь книги Абдуллы (Абу Джафара) Мухаммеда бен Муса аль-Хорезми (из города Хорезма), написанной в 825 году н.э., в которой были описаны способы выполнения арифметических действий над многозначными числами. Аль-Хорезми тогда писалось как «Алгоритми». Теория алгоритмов – область математики – посвящена исследованию свойств, способов записи, видов и сферы применения различных алгоритмов. Первое определение понятия «алгоритм» создал американский математик Алонзо Чёрч ( ) в 1930 г. В дальнейшем это понятие уточнялось различными учёными-математиками. Алгоритмическая модель или алгоритм информационной моделипоследовательности действийпланк решению поставленной задачиконечное число шагов Алгоритмическая модель или алгоритм – это разновидность информационной модели, где содержится описание последовательности действий (план), строгое исполнение которых приводит к решению поставленной задачи за конечное число шагов. Алгоритмизацияпроцесс разработкиалгоритма Алгоритмизация – процесс разработки алгоритма (плана действий) для решения задачи.

3 АЛГОРИТМ ДИСКРЕТНОСТЬТОЧНОСТЬКОНЕЧНОСТЬМАССОВОСТЬРЕЗУЛЬТАТИВНОСТЬ 1. Дискретность (лат. discretus – разделённый, прерывистый). Любой алгоритм должен состоять из конкретных действий, следующих в определённом порядке (например: невозможно повернуть ключ в замке, если вы не вставили его в этот замок; или проехать три остановки в автобусе, в который вам не удалось сесть); 2. Точность (детерминированность) (лат. determinate – определённость, точность). Любое действие алгоритма должно быть строго определено в каждом случае и не допускать двух и более различных трактовок (например: чтобы доехать до определённого места вам необходим определённый автобус (например, 101), поэтому, если в описании пути стоит фраза «кажется, то ли 101, то ли 111 автобус, вы рискуете до места не доехать); 3. Конечность. Каждое действие в алгоритме и сам алгоритм должны иметь возможность завершения (например: если поставить в ЛогоМирах в инструкции для кнопки опцию «Много раз», то алгоритм в инструкции будет выполняться бесконечно). 4. Массовость. Один и тот же алгоритм можно использовать с разными исходными данными (например: бутерброд можно приготовить с колбасой, сыром, мясом и т.д., но порядок приготовления будет один и тот же); 5. Результативность. В алгоритме не должно быть ошибок, т.е. применение алгоритма должно приводить к правильному результату (например: если нарушить порядок действий в алгебраическом выражении, невозможно будет получить его правильное значение; или при решении физической задачи применить неверную формулу).

4 Линейный последовательныйалгоритм однократнозаданном порядкепоследовательно Линейный (последовательный) алгоритм – описание действий, которые выполняются однократно, в заданном порядке (последовательно, одно за другим). Например: Алгоритм отпирания дверей; Алгоритм вычисления значения числовых выражений, содержащих только действия сложения и вычитания (1299 – – 789). Циклический алгоритм повторяться Перечень повторяющихся действийтелом цикла Циклический алгоритм – описание действий, которые должны повторяться указанное число раз или пока не выполнено заданное условие. Перечень повторяющихся действий называется телом цикла. Например: Алгоритм покраски забора: 1) покрасить одну доску; 2) перейти к следующей; 3) выполнить действие 1; 4) завершить работу только после покраски последней доски.

5 Разветвляющийсяалгоритм Разветвляющийся алгоритм – алгоритм, в котором в зависимости от условия выполняется либо одна, либо другая последовательность действий. Полная формаДействия при выполнении условияприневыполнении Полная форма: «если выполняется условие, то …, иначе …». Действия предусмотрены и при выполнении условия, и при его невыполнении. Неполная формаДействия только при выполнении условия Неполная форма: «если выполняется условие, то …». Действия предусмотрены только при выполнении условия. При невыполнении условия никакие действия не выполняются. Например: 1) Если пошёл дождь, то откройте зонт, иначе – зонт положите в сумку (полная форма разветвляющегося алгоритма); Если пошёл дождь, то откройте зонт (неполная форма разветвляющегося алгоритма). 2) Если билет в кино стоит не больше 100 рублей, то купить билет и занять место в зале, иначе – вернуться домой. (Определите форму алгоритма) 3) Из инструкции коммунальным службам: «Если среднесуточная температура воздуха ниже 8 градусов, то включить отопление. (Определить форму алгоритма)

6 Вспомогательный алгоритмалгоритмспользовать других алгоритмах Вспомогательный алгоритм – алгоритм, который можно использовать в других алгоритмах, указав только его имя. должно быть присвоено имя Вспомогательному алгоритму должно быть присвоено имя. Например: 1) 1) Вычислить значение выражения 5a + b:4. 1. Установить значение для переменной а ; умножение 2. Выполнить умножение числа 5 на a записать их произведение; 3. Установить значение для переменной b ; деление 4. Выполнить деление чисел b:4 и записать частное; сложение 5. Выполнить сложение полученных на шаге 2 произведения и на шаге 4 частного. имена Арифметические действия умножения, деления и сложения – выполняются по определённым алгоритмам, известным из курса математики начальной школы и носят соответствующие имена. 2) 2) В ЛогоМирах вы строили Домик. При этом сначала вы создавали процедуры построения двух квадратов и треугольника (каждая процедура получала собственное имя), а затем «собирали» домик из этих вспомогательных процедур и других команд.

7 Формы представления алгоритмов: 1) На естественном языке (словесная, описательная, содержит перечисление необходимых действий) – допустима, если достаточно приближённо описать суть алгоритма; 2) На специальном языке (например, на языке программирования – в виде программы, последовательности команд); 3) На языке формул (например, оформление решения задач по таким предметам, как физика, алгебра, химия); 4) В графической форме – в виде блок-схемы; И т.д.

8 Блок-схема составляется из стандартных графических объектов: Вид стандартного графического объекта Назначение Начало алгоритма Конец алгоритма Выполняемое действие. Записывается внутри прямоугольника Условие выполнения действия. Записывается внутри ромба Последовательность выполнения действий: «влево» и «вверх» - линия со стрелкой «вправо» и «вниз» - линия без стрелки

9 начало После школы иду гулять Возвращаюсь домой Делаю уроки конец начало Взять тарелку Нанести мою- щее средство Промыть губкой конец Пока тарелки не закончатся конец начало Меньше полуночи? Смотрю телевизор да нет конец начало Точить карандаш Пустая коробка? нет да Линейный алгоритм Циклический алгоритм Циклический алгоритм с условием в начале цикла Циклический алгоритм с условием в конце цикла

10 Задача 1: Если встречу на улице своего знакомого, скажу, что мне срочно нужна находящаяся у него моя книга. Задача 2: Если встречу на улице своего знакомого, скажу, что мне срочно нужна находящаяся у него моя книга, если не встречу, то зайду к нему. начало конец встречу? скажу да нет начало конец встречу? скажузайду да нет Разветвляющийся алгоритм. Неполная форма Разветвляющийся алгоритм. Полная форма

11 Первая стадия Первая стадия – алгоритм должен быть представлен в форме, понятной человеку, который его разрабатывает. На этой стадии разрабатывается приближённый алгоритм, ориентированный на создающего его человека (если алгоритм создаёте вы, то на вас ). Для этого необходимо: Определить цель, для достижения которой будет создан алгоритм; Наметить приблизительный план действий для достижения поставленной цели. Вторая стадия Вторая стадия – детализация алгоритма с учётом специфики среды и других объектов (т.е. с учётом того, кто или что будет выполнять данный алгоритм, каким способом, какими средствами и т.д.). Для этого необходимо: Выбрать среду и объекты, посредством которых алгоритм будет реализован; Детализировать алгоритм с учётом особенностей выбранной среды. Например. Прежде, чем рассказать алгоритм решения какой-нибудь задачи на уроке, учитель разбирает этот алгоритм «для себя», так, чтобы алгоритм был понятен ему (первая стадия создания алгоритма). После этого учитель представляет себе класс и учеников, которым он будет объяснять этот алгоритм, и старается сделать его проще, подобрать слова для описания алгоритма, понятные учащимся, т.е. учитывает особенности исполнителя алгоритма (вторая стадия создания алгоритма).