Инструкция в которой присутствуют неточности можно назвать алгоритмом

Вопросы
для подготовки к экзамену по дисциплине
«Информатика»

Наша учеба, работа, личные дела — это
каждодневное, ежечасное решение различных
задач. Каждая задача требует для своего
решения выполнения определенных
действий. Многократно решая задачи,
можно заметьть, что необходимые действия
должны выполняться в строго определенном
порядке. В таких случаях принято говорить
об алгоритме решения задач. Понятие
алгоритма считается одним из древнейших.
Оно возникло задолго до появления ЭВМ,
но с развитием вычислительной техники
его роль значительно возросла.

Происхождение понятия алгоритма связано
с именем великого среднеазиатского
ученого Аль Хорезми, жившего в 9 веке
н.э. Им были сформулированы впервые
правила выполнения четырех арифметических
действий.

Алгоритм — это точная инструкция, а
инструкции встречаются во всех областях
человеческой деятельности. Однако не
всякую инструкцию можно назвать
алгоритмом. Решая задачу, человек часто
не задумывается над тем, как он это
делает, и порой, затрудняется записать
последовательность выполняемых действий.
Но для того, чтобы поручить решение
задачи автоматическому устройству
необходимо составить алгоритм с четким
указанием последовательности действий.
Чтобы автоматическое устройство могло
решить задачу в соответствии с алгоритмом,
оно должно понимать каждое указание
алгоритма. Алгоритм применяется к
искомому набору исходных величин,
называемых аргументами. Цель исполнения
алгоритма получение определенного
результата, если в результате исполнения
алгоритма не достигнута определенная
цель, значит алгоритм либо неверен, либо
не завершен.

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

Основными свойствами алгоритмов
являются:

1. Универсальность (массовость)
— применимость алгоритма к различным
наборам исходных данных.

2. Дискретность — процесс решения
задачи по алгоритму разбит на отдельные
действия.

3. Однозначность — правила и порядок
выполнения действий алгоритма имеют
единственное толкование.

4. Конечность — каждое из действий и
весь алгоритм в целом обязательно
завершаются.

5. Результативность — по завершении
выполнения алгоритма обязательно
получается конечный результат.

6. Выполнимость — результата алгоритма
достигается за конечное число шагов.

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

Выделяют три крупных класса алгоритмов:

— вычислительные алгоритмы, работающие
со сравнительно простыми видами данных,
такими как числа и матрицы, хотя сам
процесс вычисления может быть долгим
и сложным;

— информационные алгоритмы,
представляющие собой набор сравнительно
простых процедур, работающих с большими
объемами информации (алгоритмы баз
данных);

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

Для записи алгоритмов используют самые
разнообразные средства. Выбор средства
определяется типом исполняемого
алгоритма. Выделяют следующие основные
способы записи алгоритмов:

— вербальный, когда алгоритм описывается
на человеческом языке;

— символьный, когда алгоритм описывается
с помощью набора символов;

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

Общепринятыми способами записи являются
графическая запись с помощью блок-схем
и символьная запись с помощью какого-либо
алгоритмического языка.

Описание алгоритма с помощью блок схем
осуществляется рисованием последовательности
геометрических фигур, каждая из которых
подразумевает выполнение определенного
действия алгоритма. Порядок выполнения
действий указывается стрелками. Написание
алгоритмов с помощью блок-схем
регламентируется ГОСТом. Внешний вид
основных блоков, применяемых при
написании блок схем, приведен на рисунке:

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

В алгоритмах линейной структуры действия
выполняются последовательно одно за
другим:

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

В алгоритмах циклической структуры в
зависимости от выполнения или невыполнения
какого-либо условия выполняется
повторяющаяся последовательность
действий, называющаяся телом
цикла. Вложенным называется цикл,
находящийся внутри тела другого цикла.
Различают циклы с предусловием и послеусловием:

Итерационным называется цикл, число
повторений которого не задается, а
определяется в ходе выполнения цикла.
В этом случае одно повторение цикла
называется итерацией.

Соседние файлы в предмете [НЕСОРТИРОВАННОЕ]

• #
• #
• #
• #
• #
• #
• #
• #
• #
• #
• #

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

Сейчас под этим словом понимают любые последовательности действий, которые можно четко описать и разделить на простые шаги и которые приводят к достижению какой-то цели. Например, пойти на кухню, налить воду и положить в нее пакетик чая — это алгоритм для выполнения задачи «Заварить чай».

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

Кто пользуется алгоритмами

