Лекция №1

Основы программирования

1. Программное обеспечение персонального компьютера

Компьютер сам по себе ("Наrdwаrе" — "жесткий товар" — аппаратные средст­ва, аппаратура) без разработанных человеком для него программ ("Softwаrе" — "мягкий товар" — программные средства, программное обеспечение) не может вы­полнить какой-либо работы. Программным обеспечением (ПО) называют органи­зованную совокупность программ постоянного употребления, ориентирующую ЭВМ на тот или иной класс применений.

Различают три основные группы программ для компьютера: системное, при­кладное программное обеспечение и инструментальные средства, обеспечивающие создание новых программ для ЭВМ.

1.1. Системное программное обеспечение

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

1.2. Прикладное программное обеспечение

Прикладное программное обеспечение — программы для решения класса за­дач в определенной области применения систем обработки данных. Примеры при­кладных программ: программа для обработки экспериментальных данных, про­грамма бухгалтерского учета, игровые, обучающие программы и т.п.

1.3. Инструментальные средства

Инструментальные средства (системы программирования) — это пакеты про­грамм для создания или изменения программ для ЭВМ. Современные системы про­граммирования предоставляют программисту мощные и удобные средства для раз­работки программ.

2. Основные этапы решения задач на компьютере

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

Рассмотрим эти этапы на следующем примере: пусть требуется вычислить сум­му двух целых чисел и вывести на экран видеомонитора результат.

Первый этап — постановка задачи. На этом этапе участвует человек, хо­рошо представляющий предметную область задачи. Он должен четко определить цель задачи, дать словесное описание содержания задачи и предложить общий подход к ее решению. Для задачи вычисления суммы двух целых чисел человек, знающий, как складываются числа, может описать задачу следующим образом: ввести два целых числа, сложить их и вывести сумму в качестве результата реше­ния задачи.

Второй этап — математическое или информационное моделирование. Цель этого этапа — создать такую математическую модель решаемой задачи, ко­торая может быть реализована в компьютере. Существует целый ряд задач, где математическая постановка сводится к простому перечислению формул и логи­ческих условий. Этот этап тесно связан с первым этапом, и его можно отдельно не рассматривать, однако возможно, что для полученной модели известны несколько методов решения, и тогда предстоит выбрать лучший. Для вышеописанной задачи данный этап сведется к следующему: введенные в компьютер числа запомним в па­мяти под именами А и В, затем вычислим значение суммы этих чисел по формуле А+В, и результат запомним в памяти под именем Summa.

Третий этап — алгоритмизация задачи. На основе математического описа­ния необходимо разработать алгоритм решения.

Алгоритмом	называется точное предписание, определяющее последователь­ность действий исполнителя, направленных на решение поставленной задачи. В роли исполнителей алгоритмов могут выступать люди, роботы, компьютеры.
Алгоритм	- формальное однозначное описание последовательности действий.
Алгоритм	- точное предписание, определяющее вычислительный процесс, ведущий от варьируемых начальных данных к искомому результату. [ГОСТ 19.004-80].

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

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

Прежде всего, для задания алгоритма необходимо определить объект воздействия (или управления), а также тот набор действий, который позволительно производить с ним. Эти три элемента "алгоритм, набор действий и объект управления" определяют процесс, который происходит при выполнении алгоритма. Но алгоритм представляет всего-навсего описание этого процесса. Чтобы воспроизвести этот процесс, необходимо нечто, понимающее и воспроизводящее алгоритм. Назовем это интерпретатором алгоритма.

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

• -данные - переменные, создаваемые на основе типов данных;

• -выражения, включающие переменные и операции по их обработке;

• -логика алгоритма, составленная из операторов;

• -модули, соответствующие логически завершенным частям алгоритма.

Если отнести последние три компоненты к алгоритмической части программы, то можно дать такое короткое определение: Программа = алгоритм + данные.

Примечание:

Понятие алгоритм является основным для всей области компьютерного программирования, поэтому начнем с анализа этого термина. Слово "алгоритм" (algorithm) (иногда используется устаревшее слово "алгорифм") уже само по себе представляет большой интерес. Этого слова еще не было в издании словаря Webster's New World Dictionary, вышедшем в 1957 году. Мы находим там только устаревшую форму "algorism" — старинное слово, которое означает "выполнение арифметических действий с помощью арабских цифр". В средние века абакисты считали на абаках (счетных досках), а алгоритмики использовали "algorism". В эпоху Возрождения происхождение этого слова оказалось забытым. Одни лингвисты того времени пытались объяснить его значение путем сочетания слов algiros [больной] и arithmos [число], другие не соглашались с таким толкованием и утверждали, что это слово происходит от "King Algor of Castile". Наконец историки математики обнаружили истинное происхождение слова "algorism": оно берёт начало от имени автора знаменитого персидского учебника по математике, Аbu Abd Allah Muhammad ibn Musa al-Khwarizmi (Абу Абд Аллах Мухаммед ибн Муса аль-Хорезми) (ок. 825 г.). Аль-Хорезми написал знаменитую книгу Kitab al-jabr wal-muqabala (Китаб аль-джебр валь-мукабала— "Книга о восстановлении противопоставлении"). От названия этой книги, которая была посвящена решению линейных и квадратных уравнений, произошло еще одно слово - "алгебра".

Постепенно форма и значение слова algorism исказились; как объясняется в словаре Oxford English Dictionary, это слово "претерпело множество псевдоэтимологических искажений, включая последний вариант algorithm, где произошла путаница" с корнем слова греческого происхождения arithmetic. Этот переход от “algorism" к "algorithm" кажется вполне закономерным ввиду того, что происхождение рассматриваемого слова было полностью забыто.

