Презентация, доклад по информатике на тему Алгоритмы обработки информации 10 класс

изменять, а также отказаться выполнять
одну и ту же команду выполняет каждый раз по-разному
неформальный исполнитель сам отвечает за свои действия
в роли неформального исполнителя чаще всего выступает человек

Исполнитель алгоритма

Исполнитель алгоритма – это субъект или устройство, способные правильно интерпретировать описание алгоритма и выполнить со­держащийся в нём перечень действий.

!

не размышляет над выпол­няемыми командами, а строго следует пошаговым инструк­циям алгоритма
одну и ту же команду всегда выполняет одинаково
за действия формального исполни­теля отвечает управ­ляющий им объект
в роли формального исполни­теля чаще всего выступает техническое устройство

Неформальный исполнитель

Формальный исполнитель

исполнителя над некоторыми объектами (исходными и промежуточными данными) для получения искомого результата за конечное число шагов.

!

ПРИМЕРЫ АЛГОРИТМОВ

Закрыть входную дверь ключом

Нахождение n первых простых чисел (метод Эратосфена)

Построение перпендикуляра к прямой

ключ в замочную скважину.
Повернуть ключ два раза на 180 градусов против часовой стрелки.
Вынуть ключ из замочной скважины.

по методу Эратосфена»

Выписать подряд все целые числа от 2 до n (2, 3, 4, …, n).
Присвоить переменной p значение 2 (2 – первое простое число).
Зачеркнуть в списке числа, кратные p: 2p, 3p, 4p, …
Найти первое незачёркнутое число в списке, большее чем p, и присвоить p соответствующее значение.
Повторять шаги 3 и 4, пока возможно (пока p2 ≤ n).
Незачёркнутые числа и есть все простые числа от 2 до n.

Простые числа от 2 до 100

Выполнить

по методу Эратосфена»

Простые числа от 2 до 100

p = 2

p = 3

p = 5

p = 7

Выписать подряд все целые числа от 2 до n (2, 3, 4, …, n).
Присвоить переменной p значение 2 (2 – первое простое число).
Удалить из списка числа, кратные p: 2p, 3p, 4p, …
Найти первое число в списке, большее чем p, и прис­воить p соответствующее значение.
Повторять шаги 3 и 4, пока возможно (пока p2 ≤ n).
Оставшиеся числа и есть все простые числа от 2 до n.

лежащую на прямой с помощью циркуля и линейки»

Выполнить

Провести окружность с центром в точке O и радиусом 1 см.
Обозначить точки пересечения окружности с прямой: левую - A, правую - B.
Провести окружность с центром в точке A и радиусом равным AB.
Провести окружность с центром в точке В и радиусом равным AB.
Обозначить точки пересечения окружностей: верхнюю - C, нижнюю - D.
Провести прямую СD.

лежащую на прямой с помощью циркуля и линейки»

О

А

В

С

D

Провести окружность с центром в точке O и радиусом 1 см.
Обозначить точки пересечения окружности с прямой: левую - A, правую - B.
Провести окружность с центром в точке A и радиусом равным AB.
Провести окружность с центром в точке В и радиусом равным AB.
Обозначить точки пересечения окружностей: верхнюю - C , нижнюю - D.
Провести прямую СD.

действие, можно приступать к выполнению следующего. Произвести каждое отдельное действие исполнителю предписывает специальное указание в записи алгоритма – команда.

Детерминированность
Каждая команда алгоритма определяет однозначное действие исполнителя, и недвусмысленно указывает, какая команда должна выполняться следую­щей. Многократное выполнение алго­ритма при одном и том же наборе входных данных, дает одинаковые промежуточные и выходной результаты.

Понятность
Алгоритм не должен содержать предписаний, смысл которых может восприниматься исполнителем неодно­знач­но, т. е. запись алгоритма должна быть настолько чёткой и полной, чтобы у исполнителя не возникло потребности в принятии каких-либо самостоятельных решений.

Результативность
При точном исполнении команд алгоритма процесс должен прекратиться за конеч­ное число шагов, и при этом должен быть получен ответ на вопрос задачи. В качестве одного из возможных ответов может быть установление того факта, что задача решений не имеет.

Массовость
Алгоритм пригоден для решения любой задачи из некоторого класса задач, т. е. алгоритм правильно работает на неко­тором множестве исходных данных, которое называется областью примени­мости алгоритма.

Алгоритм – конечная система правил, сформулированных на языке исполнителя, которая определяет последовательность перехода от допустимых исходных данных к конечному результату и обладает свойствами дискретности, детерминированности, понятности, результативности, конечности и массовости.

!

зрения свойств алгоритма.

?

программирования