В общем смысле — абсолютно все живые и некоторые неживые существа, потому что любую последовательность действий, ведущую к цели, можно считать алгоритмом. Поиск еды животным — алгоритм, движения робота тоже описываются алгоритмом.

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

Для чего нужны алгоритмы

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

Например, отсортировать массив можно в ходе полного перебора — это самое очевидное решение. А можно воспользоваться алгоритмом быстрой сортировки: он сложнее и не так очевиден, зато намного быстрее работает и не так сильно нагружает мощности компьютера. Строго говоря, полный перебор — это тоже алгоритм, но очень простой.

Существуют алгоритмически неразрешимые задачи, для решения которых нет и не может существовать алгоритма. Но большинство задач в IT разрешимы алгоритмически, и алгоритмы активно используются в работе с ними.

Алгоритмы применяются во всех направлениях IT и во многих других отраслях. Инструкции для автоматизированного станка или линии производства — алгоритмы, рецепт блюда — тоже.

Свойства алгоритмов

Дискретность. Алгоритм — не единая неделимая структура, он состоит из отдельных маленьких шагов, или действий. Эти действия идут в определенном порядке, одно начинается после завершения другого.

Результативность. Выполнение алгоритма должно привести к какому-либо результату и не оставлять неопределенности. Результат может в том числе оказаться неудачным — например, алгоритм может сообщить, что решения нет, — но он должен быть.

Детерминированность. На каждом шаге не должно возникать разночтений и разногласий, инструкции должны быть четко определены.

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

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

Конечность. Алгоритмы конечны, они должны завершаться и выдавать результат, в некоторых определениях — за заранее известное число шагов.

Какими бывают алгоритмы

Несмотря на слово «последовательность», алгоритм не всегда описывает действия в жестко заданном порядке. Особенно это актуально сейчас, с распространением асинхронности в программировании. В алгоритмах есть место для условий, циклов и других нелинейных конструкций.

Линейные. Это самый простой тип алгоритма: действия идут друг за другом, каждое начинается после того, как закончится предыдущее. Они не переставляются местами, не повторяются, выполняются при любых условиях.

Ветвящиеся. В этом типе алгоритма появляется ветвление: какие-то действия выполняются, только если верны некоторые условия. Например, если число меньше нуля, то его нужно удалить из структуры данных. Можно добавлять и вторую ветку: что делать, если условие неверно — например, число больше нуля или равно ему. Условий может быть несколько, они могут комбинироваться друг с другом.

Циклические. Такие алгоритмы выполняются в цикле. Когда какой-то блок действий заканчивается, эти действия начинаются снова и повторяются некоторое количество раз. Цикл может включать в себя одно действие или последовательность, а количество повторений может быть фиксированным или зависеть от условия: например, повторять этот блок кода, пока в структуре данных не останется пустых ячеек. В некоторых случаях цикл может быть бесконечным.

Рекурсивные. Рекурсия — это явление, когда какой-то алгоритм вызывает сам себя, но с другими входными данными. Это не цикл: данные другие, но «экземпляров» работающих программ несколько, а не одна. Известный пример рекурсивного алгоритма — расчет чисел Фибоначчи.

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

Вероятностные. Такие алгоритмы упоминаются реже, но это довольно интересный тип: работа алгоритма зависит не только от входных данных, но и от случайных величин. К ним, например, относятся известные алгоритмы Лас-Вегас и Монте-Карло.

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

Графическое изображение алгоритмов

Алгоритмы могут записывать текстом, кодом, псевдокодом или графически — в виде блок-схем. Это специальные схемы, состоящие из геометрических фигур, которые описывают те или иные действия. Например, начальная и конечная точка на схеме — соответственно, начало и конец алгоритма, параллелограмм — ввод или вывод данных, ромб — условие. Простые действия обозначаются прямоугольниками, а соединяются фигуры с помощью стрелок — они показывают последовательности и циклы.

В схемах подписаны конкретные действия, условия, количество повторений циклов и другие детали. Это позволяет нагляднее воспринимать алгоритмы.

Сложность алгоритма

Понятие «сложность» — одно из ключевых в изучении алгоритмов. Оно означает не то, насколько трудно понять тот или иной метод, а ресурсы, затраченные на вычисление. Если сложность высокая, алгоритм будет выполняться медленнее и, возможно, тратить больше аппаратных ресурсов; такого желательно избегать.

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

Какой бывает сложность. Полностью разбирать математическую O-нотацию, как ее называют, мы не будем — просто перечислим основные обозначения сложности в теории алгоритмов.

