Лекции. Основные понятия и определения

• Название: Основные понятия и определения
• Дата: 27.03.2018
• Размер: 1.94 Mb.
• Имя файла: Лекции.docx
• Тип: Контрольные вопросы; #39570
• страница: 3 из 58

1.2. АЛГОРИТМЫ

Алгоритм – это последовательность действий, которая на основании известных данных однозначно приводит к заданному результату. Свойства алгоритма:

- дискретность – последовательность выполнения отдельных шагов,

- массовость – применимость к целому классу задач,

- определенность – однозначное толкование каждого шага,

- результативность – приведение к результату за конечное число шагов,

- формальность – способность исполнителя выполнить все шаги алгоритма, не понимая их смысла.

Формы записи алгоритмов

Естественный язык

Пример. Нахождение наибольшего общего делителя (НОД) двух чисел – алгоритм Евклида.

Шаг 1. Ввести 2 числа.

Шаг 2. Если числа равны, взять первое и закончить выполнение, в противном случае перейти к шагу 3.

Шаг 3. Определить большее число. Заменить большее число на разность большего и меньшего и перейти к шагу 2.

Достоинство формы: универсальность. Недостаток: неформальность.

Блок – схемы (по ГОСТу - Схемы алгоритмов)

Пример. Алгоритм Евклида.

Шаги алгоритма показываются с помощью специальных графических символов, которые связываются линиями передачи управления. Оговорены ссылки между листами. Существует ГОСТ.

Достоинства: наглядность, формальность.

Начало

Вывод A

Конец

Недостатки: трудоемкость разработки и коррекции; несовпадение с текстом программы, реализующей алгоритм.

Псевдокоды

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

Пример. Алгоритм Евклида.

ввод A, B

пока A ≠ B делать

если A > B то

A = A – B

иначе

B = B – A

конец если

конец пока

вывод A на печать

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

Недостаток: уступают по наглядности блок – схемам.

Рекомендация: наиболее предпочтительная форма записи алгоритмов

Существует также метод HIPO диаграмм, который используется для описания больших программных проектов. HIPO означает: иерархия (hierarchy), ввод (input), обработка (processing), вывод (output).

1.3. ПРОГРАММЫ И ЯЗЫКИ

Программа – это список инструкций для выполнения задачи на ЭВМ.

Программирование – действия по ее созданию.

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

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

Алфавит – набор допустимых символов.

Лексема – неделимая конструкция языка, имеющая определенный смысл.

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

Оператор – лексема, обозначающая некоторое действие.

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

Синтаксис – набор правил построения программы из конструкций языка.

Семантика – описание понятий языка.

Выполнение программы

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

Машинный и алгоритмический языки

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

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

01 0016 0022 0012

Здесь:

- 01 – код операции сложения,

- 0016 – адрес 1 операнда,

- 0022 – адрес 2 операнда,

- 0012 – адрес, куда помещается результат операции.

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

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

- не выявляется внутренняя структура алгоритма;

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

- трудность внесения изменений и отыскания ошибок;

- большой объем.

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

Программа на алгоритмическом языке предварительно должна быть переведена на машинную систему команд. Для этой цели различными фирмами были разработаны специальные программы – трансляторы, которые вместе со средствами подготовки текстов, отладки программ и другими, составляют интегрированную среду разработки (IDE – Integrated Development Environment).

Метаобозначения

Метаязык – это язык для описания другого языка. Наиболее распространенными метаязыками для описания языков программирования являются нотация Бэкуса-Наура (БНФ) и синтаксические диаграммы. В данном пособии принята следующая система описаний правил и понятий языков программирования:

- := - фраза "это есть";

- { } – обязательный элемент конструкции; значение выбирается из нескольких альтернатив;

- [ ] – необязательный (optional) элемент конструкции;

- ... – предыдущий элемент конструкции может повторяться произвольное число раз;

- | - фраза "или";

- <...> - используется для обозначения понятий, а не конструкций языка.

Пример.

dim <список>

<список>:=<элемент>[,<элемент>]...

<элемент>:={<переменная>|<массив>} as <тип>

