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

Теория формальных структур данных и алгоритмов их обработки

ЧАСТЬ 2. Математические основы информатики

Системы программирования

Инструментальные языки и системы программирования

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

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

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

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

Системы программирования на основе языков высокого уровня, как правило, включают следующие компоненты:

· текстовый редактор;

· транслятор языка;

· средства редактирования, компоновки и загрузки программы;

· макроассемблер;

· отладчик машинных программ.

Примеры систем программирования: Visual Basic, С++Builder, Delphi.

Во второй части настоящего учебного пособия вы подробно познакомитесь особенностями работы в системе программирования Delphi, созданной на основе алгоритмического языка Object Pascal.

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

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

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

Там, где речь идет об алгоритме решения задачи, мы имеем дело с данными, так как они являются объектами, к которым применяется этот алгоритм.

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

В зависимости от характера решаемой задачи используются данные различного типа (например, текстовые, числовые, логические). Используется более конкретное понятие: данные ЭВМ (машинные данные) – информация, представленная в виде, однозначно воспринимаемом ЭВМ и ее устройствами. Поэтому предполагается, что данные обычно записаны на определенных носителях и передаются в виде сигналов.

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

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

Рассмотрим основные свойства алгоритма.

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

2. Детерминированность (определенность). Каждый шаг алгоритма должен быть однозначно понимаем.

3. Результативность (конечность). Алгоритм должен приводить к решению задачи за конечное число шагов.

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

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

Сущность алгоритмизации в следующем:

· выделении автономных этапов (шагов) вычислительных процессов;

· формальной записи содержания каждого из них;

· назначении порядка выполнения выделенных автономных этапов вычислительного процесса;

· проверке правильности выбранного алгоритма по реализации заданного метода вычислений.

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

Вычислительная схема – некоторая последовательность операций и форма записи результатов этих операций.

Чтобы подготовить какой-либо алгоритм для решения задачи на ЭВМ. необходимо его записать по определенным правилам в формализованном виде на конкретном алгоритмическом языке.

Задачи на ЭВМ решаются по заранее составленной программе. В соответствии с ГОСТ 19781-83 программа – это данные, предназначенные для управления конкретными компонентами системы обработки данных в целях реализации определенного алгоритма.

В более простом виде программой называют алгоритм, записанный на каком-либо алгоритмическом языке. Если говорить о программе для ЭВМ, то такая запись представляет собой наряду с описаниями типов и структуры данных задаваемые для ЭВМ инструкции: в какой последовательности, над какими данными и какие операции должна выполнять машина и в какой форме выдавать результат. Задание для ЭВМ таких инструкций обеспечивают операторы.

Оператор – это совокупность символов, указывающих операцию и значения или местонахождение ее операндов (данных, к которым применяется эта операция).

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