•  O(1) означает, что алгоритм выполняется за фиксированное константное время. Это самые эффективные алгоритмы.
•  O(n) — это сложность линейных алгоритмов. n здесь и дальше обозначает размер входных данных: чем больше n, тем дольше выполняется алгоритм.
•  O(n²) тоже означает, что чем больше n, тем выше сложность. Но зависимость тут не линейная, а квадратичная, то есть скорость возрастает намного быстрее. Это неэффективные алгоритмы, например с вложенными циклами.
•  O(log n) — более эффективный алгоритм. Скорость его выполнения рассчитывается логарифмически, то есть зависит от логарифма n.
•  O(√n) — алгоритм, скорость которого зависит от квадратного корня из n. Он менее эффективен, чем логарифмический, но эффективнее линейного.

Существуют также O(n³), O(nn) и другие малоэффективные алгоритмы с высокими степенями. Их сложность растет очень быстро, и их лучше не использовать.

Графическое описание сложности. Лучше разобраться в сложности в O-нотации поможет график. Он показывает, как изменяется время выполнения алгоритма в зависимости от размера входных данных. Чем более пологую линию дает график, тем эффективнее алгоритм.

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

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

Мы приведем несколько примеров использования разных алгоритмов в отраслях программирования. На самом деле их намного больше — мы взяли только часть, чтобы помочь вам понять практическую значимость алгоритмов.

Разработка ПО и сайтов. Алгоритмы используются для парсинга, то есть «разбора» структур с данными, таких как JSON. Парсинг — одна из базовых задач, например в вебе. Также алгоритмы нужны при отрисовке динамических структур, выводе оповещений, настройке поведения приложения и многом другом.

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

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

Поисковые задачи. Алгоритмы поиска — отдельная сложная отрасль. Их выделяют в отдельную группу, в которой сейчас десятки разных алгоритмов. Поиск важен в науке о данных, в методах искусственного интеллекта, в аналитике и многом другом. Самый очевидный пример — поисковые системы вроде Google или Яндекса. Кстати, подробности об используемых алгоритмах поисковики обычно держат в секрете.

Машинное обучение. В машинном обучении и искусственном интеллекте подход к алгоритмам немного другой. Если обычная программа действует по заданному порядку действий, то «умная машина» — нейросеть или обученная модель — формирует алгоритм для себя сама в ходе обучения. Разработчик же описывает модель и обучает ее: задает ей начальные данные и показывает примеры того, как должен выглядеть конечный результат. В ходе обучения модель сама продумывает для себя алгоритм достижения этого результата.

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

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

int linear_search(int[] arr, int x):
	if arr is empty:
		return -1
	for i in 0..n:
		if arr[i] == x:
			return i
	return -1	

def foo(x):
   #код 

print("Hello!")
word = input()

100 - 10
25 + 100
6 * 12.0

if n < 5:
   sum += 10

for k,v in enumerate(arr):
   print(k, v)

f = open("text.txt", 'r')
f.close()

x = int(input())
x = x * 100
print(x)

>>> 5
>>> 500

visits_counter = 0
answer = int(input("Сколько вам лет? "))
if answer >= 18:
   print("Добро пожаловать!")
   visits_counter += 1
else:
   print("Доступ запрещён")

count = 0
#прибавлять 1 к count, пока count меньше 10
while count < 10:
   count += 1
   print(count)
print("Переменная count равна 10!")

1
2
3
4
5
6
7
8
9
10

#функция, которая вызывает саму себя
def factorial(n):
   if n == 1:
       return 1
   #когда функция возвращает значение, 
   #она вызывает себя, но с аргументом n - 1
   return n * factorial(n - 1)

Научитесь: Профессия Python-разработчик
Узнать больше

Что такое алгоритм?

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

Когда вы закончили проектировать алгоритм, необходимо ответить на два важных вопроса: «Правильно ли он работает?» и «Сколько времени занимает выполнение?». Разумеется, вас не устроит алгоритм, который выдаёт правильный результат лишь в половине случаев или требует $1,000$ лет для поиска ответа.

Псевдокод

Чтобы понять, как работает алгоритм, нам необходимо перечислить шаги, которые он выполняет. Для этого мы будем использовать псевдокод — язык, которым пользуются разработчики для описания алгоритмов. Он игнорирует многие детали, необходимые в языках программирования, но он более точен, чем рецепт из кулинарной книги.

Задача и экземпляр задачи

