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

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

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

3 Примеры алгоритмов в повседневной жизни: Рецепты блюд из кулинарной книги; Инструкция по эксплуатации какого-либо прибора; Каждый шофёр должен знать правила дорожного движения (алгоритм поведения на дороге); Массовый выпуск любой техники возможен только тогда, когда хорошо продуман порядок её сборки на конвейере; Садовод-огородник может получить урожай только при условии соблюдения правил посадки, полива и удобрения различных растений; Правила поведения в общественных местах (этикет); Правила расстановки знаков препинания (в русском языке); Порядок выполнения математических действий.

4 Задание 1. Напишите алгоритм нахождения значения данного выражения двумя способами: (2,45 – 2,1 2 ) 3 1,2 2 – 1,1 2 Пример алгоритма. Найти значение выражения: ( ) · 56 (670 – 235) · Выполнить сложение чисел 255 и 378 и получить значение, которое назовём Результат1. 2. Выполнить умножение величины Результат1 на 56. Записать полученное число. Обозначить его как Результат2. 3. Вычесть из числа 670 число 235 и получить Результат3. 4. Выполнить умножение величины Результат3 на число 33. Полученное число Результат4 записать. 5. Выполнить деление числа Результат2 на значение Результат4. Результат деления – искомое значение выражения.

5 АЛГОРИТМ ДИСКРЕТНОСТЬТОЧНОСТЬКОНЕЧНОСТЬМАССОВОСТЬРЕЗУЛЬТАТИВНОСТЬ

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

7 Алгоритмы могут быть Алгоритмы могут быть: очень простые (например: какие действия надо совершить, чтобы открыть входную дверь), средней сложности (например: инструкция по сборке табурета) и очень сложные (например: процесс сборки современного автомобиля включает множество операций, которые должны происходить в определённой и строгой последовательности). Но алгоритм любой сложности можно составить, используя всего четыре типовые (элементарные) алгоритмические конструкции четыре типовые (элементарные) алгоритмические конструкции: ЛИНЕЙНЫЙ АЛГОРИТМЛИНЕЙНЫЙ АЛГОРИТМ; ЦИКЛИЧЕСКИЙ АЛГОРИТМЦИКЛИЧЕСКИЙ АЛГОРИТМ; РАЗВЕТВЛЯЮЩИЙСЯ АЛГОРИТМРАЗВЕТВЛЯЮЩИЙСЯ АЛГОРИТМ; ВСПОМОГАТЕЛЬНЫЙ АЛГОРИТМВСПОМОГАТЕЛЬНЫЙ АЛГОРИТМ.

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

9 Циклический алгоритм повторяться Перечень повторяющихся действийтелом цикла Циклический алгоритм – описание действий, которые должны повторяться указанное число раз или пока не выполнено заданное условие. Перечень повторяющихся действий называется телом цикла. Например: Алгоритм покраски забора: 1) покрасить одну доску; 2) перейти к следующей; 3) выполнить действие 1; 4) завершить работу только после покраски последней доски. Алгоритм умножения – это выполнение заданного количества повторения действия сложения – например: = … + 20 – результат сложения 45 слагаемых, каждое из которых равно 20. Задание 3: Составьте и запишите алгоритм разложения составного числа на простые множители.

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

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