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

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

2. Используемые на практике алгоритмы составляются с ориентацией на опреде­ленного исполнителя. Чтобы составить для него алгоритм, нужно знать, какие команды этот исполнитель может понять и исполнить, а какие - не может. Мы знаем, что у каждого исполнителя имеется своя система команд. Очевидно, составляя запись алгоритма для определенного исполнителя, можно использовать лишь те команды, которые имеются в его СКИ. Это свойство алгоритмов будем называть понятностью.

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

Отмеченное свойства алгоритмов называют определенностью или детерминиро­ванностью.

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

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

6. Эффективность – для успешного решения задачи должны использоваться ограниченные ресурсы конкретного компьютера (время работы процессора, объем ОП, быстродействие ЖД)

Тема 5. Языки программирования: эволюция, классификация. Система программирования.

Одной из самых революционных идей, приведших к созданию автоматических цифровых вычислительных машин, была высказанная в 20-х годах XIX века Ч.Бэббиджем мысль о предварительной записи порядка действий машины для последующей автоматической реализации вычислений - программе. И, хотя исполь­зованная Бэббиджем запись программы на перфокартах, придуманная для управления ткацкими станками французским изобретателем Жозефом Мари Жаккаром, технически не имеет ничего общего с современными приемами хранения программ в ЭВМ, принцип здесь по существу один. С этого момента начинается история программирования.

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

Революционным моментом в истории языков программирования стало появле­ние системы кодирования машинных команд с помощью специальных символов, предложенной Джоном Моучли, сотрудником Пенсильванского университета. Система кодирования, предложенная Моучли, увлекла одну из сотрудниц его компании - Грейс Мюррей Хоппер, которая посвятила всю свою жизнь компью­терам и программированию. Она вспоминает, что стала «третьим в мире про­граммистом первого в мире большого цифрового компьютера». Г.Хоппер дока­зала, чего она стоит как программист. Впоследствии она писала: «Я имелатопреимущество, что изучала как технику, так и математику и знала, как работает машина от начала и до конца».

При работе на компьютере «Марк-1» Г.Хоппер и ее группе пришлось столкнуть­ся со многими проблемами и все, что ими придумано, было впервые. В частности, они придумали подпрограммы. Сейчас любой программист не задумываясь использует аппарат подпрограмм в любом языке программирования. И еще одно фундаментальное понятие техники программирования впервые ввели Г.Хоппер и ее группа - «отладка». Однажды жарким летним днем 1945 г. неожиданно произошла остановка компьютера «Марк-1». Обнаружилась неисправность одного реле, контакты которого были заблокированы мотыльком, залетевшим неизвестно каким образом в помещение вычислительного центра. Вспоминает Г.Хоппер: «Когда к нам зашел офицер, чтобы узнать, чем мы занимаемся, мы ответили, что очищаем компьютер от насекомых (debuging)». С тех пор термин «debuging» (отладка) используется в технических процессах тестирования неисправностей в компьютере, а также в системах программирования.

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

В конце 40-х годов, до прихода Г.Хоппер в фирму Джона Моучли, последний создал систему под названием «short code», которая являлась примитивным языком программирования высокого уровня. В ней программист записывал решаемую задачу в виде математических формул, а затем, используя специальную таблицу, переводил символ за символом, преобразовывал эти формулы в двухлитерные коды. В дальнейшем специальная программа компьютера превращала эти коды в двоичный машинный код. Система, разработанная Дж. Моучли, была по существу одним из первых примитивных интерпретаторов.

Уже в 1951 г. Хоппер создала первый в мире компилятор и ею же был введен сам этот термин. Компилятор Хоппер осуществлял функцию объединения команд и в ходе трансляции производил организацию подпрограмм, выделение памяти компьютера, преобразование команд высокого уровня (в то время псевдокодов) в машинные команды. «Подпрограммы находятся в библиотеке (компьютера), а когда вы подбираете материал из библиотеки - это называется компиляцией» - так она объясняла происхождение введенного ею термина.

В 1954 г. группа под руководством Г.Хоппер разработала систему, включающую язык программирования и компилятор, которая в дальнейшем получила название МАТН-МАТ1С. После удачного завершения работ по созданию МАТН-МАТ1С- Хоппер и ее группа принялись за разработку нового языка и компилятора, который позволил бы пользователям программировать на языке, близком к обычному английскому. Необходимость появления подобной системы Хоппер объясняла следующим образом: «Существует много различных людей, которым нужно решать разные задачи. Некоторые из них связаны с обработкой символов, другие - с обработкой слов, и им нужны языки другого типа, а не наши попытки превратить их всех в математиков». В 1958 г. появился компилятор FLOW-МАТ1С.

Дата добавления: 2014-01-06