Задача описывает класс возможных входных данных. Экземпляр задачи — это один конкретный ввод такого класса. Чтобы продемонстрировать понятия задачи и экземпляра задачи, рассмотрим следующий пример. Вы оказались в книжном магазине и собираетесь купить книгу за $4,23$＄, расплатившись купюрой в $5$＄. Вам должны вернуть $77$ центов в качестве сдачи. Теперь кассир принимает решение, как именно это сделать. Согласитесь, неприятно получить горсть из $77$ пенни или $15$ никелей и $2$ пенни. Возникает вопрос: как выдать сдачу, не расстроив клиента? Большинство кассиров стараются уместить сумму сдачи в наименьшее количество монет.

💡 Остановитесь и подумайте:
Каково минимальное количество монет номиналом $(25, 10, 5, 1)$, необходимо для сдачи в $77$ центов?

Пример с $77$ центами представляет собой экземпляр задачи Размен. Предполагается, что есть $d$ номиналов, которые представлены массивом $c = (c_1, c_2, dotsc, c_d)$. Для упрощения будем считать, что номиналы даны в порядке убывания. Например, $c = (25, 10, 5, 1)$ для монет, используемых в США.

Задача "Размен"

Переведите определенное количество денег в данные номиналы, используя как можно меньше монет.

• Входные данные: Целое число $money$ и массив из $d$ номиналов $c = (c_1, c_2, dotsc, c_d)$ в порядке убывания ( $c_1 > c_2 > dotsb > c_d$ ).
• Выходные данные: Список из $d$ целых чисел $i_1, i_2, dotsc , i_d$, в котором $c_1cdot i_1+c_2 cdot i_2+dotsm+ c_d cdot i_d = money$ и $i_1 + i_2 +dotsm +i_d$ как можно меньше.

Кассиры по всему миру решают эту проблему с помощью простого алгоритма:

Change(money, c, d):
    while money > 0:
        coin = ... // монета с самым большим номиналом, который не превышает money
        // дать монету с номиналом coin клиенту
        money = money - coin

Вот быстрая версия Change:

Change(money, c, d):
    for k in range(1, d + 1) 
        i_k = floor(money / c[k]) // наибольшее количество монет номинала c[k]
        // дать i_k монет с номиналом c_k клиенту
        money = money - c[k] * i_k

Корректные и некорректные алгоритмы

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

💡 Остановитесь и подумайте:
Каково минимальное количество монет номиналами $(25, 20, 10, 5, 1)$, необходимое для сдачи в $40$ центов?

Change — это некорректный алгоритм! Представьте сдачу в 40 центов, выданную в номиналах $c_1 = 25$, $c_2 = 20$, $c_3 = 10$, $c_4 = 5$ и $c_5 = 1$. Change привел бы к неправильному результату: он выдал бы 1 четвертак (25 центов), 1 дайм (10 центов) и 1 никель (5 центов) вместо 2 монет по двадцать центов. Хоть это и может выглядеть надуманно, в 1875 году в США существовала монета в двадцать центов. Насколько мы можем быть уверены, что Change выдаст минимальное количество монет в современных номиналах Соединенных Штатов или любой другой страны?

Чтобы исправить алгоритм Change, нам нужно рассмотреть все возможные комбинации монет с номиналами $c_1, c_2, dotsc , c_d$, которые дают в сумме $money$, и выдать комбинацию с минимальным количеством монет. Мы рассматриваем только комбинации, в которых $i_1 le money/c_1$ и $i_2 le money/c_2$ (в целом, величина $i_k$ не должна превышать $money/c_k$), в ином случае мы вернем большее количество денег, чем $money$. В псевдокоде, приведенном ниже, используется символ $sum$. Он обозначает суммирование: $sum^m_{i=1} a_i = a_1 + a_2 + dotsm + a_m$. Псевдокод также использует концепт «бесконечность» (обозначается $infty$) в качестве начального значения для $smallestNumberOfCoins$. Реализация описанного подхода на реальных языках программирования может различаться, но сейчас подробности для нас не важны.

BruteForceChange(money, c, d):
    smallestNumberOfCoins = ∞
    for each combinations of coins (i_1,...,i_d)
    // от (0,...,0) до (money/c[1],...,money/c[d])
        valueOfCoins = ∑ i_k*c_k // сумма по всем k от 1 до d
        if valueOfCoins = M:
            numberOfCoins = ∑ i_k // суммарное количество монет
            if numberOfCoins < smallestNumberOfCoins:
                smallestNumberOfCoins = numberOfCoins
                change = (i_1, i_2, ... ,i_d)
    return change

Вторая строка повторяется с каждой возможной комбинацией $(i_1, dotsc, i_d)$ из $d$ индексов и останавливается, когда достигает

