Конспект для ученика по теме «Элементы теории алгоритмов»

59
2

В статье рассмотрена важная для понимания тема: «Элементы теории алгоритмов». Подробно разобрана теория и есть возможность отработать все на практике. Материал актуален для подготовки к ЕГЭ.

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

inf271. Постановка задачи. Необходимо определить исходные данные (что подаётся «на вход») и требуемые результаты (что следует получить «на выходе»), указать связи между исходными данными и результатами.
inf272. Формализация. На этом этапе определяется класс, к которому принадлежит задача, связи между исходными данными и результатами записываются с помощью математических соотношений.
inf273. Выбор метода решения и разработка алгоритма. Это один из важнейших этапов решения задачи; от правильности выбора метода зависит эффективность алгоритма, определяющая быстродействие программы и размер необходимой для её выполнения памяти.
inf274. Составление программы (запись алгоритма на языке программирования) и её ввод в память компьютера. Сейчас этот этап принято называть кодированием.
inf275. Отладка программы. Созданная программа может содержать ошибки, допущенные как в процессе кодирования, так и на любом из предыдущих этапов. Ошибки могут быть выявлены в процессе тестирования — выполнения программы с заранее подготовленными наборами исходных данных, для которых известен результат.
inf276. Вычисление и обработка результатов.

Задачи, которые мы будем рассматривать в данной главе, достаточно чётко поставлены и формализованы. Основное внимание при их решении мы будем уделять этапам 3-6.

Понятие алгоритма

Каждый из нас ежедневно решает задачи различной сложности: как быстрее добраться в школу или на работу в условиях недостатка времени, в каком порядке выполнить дела, намеченные на текущий день, и т. д. Некоторые задачи настолько сложны, что требуют длительных размышлений для нахождения решения (которое иногда так и не удаётся найти). Другие задачи мы решаем автоматически, т. к. выполняем их ежедневно на протяжении многих лет (выключить звенящий будильник; почистить утром зубы; вскипятить воду в чайнике; позвонить другу по телефону; открыть или закрыть входную дверь ключом). В большинстве случаев в решении каждой задачи можно выделить отдельные шаги.

Пример 1. Решение задачи «Закрыть входную дверь ключом» предполагает выполнение следующих шагов.

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

Последовательность шагов, приведённая в примере 1, является алгоритмом решения задачи «Закрыть входную дверь ключом». Исполнитель этого алгоритма — человек. Объекты этого алгоритма — ключ, дверь.

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

Из курса информатики основной школы вам известны понятия алгоритма и исполнителя.

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

Исполнители бывают двух типов: формальные и неформальные. Далее мы будем говорить преимущественно о формальных или «неразмышляющих» исполнителях. Формальный исполнитель не размышляет над выполняемыми командами, а строго следует пошаговым инструкциям алгоритма. Одну и ту же команду формальный исполнитель всегда выполняет одинаково. За действия формального исполнителя отвечает управляющий им объект.

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

Приведённое определение не является определением в строгом смысле этого слова, это — описание понятия алгоритма, раскрывающее его сущность. Оно не является формальным, потому что в нём используются такие неуточняемые понятия, как «система предписаний», «действия исполнителя», «объект».

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

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

Пример 2.

inf60  Простые числа — это натуральные числа, большие единицы, которые имеют только два делителя: единицу и само это число (рис. 2.1).

91

Рис. 2.1. Примеры простых чисел (иллюстрация Н. П. Антокольской)

Метод нахождения простых чисел в интервале [2; n] предложил греческий математик Эратосфен (275-194 гг. до н. э.). По одной из версий, он выписал все числа от 2 до 10 ООО на папирусе, натянутом на рамку, и прокалывал составные числа. Папирус стал подобен решету, которое «просеивало» составные числа, а простые оставляло. Поэтому метод Эратосфена называют ещё Эратосфеновым решетом.

Во все времена люди хотели найти как можно большее простое число.

Пока люди считали только при помощи карандаша и бумаги, им нечасто удавалось обнаружить новые простые числа. До 1952 г. самое большое известное простое число состояло из 39 цифр.

В 2013 г. открыто простое число, запись которого в десятичной системе счисления состоит из 17 425 170 знаков. На проверку простоты нового числа ушло 39 дней работы персонального компьютера в Университете Центрального Миссури, США.

Для нахождения всех простых чисел не больше заданного числа n, следуя методу Эратосфена, нужно выполнить следующие шаги:

