Основы программирования
Понятие алгоритма и исполнителя. Виды и свойства алгоритма.
Этапы решения задачи с использованием компьютера.
Парадигмы программирования. Операциональное программирование.
Структурное и модульное программирование.
Объектно-ориентированное программирование.
Термин алгоритм происходит от имени средневекового узбекского математика Аль-Хорезми, который еще в 825 году описал правила выполнения четырех арифметических действий в десятичной системе счисления. Процесс их выполнения и был назван алгоризмом.
Далее алгорисмус – смысл: комбинирование четырех операций арифметического исчисления: сложения, вычистания, умножения и деления.
Затем алгорифм. Связывают с алгорифмами Евклида – описаниями процессов нахождения наибольшего общего делителя двух натуральных чисел, наибольшей общей меры двух отрезков и т.п.
Под алгоритмом же понимали конечную последовательность точно сформулированных правил, которые позовляют решать различные классы задач. Такое определение алгоритма не является строго математическим, так как в нем не содержится точной характеристики того, что следует понимать по классами задач и под правилами их решения.
Так, можно нестрого определить алгоритм как однозначно трактуемую процедуру решения задачи.
Алгоритм – это система однозначных инструкций (указаний), которая определяет последовательность действий над выбранными объектами с целью получения результата за конечное число шагов.
Дополнительные требования о выполнении алгоритма за конечное время для любых входных данных приводит к еще одному неформальному определению алгоритма.
Алгоритм – это заданное на некотором языке конечное предписание, задающее конечную последовательность выполнимых и точно определенных элементарных операций для решения задачи.
Наиболее удачными определениями алгоритма является определения, принадлежащие российским ученым Колмогорову Андрею Николаевичу и Маркову Андрею Андреевичу.
Алгоритм (по Колмогорову) – это система вычислений, выполняемых по строго определенным правилам, которая после какого-либо числа шагов заведомо приводит к решению поставленной задачи.
Алгоритм (по Маркову) – это точное предписание, определяющее вычислительный процесс, идущий от варьируемых исходных данных к искомому результату.
Алгоритмы, в соответствии с которыми решение поставленных задач сводится к арифметическим действиям, называются численными алгоритмами.
Алгоритмы, в соответствии с которыми решение поставленных задач сводится к логическим действиям, называются логическими алгоритмами.
Исполнитель алгоритма – это реальная или виртуальная (техническая, биологическая, биотехническая) система, способная выполнить действия, предписываемые алгоритмом.
Исполнителя характеризует:
1. среда обитания
2. система команд
3. элементарные действия
4. отказы
Свойства алгоритма:
дискретность
определенность (точность)
понятность
результативность (конечность)
массовость (но это уже больше качество алгоритма, нежели свойство)
Формы записи алгоритмов:
Псевдокод – удобный промежуточный язык. Симбиоз естественного языка и языка программирования.
В зависимости от степени детализации предписаний обычно определяется уровень языка программирования – чем язык менее детален, тем выше его уровень. Тогда можно выделить:
- машинно-ориентированные языки – машинные языки и языки ассемблера
- машинно-независимые языки – языки высокого уровня.
Процедурные или алгоритмические языки (Basic, Pascal, С) предназначены для однозначного описания алгоритмов в виде некоторой последовательности операторов языка.
Логические языки (Prolog, Lisp) ориентированы не на разработку решения задачи, а на систематическое и формализованное описание задачи, из которого должно следовать решение.
Объектно-ориентированные языки (Borland Pascal, C++, Java, C#), в основе которых лежит понятие объекта, сочетают в себе данные и действия над ними. Программа на ООЯП, решая некоторую задачу, по сути, описывает часть мира, относящуюся к этой задаче.
К базовым алгоритмическим конструкциям относятся: линейная, разветвляющаяся, циклическая.
Линейный алгоритм – это алгоритм, в котором действия осуществляются последовательно друг за другом.
Разветвляющийся алгоритм – это алгоритм, в котором действия выполняются по одной из возможных ветвей решения задачи в зависимости от выполнения условий.
Циклический алгоритм – это алгоритм, в котором некоторая часть команд (тело цикла) выполняется многократно.
2. Этапы решения задач с использованием компьютера.
Работа по решению любой задачи с сипользованием ЭВМ делися на следующие этапы:
Постановка задачи
Формализация задачи
Построение алгоритма
Составление программы на языке программирования
Отладка и тестирование программы
Проведение расчетов и анализ полученных результатов
Часто эту последовательность называют технологической цепочкой решения задачи на ЭВМ.
3. Парадигмы программирования.
За те пятьдесят с небольшим лет, которые существует дисциплина: "программирование", - сменилось несколько поколений правил, концепций, моды, взглядов на то, как надо "писать программы". Все эти правила, концепции, взгляды, мода, наконец, позже назвали в информатике "парадигмами программирования". Вот неполный список парадигм, вместе с датами их появления:
1957г., процедурная парадигма, язык ФОРТРАН, создатель Бэкус;
1967г., функциональная парадигма, язык ЛИСП, создатель Маккарти;
1970г., структурированная парадигма, язык ПАСКАЛЬ, создатель Вирт;
1974г., логическая парадигма, язык ПРОЛОГ;
1983г., объектно-ориентированная парадигма, пример - язык C++, создатель Страуструп.
В конце списка представлены языки программирования и их создатели, внесшие значительный вклад в популяризацию этих парадигм.
В процессе своего развития эти парадигмы "мутировали", "отпочковывались", "объединялись" (так, язык Си объединил в себе процедурную и структурированную парадигму). В результате этих "мутаций" по состоянию на 01.06.2008 года оформились следующие парадигмы программирования:
Процедурная (или модульная) парадигма;
Логическая парадигма;
Объектно-ориентированная парадигма.
Эти три совершенно разные по подходу парадигмы составляют основу современного программирования. Хотя в настоящее время наиболее "модной" является объектно-ориентированная парадигма, остальные парадигмы также используются на практике и изучаются в ВУЗах. Их мы и рассмотрим ниже.
Кроме деления языков программирования по парадигмам, существует также деление языков на "императивные" и "декларативные".
Императивными называются такие языки программирования, в которых описываются в основном "инструкции" по пошаговому выполнению алгоритмов. Все внимание в них отводится лишь реализации этой последовательности действий, а данным и их структуре отводится второстепенная роль. Примером такого рода языков может служить языки создания драйверов устройств: Assembler и C++. При использовании этих языков мы не знаем, какие данные будет отправлять/получать устройство, но зато мы знаем, какие действия нужно осуществить над данными.
Декларативными называются языки программирования, в которых алгоритм работы с данными "зашит" в языке программирования, а сама программа представляет собой данные, упорядоченные и структурированные таким образом, что их легко обрабатывают "стандартные" алгоритмы вывода. В декларативных языках как бы "нет разницы" между данными и алгоритмом, их обрабатывающим. От "значения" данных, подаваемых на вход программы, зависит дальнейшее направление расчетов. Примерами декларативных языков могут служить языки: LISP и Prolog. И программа, и данные на языке ЛИСП представляют собой "списки" вместе с функциями, выполняемыми над ними. На языке ПРОЛОГ есть условное разделение программы на данные ("факты") и код ("правила", "продукции"). Но это разделение достаточно условно: и факты, и правила имеют одну и ту же форму записи.
Декларативные языки лучше всего использовать в случаях, когда "данные управляют программой": при написании экспертных систем, при конструировании трансляторов с языков программирования, для большинства задач искусственного интеллекта. Именно там их использование приведет к наибольшей эффективности.
Операциональный Подход
Если программа составлена из команд, непосредственно исполняющихся компьютером; простейших арифметических операции операций сравнения чисел; операторов безусловного и условных переходов; операторов вызова подпрограмм, то такой подход в программировании, направленный на исполнение конкретных операций называют операциональным.
Операция присваивания состоит в том, что некоторое значение фигурирующей в программе величины помещается в ячейку памяти компьютера. После этого указанное значение сохраняется до тех пор, пока не будет заменено другим в результате другого присваивания. Ячейка памяти, где размещается значение, в программе обозначается идентификатором соответствующей переменной.
Операции сравнения числовых значений сводится к определению знака разности этих значений. Этот знак отображается с помощью специальной ячейки памяти вычислительного устройства компьютера и может использоваться при выполнении условных переходов между командами алгоритма.
Безусловным называется переход, для которого изменение порядка выполнения команд определено раз и навсегда и не зависит ни от каких условий. Условным называется переход, для которого порядок выполнения команд определяется по некоторому условию, чаще всего условию сравнения числовых величин.
Операция вызова подпрограмм – это такой переход в последовательности команд алгоритма, при котором на определенном этапе алгоритма происходит вначале переход на другую программу, а затем после ее завершения возврат в точку вызова подпрограммы и продолжения выполнения команд, начиная со следующей за вызовом подпрограммы.
Операционный подход в программировании имеет недостатки:
запутанная структура программы;
непонятности, сложность в модификации, трудоемкость и высокая стоимость.