$$
left(frac{money}{c_1}, dotsc, frac{money}{c_d}right),
$$

Как мы можем узнать, что BruteForceChange не содержит ту же проблему, что и Change, — неверный результат при каком-то вводе? Раз BruteForceChange рассматривает все возможные комбинации номиналов, рано или поздно алгоритм придёт к оптимальному решению и запишет его в массив $change$. В любой комбинации монет, которая даёт в сумме $M$, должно быть как минимум столько же монет, сколько и в оптимальной. Таким образом, BruteForceChange никогда не завершит работу с неоптимальным набором $change$.

На данный момент мы ответили только на один из двух важных вопросов об алгоритмах: «Работает ли он?». Однако мы не ответили на вопрос: «Сколько времени занимает выполнение?».

💡 Остановитесь и подумайте:
Сколько примерно итераций цикла for выполняет BruteForceChange?

• money
• $money^d$
• $d$

Быстрые и медленные алгоритмы

Настоящие компьютеры требуют определенное количество времени на выполнение таких операций, как сложение, вычитание или проверка условий цикла while. Суперкомпьютер может выполнить сложение за $10^{-10}$ секунды, а калькулятор — за $10^{-5}$. Представьте, что у вас есть компьютер, которому требуется $10^{-10}$ секунды на выполнение простой операции (например, сложения), и вы знаете, сколько операций выполняет какой-то конкретный алгоритм. Вы могли бы рассчитать время выполнения алгоритма, просто взяв произведение количества операций и времени, которое занимает одна операция. Однако компьютеры постоянно улучшаются, благодаря чему им требуется меньше времени на операцию. Так, ваше представление о времени выполнения быстро стало бы устаревшим. Вместо того, чтобы рассчитывать время выполнения на каждом компьютере, мы описываем время выполнения через общее количество операций, необходимых алгоритму, — это характеристика самого алгоритма, а не компьютера, который вы используете.

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

Представьте, что алгоритм $A$ выполняет $n^2$ операций при вводе размера $n$, и алгоритм $B$ решает ту же задачу за $3n+2$ операций. Какой алгоритм быстрее: $A$ или $B$? Хотя $A$ и может быть быстрее, чем $B$, при более малом значении $n$ (например, при $n$ между 1 и 3), $B$ будет быстрее при больших значениях $n$ (например, $n >4$). См. рис.. Так как $f(n)=n^2$ — это, в каком-то смысле, более «быстрорастущая» функция относительно $n$, чем $g(n)=n$. При этом константы 3 и 2 в $3n+2$ не влияют на конкуренцию между двумя алгоритмами при больших значениях $n$. Мы называем $A$ квадратичным алгоритмом и $B$ — линейным. $A$ менее эффективен, чем $B$, потому что он выполняет больше операций для решения задачи, когда значение $n$ большое. Так, иногда мы будем допускать неточности при подсчете операций алгоритма: поведение алгоритма при маленьком вводе неважно.

Рассчитаем примерное количество операций, которое потребуется для BruteForceChange при вводе из $M$ центов и номиналов $(c_1, c_2, dotsc, c_d)$. Чтобы рассчитать общее количество операций в цикле for, нам необходимо взять примерное число операций, выполняемое при каждой итерации, и умножить его на общее количество итераций. Так как в нашем случае около

$$
frac{money}{c_1} times frac{money}{c_2} times dotsm times frac{money}{c_d}
$$

Такой тип алгоритмов называется экспоненциальным в противоположность квадратичным, кубическим или другим полиномиальным алгоритмам. Выражение времени выполнения экспоненциального алгоритма использует $n^d$, где $n$ и $d$ — это параметры задачи (например, $n$ и $d$ можно произвольно сделать большими, изменив ввод для алгоритма). Время выполнения полиномиального алгоритма ограничено $n^k$, где $k$ — это константа, не связанная с величиной параметров задачи.

Например, алгоритм с временем выполнения $n^1$ (линейный), $n^2$ (квадратичный), $n^3$ (кубический) или даже $n^{2018}$ будет полиномиальным. Конечно, алгоритм с временем выполнения $n^{2018}$ не очень практичен. Возможно, даже менее практичен, чем некоторые экспоненциальные алгоритмы. Впрочем, разработчики тратят много усилий, чтобы проектировать всё более и более быстрые полиномиальные алгоритмы. Раз значение $d$ может быть большим при вызове алгоритма с большим количеством номиналов (например, $c = (1, 2, 3, 4, 5, dotsc , 100)$), мы видим, что выполнение BruteForceChange может потребовать много времени.

Цели урока:

