К 11 классу ты уже программировал. Теперь взглянем на алгоритмы строго и системно — это фундамент, который спрашивают и на экзаменах.
Чему ты научишься. называть свойства алгоритма и объяснять, что такое сложность алгоритма и зачем её оценивают.
Алгоритм и его свойства
Алгоритм — конечная последовательность точных предписаний, приводящая от исходных данных к результату. Строгие свойства алгоритма:
СВОЙСТВА АЛГОРИТМА: дискретность — состоит из отдельных шагов детерминированность — при одних данных — всегда один результат понятность — команды из системы команд исполнителя результативность — даёт результат конечность — завершается за конечное число шагов массовость — применим к классу однотипных задач
Сложность алгоритма
Одну задачу можно решить разными алгоритмами. Сложность алгоритма — оценка того, сколько шагов (времени) и памяти он требует. Из двух верных алгоритмов лучше тот, что работает быстрее и экономнее — особенно на больших данных.
Контрольный вопрос. Свойство, при котором алгоритм при одних и тех же данных всегда даёт один результат, — это…
Подсказка: Без случайности.
Онлайн-проверка ответа появится позже
Контрольный вопрос. Свойство алгоритма, при котором он состоит из отдельных, чётко разделённых шагов, называется ______. Впиши слово.
Подсказка: От слова «дискретный» — не непрерывный, а по шагам.
Онлайн-проверка ответа появится позже
Контрольный вопрос. Свойство, при котором каждая команда алгоритма входит в систему команд исполнителя (исполнитель её понимает), называется…
Подсказка: Если исполнитель не знает команду — он её не выполнит.
Онлайн-проверка ответа появится позже
Контрольный вопрос. Свойство, гарантирующее, что алгоритм действительно даёт результат, а не просто выполняется, называется…
Подсказка: Без него алгоритм мог бы работать «в никуда».
Онлайн-проверка ответа появится позже
Контрольный вопрос. Свойство алгоритма, при котором он применим не к одной задаче, а к целому классу однотипных задач, называется ______. Впиши слово.
Подсказка: Один и тот же алгоритм решает МНОГО похожих задач.
Онлайн-проверка ответа появится позже
Контрольный вопрос. Свойство, гарантирующее, что алгоритм завершится за конечное число шагов, — это…
Подсказка: Не зациклится.
Онлайн-проверка ответа появится позже
Контрольный вопрос. Оценка числа шагов и памяти, необходимых алгоритму, — это его…
Подсказка: Быстрее и экономнее — лучше.
Онлайн-проверка ответа появится позже
Контрольный вопрос. Алгоритм А решает задачу за 100 шагов, алгоритм Б — за 10000 шагов на тех же входных данных. Какой алгоритм имеет меньшую сложность (по числу шагов)?
Подсказка: Меньше шагов — меньше сложность.
Онлайн-проверка ответа появится позже
Контрольный вопрос. Алгоритм при одинаковых входных данных в разные разы выдаёт то один результат, то другой. Какое свойство алгоритма нарушено?
Подсказка: Это свойство требует ОДНОГО результата при ОДНИХ данных.
Онлайн-проверка ответа появится позже
Задание. Опиши своими словами алгоритм из повседневной жизни (например, «заварить чай» или «перейти дорогу по светофору») минимум из 5 шагов.
1) Перечисли шаги по порядку.
2) Проверь свой алгоритм на 3 свойства: дискретность, детерминированность и конечность — объясни для каждого, выполняется ли оно и почему.
3) Придумай пример входных данных, при которых твой алгоритм НЕ сработает так, как задумано (нарушится результативность), и объясни почему.Подсказка: Дискретность — шаги разделены; детерминированность — одни данные дают один результат; конечность — алгоритм заканчивается.
Онлайн-проверка ответа появится позже
Итог. Алгоритм — конечная последовательность точных предписаний от исходных данных к результату. У него есть строгие свойства: дискретность, детерминированность, понятность, результативность, конечность, массовость. Сложность алгоритма показывает, сколько шагов и памяти он требует, — и лучше тот, что работает быстрее и экономнее.
Что дальше
Любой алгоритм собирается из нескольких базовых структур. О них следующий урок.
