Экономическая информатика

1. Понятие и свойства алгоритма

1. История возникновения алгоритма

Современное формальное определение  алгоритма было дано в 30—50-х годы XX века в работах Тьюринга, Поста, Чёрча (тезис Чёрча — Тьюринга), Н. Винера А.А. Маркова. Само слово «алгоритм» происходит от имени учёного Абу Абдуллах Мухаммеда ибн Муса аль-Хорезми. Около 825 года он написал сочинение, в котором впервые дал описание придуманной в Индии позиционной десятичной системы счисления. К сожалению, арабский оригинал книги не сохранился. Аль-Хорезми сформулировал правила вычислений в новой системе и, вероятно, впервые использовал цифру 0 для обозначения пропущенной позиции в записи числа (её индийское название арабы перевели как as-sifr или просто sifr, отсюда такие слова, как «цифра» и «шифр»). Приблизительно в это же время индийские цифры начали применять и другие арабские учёные. В первой половине XII века книга аль-Хорезми в латинском переводе проникла в Европу. Переводчик, имя которого до нас не дошло, дал ей название Algoritmi de numero Indorum («Алгоритми о счёте индийском»). По-арабски же книга именовалась Китаб аль-джебр валь-мукабала («Книга о сложении и вычитании»). Из оригинального названия книги происходит слово Алгебра.

Таким образом, мы видим, что латинизированное имя среднеазиатского ученого было вынесено в заглавие книги, и сегодня ни у кого нет сомнений, что слово «алгоритм» попало в европейские языки именно благодаря этому сочинению. Однако вопрос о его смысле длительное время вызывал ожесточённые споры. На протяжении многих веков происхождению слова давались самые разные объяснения. Упомянутый выше перевод сочинения аль-Хорезми стал первой ласточкой, и в течение нескольких следующих столетий появилось множество других трудов, посвящённых всё тому же вопросу — обучению искусству счёта с помощью цифр. И все они в названии имели слово algoritmi. [1]

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

Алгоритм – это понятное и точное предписание исполнителю выполнить конечную последовательность команд, приводящих от искомых данных к искомому результату. В этом определении содержатся основные понятия, связанные с алгоритмом и его главные свойства. Взаимосвязь понятий отражена на рис 1.[9]

Исполнитель алгоритма  – это тот объект (или субъект), для управления которым составлен алгоритм (человек, машина, компьютер и т.д.). Центральным объектом в этой системе является ИСПОЛНИТЕЛЬ алгоритмов.[7]

Рис. 1. Схема функционирования исполнителя  алгоритмов

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

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

 однозначностью (детерминированностью) - любое действие алгоритма должно  быть строго и недвусмысленно  определено в каждом случае;

 дискретностью – разбиение  алгоритма на ряд отдельных  законченных действий (шагов);

 конечностью - каждое действие  в отдельности и алгоритм в  целом должны иметь возможность завершения;

 массовостью - возможность применения  данного алгоритма для решения целого класса задач с разными исходными данными;

 результативностью - алгоритм должен приводить к правильному результату для всех допустимых входных значениях.

Основной характеристикой исполнителя, с точки зрения управления, является система команд исполнителя (СКИ). Это конечное множество команд, которые понимает исполнитель, т.е. умеет их выполнять.

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

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

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

Еще одно свойство, которое отражено в определении алгоритма —  конечность. Оно формулируется так: исполнение алгоритма и, следовательно, получение искомого результата должно завершиться за конечное число шагов. Здесь под шагом подразумевается выполнение отдельной команды. Это свойство является предупреждением ситуации, которую программисты называют зацикливанием. Бесконечно исполняемый алгоритм безрезультатен. Поэтому свойство конечности называют еще результативностью алгоритма.

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

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

Другими словами, это можно назвать универсальностью алгоритма по отношению к исходным данным решаемой задачи. Заметим, что данное свойство не является необходимым свойством алгоритма, а скорее определяет качество алгоритма: универсальный алгоритм лучше неуниверсального (алгоритм решения частной задачи — тоже алгоритм!)[6]

2. Языки и системы программирования

1. Понятие о языке программирования