Этапы обработки программы на компьютере

текст маш.код отн.адреса абс.адреса
ИМ ОМ ЗМ память
результаты

периферия

Терминология

Исходные модули (ИМ) – тексты программы на алгоритмическом языке.

Объектные модули (ОМ) – оттранслированные тексты программы на машинном языке в относительных адресах.

Загрузочный модуль (ЗМ) – единая готовая к выполнению программа, по-прежнему, в относительных адресах.

Рассмотрим более подробно каждый этап.

Трансляция

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

Замечание. В современных визуальных средах разработки в качестве главной может применяться специальный объект – форма. При объектно-ориентированной разработке появляется еще 1 очень важный программный объект – класс. Он включает свойства объекта и операции, которые могут выполняться над объектом (или их совокупностью). Эти операции реализуются с помощью методов. Метод записывается практически по правилам процедур. Существует полностью объектно-ориентированные языки программирования, основным элементом которых является класс, например, C# (Си Шарп).

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

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

Для обозначения объектов программы на алгоритмическом языке используется понятие имя.

Пример. Возможные имена.

x matrix Height Copy1 Sum

Во время трансляции происходит распределение памяти, т.е. процесс выделения каждому именованному объекту программы области памяти необходимого размера. Выделенная область памяти характеризуется начальным адресом расположения объекта. Поэтому распределение памяти – это процесс установления взаимно однозначного соответствия между именем в исходном модуле и адресом в объектном модуле. Схематически это можно изобразить так.

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

Наиболее распространенными языками программирования являются: FORTRAN (Formula Translator – переводчик формул), PL/1 (Programming Language/1 – язык программирования 1), C, С# и C++, Pascal, BASIC (Beginner's All-purpose Symbolic Instruction Code – универсальный язык символического кодирования для начинающих), Java.

Редактирование связей (компоновка)

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

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

Загрузка

Процесс загрузки программы был описан выше, поэтому отметим лишь основные функции данного этапа:

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

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

- передача управления первой инструкции главной процедуры.

Выполнение

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

Типы вычислительных процессов

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

Следование

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

Пример.

y=a+b z=2*y*y+a*y+b print(z)

Развилка

Это двухальтернативный выбор, который на псевдокоде можно записать так:

если <условие> то

<действие 1>

[иначе

<действие 2>]

конец если

Как <действие 1>, так и <действие 2> могут являться комбинацией всех 3 базовых структур, поэтому с помощью данной структуры можно организовать более двух ветвей алгоритма. Квадратные скобки вокруг альтернативы иначе означают необязательность этой ветви.

Пример. Найти x=max(a, b), y=min(a, b).

Вариант 1.

если a>b то

x=a

y=b

иначе

x=b

y=a

конец если

Вариант 2.

x=a

y=b

если aто

x=b

y=a

конец если

Цикл

Это последовательность действий, повторяющаяся до тех пор, пока выполняется некоторое условие. Цикл в общем случае состоит из 4 блоков: инициализации цикла; логического блока, содержащего условие продолжения или окончания цикла; тела цикла – последовательности инструкций, выполняемых при каждом повторении, и блока, в котором производится изменение условия продолжения (или окончания) цикла. В зависимости от того, как расположен блок условия по отношению к телу цикла, различают цикл с предусловием (условие проверяется до выполнения тела цикла) и цикл с постусловием (условие проверяется после выполнения тела цикла). В первом случае тело цикла может ни разу не выполниться, во втором – оно выполнится хотя бы 1 раз. На рисунке показаны обобщенные блок-схемы цикла каждого вида. В некоторых частных случаях отдельные блоки могут отсутствовать.

Цикл с предусловием Цикл с постусловием

Пример. Сортировка массива методом "пузырька" {a_i}, i=1...n.

k=1 Исходный массив: {24, -12, 0, 123, -2, 57}

пока k>0 делать Результат: {-12, -2, 0, 24, 57, 123}

k=0

для i от 1 до n-1 выполнить

если a_i > a_i+1то

b=a_i

a_i=a_i+1

a_i+1=b

k=1

конец если

конец для

конец пока