Графическая форма записи алгоритмов

(ГОСТ 19.701-90 Схемы алгоритмов, программ данных и систем). Рассмотрим основные графические элементы, применяемые для записи алгоритмов.

Начало-конец (терминатор по ГОСТу)

Поток данных или управления

Ввод данных

Процесс (выполнение операции или группы операций)

Цикл (вытянутый по горизонтали шестиугольник)

Условие, имеет один вход и ряд альтернативных выходов, один из которых активизируется, после вычисления условий, определенных внутри символа.

Всего в ГОСТе десятки элементов.

Основные алгоритмические структуры

1. Линейный алгоритм (алгоритм следования)

2. Алгоритм на ветвление

3. Алгоритм на цикл с предусловием

4. Алгоритм на цикл с послеусловием

5. Алгоритм на цикл с параметром

где: i – параметр,

n – начальное значение параметра,

m – конечное значение параметра,

l – шаг изменения параметра.

Пример решения алгоритма:

определить значение С при n = 6.

Решение:

Итерация	i	a	b	с

Ответ: с = 8

Эволюция и классификация языков программирования. Основные понятия языков программирования.

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

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

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

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

Классификация ЯП

Разработаны тысячи языков программирования. Классифицировать ЯП можно по разным признакам: уровню языка, способу реализации и стилю программирования.

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

Языки программирования низкого уровня (ЯПНУ) – это машинно-зависимые языки, которые можно применять на ограниченном подмножестве машин с одинаковой архитектурой и платформой.

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

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

Языки программирования высокого уровня (ЯПВН) – машинно-независимые языки, применимые на любых компьютерах.

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

Особенность: понятность и легкая обучаемость языку.

Примеры: Паскаль – очень популярный язык, разработан в 1970 г. швейцарцем Н. Виртом.

Бэйсик – язык для начинающих, 1964, Дартмутский колледж.

Си – разработан в начале 70-х годов для реализации разработки операционных систем, трансляторов, баз данных и других системных и прикладных программ. В нем заложены возможности непосредственного обращения к некоторым машинным командам и участкам памяти компьютера.

Фортран (1953 г.), Delphi и т.д.

Способ реализации ЯП.

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

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

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

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

Если программа написана на интерпретируемом языке, то интерпретатор непосредственно выполняет (интерпретирует) исходный текст без предварительного перевода всей программы. При этом программа остаётся на исходном языке и не может быть запущена без интерпретатора. (С++).

Кратко говоря, компилятор переводит исходный текст программы на машинный язык сразу и целиком, создавая при этом отдельную машинно-исполняемую программу, а интерпретатор выполняет исходный текст прямо во время исполнения программы («интерпретируя» его своими средствами).

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

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

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

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

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

Понятие о структурном программировании. Подпрограммы. Принципы проектирования программ «сверху – вниз» и «снизу – вверх». Модульный принцип программирования.

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

Структурное или процедурное программирование (70-е годы ХХ в., программирование без GOTO) является отражением архитектуры традиционных ЭВМ, которая была предложена фон Нейманом в 1940-х годах.

В соответствии с данной методологией:

Любая программа представляет собой структуру, построенную из трёх типов базовых конструкций:

последовательное исполнение – однократное выполнение операций в том порядке, в котором они записаны в тексте программы;

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

цикл – многократное исполнение одной и той же операции до тех пор, пока выполняется некоторое заданное условие (условие продолжения цикла).

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

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

Разработка программы ведётся пошагово, методом «сверху вниз».

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

Операторы присваивания в языках программирования задают значения переменных.

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

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

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

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

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

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

Одним из основных компонентов системы программирования, служащим для ускорения и облегчения программирования задач определенного класса, является библиотека подпрограмм, оформленная в виде модуля.

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

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

Пример языков структурного программирования: Pascal, Basic, Си, Фортран, КОБОЛ.

Объектно-ориентированное программирование

Объе́ктно-ориенти́рованное, или объектное, программирование (в дальнейшем ООП) – парадигма программирования, в которой основными концепциями являются понятия объектов и классов (80-е годы ХХ в).

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

Основные понятия:

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

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

Инкапсуляция означает объединение в единое целое данных и алгоритмов обработки этих данных.

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

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

Событиями в объектно-ориентированном программировании называются уведомления, получаемые или передаваемые другим объектам или приложениям.