К 1950 году слово "алгоритм" чаще всего ассоциировалось с алгоритмом Евклида, который представляет собой процесс нахождения наибольшего общего делителя двух чисел. Этот алгоритм приведен в книге Евклида (Euclid) Начала (книга 7, предложения 1 и 2).

Алгоритм Евклида. Даны два целых положительных числа т п. Требуется найти их наибольший общий делитель, т. е. наибольшее целое положительное число, которое нацело делит оба числа m и n.

1. [Нахождение остатка.] Разделим m на n, и пусть остаток от деления будет равен r (где 0 ≤ r ≤ n).

2. [Сравнение с нулем.] Если r = 0, то выполнение алгоритма прекращается; n — искомое значение.

3. [Замещение.] Присвоить m ← n, n ←r и вернуться к шагу 1.

Р ис. 1. Блок-схема алгоритма Е.

Примечание:

Для удобства программной реализации алгоритма Евклида приведенный алгоритм имеет смысл переписать следующим образом.

0. [Сравнение m и n.] Если n > m, то поменять значения m и n местами.

1. [Нахождение остатка.] Разделим m на n, и пусть остаток от деления будет равен r (где 0 ≤ r ≤ n).

3. [Замещение.] Присвоить m ← n, n ←r.

2. [Сравнение с нулем.] Если r = 0, то выполнение алгоритма прекращается; m — искомое значение, иначе вернуться к шагу 1.

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

Однозначность (определенность) алгоритма, под которой понима­ется единственность толкования исполнителем правил выполнения действий и порядка их выполнения. Чтобы алгоритм обладал этим свойством, он должен быть за­писан командами из системы команд исполнителя. Данное свойство означает, что все операции в алгоритме должны быть однозначными, не допуская произвольного толкования. Вследствие этого их выполнение осуществляется механически, и никаких дополнительных указаний не требуется.

Для нашего примера исполнитель должен понимать такую запись действий, как сложить числа А и В.

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

Конечность алгоритма — обязательность завершения каждого из действий, составляющих алгоритм, и завершимость выполнения алгоритма в целом. Записан­ный алгоритм обладает этим свойством, так как запись действий испол­нителя завершается записью об окончании алгоритма.

Алгоритм Евклида удовлетворяет этому условию, потому что после шага 1 значение r меньше, чем п. Поэтому если r≠0, то в следующем цикле на шаге 1 значение n уменьшается. Убывающая последовательность положительных целых чисел имеет конечное число членов, поэтому шаг 1 может выполняться только конечное число раз для любого первоначально заданного значения n. Но имейте в виду, что количество шагов может быть сколь угодно большим; выбор слишком больших значений т и п приведет к тому, что шаг 1 будет выполняться более миллиона раз.

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

Процедура, обладающая всеми характеристиками алгоритма, за исключением, возможно, конечности, называется методом вычислений. Евклид (Euclid) предложил не только алгоритм нахождения наибольшего общего делителя, но и аналогичное ему геометрическое построение "наибольшей общей меры" длин двух отрезков прямой; это уже метод вычислений, выполнение которого не заканчивается, если заданные длины оказываются несоизмеримыми.

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

Массовость, т. е. возможность применения данного алгоритма для решения целого класса задач, отвечающих общей постановке задачи. Так как рассматриваемый алгоритм позволяет правильно подсчитать сумму не только чисел 2 и 3, но любой другой пары целых чисел, он обладает свойством массовости. Для того чтобы алгоритм обладал свойством массовости, следует составлять алгоритм, ис­пользуя обозначения величин (переменные) и избегая конкретных значений. Данное свойство означает, что разрабатываемый алгоритм должен иметь общий вид. Иначе говоря, нужно, чтобы алгоритм можно было применять для любых задач какого-то определенного класса, различающихся только исходными данными. Причем исходные данные можно выбирать из так называемой области применимости алгоритма.

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

(Можно легко доказать, что число r в реализации алгоритма Евклида действительно является наибольшим общим делителем. После шага 1 имеем

m = qn + r,

где q — некоторое целое число. Если r = 0, то m кратно n и, очевидно, в этом случае n — наибольший общий делитель тип. Если r≠0, то любой делитель обоих чисел m и n должен быть также делителем m — qn = r и любой делитель n и r — также делителем qn+r=m. Таким образом, множество делителей чисел {m,n} совпадает с множеством делителей чисел {n,r}. Следовательно, пары чисел {m, n} и {n,r} имеют один и тот же наибольший общий делитель. Таким образом, шаг 3 не изменяет ответа исходной задачи.)

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

Ввод. Алгоритм имеет некоторое (возможно, равное нулю) число входных данных, т. е. величин, которые задаются до начала его работы или определяются динамически во время его работы. Эти входные данные берутся из определенного набора объектов. Например, в алгоритме Евклида есть два входных значения, а именно — т и п, которые принадлежат множеству целых положительных чисел.

Вывод. У алгоритма есть одно или несколько выходных данных, т. е. величин, имеющих вполне определенную связь с входными данными. У алгоритма Евклида имеется только одно выходное значение, а именно — n, получаемое на шаге 2. Это наибольший общий делитель двух входных значений.

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

Разработанный алгоритм можно описать или реализовать следующими способами:

• На естественном языке.

• В виде блок-схемы.

• На алгоритмическом языке.

На практике используются различные способы записи алгорит­мов. Широко распространен словесный способ записи: это записи рецептов приготовления различных блюд в кулинарной книге, инструкции по использованию тех­нических устройств, правила правописания и многие другие. Наглядно представляется алгоритм языком блок-схем.