Билет 18

1. ПОНЯТИЕ АЛГОРИТМА. СВОЙСТВА АЛГОРИТМОВ. ФОРМЫ ЗАПИСИ АЛГОРИТМОВ. ПРОИЗВОДИТЕЛЬНОСТЬ АЛГОРИТМОВ, ОТ ЧЕГО ОНА ЗАВИСИТ. РЕКУРСИВНЫЕ АЛГОРИТМЫ.

1. В коробке лежат 64 цветных карандаша. Сообщение о том, что достали белый карандаш, несет 4 бита информации. Сколько белых карандашей было в коробке?

Алгоритм - это последовательность инструкций для выполнения какого либо задания.

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

? ДИСКРЕТНОСТЬ – разделение выполнения решения задачи на отдельные операции

? ОПРЕДЕЛЕННОСТЬ (точность) алгоритма – определение однозначных действий исполнителя

? ПОНЯТНОСТЬ – не должен быть рассчитан на принятие каких-либо самостоятельных решений

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

? РЕЗУЛЬТАТИВНОСТЬ (конечность) алгоритма – исполнение алгоритма должно закончиться за конечное число ша-гов

ФОРМЫ ЗАПИСИ АЛГОРИТМОВ:

? ЗАПИСАН НА ЕСТЕСТВЕННОМ ЯЗЫКЕ; Алгоритм записывается в виде пронумерованных этапов его выполнения.

? ИЗОБРАЖЕН В ВИДЕ БЛОК СХЕМЫ; Алгоритм записывается в виде схемы, состоящей из блоков (геометрических фигур) с размещенными в них действиями. Блоки соединяются стрелочками и показывают структуру всего алго-ритма. Алгоритм в виде блок-схемы начинается блоком «начало» и заканчивается блоком «конец».

? ЗАПИСАН НА АЛГОРИТМИЧЕСКОМ ЯЗЫКЕ. Это запись алгоритма на специальном языке (в том числе и на языке программирования). Она осуществляется, строго следуя правилам того или иного алгоритмического языка. Заго-ловок включает в себя название алгоритма, имена исходных данных (это величины, без которых выполнить ал-горитм невозможно) и имена результатов (это величины, значения которых вычисляются в алгоритме). Для ука-зания начала и конца алгоритма используются служебные слова нач и кон. Между ними записывают одну или несколько команд алгоритма, их называют тело алгоритма.

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

O(f(N)) (произносится «О большое от F от N»),

если с увеличением размерности исходных данных N время выполнения алгоритма растет пропорционально функции f(N).

Производительность алгоритмов:

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

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

? Требования к ПК

o Размер оперативной памяти

o Скорость работы диска

o Скорость (частота) работы процессора

Рекурсивные алгоритмы - алгоритмы, вызывающие сами себя до тех пор, пока не будет достигнуто некоторое условие возвращения. Рекурсивными процедурами (recursive procedure) называются процедуры, вызывающие сами себя. Во многих рекурсивных алгоритмах именно степень вложенности рекурсии определяет сложность алгоритма, при этом по-рядок сложности не всегда легко оценить. Рекурсивная процедура может выглядеть простой, но в то же время серьезно усложнять программу, многократно вызывая саму себя. Но у такого алгоритма есть один существенный минус – он тре-бует огромных машинных ресурсов. Посудите сами, необходимо хранить в памяти для каждой "копии" функции все те данные, которыми вы пользовались, не говоря уже о самой функции.

2.