Модели решения функциональных и вычислительных задач

Элементы технологии обработки информации с помощью ЭВМ.

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

1. Вычислительные задачи, связанные с обработкой числовой информации.

2. Задачи по обработке символьной информации, связанные с созданием и редактированием текстов.

3. Задачи по обработке графической информации, т.е. схем, чертежей, графиков и т.д.

Процесс решения задач с использованием компьютера условно можно разбить на ряд этапов:

1. Постановка задачи (описание результатов и необходимых исходных данных).

2. Построение модели (описание соотношений между исходными данными и результатами).

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

4. Реализация метода на компьютере (представление найденной последовательности операций в специальном виде и их выполнение).

5. Анализ полученных результатов (сравнение полученных результатов с предполагаемыми и, в случае расхождений, установление их причин).

В разных задачах трудоемкость отдельных этапов может быть различной. Примеры.

- вычислительная задача;

- обработка текста;

- обработка графической информации, схемы, графики, чертежи, графич. редакторы.

а), б) вне этого курса.

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

Основные характеристики алгоритма.

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

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

Результативность (конечность) алгоритма предполагает, что исполнение сводится к выполнению конечного числа действий и всегда приводит к некоторому результату.

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

Формы представления алгоритмов:

- словесное описание (вербальная форма);

- построчная запись;

- блок-схема;

- запись на каком-л. языке программирования.

Рассмотрим особенности каждой формы на примере алгоритма Евклида (НОД).

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

Например, если числа равны, НОД равен одному из них. В противном случае надо из большего вычесть меньшее, полученную разность запомнить вместо значения большего числа и повторить все сначала.

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

1. Шаги (предписания) алгоритма нумеруются.

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

3. Типичными шагами алгоритма являются:

- чтение (ввод) данных;

- обработка данных (вычисления) по формулам;

- сообщение (вывод) результата;

- проверка условия;

- переход к шагу с номером N;

- конец вычислений.

[1] чтение a, b

[2] если a=b, идти на [8]

[3] если a>b, идти на [6]

[4] b=b-a

[5] идти на [2]

[6] a=a-b

[7] идти на [2]

[8] НОД = a

[9] запись НОД

[10] останов

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

Блок-схемы...

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

Основные типы алгоритмических структур. Их всего три: линейная, разветвляющаяся и циклическая.

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

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

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

Языки программирования являются одним из средств общения пользователя с компьютером. Все они (а их насчитывается более 1000) имеют сходство с естественным языком, а именно: так же, как и естественные языки базируются на некотором множестве допустимых символов (алфавите), из которых согласно синтаксическим правилам формируются слова (лексические единицы) и предложения языка (операторы). Совокупность операторов (команд), описывающих алгоритм решения задачи, называется программой. И все же языки программирования могут использоваться только для общения человека с компьютером, а не человека с человеком, так как они имеют чрезвычайно скудный запас слов. Обычно словарь языка программирования насчитывает не более 500 слов (число допустимых в нем слов). Синтаксические правила языка программирования допускают лишь однозначный способ построения предложений (операторов). Эти ограничения на язык налагает специальная программа, называемая транслятором, которая служит переводчиком с языка программирования на язык машинных команд.

Язык и транслятор с этого языка называют системой. Различают два типа систем: компилирующие и интерпретирующие.

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

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

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

Инструментальные языки и системы программирования - это особая категория программных средств. С их помощью создаются все другие программы. К категории инструментальных средств относятся не только трансляторы с языков высокого уровня, таких как Basic, Pascal или Fortran, но и ассемблеры, загрузчики, отладчики, другие системные программы. С помощью инструментальных средств создается и прикладное ПО, и новые средства системного программирования, включая трансляторы с языков высокого уровня. Следовательно, эта категория ПС совершенно аналогична средствам производства в промышленности - таким как станки, инструменты, средства переработки сырья в нужную форму. При этом роль сырья играет информация - текстовые и числовые данные, закодированные сообщения, графические изображения.

Критерии выбора языка программирования:

- назначение разрабатываемой программы - нужна ли она временно или будет использоваться постоянно, планируется ее передача другим организациям;

- требуемая скорость работы программы, соотношение ее диалоговых и вычислительных компонентов;

- ожидаемый размер программы;

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

- характер и уровень использования аппаратных средств;

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