с помощью блок-схемы – стандартных графических объектов (геометрических фигур)

запись алгоритма с помощью формул, рисунков, таблиц

стандартом ГОСТ 19.701–90 (ИСО 5807–85) «Схемы алгоритмов, программ, данных и систем. Обозначения условные и правила выполнения».

Блок-схема

и той же задачи, на основе которого можно выбрать самый эффективный (наилучший) алгоритм.

Вычислительным процессом, порождённым алгоритмом, называется последовательность шагов алгоритма, пройденных при его ис­полнении.
Сложность алгоритма – количество элементарных шагов (действий) в вычислительном процессе этого алгоритма.

!

Для решения задачи могут быть разработаны алгоритмы, имеющие разную сложность. Лучшим среди них считается алгоритм, имеющий наименьшую сложность.

Эффективность оценивается количеством элементарных операций, которые необходимо выполнить для решения задачи, а также количеством памяти, требующейся для выполнения алгоритма.

объёма входных данных.
Задание. Оцените сложность алгоритмов:

Сложность алгоритма будет O(log2n).
Таким образом, в книге объёмом в 1000 страниц страница с нужной фамилией находится не больше, чем за O(log21000) ≈ 10 раз.

В данном случае, за счет сортировки имен по алфавиту, можно сократить поиск, применив метод половинного деления (открыв книгу примерно в середине, мы уменьшаем размер «оставшейся проблемы» вдвое).

При линейном поиске – последовательной проверки всех книг подряд – сложность, в худшем случае, будет равна количеству книг, т.е. O(n) = 1000.

В старинной библиотеке в одном из 1000 томов, посвященных кладам и тайникам, спрятана книга-сейф. Надо найти ее.

в двоичной системе счисления.
Заменим каждую 1 парой букв КХ, а каждый 0 – буквой К.
Вычеркнем крайнюю левую пару КХ.
Полученная строка, читаемая слева направо, даёт правило быстрого вычисления хn, если букву К рассматривать как операцию возведения результата в квадрат, а букву X – как операцию умножения результата на х. Вначале результат равен х.

К

К

Х

К

К

К

х2

х4

х5

х10

х20

х40

последовательность перехода от допустимых исходных данных к конечному результату и обладает свойствами дискретности, детерминированности, понятности, результативности, конечности и массовости.
Исполнитель алгоритма – субъект или устройство, способные правильно интерпретировать описание алгоритма и выполнить содержащийся в нём перечень действий.
Один и тот же алгоритм может быть записан разными способами: на естественном языке, псевдокодом, с помощью блок-схем, на языке программирования и т. д.
Теория алгоритмов предоставляет аппарат анализа различных алгоритмов решения одной и той же задачи, на основе которого можно выбрать самый эффективный (наилучший) алгоритм.

Шаг алгоритма – отдельное действие, которое исполнитель выполняет по команде. Вычислительным процессом, порождённым алгоритмом, называется последовательность шагов алгоритма, пройденных при его исполнении.
Сложность алгоритма – количество элементарных шагов (действий) в вычислительном процессе этого алгоритма. Наряду со сложностью важной характеристикой алгоритма является эффективность. Эффективность оценивается количеством элементарных операций, которые необходимо выполнить для решения задачи, а также количеством памяти, требующейся для выполнения алгоритма.

этому числу строится новое число по следующим правилам:
Складываются первая и вторая, а также вторая и третья цифры исходного числа.
Полученные два числа записываются друг за другом в порядке убывания (без разделителей).
Укажите наименьшее число, в результате обработки которого автомат выдаст число 1711.

Решение:
Единственный способ разбить запись 1711 на два числа – это 17 и 11.
Чтобы число было меньше, надо чтобы сумма первой и второй цифр была наименьшей, в данном случае 11.
Сумма значений двух последних цифр равна 17. Не трудно заметить, что 17 = 8 + 9 = 9 + 8. Других вариантов нет.
Тогда 11 = 2 + 9 = 3 + 8. Выбираем пару, которая даст меньшее число.
Ответ: 298.

«столбиком» при условии, что одно из них состоит из n, а второе – из m десятичных цифр.

Решение:
Сложение двух чисел столбиком в случае, если одно из них состоит из n, а другое – из m цифр требует не более max(n, m) сложений и не более max(n, m) запоминаний (в случае перехода через десяток).
Т.е. данный алгоритм имеет сложность порядка O(n+m).
Выражение показывает только порядок величины – постоянные факторы в нем не учитываются.

на 8 минут. Для приготовления эликсира бессмертия его надо варить ровно 7 минут. Как это сделать? Придумайте систему команд исполнителя Колдун. Запишите с их помощью план действий исполнителя по приготовлению эликсира.

Графический способ решения: