Список рекомендуемой литературы
1. Информатика // Большая российская энциклопедия / С. Л. Кравец. — М.: ОАО «Научное издательство «Большая Российская Энциклопедия», 2008. 768 с.
- Макарова Н.В., Волков В.Б. Информатика: учебник для вузов. СПб.: Питер, 2011. 576 с.
- Информатика. Мультимедийный электронный учебник [сайт]. URL: http://inf.e-alekseev.ru/text/Cod.html (дата обращения: 01.02.2014).
Глава 2. Основы алгоритмизации
Алгоритм: понятие, свойства, формы записи.
Понятие алгоритма
Под программированием в настоящее время понимается теория и практика создания программ для ЭВМ. Для того чтобы освоить современные технологии программирования необходимо, в первую очередь, понять что такое алгоритм и научиться составлять алгоритмы.
Понятие алгоритма является одним из основных понятий современной математики. Конечно же, алгоритм вовсе не изобретение XX века, когда появились первые электронно-вычислительные машины. Особый интерес проявляли к алгоритмам математики. Один из древнейших известных алгоритмов — алгоритм Евклида для вычисления наибольшего общего делителя (НОД) двух натуральных чисел, он считается первым алгоритмом.
Слово «алгоритм» происходит от имени узбекского математика IX в. Мухаммеда из Хорезма (по-арабски – “Аль-Хорезми”). Его работы по арифметике и алгебре были переведены на латинский язык в XII в. и оказали большое влияние на развитие математики в Европе. Сформулированные им правила выполнения четырех арифметических действий получили название “алгоризм”, которое впоследствии трансформировалось в “алгоритмус”, затем в “алгорифм” и “алгоритм”.
|
|
|
Интуитивное понятие алгоритма, которым люди пользуются уже много лет (но есть еще и строгое), можно выразить следующим образом: алгоритм – это заданная определенным образом последовательность действий, приводящая за конечное число шагов к достижению поставленной цели (к решению поставленной задачи).
Понятие «действие», в дальнейшем будем считать тождественным понятиям инструкция и оператор.
Действия (инструкции, операторы) выполняются некоторым исполнителем. Исполнитель алгоритма — это некоторая абстрактная или реальная (техническая, биологическая или биотехническая) система, способная выполнить действия, предписываемые алгоритмом.
Исполнителя хаpактеpизуют:
1. среда;
2. элементарные действия;
3. система команд;
4. отказы.
Среда (или обстановка) — это "место обитания" исполнителя.
Каждый исполнитель может выполнять команды только из некоторого строго заданного списка — системы команд исполнителя. Для каждой команды должны быть заданы условия применимости (в каких состояниях среды может быть выполнена команда) и описаны pрезультаты выполнения команды.
|
|
|
После вызова команды исполнитель совершает соответствующее элементарное действие.
Отказы исполнителя возникают, если команда вызывается пpи недопустимом для нее состоянии сpеды.
Обычно исполнитель ничего не знает о цели алгоpитма. Он выполняет все полученные команды, не задавая вопросов "почему" и "зачем".
Если исполнителем алгоритма является процессор ЭВМ, то алгоритм это программа. Можно сказать, что суть работы ЭВМ выполнение процессором команд программы.
В жизни алгоритмы встречаются нам повсюду. Любая целенаправленная деятельность человека – алгоритм (или его выполнение).
Богатым сборником алгоритмов является кулинарная книга. Например, рецепт приготовления каши:
1) поставить на огонь воду;
2) ждать, пока не закипит;
3) посолить;
4) насыпать крупу;
5) ждать, пока не закипит;
6) убавить огонь;
7) ждать 20 минут.
Очень тщательно и подробно алгоритмы изучаются в таком направлении информатики, как теория алгоритмов.
Теория алгоритмов - это наука, изучающая общие свойства и закономерности алгоритмов, разнообразные формальные модели их представления. На основе формализации понятия алгоритма возможно сравнение алгоритмов по их эффективности, проверка их эквивалентности, определение областей применимости.
|
|
|
Долгое время считалось, что для любой математической задачи можно найти метод (алгоритм) решения, просто для ряда задач такие алгоритмы еще не найдены. Эту идею высказал еще аль Хорезми, такой же точки зрения придерживались и другие математики вплоть до начала XX века. Однако, несмотря на все усилия, решить некоторые задачи не удавалось в течение столетий. Например, безуспешно закончились многочисленные попытки найти алгоритм доказательства правильности любой теоремы на основе заданной системы аксиом.
В 1931 году австрийский математик К.Гедель доказал теорему о неполноте, смысл которой состоит в том, что в любой достаточно сложной формальной системе, основанной на аксиомах (например, в арифметике, где введены натуральные числа и операции сложения и умножения), есть утверждение, которое невозможно ни доказать, ни опровергнуть в рамках этой системы. Поэтому было высказано предположение о том, что некоторые задачи алгоритмически неразрешимы, то есть для них в принципе не существует алгоритма решения, и поэтому искать его бессмысленно. Чтобы строго доказать или опровергнуть эту гипотезу, нужно было ввести математическое понятие алгоритма.
|
|
|
Определение алгоритма, которое приведено в начале пункта, часто называют интуитивным, потому что оно содержит такие «нематематические» понятия, как «точный набор», «инструкция», «исполнитель», «решение задачи».
Эти термины невозможно записать строго, используя язык математики и логики, поэтому для математического доказательства такое определение не подходит.
Исследования в этой области, которые начали активно проводиться в 30-х годах XX века, привели к возникновению теории алгоритмов, которая занимается:
• доказательством алгоритмической неразрешимости задач;
• анализом сложности алгоритмов;
• сравнительной оценкой качества алгоритмов.
Значительный вклад в развитие теории алгоритмов внесли математики А.Тьюринг (Великобритания), Э.Пост (США), А.Чёрч (Великобритания), С.Клини (США) и А.А. Марков (СССР).
Понятие алгоритма оказывается «привязанным» к его исполнителю и некоторому языку программирования. Это не позволяет определить алгоритм как математический объект.
Поэтому возникла идея попытаться построить универсального исполнителя.
Универсальный исполнитель — это исполнитель, для которого можно построить алгоритм, эквивалентный любому алгоритму для любого другого исполнителя. Такого исполнителя можно было бы использовать для доказательства разрешимости или неразрешимости задач. Если удается построить алгоритм решения задачи для универсального исполнителя, то задача разрешима. Если доказано, что алгоритма не существует, то задача неразрешима. Система команд такого исполнителя должна быть как можно проще — так его будет легче использовать в доказательствах.
В середине XX века было предложено (разными учеными, независимо друг от друга) несколько исполнителей, претендующих на роль универсальных, причем в теории алгоритмов доказано, что все они эквивалентны друг другу, то есть алгоритм, который можно запрограммировать для одного универсального исполнителя, можно запрограммировать также и для остальных. Более подробно вы познакомитесь с ними в процессе изучения дисциплины «Теория автоматов и теория алгоритмов».
Свойства алгоритма
На основании работ различных авторов можно выделить следующие свойства алгоритмов.
1. Конечность (финитность) алгоритма. Алгоритм должен приводить к решению задачи обязательно за конечное время. Последовательность правил, приведшая к бесконечному циклу, алгоритмом не является.
2. Определенность, или детерминированность, алгоритма. Это свойство означает, что неоднозначность толкования записи алгоритма недопустима.
3. Результативность алгоритма. Под результативностью понимается доступность результата решения задачи для пользователя, иными словами, алгоритм должен обеспечить выдачу результата решения задачи на печать, на экран монитора или в файл.
4. Массовость алгоритма. Это означает, если правильный результат по алгоритму получен для одних исходных данных, то правильный результат по этому же алгоритму должен быть получен и для других исходных данных, допустимых в данной задаче.
5. Дискретность - означает, что алгоритм состоит из последовательности отдельных шагов - элементарных действий, выполнение которых не представляет сложности. Именно благодаря этому свойству алгоритм может быть реализован на ЭВМ.
6. Эффективность алгоритма. Под эффективностью алгоритма понимают такое его свойство (качество), которое позволяет решить задачу за приемлемое для разработчика время. К параметру, характеризующему эффективность алгоритма, следует отнести также объем памяти компьютера, необходимый для решения задачи.
7. Корректность - означает, что если алгоритм создан для решения определенной задачи, то для всех исходных данных он должен всегда давать правильный результат и ни для каких исходных данных не будет получен неправильный результат. Если хотя бы один из полученных результатов противоречит хотя бы одному из ранее установленных и получивших признание фактов, алгоритм нельзя признать корректным.
Дата добавления: 2018-09-22; просмотров: 332; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!