• познакомить с понятием алгоритма, исполнителем
  алгоритма, видами исполнителя, средой, СКИ и
  системой отказов исполнителя, свойствами
  алгоритма, показать среду, СКИ и систему отказов
  для конкретного исполнителя,
• развивать умение работать самостоятельно,
  творчески.
• воспитывать нравственное отношение к труду.

ХОД УРОКА

Презентация 1

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

Учащиеся записывают тему урока (с
презентации).
На экране вы видите команды, необходимо
составить алгоритм заваривания чая.
Работа идет со всем классом, учащиеся
обсуждают о выборе последовательности команд,
учитель на доске регистрирует их ответ.

• размешать сахар ложечкой;
• добавить кипятку;
• налить в чашку заварку;
• вскипятить воду;
• положить сахар.

У вас должен был получиться такой алгоритм:

1. вскипятить воду;
2. налить в чашку заварку;
3. добавить кипятку;
4. положить сахар;
5. размешать сахар ложечкой;

В природе все взаимосвязано, все на все влияет и
все зависит друг от друга. Складываются сложные
цепочки событий. Если вынуть хоть одно звено, вся
цепочка разорвется.
Как вы думаете, что будет если убрать из рецепта
вторую команду? А четвертую?
Надо научится выстраивать в нужном порядке все
звенья какой-нибудь жизненной или
математической задачи. Эти умения нужны и при
обработке информации. Информацию следует
обрабатывать по определенным правилам, которые
выполняются в определенном порядке.
Итак, давайте  с вами, попробуем дать
определения понятию алгоритм.

Учащиеся формулируют и записывают с доски.

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

Учащиеся записывают в тетрадь определение.

Синонимы слова «алгоритм»:

•  план;
•  инструкция;
•  рецепт;
•  предписание.

Происхождение термина «алгоритм» связывают с
именем великого узбекского математика и
астронома аль-Хорезми (жившего в IX в.). Абу
Абдуллах Мухаммад ибн Муса аль-Хорезми (ок. 783,
Хива , Хорезм — ок. 850, Багдад) — один из
крупнейших средневековых ученых (математик,
астроном, географ и историк) IX века, основатель
классической алгебры.
Ал-Хорезми известен прежде всего своей «Книгой о
восполнении и противопоставлении» («Аль-китаб
аль-мухтасар фи хисаб аль-джабр ва-ль-мукабала»),
которая сыграла важнейшую роль в истории
математики. От названия этой книги произошло
слово «алгебра».

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

Латинский перевод книги начинается словами
«Dixit Algorizmi» (сказал Алгоризми). Так как сочинение
об арифметике было очень популярно в Европе, имя
автора (Algorizmi или Algorizmus) стало нарицательным и
средневековые математики так называли
арифметику, основанную на десятичной
позиционной системе счисления. Позднее
европейские математики стали называть так
всякую систему вычислений по определенному
правилу. В настоящее время термин «алгоритм»
означает набор инструкций, описывающих порядок
действий исполнителя для достижения результата
решения задачи за конечное число действий.

Затем понятие алгоритма переместилось в
область логики, где появилась теория алгоритмов,
изучавшая процесс доказательств или
разрешимость и неразрешимость математических
задач. В 1937 году, когда английский
математик Алан Тьюринг доказал
теоретически возможность построения устройства,
осуществляющего алгоритм. Такое абстрактное
устройство получило название МАШИНА ТЬЮРИНГА.
Аналогичный, но более простой исполнитель
алгоритма – МАШИНА ПОСТА. Когда же были
созданы первые ЭВМ, понятие алгоритма и теория
алгоритмов переместились в новую науку,
связанную с этими вычислительными устройствами
– информатику.

Приведите примеры алгоритмов.
А теперь скажите кто может выполнить данный
алгоритм?
Приведите пример алгоритмов с разными
исполнителями.

Получается, всякий алгоритм составляется в
расчете на определенного исполнителя. Им может
быть человек, робот, компьютер и др. Чтобы
составить алгоритм для исполнителя, нужно знать,
какие команды исполнитель может понять и
исполнить, а какие нет.
Исполнитель – объект, который будет выполнять
алгоритм.

Приведите примеры исполнителей и что они
могут делать.

В классе исполнителей выделяют два  типа:
формальные, неформальные. Формальный
исполнитель одну и ту же команду всегда выполнит
одинаково, неформальный может выполнять команду
по-разному. Неформальный исполнитель – человек,
формальный – технические устройства.
У каждого исполнителя можно выделить: среду
исполнителя, систему команд исполнителя, систему
отказов.