Программирование в машинном коде — трудоемкий процесс, в ходе которого трудно избежать ошибок. Упростить этот процесс можно, если автоматизировать работу, поручив часть ее самому компьютеру. Прогресс компьютерных технологий определил процесс появления новых разнообразных знаковых систем для записи алгоритмов – языков программирования. 
Сегодня для записи программ используют языки программирования. Язык программирования — это формальный язык для записи алгоритмов в виде, допускающем их автоматическую подготовку к выполнению на компьютере. Для преобразования программы в машинный код служит специальное программное средство — транслятор.

Язык программирования содержит три основных компонента: алфавит, синтаксис и семантику. Эти компоненты определяют правила  записи программ. Алфавит языка — это набор символов, которые можно применять в инструкциях языка программирования. Другие символы допустимы только в особых случаях, например в строковых константах.

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

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

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

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

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

Язык программирования служит двум связанным между собой  целям: он дает программисту аппарат  для задания действий, которые  должны быть выполнены, и формирует концепции, которыми пользуется программист.

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

2. История возникновения языков  программирования

На заре компьютеризации (в начале 1950-х г.г.), машинный язык был единственным языком, большего человек к тому времени не придумал. Для спасения программистов от сурового машинного языка программирования, были созданы языки высокого уровня (т.е. немашинные языки), которые стали своеобразным связующим мостом между человеком и машинным языком компьютера. Языки высокого уровня работают через трансляционные программы, которые вводят "исходный код" (гибрид английских слов и математических выражений, который считывает машина), и в конечном итоге заставляет компьютер выполнять соответствующие команды на машинном языке. Каждый процессор имеет свою систему команд. Компьютер способен выполнять только последовательности команд, понятных процессору, — машинный код. Первоначально программы для компьютеров и писались с использованием машинного кода.

Один из самых  старых языков программирования Фортран был создан в 50-х гг. нашего века. Фортран и подобные ему языки программирования (Алгол, ПЛ/1) предназначались для решения вычислительных задач, возникающих в математике, физике, инженерных расчетах, экономике и т.п. Эти языки в основном работают с числами. Фортран был задуман для использования в сфере научных и инженерно-технических вычислений. Однако на этом языке легко описываются задачи с разветвленной логикой (моделирование производственных процессов, решение игровых ситуаций и т.д.), некоторые экономические задачи и особенно задачи редактирования (составление таблиц, сводок, ведомостей и т.д.). Одним из первых и наиболее удачных компиляторов стал язык Фортран, разработанный фирмой IBM. Профессор Дж. Букс и группа американских специалистов в области программирования в 1954 году опубликовало первое сообщение о языке. Дословно, название языка Formulae Translation –преобразование формул.

Язык Бейсик (BASIC — Beginners All-purpose Symbolic Instruction Code — универсальный символьный код для начинающих) был создан в 1965 г. Дж. Кемени и Т. Курцем как язык, облегчающий написание простых программ.

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

В своем первоначальном виде Паскаль имел довольно ограниченные возможности, но расширенный вариант этого языка — Turbo Pascal, является очень мощным языком программирования.

Язык Си разработан Деннисом Ритчи в 1972 г. как язык, пригодный для программирования новой операционной системы UNIX. Си не очень прост в изучении и требует тщательности в программировании, но позволяет создавать сложные и весьма эффективные программы.

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

3. Классификация языков программирования

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

Набор команд процессора содержит:

арифметико-логические команды - команды арифметических действий над двоичными числами и логических действий над двоичными векторами;

команды управления - команды перехода, ветвлений, повторений, и некоторые другие команды;

команды пересылки данных - команды, с помощью которых обмениваются данными ОЗУ и ЦП;

команды ввода-вывода данных - команды, с помощью которых  обмениваются данными ЦП и внешние устройства.

Каждая команда  содержит код операции, ею выполняемой и информацию об адресах данных, над которыми эта операция выполняется. Кроме этого, команда (непосредственно - команды управления и косвенно - другие команды) содержит информацию об адресе команды, которая будет выполняться следующей. Таким образом, любая последовательность команд, размещенная в ОЗУ, фактически представляет из себя алгоритм, записанный в системе команд процессора - машинную программу. Каждый процессор имеет свою систему команд. Компьютер способен выполнять только последовательности команд, понятных процессору, — машинный код. Первоначально программы для компьютеров и писались с использованием машинного кода.

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

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