Алгоритм. Основные свойства. Способы представления алгоритмов

Понятие алгоритма - одно из основных понятий математики и вычислитель­ной техники.

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

Алгоритм обладает тремя основными свойствами: детерминированности, массовости и результативности.

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

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

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

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

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

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

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

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

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

Программное обеспечение компьютера. Основные понятия.

Программное обеспечение (ПО, software) компьютера - это совокупность взаимодействующих друг с другом программ, их описаний и руководств, пред­назначенных для эффективного использования вычислительных систем (ВС).

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

Для подключения подпро­грамм из библиотек были разработаны программы-компоновщики (редакторы связей). Они "собирали" программу из частей в единое целое.

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

Вначале появились машинно-ориентированные языки: ассемблер, автокоды. Затем процедурно-ориентиро­ванные (Фортран, Алгол, ПЛ-1, Паскаль и др.).

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

Типы программного обеспечения. Системы программирования. Качество программ.

Программы можно разделить на 3 типа: прикладные программы, системные программы, инструментальные системы.

Прикладные программы обеспечивают выполнение работ, необходимых поль­зователю: редактирование текстов, рисование картинок, обработку массивов данных и т. д. Это могут быть: редакторы текстов, графические редакторы, изда­тельские системы, системы деловой и научной графики, системы автоматизиро­ванного проектирования (САПР), бухгалтерские системы и пр.

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

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

Существующие системы программирования делятся на компилирующие и интерпретирующие в соответствии с типом их трансляторов.

Трансляторы - это программы, которые переводят текст, с языка программирования на ма­шинный. Они могут быть двух типов: компиляторы и интерпретаторы.

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

Интерпретаторы - это трансляторы, в которых текст транслиру­ется и выполняется пооператорно, т. е. трансляция и выполнение операторов программы совмещены во времени. Примеры компиляторов - это компиляторы с языков Паскаль и Си. Пример интерпретатора - интерпретатор команд ОС.

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

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

Основные характеристики качества программ: правильность (соответствие техническому заданию), минимальные запросы к ресурсам ВС (оперативной памяти (ОП), времени счета), структурированность, модульность, надежность, легкость освоения, простота и удобство использования, адаптируемость на но­вые области применения, экономическая эффективность (минимальная стои­мость разработки, освоения и сопровождения).

Периодичность использования программ может быть от многократного ис­пользования в течение дня (например, транслятора) до нескольких раз в год (например, квартальные экономические отчеты), в зависимости от области их применения.

Языки программирования.

Алгоритмический язык - это набор символов, являющихся алфавитом язы­ка, система правил связи символов для образования "слов" и "предложений" (синтаксис языка), с помощью которых представляются компоненты языка, и система правил их истолкования (семантика).

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

Наиболее общей классификацией языков программирования является клас­сификация по степени зависимости от машинного языка.

Машинный язык - это система команд компьютера.

Машинно-ориентированные языки - это мнемокоды, автокоды, языки ас­семблера. В них коды операции и адреса операндов представляются идентифи­каторами и числами.

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

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

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

Перспектива разви­тия прикладного ПО, использующего проблемно-ориентированные языки, на­правлена на разработку программных систем для использования их непро­граммистами.

Процедурно-ориентированные языки - это машинно-независимые языки для описания алгоритмов решения задачи. С их помощью описывается процесс об­работки данных в терминах языка. Тексты на этих языках определяют как реализуется алгоритм обработки данных в виде процедур обработки данных. Примеры процедурно-ориентированных языков: Фортран, Алгол-60, ПЛ-1, Ко­бол, Паскаль, Си. Их достоинства: высокая производительность и возможность переноса программы с одного компьютера на дру­гой (в случае наличия транслятора с этого языка). Недостаток - сложность языков.

Фортран (FORmula TRANslation language) - это первый язык программирова­ния высокого уровня с элементами машинно-ориентированного языка. Разра­ботан сотрудниками фирмы IBM в 1954 г. В 1957 г. разработан первый транс­лятор с Фортрана. Фортран имеет обширную библиотеку научных подпро­грамм. Язык предназначен для решения численных задач.

Алгол-60 создан в 1960 г. Он также предназначен для решения численных задач. В середине 60-х гг. фирмой IBM разработан универсальный язык ПЛ-1.

Лекция №2