Понятие алгоритма. Свойства алгоритма основные сведения об алгоритмах алгоритм
 Скачать 1.83 Mb.
|
ПОНЯТИЕ АЛГОРИТМА. СВОЙСТВА АЛГОРИТМАОСНОВНЫЕ СВЕДЕНИЯ ОБ АЛГОРИТМАХалгоритм
Исполнитель алгоритмаХудожник Василий Тропинин «Золотошвейка» (1826)
Исполнитель алгоритма – это субъект или устройство, способные правильно интерпретировать описание алгоритма и выполнить содержащийся в нём перечень действий. !
Неформальный исполнитель Формальный исполнитель Понятие алгоритмаАлгоритм – точная система предписаний, определяющая содержание и порядок действий исполнителя над некоторыми объектами (исходными и промежуточными данными) для получения искомого результата за конечное число шагов. ! ПРИМЕРЫ АЛГОРИТМОВ Закрыть входную дверь ключом Нахождение n первых простых чисел (метод Эратосфена) Построение перпендикуляра к прямой Пример 1Исполнитель: человек Объекты алгоритма: ключ, дверь Алгоритм «Закрыть входную дверь ключом»
Пример 2
Простые числа от 2 до 100 Выполнить 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 Пример 2
Простые числа от 2 до 100
p = 2
p = 3
p = 5
p = 7
Пример 3Алгоритм «Построение перпендикуляра к прямой, проходящей через заданную точку O, лежащую на прямой с помощью циркуля и линейки» Выполнить
Пример 3Алгоритм «Построение перпендикуляра к прямой, проходящей через заданную точку O, лежащую на прямой с помощью циркуля и линейки» О А В С D
Свойства алгоритмаДискретность Детерминированность Понятность Результативность Массовость Дискретность Выполнение алгоритма разбивается на последовательность законченных действий-шагов. Только выполнив одно действие, можно приступать к выполнению следующего. Произвести каждое отдельное действие исполнителю предписывает специальное указание в записи алгоритма – команда. Детерминированность Каждая команда алгоритма определяет однозначное действие исполнителя, и недвусмысленно указывает, какая команда должна выполняться следующей. Многократное выполнение алгоритма при одном и том же наборе входных данных, дает одинаковые промежуточные и выходной результаты. Понятность Алгоритм не должен содержать предписаний, смысл которых может восприниматься исполнителем неоднозначно, т. е. запись алгоритма должна быть настолько чёткой и полной, чтобы у исполнителя не возникло потребности в принятии каких-либо самостоятельных решений. Результативность При точном исполнении команд алгоритма процесс должен прекратиться за конечное число шагов, и при этом должен быть получен ответ на вопрос задачи. В качестве одного из возможных ответов может быть установление того факта, что задача решений не имеет. Массовость Алгоритм пригоден для решения любой задачи из некоторого класса задач, т. е. алгоритм правильно работает на некотором множестве исходных данных, которое называется областью применимости алгоритма. Алгоритм – конечная система правил, сформулированных на языке исполнителя, которая определяет последовательность перехода от допустимых исходных данных к конечному результату и обладает свойствами дискретности, детерминированности, понятности, результативности, конечности и массовости. ! Давайте обсудимМожно ли кулинарный рецепт считать алгоритмом? Ответ обоснуйте с точки зрения свойств алгоритма. ? Способы записи алгоритмовсловесная запись алгоритма на естественном языке запись алгоритма на языке программирования с помощью блок-схемы – стандартных графических объектов (геометрических фигур) запись алгоритма с помощью формул, рисунков, таблиц Сложение смешанных дробей
Нахождение максимума из 10 целых чисел Нахождение НОД Program NOD; var a, b, n: integer; Begin writeln ('Введите два числа: '); readln (a, b); while a <> b do if a>b then a := a - b else b := b – a; n:= a; writeln ('НОД = ', n); End. Шахматный этюд Мат в два хода. Белые начинают и выигрывают № Белые Черные 1 Ф f1-a1 K h8-g8 2 Ф a1-a8 № Белые Черные 1 Ф f1-a1 g6-g5 2 K f6-f7 № Белые Черные 1 Ф f1-a1 С h7-g8 2 K f6-g6 Решение: Блок-схемаПравила выполнения блок-схем, внешний вид графических блоков и их назначение определяются стандартом ГОСТ 19.701–90 (ИСО 5807–85) «Схемы алгоритмов, программ, данных и систем. Обозначения условные и правила выполнения».
Понятие сложности алгоритмаТеория алгоритмов предоставляет аппарат анализа различных алгоритмов решения одной и той же задачи, на основе которого можно выбрать самый эффективный (наилучший) алгоритм.Вычислительным процессом, порождённым алгоритмом, называется последовательность шагов алгоритма, пройденных при его исполнении. Сложность алгоритма – количество элементарных шагов (действий) в вычислительном процессе этого алгоритма. ! Для решения задачи могут быть разработаны алгоритмы, имеющие разную сложность. Лучшим среди них считается алгоритм, имеющий наименьшую сложность. Эффективность оценивается количеством элементарных операций, которые необходимо выполнить для решения задачи, а также количеством памяти, требующейся для выполнения алгоритма. Временная сложность«Найти книгу с секретом»Сложность алгоритма выражают в виде функции от объёма входных данных. Задание. Оцените сложность алгоритмов: «Поиск в телефонной книге» В сейфе оказался клочок страницы с фамилией и первой цифрой номера телефона. Надо найти страницу с нужной фамилией в телефонном справочнике, в котором 1000 страниц . Сложность алгоритма будет O(log2n). Таким образом, в книге объёмом в 1000 страниц страница с нужной фамилией находится не больше, чем за O(log21000) ≈ 10 раз. В данном случае, за счет сортировки имен по алфавиту, можно сократить поиск, применив метод половинного деления (открыв книгу примерно в середине, мы уменьшаем размер «оставшейся проблемы» вдвое). При линейном поиске – последовательной проверки всех книг подряд – сложность, в худшем случае, будет равна количеству книг, т.е. O(n) = 1000. В старинной библиотеке в одном из 1000 томов, посвященных кладам и тайникам, спрятана книга-сейф. Надо найти ее. Пример 4X40 Задание. Найти Алгоритм «Возведение числа в натуральную степень (xn)»
К Х К К Х К К К возведение результата в Квадрат К умножение результата на Х Х 1 0 1 0 0 0 40 = 2 х2 х4 х5 х10 х20 х40 Исполнитель алгоритма – субъект или устройство, способные правильно интерпретировать описание алгоритма и выполнить содержащийся в нём перечень действий.Один и тот же алгоритм может быть записан разными способами: на естественном языке, псевдокодом, с помощью блок-схем, на языке программирования и т. д.Теория алгоритмов предоставляет аппарат анализа различных алгоритмов решения одной и той же задачи, на основе которого можно выбрать самый эффективный (наилучший) алгоритм.Сложность алгоритма – количество элементарных шагов (действий) в вычислительном процессе этого алгоритма. Наряду со сложностью важной характеристикой алгоритма является эффективность. Эффективность оценивается количеством элементарных операций, которые необходимо выполнить для решения задачи, а также количеством памяти, требующейся для выполнения алгоритма.Вопросы и заданияЗадание 1. Автомат получает на вход трёхзначное число. По этому числу строится новое число по следующим правилам:
Укажите наименьшее число, в результате обработки которого автомат выдаст число 1711.Решение:
Ответ: 298. Вопросы и заданияЗадание 2. Подсчитайте сложность алгоритма сложения двух натуральных чисел «столбиком» при условии, что одно из них состоит из n, а второе – из m десятичных цифр.Решение: Сложение двух чисел столбиком в случае, если одно из них состоит из n, а другое – из m цифр требует не более max(n, m) сложений и не более max(n, m) запоминаний (в случае перехода через десяток). Т.е. данный алгоритм имеет сложность порядка O(n+m). Выражение показывает только порядок величины – постоянные факторы в нем не учитываются. Вопросы и задания8 3 3 3 3 3 Задание 1. Есть двое песочных часов: на 3 и на 8 минут. Для приготовления эликсира бессмертия его надо варить ровно 7 минут. Как это сделать? Придумайте систему команд исполнителя Колдун. Запишите с их помощью план действий исполнителя по приготовлению эликсира. Графический способ решения: Информационные источники
|