Среда – обстановка, в которой
работает исполнитель.
Система команд исполнителя (СКИ) –
совокупность команд, которую исполнитель умеет
выполнять.
Система отказов – ситуации сбоя
работы исполнителя, которые возникают, если
команда вызывается пpи недопустимом для нее
состоянии сpеды («не понимаю», «не могу»).
«Не понимаю» – возникает тогда, когда
исполнителю дается команда не входящая в его СКИ,
«не могу» – когда команда из СКИ не может быть
выполнена в конкретных условиях среды.

Укажите для данных примеров среду, ски,
систему отказов.

Свойства алгоритмов

1. Как мы уже знаем, алгоритм задает полную
последовательность действий, которые необходимо
выполнять для решения задачи. При этом, как
правило, для выполнения этих действий их
расчленяют (разбивают) в определенной
последовательности на простые шаги. Возникает
упорядоченная запись совокупности четко
разделенных предписаний (директив, команд),
образующих прерывную (или, как говорят,
дискретную) структуру алгоритма. Выполнить
действия следующего предписания можно лишь
выполнив действия предыдущего.
Под ДИСКРЕТНОСТЬЮ понимают возможность
разбиения алгоритма на отдельные элементарные
действия, выполнение которых человеком или
машиной не вызывает сомнения.

Пример по алгоритму заваривая чая

2. Чтобы исполнитель сумел решить поставленную
перед ним задачу, используя алгоритм, он должен
уметь выполнить каждое его указание. Иными
словами, он должен понимать суть управления. То
есть при составлении алгоритма нужно
обязательно учитывать «правила игры», т.е.
систему предписаний (или систему команд), которые
понимает ЭВМ. Мы будем говорить в данном случае о
«понятности» алгоритма.
Под «ПОНЯТНОСТЬЮ» алгоритмов понимают
указания, которые понятны исполнителю.

Пример по пришиванию пуговицы.

3. Будучи понятным, алгоритм не должен все же
содержать предписаний, смысл которых может
восприниматься неоднозначно. Этими свойствами
часто не обладают предписания  и инструкции,
которые составляются для людей.
Например, вспомним известную всем притчу о
царской воле. Царь приказал подчиненным
выполнить такой указ: «Казнить нельзя
помиловать». Он забыл в указе поставить
запятую, а подчиненные не знали, что им делать.
Указание «казнить нельзя, помиловать» и
«казнить, нельзя помиловать» задают совсем
разные действия, от которых зависит жизнь
человека.
Кроме того, в алгоритмах недопустимы такие
ситуации, когда после выполнения очередного
предписания алгоритма исполнителю неясно, какое
из них должно выполняться на следующем шаге.
Под ОДНОЗНАЧНОСТЬЮ алгоритмов понимается
единственность толкования правил выполнения
действий и порядка их выполнения.

Пример, фрагмент мультфильма «Стран
невыученных уроков».

4. Очень важно, чтобы составленный алгоритм
обеспечивал решение не одной частной задачи, а
мог выполнять решение широкого класса задач
данного типа.
Алгоритм можно использовать для любого
квадратного у равнения. Такой алгоритм будет
МАССОВЫЙ.

Пример с чайниками, обогревателями.

5. Под КОНЕЧНОСТЬЮ алгоритмов понимают
завершение работы алгоритма в целом за конечное
число шагов.

Пример с ловлей рыбы.

6. Еще к желательным свойствам алгоритмов нужно
отнести РЕЗУЛЬТАТИВНОСТЬ, она предполагает, что
выполнение алгоритмов должно завершаться
получением определенных результатов.
Подобные ситуации в информатике возникают, когда
какие-либо действия невозможно выполнить. В
математике такие ситуации называют
неопределенностью. Например, деление числа на
ноль, извлечение квадратного корня из
отрицательного числа, да и само понятие
бесконечности неопределенно. Поэтому, если
алгоритм задает бесконечную последовательность
действий, то в этом случае он также считается
результатом неопределенным.
Но можно действовать по-другому. А именно:
указать причину неопределенного результата. В
таком случае, пояснения типа «на ноль делить
нельзя», «компьютер выполнить такое не в
состоянии» и т.п. можно считать результатом
выполнение алгоритма.
Таким образом, свойство результативности
состоит в том, что во всех» случаях можно
указать, что мы понимаем под результатом
выполнения алгоритма.

Пример с нахождением стрелы Ивана Царевича у
лягушки.

7. И последнее общее свойство алгоритмов – их
правильность.

