Тема 6. Алгоритмизация и программирование Лекция 12. Алгоритмы. Свойства алгоритмов. Языки программирования.

План лекции:

Алгоритм, численные и логические алгоритмы. Свойства алгоритмов, дискретность, определенность, понятность, результативность. Формы записи алгоритма, блок-схемы, основные элементы блок схем. Базовые структуры алгоритмов, линейные, разветвляющиеся, циклические алгоритмы. Данные и их типы. Логические основы алгоритмизации. Языки программирования, эволюция, классификация. Языки программирования высокого и низкого уровня. Компилируемые языки. Интерпретируемые языки. Объектно-ориентированные языки. Модульный принцип программирования. Принципы проектирования программ сверху-вниз и снизу-вверх. Системы программирования, схема разработки прикладных программ в среде системы программирования, трансляция (компиляция), исполнимый код.

Краткий конспект лекции

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

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

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

Языки программирования низкого уровня: Машинный язык и ассемблер

Языки программирования высокого уровня представляют специальный набор инструкций, использующих ключевые слова и синтаксис, похожий на английский:. Visual Basic, Visual Fortran, Cobol, Delphi, С++.

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

Трансляторы делятся на два типа: интерпретаторы и компиляторы.

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

Компилятор переводит в машинный код исходный текст программы целиком, используется для языков программирования Pascal, С и др.

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

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

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

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

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

Генерация и оптимизация промежуточного кода – перевод текста программы в язык ассемблера и устранение "лишнего" кода.

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

В результате работы компилятора получается исполняемый файл – приложение.

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

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

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

• Проектирование программы – определение входных данных, процедур обработки данных и выходных данных.

• Кодирование программы – запись программы на языке программирования в соответствии с алгоритмом задачи.

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

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

Процесс отладки программы начинается с выявления:

• синтаксических ошибок в тексте (неверно записанных операторов),

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

• алгоритмических ошибок (неверно составлен или запрограммирован алгоритм).

• Документирование программы - создание подробного руководства по программе: описание вводимых и выводимых данных, тестовые примеры расчета.

Алгоpитм - заранее заданное понятное и точное предписание возможному исполнителю совершить определенную последовательность действий для получения решения задачи за конечное число шагов

Слово «алгоритм» происходит от латинской формы написания имени арабского математика Аль Хорезми. Известно, что он родился до 800 г., а умер после 847 г., жил и работал в Багдаде - крупном научном центре и влиятельной столице Древнего Востока. Аль Хорезми использовал индийскую позиционную систему счисления с нулём и сформировал правила четырёх арифметических действий над многозначными числами.

Формы записи алгоритмов: графическая запись (блок-схемы); словесная запись (псевдокоды); язык программирования.

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

• Дискретность - разбиение алгоритма на ряд отдельных законченных действий – шагов

• Определенность (детерминированность) - однозначные указания, применение алгоритма к одним и тем же исходным данным должно приводить к одному и тому же результату

• Понятность - однозначное понимание и исполнение каждого шага алгоритма его исполнителем

• Результативность - обязательное получение результата за конечное число шагов

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

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

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

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

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

Концепцию модульного программирования можно сформулировать в виде нескольких понятий и положений:

1. 1) большие задачи разбиваются на ряд более мелких, функционально самостоятельных подзадач — модулей, которые связаны между собой только по входным и выходным данным;

2. 2) модуль представляет собой «черный ящик» с одним входом и одним выходом. Это позволяет безболезненно производить модернизацию программы в процессе ее эксплуатации, облегчает ее сопровождение, а также позволяет разрабатывать части программодного проекта на разных языках программирования;

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

4. 4) исходный текст модуля должен иметь заголовок и интерфейсную часть, где отражаются назначение модуля и все его внешние связи;

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

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

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

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

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

Вопросы по данной теме:

1. Что такое алгоритм?

2. Что такое блок-схема?

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

4. Опишите базовые управляющие конструкции алгоритмов.

5. Перечислите основные методы современной технологии проектирования алгоритмов.

Литература по теме:

1. Информатика. Общий курс / Под ред. В.И. Колесникова. - 2-е изд. - М.: Дашков и К; Наука-Пресс, 2008. - 400 с.

2. Игошин В.И. Математическая логика и теория алгоритмов: Уч. пос. - М.: Академия, 2004. - 448с.

3. Микрюков В.Ю. Алгоритмизация и программирование: Учебн. пос.- Ростов н/Д: Феникс, 2007.