Тема 4. Алгоритмизация и программирование. Языки программирования высокого уровня. Технологии программирования.

Этапы решения задач на компьютерах. Трансляция, компиляция и интерпретация.

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

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

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

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

Процессор компьютера «не понимает» алгоритмических языков, так как он воспринимает только команды машинного языка, состоящие из последовательности нулей и единиц. На заре компьютерной эры программисты так и писали программы в машинных кодах. Однако поскольку это очень трудоемкая и низкопроизводительная работа, были изобретены языки программирования. Языки программирования высокого уровня многократно ускорили процесс написания программ, но потребовался перевод программы, написанной на таком языке, в машинные коды. К счастью, такой перевод может делать сам компьютер с помощью специальной программы. Итак, после написания программы она переводится на машинный язык с помощью специальной программы – транслятора. Трансляторы бывают двух типов: интерпретаторы и компиляторы. В результате получается файл, который называется объектным модулем.

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

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

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

Документирование программы и ее сопровождение.

Интегрированная среда программирования (Turbo Pascal, Visual Basic, Delphi, Microsoft Visual Studio и др.) включает в себя следующие основные компоненты:

1. Текстовый редактор.

2. Транслятор.

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

4. Отладчик.

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

Понятие алгоритма и его свойства. Способы записи алгоритма. Блок-схема алгоритма.

Алгоритм – понятное и точное предписание исполнителю совершить последовательность действий, направленных на достижение поставленной цели.

Термин произошел от имени древнего арабского математика Абу Абдулах Мухамед ибн Муса Аль-Хорезми.

Алгоритмизация – процесс систематического составления алгоритмов для решения поставленных прикладных задач.

Свойства алгоритмов

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

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

Массовость – алгоритм должен быть применим к разным наборам исходных данных.

Результативность – завершение алгоритма определенными результатами.

Эвристика – это неформализованная процедура, сокращающая количество шагов поиска решений.

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

Наиболее распространенные способы записи алгоритмов:

Словесная (инструкции).

Графическая в виде блок-схем.

Программная, на языках программирования.

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

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

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

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

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

Ввод данных

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Решение:

Итерация

i

a

b

с

1

3

1

2

2

2

4

2

3

3

3

5

3

5

5

4

6

5

8

8

Ответ: с = 8

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Принципы ООП

Всё является объектом.

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

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

Каждый объект является представителем класса, который выражает общие свойства объектов (таких, как целые числа или списки).

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

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

Например, объект человек может иметь поля имя, фамилия и методы есть и спать. Соответственно, в программе можем использовать операторы Человек.Имя:="Иван" и Человек.Есть(пища).

Языки ООП: C#,C++,Delphi,Java.

Функциональные и логические языки

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

Достоинства: краткость и простота.

Пример: язык Лисп. Он широко используется в системе автоматизированного проектирования AutoCAD и называется AutoLISP.

Логические языки – языки программирования в терминах математической логики.

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

Prolog – самый известный язык логического программирования.