Мы говорим, что алгоритм ПРАВИЛЬНЫЙ, если его
выполнение дает правильные результаты решения
поставленных задач.
Соответственно мы говорим, что алгоритм СОДЕРЖИТ
ОШИБКИ, если можно указать такие допустимые
исходные данные или условия, при которых
выполнение алгоритма либо не завершится вообще,
либо не будет получено никаких результатов, либо
полученные результаты окажутся неправильными.

Пример с арифметическим выражением.

Вывод:

Основные свойства алгоритмов:

• дискретность;
• понятность;
• однозначность;
• массовость;
• результативность;
• конечность;
• правильность.

Учащиеся записывают в тетрадь свойства.

Решение задач на определение свойств.
Обсуждение свойств с классом.

Задание 1.

Определить какое свойство алгоритма, не
выполняется в данной инструкции и  какие
изменения необходимо внести, чтобы получился
алгоритм.
Инструкция по варке манной каши
Молоко вскипятить добавить соль, сахар, засыпать
тонкой струйкой, непрерывно помешивая манную
крупу, довести до кипения, прокипятить минут 5-7,
добавить масло и дать остыть.
Нет понятности: какое количество (в граммах)
брать продуктов.

Возможный исправленный вариант

1. Включить плиту
2. Влить в кастрюлю 1,5 литра молока
3. Добавить 5 грамм соли, 15 грамм сахара
4. Довести молоко до кипения
5. 8 столовых ложек манной крупы засыпать тонкой
   струйкой, непрерывно помешивая молоко
6. Довести до кипения
7. Кипятить 5 минут
8. Добавить 20 грамм сливочного масла
9. Выключить плиту, снять с плиты кастрюлю.

Задание 2.

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

Инструкция нахождения большего из двух данных
чисел.

1. Из числа А вычесть число В.
2. Если получилось отрицательное значение, то
   сообщить, что число В больше.
3. Если получилось положительное значение, то
   сообщить, что число А больше

Нет результативности. Что делать в том случае,
если А=В?

Возможный исправленный вариант

1. Из числа А вычесть число В.
2. Если получилось отрицательное значение, то
   сообщить, что число В больше.
3. Если получилось положительное значение, то
   сообщить, что число А больше
4. Если получился ноль, сообщить, что числа равны

Задание 3.

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

1. Покрасить первую доску.
2. Переместиться к следующей доске.
3. Перейти к действию 1.

Нет конечности. Что делать в том случае, когда
доски закончились?

Возможный исправленный вариант

1. Покрасить первую доску.
2. Если есть еще доска, переместиться к следующей
   доске.
3. Перейти к действию 1.
4. Если доски закончились, завершить работу.

Практическая работа в парах (5 мин.)

Приложение 1

Задание 1. Исправьте алгоритм
«Получения кипятка», чтобы предотвратить
несчастный случай.
Задание 2. Используя представленные
команды, составить алгоритм покраски мяча
Задание 3. Составить инструкцию, в
которой не выполняется хотя бы одно свойство
алгоритма. Записать какие изменения нужно в нее
внести, чтобы получить алгоритм.

Тест самопроверкой (5 мин.)

1. Алгоритм – это:

А) Указание на выполнение действий,
Б) Система правил, описывающая
последовательность действий, которые необходимо
выполнить для решения задачи,
В) Процесс выполнения вычислений, приводящих к
решению задачи

2. Свойство алгоритма – дискретность, выражает,
что:

А) Команды должны следовать последовательно
друг за другом,
Б) Каждая команда должна быть описана в расчете
на конкретного исполнителя,
В) Разбиение алгоритма на конечное число команд

3. Среда исполнителя – это:

А) Обстановка, в которой работает исполнитель.
Б) Объект, который будет выполнять алгоритм
В) Совокупность команд, которую исполнитель
умеет выполнять.

4. В расчете на кого должен строиться алгоритм:

А) В расчете на ЭВМ,
Б) В расчете на умственные способности товарища,
В) В расчете на конкретного исполнителя

5. Какое из перечисленных свойств относится к
свойствам алгоритма:

А) Визуальность,
Б) Совокупность,
В) Понятность

6. Исполнитель «человек» – это

А) Формальный исполнитель
Б) Неформальный исполнитель
В) Нормальный исполнитель

Проверка теста.

Подведение итогов (5 мин.)

Домашнее задание:

1. Выучить теоретический материал
2. Привести 3 примера алгоритмов для различных
исполнителей.
3. Составить 2 инструкции, в которых не
выполняется хотя бы одно свойство алгоритма.
Записать какие изменения нужно в них внести,
чтобы получить алгоритм.