Учебник. А. Ю. Босова Москва бином. Лаборатория знаний 2016 11 класс Базовый уровень Учебник
 Скачать 4.61 Mb.
|
|
Глава 2. алгоритмы и программирование Пример 3. Опишем метод построения перпендикуляра к пря- мой MN, проходящего через заданную точку A этой прямой, с помощью линейки и циркуля (рис. 2.2): 1) отложить в обе стороны от точки A на прямой MN циркулем отрезки равной длины с концами B и C; 2) увеличить раствор циркуля до радиуса, в полтора-два раза больше длины отрезков AB и AC; 3) провести указанным раствором циркуля дуги окружностей с центрами в точках B и C так, чтобы они охватили точку А и образовали две точки пересечения друг с другом (D и E); 4) взять линейку, приложить её к точкам D и E и соединить их отрезком; при правильном построении отрезок пройдёт через точку A и будет являться перпендикуляром к прямой MN. рис. 2.2. Построение перпендикуляра к прямой Почему этот способ построения перпендикуляра к прямой не яв ляется алгоритмом? Какое свойство алгоритмов здесь нарушено? Есть задачи, которые человек успешно решает, но при этом не может представить процесс их решения в виде последователь- ности шагов. Например, если перед человеком положить фотографии собак и кошек и попросить определить, на каких фотографиях изобра- жены собаки, а на каких кошки, то человек практически мгно- венно и безошибочно решит эту задачу. Написать же формальный алгоритм решения этой и подобных ей задач пока что не удалось, хотя определённые успехи в этой области, называемой теорией распознавания образа, уже достигнуты. 69 Основные сведения об алгоритмах §5 В супермаркетах вы видите системы распознавания штрихкодов, используете системы оптического распознавания символов, знаете о распознавании автомобильных номеров, слышали о распознава нии изображений лиц, речи и т. д. Технические системы распознавания образов находят сегодня ши рокое применение в самых разных областях — от военного дела и систем безопасности до оцифровки аналоговых сигналов. Их раз работка базируется на теории распознавания образов — разделе информатики и смежных дисциплин, развивающем основы и методы классификации и идентификации предметов, явлений, процессов, сигналов, ситуаций и тому подобных объектов, характеризующихся конечным набором некоторых свойств и признаков. С учётом рассмотренных свойств алгоритма можно дать более формальное определение этого понятия, которое также не явля- ется строгим, т. к. в нём всё ещё используются не определяемые точно термины. алгоритм — это конечная система правил, сформулированных на языке исполнителя, которая определяет последовательность перехо да от допустимых исходных данных к конечному результату и обла дает свойствами дискретности, детерминированности, понятности, результативности, конечности и массовости. Математики достаточно долго пользовались интуитивным (нестро гим) понятием алгоритма, записывая алгоритмы примерно так, как в примере 3. Ими были сформулированы многие успешно приме няемые на практике алгоритмы решения таких задач, как выпол нение арифметических действий «столбиком», нахождение корней квадратных и кубических уравнений, решение систем линейных уравнений и др. Постепенно математики подходили к постановке и решению всё более сложных задач, требовавших построения фор мального определения алгоритма. Попытки разработать формальное определение алгоритма приве ли в 20–30х годах XX века к возникновению теории алгоритмов — науки, изучающей общие свойства и закономерности алгоритмов и разнообразные формальные модели их представления. Вместе с математической логикой теория алгоритмов образует теоретическую основу вычислительных наук. Математики (А. Тьюринг, Э. Пост, А. Н. Колмогоров, А. А. Марков и др.) предложили несколько подходов к формальному определению алгоритма: нормальный алгоритм Маркова, машина Тьюринга, ма шина Поста и т. д. Дальнейшее показало, что все эти определения эквивалентны. На основании этих определений учёные пришли к выводу о существовании алгоритмически неразрешимых задач — за дач, для которых невозможно построить процедуру решения. 70 Глава 2. алгоритмы и программирование 5.2. Способы записи алгоритма Из курса информатики основной школы вам известны разные способы записи одного и того же алгоритма: • словесная запись алгоритма на естественном языке; • запись алгоритма псевдокодом — частично формализованным естественным языком с элементами языка программирования и общепринятыми математическими обозначениями; • запись алгоритма в виде блок-схемы — подробного графиче- ского представления логической структуры программы или алгоритма с помощью стандартных блоков (условных симво- лов), соединённых линиями; • запись алгоритма на языке программирования и т. д. Выбор способа записи алгоритма зависит от ряда причин. Не- большой алгоритм можно записать и в словесной форме. Если для вас наиболее важна наглядность, то разумно использовать блок-схему. Алгоритм же, готовый к реализации, должен быть записан на языке, понятном исполнителю. Правила выполнения блоксхем, внешний вид графических блоков и их назначение определяются стандартом ГОСТ 19.701–90 (ИСО 5807–85) «Схемы алгоритмов, программ, данных и систем. Обозна чения условные и правила выполнения». Напомним основные условные графические обозначения (символы), которые мы будем использовать в дальнейшем (табл. 2.1). Таблица 2.1 Основные символы блок-схем и отображаемые ими функции Символ Функция Пуск/останов. Начало, конец, прерывание процесса обработки данных или выполнения программы Ввод/вывод. Преобразование данных в форму, при- годную для обработки (ввод) или отображения результатов обработки (вывод) Процесс. Выполнение операций или группы опера- ций, в результате которых изменяется значение, форма представления или расположение данных Решение. Выбор направления выполнения алгоритма или программы в зависимости от некоторых переменных условий 71 Основные сведения об алгоритмах §5 Символ Функция Модификация. Выполнение операций, меняющих команды или группу команд, изменяющих программу Предопределённый процесс. Использование ранее созданных и отдельно описанных алгоритмов или программ Пример 4. Вспомним детскую игру «Угадай-ка». Первый иг- рок задумывает целое число и сообщает второму игроку, из ка- кого оно диапазона. Второй игрок должен как можно быстрее угадать загаданное число. Второй игрок может называть числа, а первый должен говорить, меньше или больше названное число задуманного. Игра заканчивается, если названо число, равное за- думанному. Пусть задумано число X ∈ [A, B]. Представим в виде блок- схемы алгоритм решения этой задачи — известный вам метод половинного деления (рис. 2.3). рис. 2.3. Метод половинного деления Окончание табл. 2.1 72 Глава 2. алгоритмы и программирование Подсчитайте, какое наибольшее число шагов может понадобиться для угадывания по этому алгоритму числа X ∈ [0, 100]. 5.3. Понятие сложности алгоритма В теории алгоритмов установлено, что для задачи, имеющей алгоритмическое решение, можно придумать множество различ- ных способов её решения, т. е. алгоритмов. Какой же алгоритм лучше подходит для решения конкретной задачи? По каким критериям его следует выбирать из множества возможных? Человек может назвать алгоритм сложным и запутанным из- за того, что тот обладает разветвлённой логической структурой, содержащей много проверок условий и переходов. Однако для компьютера выполнение программы, реализующей такой алго- ритм, не составит труда, т. к. он выполняет одну команду за другой, и для компьютера неважно — операция ли это умноже- ния или проверка условия. Теория алгоритмов предоставляет аппарат анализа различных алгоритмов решения одной и той же задачи, на основе которого можно выбрать самый эффективный (наилучший) алгоритм. Вычислительным процессом, порождённым алгоритмом, называ ется последовательность шагов алгоритма, пройденных при его ис полнении. Сложность алгоритма — количество элементарных шагов (дейст вий) в вычислительном процессе этого алгоритма. Обратите внимание, в определении сложности алгоритма речь идёт именно о вычислительном процессе, а не о самом алгорит- ме. Алгоритм состоит из команд. Команда — это отдельная ин- струкция в описании алгоритма. Шаг алгоритма — это отдельное действие, которое исполнитель выполняет по команде. В цикли- ческих алгоритмах за счёт повторного выполнения одних и тех же команд число шагов при выполнении алгоритма может быть значительно больше числа команд в алгоритме. Очевидно, что в наибольшей степени число операций при вы- полнении алгоритма зависит от количества обрабатываемых дан- ных. Действительно, для упорядочивания по алфавиту списка из 100 фамилий требуется существенно меньше операций, чем для упорядочивания списка из 100 000 фамилий. Поэтому сложность алгоритма выражают в виде функции от объёма входных данных. 73 Основные сведения об алгоритмах §5 Так, например, алгоритм, выполняющий только операции чте- ния данных и занесения их в оперативную память, имеет линей- ную сложность О(n) (читается «о большое от эн»). Существуют алгоритмы, имеющие квадратичную и кубическую сложности. Для решения задачи могут быть разработаны алгоритмы, имею щие разную сложность. Лучшим среди них считается алго- ритм, имеющий наименьшую сложность. Наряду со сложностью важной характеристикой алгоритма яв- ляется эффективность. Эффективность оценивается количеством элементарных операций, которые необходимо выполнить для ре- шения задачи, а также количеством памяти, требующейся для выполнения алгоритма. Пример 5. Известно, что во многих языках программирования нет операции возведения в степень, и поэтому такой алгоритм программисту надо писать самостоятельно. Операция возведения в степень реализуется через операции умножения. С ростом пока- зателя степени растёт количество операций умножения, которые выполняются достаточно долго. Следовательно, актуален вопрос о создании эффективного алгоритма возведения в степень. Рассмотрим метод быстрого вычисления натуральной степени n вещественного числа х, описанный в Древней Индии ещё до нашей эры. 1. Запишем n в двоичной системе счисления. 2. Заменим в этой записи каждую единицу парой букв КХ, а каждый ноль — буквой К. 3. Вычеркнем крайнюю левую пару КХ. 4. Полученная строка, читаемая слева направо, даёт правило быст рого вычисления х n , если букву К рассматривать как операцию возведения результата в квадрат, а букву X — как операцию умножения результата на х. Вначале результат ра- вен х. Воспользуемся этим алгоритмом для того, чтобы возвести x в степень n = 100. 1. 100 = 1100100 2 2. Строим последовательность: KXKXKKKXKK. 3. Вычёркиваем крайнюю левую пару КХ: KXKKKXKK. 4. Вычисляем искомое значение: K: возвести х в квадрат (х 2 ); X: умножить результат на х (х 3 ); K: возвести результат в квадрат (х 6 ); 74 Глава 2. алгоритмы и программирование K: возвести результат в квадрат (х 12 ); K: возвести результат в квадрат (х 24 ); X: умножить результат на х (х 25 ); K: возвести результат в квадрат (х 50 ); K: возвести результат в квадрат (х 100 ). Мы вычислили сотую степень числа х за 8 умножений. Это значительно эффективнее «прямолинейного» алгоритма возведения в степень, требующего 99 операций умножения. СамОе ГлаВнОе Алгоритм — это конечная система правил, сформулированных на языке исполнителя, которая определяет последовательность пе- рехода от допустимых исходных данных к конечному результату и обладает свойствами дискретности, детерминированности, понят- ности, результативности, конечности и массовости. Исполнитель алгоритма — это субъект или устройство, спо- собные правильно интерпретировать описание алгоритма и выпол- нить содержащийся в нём перечень действий. Один и тот же алгоритм может быть записан разными спосо- бами: на естественном языке, псевдокодом, с помощью блок-схем, на языке программирования и т. д. Для задачи, имеющей алгоритмическое решение, можно при- думать множество различных способов её решения, т. е. алго- ритмов. Теория алгоритмов предоставляет аппарат анализа раз- личных алгоритмов решения одной и той же задачи, на основе которого можно выбрать самый эффективный (наилучший) алго- ритм. Алгоритм состоит из команд. Команда — это отдельная ин- струкция в описании алгоритма. Шаг алгоритма — это отдельное действие, которое исполнитель выполняет по команде. Вычисли- тельным процессом, порождённым алгоритмом, называется после- довательность шагов алгоритма, пройденных при его исполнении. Сложность алгоритма — количество элементарных шагов (дей- ствий) в вычислительном процессе этого алгоритма. Наряду со сложностью важной характеристикой алгоритма является эффек- тивность. Эффективность оценивается количеством элементарных операций, которые необходимо выполнить для решения задачи, а также количеством памяти, требующейся для выполнения ал- горитма. 75 Основные сведения об алгоритмах §5 Вопросы и задания 1. Перечислите основные свойства алгоритмов и проиллюстри- руйте их примерами. 2. Почему кулинарный рецепт приготовления торта нельзя счи- тать алгоритмом? Какими свойствами алгоритма он не обла- дает? 3. Переформулируйте описание способа проведения перпендику- ляра к прямой в заданной точке так, чтобы оно стало алго- ритмом. 4. Есть двое песочных часов: на 3 и на 8 минут. Для приго- товления эликсира бессмертия его надо варить ровно 7 ми- нут. Как это сделать? Придумайте систему команд исполнителя Колдун. Запиши- те с их помощью план действий исполнителя по приготовле- нию эликсира. 5. Исполнитель Вычислитель получает на вход целое число x и может выполнять с ним преобразования по алгоритму, состоящему из любого количества команд: 1) прибавить 5; 2) вычесть 2. Сколько разных алгоритмов, состоящих из пяти команд, можно составить для этого исполнителя? Сколько из них будут приводить к одинаковым результатам для заданного числа x? 6. Как известно, для каждого исполнителя набор допустимых действий всегда ограничен, иначе говоря, не может сущест- вовать исполнителя, для которого любое действие является допустимым. Докажите это утверждение, предположив, что такой исполнитель существует. 7. Перечислите известные вам способы записи алгоритмов. 8. Приведите примеры задач и оптимальных способов записи алгоритмов их решения. 9. Исполнитель Автомат получает на вход четырёхзначное чи- сло. Это число он преобразует по следующему алгоритму: 1) вычисляется сумма первой и второй цифр числа; 2) вычисляется сумма второй и третьей цифр числа; 3) вычисляется сумма третьей и четвёртой цифр числа; 4) из полученных трёх чисел (сумм) выбирается и отбрасы- вается одно — не превышающее двух других чисел; 76 Глава 2. алгоритмы и программирование 5) оставшиеся два числа записываются друг за другом в по- рядке неубывания без разделителей. Так, если исходное число 9575, то, преобразуя его, автомат создаст суммы: 9 + 5 = 14, 5 + 7 = 12, 7 + 5 = 12. Сумма, не превышающая двух других, 12. Оставшиеся суммы: 14, 12. Результат: 1214. Опишите систему команд этого исполнителя. Могут ли результатом работы этого исполнителя быть числа 1610, 1010, 1019? Укажите минимальное и максимальное значения результата работы этого исполнителя. При обработке некоторого числа x автомат выдаёт результат 1418. Укажите наименьшее и наибольшее значения x, при которых возможен такой результат. 10. Подготовьте краткое сообщение об одном из учёных (А. Тью- ринг, Э. Пост, А. Н. Колмогоров, А. А. Марков и др.), внёс- ших вклад в развитие теории алгоритмов. 11. В чём отличие шага алгоритма от команды алгоритма? При- ведите пример. 12. Что такое сложность алгоритма? От чего она зависит в наи- большей степени? 13. Подсчитайте сложность алгоритма перемножения двух нату- ральных чисел «столбиком» при условии, что одно из них состоит из n, а второе — из m десятичных цифр. 14. Какой алгоритм считается эффективным? 15. Постройте эффективный алгоритм возведения числа х в сте- пень n = 152. § 6 алгоритмические структуры Вне зависимости от выбранной формы записи элементарные шаги алгоритма объединяются в алгоритмические конструкции (структуры): последовательные, ветвящиеся, циклические, вспомо- гательные и рекурсивные. Для записи любого алгоритма достаточ- но трёх основных алгоритмических структур: последовательной, ветвящейся, циклической. 77 алгоритмические структуры §6 6.1. Последовательная алгоритмическая конструкция Алгоритм реализован через последовательную алгоритмическую конструкцию, если все команды алгоритма выполняются один раз, причём в том порядке, в котором они записаны в тексте программы. Пример 1. Алгоритм, реализованный через последовательную алгоритмическую конструкцию, представлен блок-схемой на ри- сунке 2.4. рис. 2.4. Последовательная алгоритмическая конструкция Выясните, какую задачу решает этот алгоритм. Чему равен резуль тат работы алгоритма при х = 2? Пример 2. Из курса информатики основной школы вам зна- ком исполнитель Вычислитель, выполняющий программы линей- ной структуры. Его система команд может содержать две и более команды с использованием арифметических операций. 78 Глава 2. алгоритмы и программирование Пусть исполнитель Вычислитель может выполнять следующие команды: 1) прибавь 2; 2) умножь на 3. Подсчитаем, сколько разных программ, состоящих из трёх команд, можно составить для этого исполнителя, и выясним чи- сло различных значений, которые будут получены в результате их исполнения при начальном значении 2. Так как каждую из команд вы можете выбрать одним из двух вариантов, а всего команд в программе три, общее число программ находится как N = 2 3 Для удобства поиска числа разных вариантов значений, кото- рые будут получены по этим программам, составим дерево реше- ний (рис. 2.5). В его корневой вершине (0-й уровень) записыва- ется начальное значение. Ветви дерева соответствуют командам: левые — первой, правые — второй. В каждой вершине дерева 1-го, 2-го и т. д. уровней записывается результат, полученный после применения команды к числу из вершины-предка. Путь к каждой из вершин соответствует последовательности команд (программе) для получения значения, находящегося в вершине. Таким образом в вершинах N-го уровня будут записанны резуль- таты программ, состоящих из N команд. В нашем примере все значения в вершинах третьего уровня различны. Иногда значения в вершинах одного уровня совпадают. Можно сказать, что в общем случае число различных значений на уровне не превышает числа его вершин. рис. 2.5. Пример дерева решений 79 алгоритмические структуры §6 Номер уровня, на котором впервые появляется необходимое число, равен минимальному количеству команд для его получе- ния. В нашем примере число 8 записано в вершинах 2-го и 3-го уровней, следовательно, минимальное количество команд для его получения равно двум. Для определения количества программ, с помощью которых требуемое число получается из заданного, можно подсчитать ко- личество вершин дерева, в которых записано требуемое число. Подумайте, почему при заданных условиях существует только две программы для получения из числа 2 числа 8. Если количество уровней вершин в де- рис. 2.6. Пример обратного дерева решений реве решений превышает четыре, то строить такое дерево неудобно. Так же как и в слу- чае, когда система команд исполнителя со- стоит из трёх и более команд. Для некоторых задач удобнее строить обратное дерево решений: команды испол- нителя меняются на «обратные», пути стро- ятся от результата к начальному значению. На рисунке 2.6 показан пример построения обратного дерева решений (из числа 8 полу- чаем число 2; команды: 1) вычти 2; 2) раз- дели на 3). Этот приём удобно использовать, когда обратные команды не применимы ко всем вершинам. 6.2. Ветвящаяся алгоритмическая конструкция Алгоритм реализован через ветвящуюся алгоритмическую кон- струкцию, если от входных данных зависит, какие команды алго ритма будут выполняться. При каждом конкретном наборе входных данных ветвящаяся алгоритмическая конструкция сводится к выпол нению последовательной алгоритмической конструкции. Пример 3. Алгоритм, реализованный через ветвящуюся ал- горитмическую конструкцию, представлен блок-схемой на рисун- ке 2.7. |