1) выписать подряд все целые числа от 2 до n (2, 3, 4, ..., n);
2) присвоить переменной р значение 2 (2 — первое простое число);
3) зачеркнуть в списке числа, кратные р: 2р, 3р, 4р, ...;
4) найти первое незачёркнутое число в списке, большее чем р, и присвоить переменной р соответствующее значение;
5) повторять шаги 3 и 4, пока возможно.

Числа, остающиеся незачёркнутыми после завершения работы алгоритма, и есть все простые числа от 2 до n.

На практике, алгоритм можно улучшить следующим образом. На шаге 3 числа можно зачёркивать начиная сразу с числа р2 (р • р), потому что все составные числа меньше него к этому времени уже будут зачёркнуты. И соответственно, останавливать алгоритм можно, когда р2 станет больше, чем n.

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

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

inf60  Значение слова «алгоритм» очень похоже по значению на слова «рецепт», «метод», «способ». Но, в отличие от рецепта или способа, любой алгоритм обязательно обладает следующими свойствами.

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

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

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

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

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

Докажите, что рассмотренный в примере 2 метод Эратосфена является алгоритмом.

Не любой расписанный по шагам способ решения задачи является алгоритмом. Убедимся в этом на примере.

Пример 3. Опишем метод построения перпендикуляра к прямой MN, проходящего через заданную точку А этой прямой, с помощью линейки и циркуля (рис. 2.2):

1) отложить в обе стороны от точки А на прямой MN циркулем отрезки равной длины с концами В и С;
2) увеличить раствор циркуля до радиуса, в полтора-два раза больше длины отрезков АВ и АС;
3) провести указанным раствором циркуля дуги окружностей с центрами в точках В и С так, чтобы они охватили точку А и образовали две точки пересечения друг с другом (В и Е);
4) взять линейку, приложить её к точкам В и В и соединить их отрезком; при правильном построении отрезок пройдёт через точку А и будет являться перпендикуляром к прямой MN.

92

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

Почему этот способ построения перпендикуляра к прямой не является алгоритмом? Какое свойство алгоритмов здесь нарушено?

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

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

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

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

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

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

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

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

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

5.2. Способы записи алгоритма

inf60  Из курса информатики основной школы вам известны разные способы записи одного и того же алгоритма:

• словесная запись алгоритма на естественном языке;
• запись алгоритма псевдокодом — частично формализованным естественным языком с элементами языка программирования и общепринятыми математическими обозначениями;
• запись алгоритма в виде блок-схемы — подробного графического представления логической структуры программы или алгоритма с помощью стандартных блоков (условных символов), соединённых линиями;
• запись алгоритма на языке программирования и т. д.

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

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

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

Таблица 2.1

Основные символы блок-схем и отображаемые ими функции

93

Пример 4. Вспомним детскую игру «Угадай-ка». Первый игрок задумывает целое число и сообщает второму игроку, из какого оно диапазона. Второй игрок должен как можно быстрее угадать загаданное число. Второй игрок может называть числа, а первый должен говорить, меньше или больше названное число задуманного. Игра заканчивается, если названо число, равное задуманному.

Пусть задумано число X ∈ [А, В]. Представим в виде блок-схемы алгоритм решения этой задачи — известный вам метод половинного деления (рис. 2.3).

94

Рис. 2.3. Метод половинного деления

Подсчитайте, какое наибольшее число шагов может понадобиться для угадывания по этому алгоритму числа X ∈ [0, 100].

5.3. Понятие сложности алгоритма

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

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

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

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

inf60  Вычислительным процессом, порождённым алгоритмом, называется последовательность шагов алгоритма, пройденных при его исполнении.

inf60  Сложность алгоритма — количество элементарных шагов (действий) в вычислительном процессе этого алгоритма.

Обратите внимание, в определении сложности алгоритма речь идёт именно о вычислительном процессе, а не о самом алгоритме.

Алгоритм состоит из команд.

inf60 Команда — это отдельная инструкция в описании алгоритма. Шаг алгоритма — это отдельное действие, которое исполнитель выполняет по команде. В циклических алгоритмах за счёт повторного выполнения одних и тех же команд число шагов при выполнении алгоритма может быть значительно больше числа команд в алгоритме.

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

Так, например, алгоритм, выполняющий только операции чтения данных и занесения их в оперативную память, имеет линейную сложность O(n) (читается «о большое от эн»). Существуют алгоритмы, имеющие квадратичную и кубическую сложности.

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

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

Пример 5. Известно, что во многих языках программирования нет операции возведения в степень, и поэтому такой алгоритм программисту надо писать самостоятельно. Операция возведения в степень реализуется через операции умножения. С ростом показателя степени растёт количество операций умножения, которые выполняются достаточно долго. Следовательно, актуален вопрос о создании эффективного алгоритма возведения в степень.

