Алгоритмы и программы

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

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

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

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

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

Обозначение блоков
ввод данных
Дисплей
вывод данных
Документ

Обозначение блоков
проверка условий,
цикл с условием
Решение
заголовок цикла со счетчиком
Модификация

Обозначение блоков
Предопределенный
процесс
вычисление по
подпрограмме

Пример линейного алгоритма

Пример разветвляющегося алгоритма

Пример цикла типа пока
Вывод на экран таблицы функции Y=X^2 для интервала [a,b] с шагом h

Пример цикла типа до
Вычисление суммы ряда 1/i с погрешностью E
НАЧАЛО
Sum=0;
i=1;
Вывод Sum
КОНЕЦ
s<=E
Да
s=1/i;
Sum=Sum+s;
i=i+1;
Ввод E

Пример цикла со счетчиком
Вычисление факториала

Программа и программирования
Программирование – процесс записи алгоритма на машинном языке
Программа – запись алгоритма на машинном языке

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

Языки программирования
Транслятор – программа, осуществляющая перевод программы, написанной на некотором языке программирования, на машинный язык.
Интерпретатор – вид транслятора, который в процессе перевода программы на машинный язык и сразу же ее выполняет.
Компилятор – вид транслятора, который переводит программу в объектный код (машинный язык), но не выполняет ее.
Линкер (сборщик) – программа, которая к объектному коду, скомпилированной программы, подключает код из библиотек и формирует исполняемый файл в формате определенной ОС.

Этапы трансляции
Компиляция
Сборка
Программа на языке
программирования
Объектный
код
Исполняемый код
(файл)
Код из библиотек
Компилятор
compiler
Сборщик
linker

Структура компилятора
Лексический анализ
Синтаксический анализ
Семантический анализ
Оптимизация
Редактирование
связей
Генерация кода
Таблица
символов
Другие
таблицы
Исходная программа
Лексемы
Дерево грамматического разбора
Промежуточный код
Оптимизированный код
Объектный
код
Выполняемый
код
Объектный код
других
компонентов

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

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

Классификация по методам трансляции
Виды языков:
интерпретируемые,
компилируемые,
смешанные.

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

Классификация по парадигме
Виды языков:
императивные (процедурные),
аппликативные (функциональные),
логические,
основанные на системе правил,
объектно-ориентированные.

История языков
Plankalkuel (plan calculus) – Конрад Цузе, 1945-1946 гг.
FORTRAN (formula translator) – Бэкус, 1957 г.
ALGOL-58 (algorithmic language) – 1958, 1968.
Simula-67 (simulation) – Найгард и Пол, 1967 г.
Фирма IBM:
NPL (new programming language) → MMPL (multi purpose programming) → PL/1 (PL/2) (programming language)
70-е гг.: С, Pascal, Ada
80-е гг.: C++
90-е гг.: Java, Ada 95
XXI век: C#, Ruby.

История языков
Обработка деловой информации:
COBOL (Common busyness oriented language).
Perl, SQL
Искусственный интеллект:
Lisp, Prolog.
Языки системного программирования:
CPL, BCPL, C, C++
Web-программирование:
SGML, HTML, XML, Javascript, Java и др.

Эры языков программирования
Эра универсальных ЭВМ (до 70х гг. ХХ века),
Эра персональных ЭВМ (до 90х гг. ХХ века),
Эра сетевых технологий (наше время).

Язык программирования С
Язык С был разработан в 1972 г. Дэнисом Ритчи и Кеном Томпсоном из AT&T Laboratories в рамках разработки ОС UNIX.
В настоящее время С – универсальный язык, обладающий чертами как прикладного, так и системного языка.
Стандартизация:
ANSI С89 – 1989 г (ISO/IEC 9899:1989),
ANSI С99 – 1999 г. (ISO/IEC 9899:1999),
ANSI C11 – 2011 г. (ISO/IEC 9899:2011)