Презентация на тему "алгоритмы и способы их описания". Алгоритм
В данной презентации представлен материал к разделу "Алгоритмизация". В презентации рассмотрены понятия: алгоритм, свойства алгоритма, способы записи алгоритмов, линейные алгоритмы. Представлены задачи по теме "Линейные алгоритмы".
Данная презентация может быть использована как для повторения материала по данной теме, так и для объяснения нового материала.
Скачать:
Предварительный просмотр:
Чтобы пользоваться предварительным просмотром презентаций создайте себе аккаунт (учетную запись) Google и войдите в него: https://accounts.google.com
Подписи к слайдам:
Алгоритм. Свойства. Способы записи. Линейные алгоритмы.
Понятие алгоритма Алгоритм – это строгая и четкая последовательность действий, выполнение которых приводит к определенному результату. Требования к алгоритмам Ориентированность на конкретного исполнителя. Понятность для исполнителя (алгоритм составляется в соответствии с системой команд исполнителя). Точность (каждая команда должна определять однозначное действие исполнителя). Конечность (наличие конца алгоритма через конечное число шагов). Результативность (получение нужного результата по окончанию алгоритма). Массовость (применимость для широкого класса задач). Формальность исполнения (во время исполнения алгоритма исполнитель не должен задумываться над сутью выполняемых действий).
Способы записи алгоритмов Словесный Запись на алгоритмическом языке Блок-схема (Графическое представление алгоритма) Программа (запись алгоритма на языке программирования)
Словесный способ записи (описание алгоритма с помощью слов русского языка). Пример. Алгоритм включения компьютера. Подойти к компьютеру. Включить монитор. Включить системный блок. Задание: придумайте свой пример. Запишите
Запись на алгоритмическом языке Пример. Алгоритм нахождения максимального из двух введенных чисел. Начало Ввод числа х Ввод числа у Если х > у То Вывод х Иначе Вывод у Все Конец
Блок-схема (Графическое представление алгоритма) Блок-схемы являются одним из графических способов представления алгоритмов. Блок-схема состоит из блоков, соединенных линиями. Чаще всего используются блоки следующих типов: выполнение операции; выбор направления выполнения алгоритма в зависимости от выполнения условия; - ввод/вывод данных; - начало и конец алгоритма.
Программа (запись алгоритма на языке программирования) Пример. Определение четности введенного числа. На языке BASIC: INPUT “Введите целое число”; X A $ =” четное ” IF X MOD 20 THEN A$=” не ”+A$ PRINT “ Введенное число ”, A$
Виды алгоритмических конструкций Линейная Ветвление Цикл
Линейные алгоритмы Набор команд, выполняемых последовательно во времени, друг за другом. Блок-схема базовой конструкции следование. Вход Выход
Линейные алгоритмы Словесное описание. По кулинарному рецепту приготовления орехового напитка составьте словесный алгоритм. Орехи истолочь в деревянной ступке, растворить в горячем молоке. Затем варить 10 минут на слабом огне. Подавать охлажденными. Продукты: 250 г. очищенных грецких орехов, 0,8 л. Молока, 120 г. сахара. Взять 250 г. очищенных грецких орехов. Истолочь их в деревянной ступке. Взять 0,8 л. Молока. Смешать молоко, сахар, орехи. Варить 10 мин. Охладить. Подать к столу.
Линейные алгоритмы Пример: блок-схема алгоритма, который по двум заданным вещественным числам вычисляет коэффициенты приведенного квадратного уравнения. начало Х1, х2 p:=-x1-x2 q:=x1*x2 p, q конец Дано: x1, x2 Найти: p, q Связь: x 2 +px+q=0 p=-x1-x2 q=x1*x2
Задачи: Дана длина ребра куба. Составьте блок схему алгоритма нахождения площади грани, площади полной поверхности и объема этого куба. Составьте блок-схему вычисления периметра и площади прямоугольного треугольника по длинам его двух катетов. Дана квадратная рамка. Длина внешнего края рамки 10 см., длина внутреннего – 8 см. Составить блок-схему поиска площади не закрашенной части.
Источники информации: Информатика и ИКТ: учебник для 9 класса, И.Г. Семакин и др, - М.: Бином, Лаборатория знаний, 2008 г. Информатика 9-11. Интерактивный задачник.. Крылов С.С., 2004. Андреева Е.В. Информатика. Основы алгоритмизации. Тетрадь с печатной основой. – Саратов: «Лицей», 1998. – 80 с.
Алгоритмы
Введение в программирование
Алгоритм
Появление алгоритмов связывают с зарождением математики. Более 1000 лет назад (в 825 году) ученый из города Хорезма Абдулла (или Абу Джафар) Мухаммед бен Муса аль-Хорезми создал книгу по математике, в которой описал способы выполнения арифметических действий над многозначными числами. Само слово алгоритм возникло в Европе после перевода на латынь книги этого математика.
Алгоритм – описание последовательности действий (план), строгое исполнение которых приводит к решению поставленной задачи за конечное число шагов.
- 1. Достать ключ из кармана.
- 2. Вставить ключ в замочную скважину.
- 3. Повернуть ключ два раза против часовой стрелки.
- 4. Вынуть ключ
- Дискретность (алгоритм должен состоять из конкретных действий, следующих в определенном порядке);
- Детерминированность (любое действие должно быть строго и недвусмысленно определено в каждом случае);
- Конечность (каждое действие и алгоритм в целом должны иметь возможность завершения);
- Массовость (один и тот же алгоритм можно использовать с разными исходными данными);
- Результативность (отсутствие ошибок, алгоритм должен приводить к правильному результату для всех допустимых входных значениях).
- Линейный алгоритм (описание действий, которые выполняются однократно в заданном порядке);
- Циклический алгоритм (описание действий, которые должны повторятся указанное число раз или пока не выполнено задание);
- Разветвляющий алгоритм (алгоритм, в котором в зависимости от условия выполняется либо одна, либо другая последовательность действий)
- Вспомогательный алгоритм (алгоритм, который можно использовать в других алгоритмах, указав только его имя).
- В устной форме.
- В письменной форме на естественном языке.
- В письменной форме на формальном языке.
- Для более наглядного представления алгоритма широко используется графическая форма - блок-схема , которая составляется из стандартных графических объектов.
Вид стандартного графического объекта
Назначение
Начало алгоритма
Конец алгоритма
Выполняемое действие записывается внутри прямоугольника
Условие выполнения действий записывается внутри ромба
Счетчик кол-во повторов
Последовательность выполнения действий
Пример записи алгоритма в виде блок-схемы
Ввод чисел а и b
Вычисление площади s=a*b
Вывод результата на экран
- Алгоритм должен быть представлен в форме, понятной человеку, который его разрабатывает.
- Алгоритм должен быть представлен в форме, понятной тому объекту (в том числе и человеку), который будет выполнять описанные в алгоритме действия.
Исполнители алгоритмов
Объект, который будет выполнять алгоритм, обычно называют исполнителем.
- Исполнитель - объект, который выполняет алгоритм.
Идеальными исполнителями являются машины, роботы, компьютеры...
- Компьютер – автоматический исполнитель алгоритмов.
- Алгоритм, записанный на «понятном» компьютеру языке программирования, называется программой .
- Что такое алгоритм? Приведите примеры алгоритмов.
- Какие свойства алгоритмов вы знаете?
- Какие виды алгоритмов вы знаете?
- Какие способы записи алгоритмов вы знаете?
- Что такое исполнитель алгоритмов?
- Что такое программа?
PRINT "Привет!"
PRINT "Привет!"
INPUT "Введите длину: ", a
INPUT "Введите ширину: ", b
PRINT "Площадь прямоугольника равна ",s
Слайд 2
- Алгоритм - конечная последовательность действий, описывающая процесс преобразования объекта из начального состояния в конечное, записанная с помощью точных и понятных исполнителю команд.
- Слово «алгоритм» происходит от algorithmi - латинской формы написания имени великого математика IX века аль-Хорезми
Слайд 3
- Приготовление торта- алгоритм:
- Замесить тесто
- Раскатать коржи
- Выпечь коржи
- Дать коржам остыть
- 5. Украсить торт
- Алгоритмы встречаются нам повсюду, например:
Слайд 4
Исполнитель
- Исполнитель - управляющий объект совершающий последовательность действий, направленных на достижение поставленной цели
- Исполнителем может быть человек, робот, компьютер, язык программирования и т.д. Исполнитель умеет выполнять некоторые команды.
- СКИ - совокупность команд, которые данный исполнитель умеет выполнять, называется системой команд исполнителя.
Слайд 5
Свойства алгоритмов
Слайд 6
Дискретность
- Описываемый алгоритмом процесс разбит на последовательность отдельных шагов.
- Запись представляет собой упорядоченную совокупность разделенных предписаний, образующих дискретную (прерывную) структуру алгоритма.
- Только выполнив требования одного предписания, можно приступить к выполнению следующего.
Слайд 7
- Алгоритмы составляются ориентацией на определенного исполнителя.
- Все команды в алгоритме должны быть понятны исполнителю, т.е. принадлежать его СКИ.
- Понятность
Слайд 8
Детерминированность
- Последовательность выполнения действий д.б. строго определенной.
- Каждый шаг алгоритма д.б. четким и однозначным.
- Алгоритм не должен содержать предписаний, смысл которых может восприниматься неоднозначно, т.е. одна и та же команда, будучи понятна разным исполнителям, после исполнения каждым из них должна давать одинаковый результат.
- Также недопустимы ситуации, когда после выполнения очередной команды исполнителю неясно, какая из команд должна выполняться на следующем шаге.
Слайд 9
Результативность
При точном исполнении всех предписаний алгоритм приводит к решению задачи за конечное число шагов и при этом получается определенный результат. Вывод о том, что решения не существует - тоже результат.
Слайд 10
Массовость
Алгоритм разработан в общем виде, обеспечивая решение не одной конкретной задачи, а некоторого класса задач данного типа. В простейшем случае массовость обеспечивает возможность использования различных исходных данных.
Слайд 11
Формы записи алгоритма
- Словесная (на естественном языке)
- Графическая (блок – схема)
- Программная (тексты на языках программирования)
Слайд 12
Исполнители алгоритмов
- Языки программирования:
- 1.Машинноориентированные языки: Автокод, Assembler
- 2. Языки программирования высокого уровня: машиннонезависимые языки:
- C++, Delphi, Visual Basic, Turbo Pascal,
- al = 10100110 sar al, 3 al = 11110100 sar al, 2 al = 11111101 bl = 00100110 sar bl, 3 bl = 00000010
- Программа – алгоритм записанный на языке программирования.
Слайд 13
- Процессор понимает только язык машинных команд. Обязательный элемент любой системы программирования
- Транслятор – программа - переводчик с языка программирования на ЯМК.
- Компилятор - переводит программу на ЯМК до ее исполнения
- Интерпритатор– перевод программы на ЯМК и ее исполнение производятся параллельно
Слайд 14
Блок
Алгоритм изображается в виде последовательности связанных между собой функциональных блоков. Каждый блок выполняет одно или несколько действий. Каждому типу действий соответствует геометрическая фигура.
- Алгоритмы могут описывать процессы преобразования самых разных объектов. Само слово «алгоритм» происходит от «algorithmi» - латинской формы написания имени выдающегося математика IX века аль-Хорезми, который сформулировал правила выполнения арифметических операций.
- Алгоритм - набор команд, описывающих порядок действий исполнителя для достижения результата решения задачи за конечное число действий.
Свойства алгоритмов:
1. Дискретность - алгоритм должен представлять процесс решения задачи как последовательное выполнение некоторых простых шагов. При этом для выполнения каждого шага алгоритма требуется конечный отрезок времени , то есть преобразование исходных данных в результат осуществляется во времени дискретно.
2. Детерминированность (определённость). В каждый момент времени следующий шаг работы однозначно определяется состоянием системы. Таким образом, алгоритм выдаёт один и тот же результат (ответ) для одних и тех же исходных данных.
3. Понятность - алгоритм должен включать только те команды, которые доступны исполнителю и входят в его систему команд.
4. Завершаемость (конечность) - при корректно заданных исходных данных алгоритм должен завершать работу и выдавать результат за конечное число шагов.
5. Массовость (универсальность). Алгоритм должен быть применим к разным наборам исходных данных.
6. Результативность - завершение алгоритма определёнными результатами.
Способы записи алгоритмов:
1. Словесный способ записи
Словесный способ записи алгоритмов представляет собой описание последовательных этапов обработки данных. Алгоритм задается в произвольном изложении на естественном языке .
Пример
В качестве примера словесного способа записи алгоритма рассмотрим алгоритм нахождения площади прямоугольника
где S – площадь прямоугольника; а, b – длины его сторон.
Очевидно, что a, b должны быть заданы заранее, иначе задачу решить невозможно.
Способы записи алгоритмов
Словесный способ записи алгоритма выглядит так:
- Начало алгоритма.
- Задать численное значение стороны a.
- Задать численное значение стороны b.
- Вычислить площадь S прямоугольника по формуле S=a*b.
- Вывести результат вычислений.
- Конец алгоритма.
Способы записи алгоритмов
2. Графический способ
При графическом представлении алгоритм изображается в виде последовательности связанных между собой функциональных блоков, каждый из которых соответствует выполнению одного или нескольких действий.
Такое графическое представление называется схемой алгоритма или блок-схемой. В блок-схеме каждому типу действий (вводу исходных данных, вычислению значений выражений, проверке условий, управлению повторением действий, окончанию обработки и т.п.) соответствует геометрическая фигура, представленная в виде блочного символа. Блочные символы соединяются линиями переходов, определяющими очередность выполнения действий. Далее приведены наиболее часто употребляемые символы.
Способы записи алгоритмов
Элемент блок-схемы
Наименование
Блок вычислений (вычислительный блок)
Вычислительные действия или последовательность действий
Логический блок (блок условия)
Блок ввода-вывода данных
Выбор направления выполнения алгоритма в зависимости от некоторого условия
Общее обозначения ввода (вывода) данных (вне зависимости от физического носителя)
Начало (конец)
Начало или конец алгоритма, вход или выход в подпрограмме
Способы записи алгоритмов
Элемент блок-схемы
Наименование
Процесс пользователя (подпрограмма)
Вычисление по стандартной программе или подпрограмме
Блок модификации
Функция выполняет действия, изменяющие пункты (например, заголовок цикла) алгоритма
Соединитель
Указание связи прерванными линиями между потоками информации
Способы записи алгоритмов
Пример
Алгоритм вычисления площади прямоугольника
Способы записи алгоритмов
3. Псевдокоды
полуформализованные описания алгоритмов на условном алгоритмическом языке, включающие в себя как элементы языка программирования, так и фразы естественного языка, общепринятые математические обозначения и др.
Единого или формального определения псевдокода не существует, поэтому возможны различные псевдокоды, отличающиеся набором служебных слов и основных (базовых) конструкций.
Способы записи алгоритмов
Пример
- Начало. Перейти к пункту 2.
- Ввод чисел a и b. Перейти к пункту 3.
- Вычислить S=a*b. Перейти к пункту 4.
- Вывод S. Перейти к пункту 5.
- Конец.
Способы записи алгоритмов
4. Программный способ
Запись алгоритма на выбранном языке программирования.
Пример
Writeln (‘’);
Writeln (‘S=‘ , S);
Виды алгоритмов
1. Линейный алгоритм
Это алгоритм, в котором есть только структура следование.
Следование – это расположение действий друг за другом.
Виды алгоритмов
2. Разветвляющийся алгоритм (если … то… иначе…)
Это алгоритм, в котором есть структура ветвление.
Ветвление – это выбор действия в зависимости от выполнения какого-нибудь условия.
Виды алгоритмов
3. Циклический алгоритм
это алгоритм, в котором есть структура цикл.
Цикл – это неоднократное повторение каких-либо действий.
Виды алгоритмов
4. Комбинированный алгоритм
Алгоритм, в котором содержится несколько структур одновременно.