Рассмотрим метод быстрого вычисления натуральной степени п вещественного числа х, описанный в Древней Индии ещё до нашей эры.

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

Воспользуемся этим алгоритмом для того, чтобы возвести х в степень n = 100.

  1. 100 = 11001002.
  2. Строим последовательность: КХКХКККХКК.
  3. Вычёркиваем крайнюю левую пару КХ: КХКККХКК.
  4. Вычисляем искомое значение:

    К: возвести х в квадрат (х2);
    X: умножить результат на х (x3);
    К: возвести результат в квадрат (х6);
    К: возвести результат в квадрат (х12);
    К: возвести результат в квадрат (х24);
    X: умножить результат на х (х25);
    К: возвести результат в квадрат (х50);
    К: возвести результат в квадрат (х100).

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

САМОЕ ГЛАВНОЕ

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

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

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

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

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

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

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

  1. Перечислите основные свойства алгоритмов и проиллюстрируйте их примерами.
  2. Почему кулинарный рецепт приготовления торта нельзя считать алгоритмом? Какими свойствами алгоритма он не обладает?
  3. Переформулируйте описание способа проведения перпендикуляра к прямой в заданной точке так, чтобы оно стало алгоритмом.
  4. Есть двое песочных часов: на 3 и на 8 минут. Для приготовления эликсира бессмертия его надо варить ровно 7 минут. Как это сделать?

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

  1. Исполнитель Вычислитель получает на вход целое число х и может выполнять с ним преобразования по алгоритму, состоящему из любого количества команд: 1) прибавить 5; 2) вычесть 2.

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

  1. Как известно, для каждого исполнителя набор допустимых действий всегда ограничен, иначе говоря, не может существовать исполнителя, для которого любое действие является допустимым. Докажите это утверждение, предположив, что такой исполнитель существует.
  2. Перечислите известные вам способы записи алгоритмов.
  3. Приведите примеры задач и оптимальных способов записи алгоритмов их решения.
  4. Исполнитель Автомат получает на вход четырёхзначное число. Это число он преобразует по следующему алгоритму:

    1) вычисляется сумма первой и второй цифр числа;
    2) вычисляется сумма второй и третьей цифр числа;
    3) вычисляется сумма третьей и четвёртой цифр числа;
    4) из полученных трёх чисел (сумм) выбирается и отбрасывается одно — не превышающее двух других чисел;
    5) оставшиеся два числа записываются друг за другом в порядке неубывания без разделителей.

Так, если исходное число 9575, то, преобразуя его, автомат создаст суммы: 9 + 5 = 14, 5 + 7 = 12, 7 + 5 = 12. Сумма, не превышающая двух других, 12. Оставшиеся суммы: 14, 12. Результат: 1214.

Опишите систему команд этого исполнителя.

Могут ли результатом работы этого исполнителя быть числа 1610, 1010, 1019?

Укажите минимальное и максимальное значения результата работы этого исполнителя.

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

  1. В чём отличие шага алгоритма от команды алгоритма? Приведите пример.
  2. Что такое сложность алгоритма? От чего она зависит в наибольшей степени?
  3. Подсчитайте сложность алгоритма перемножения двух натуральных чисел «столбиком» при условии, что одно из них состоит из n, а второе — из m десятичных цифр.
  4. Какой алгоритм считается эффективным?
  5. Постройте эффективный алгоритм возведения числа х в степень n = 152.
59
2
Текст прошел проверку у экспертов «ИнПро» ®
педагог по информатике
педагог по информатике
педагог по информатике
педагог по информатике

Справочно:

Материалы подготовлены Федеральным образовательным сервисом «ИнПро»® – Лицензия Минобрнауки 22Л01 № 0002491.

Готовим детей к школе, а также подтягиваем по школьной программе по всей России в 40+ центрах и онлайн, в том числе в Вашем городе.

Бесплатная горячая линия: 8 800 250 62 49 (с 6 до 14 по Мск).


Следите за новостями в социальных сетях:


Нужен репетитор? Запишитесь на бесплатное пробное занятие в «ИнПро»®

Отправка запроса ни к чему не обязывает, это бесплатно. Будем рады помочь!

Отправляя заявку, Вы соглашаетесь на обработку персональных данных.


В текущем разделе «1.20 Элементы теории алгоритмов » также читают

Нужен репетитор?
Запишитесь на бесплатное пробное занятие в «ИнПро»®

Отправка запроса ни к чему не обязывает, это бесплатно. Будем рады помочь!

Отправляя заявку, Вы соглашаетесь на обработку персональных данных.
Записаться на бесплатное занятие Бесплатное занятие