1. Понятие алгоритма
В современном мире мы постоянно сталкиваемся с алгоритмами: рецепт приготовления блюда, инструкция по сборке мебели, маршрут поездки — все это примеры алгоритмов.
Алгоритм — это понятное и точное предписание (указание) исполнителю выполнить конечную последовательность действий, направленных на достижение указанной цели или решение поставленной задачи.
Ключевые элементы алгоритма:
Исполнитель — тот, кто выполняет алгоритм (человек, робот, компьютер).
Система команд исполнителя (СКИ) — набор команд, которые понимает и может выполнить исполнитель. Например, исполнитель «Черепаха» в языке Лого понимает команды «вперед n», «направо k», а исполнитель «компьютер» понимает команды процессора.
Среда — обстановка, в которой действует исполнитель.
2. Свойства алгоритмов
Далеко не всякая последовательность действий является алгоритмом. Алгоритм должен обладать следующими свойствами:
Дискретность (от лат. discretus — прерывистый) — алгоритм должен быть разбит на отдельные, законченные действия (шаги). Выполнение каждого шага заканчивается прежде, чем начинается следующий.
Аналогия: Рецепт разбит на отдельные шаги: «нарезать», «обжарить», «посолить».
Понятность — алгоритм должен быть составлен из команд, входящих в систему команд исполнителя. Алгоритм, содержащий команду «Приготовь вкусный суп», непонятен для робота-повара, так как слово «вкусный» для него не имеет смысла.
Определённость (детерминированность) — каждая команда алгоритма должна быть однозначной и не оставлять возможности для произвольного толкования. Результат выполнения одного и того же алгоритма должен быть одинаковым при одинаковых исходных данных.
Пример неопределенности: «Добавь немного соли». Пример определенности: «Добавь 5 г соли».
Результативность (конечность) — выполнение алгоритма должно завершиться за конечное число шагов с определенным результатом. Алгоритм не может уходить в «бесконечный цикл».
Пример безрезультатности: Алгоритм: «1. Начать. 2. Перейти к шагу 1. 3. Закончить.» — никогда не достигнет шага 3.
Массовость — алгоритм должен быть применим для решения целого класса однотипных задач, отличающихся исходными данными.
Пример: Алгоритм решения квадратного уравнения $ax^2 + bx + c = 0$ должен работать для любых чисел a, b, c (где a ≠ 0).
3. Способы записи алгоритмов
Алгоритмы можно представлять различными способами:
Словесный (на естественном языке).
Графический (в виде блок-схем).
Программный (на языке программирования).
4. Языки программирования
Чтобы поручить выполнение алгоритма компьютеру, его необходимо записать на языке, понятном машине. Таким языком является язык программирования.
Язык программирования — это формальный знаковый система, предназначенная для записи алгоритмов, которые будут выполняться компьютером.
Классификация языков программирования:
1. По уровню:
Языки низкого уровня — близки к машинному коду конкретного процессора.
Машинный код: команды состоят из нулей и единиц. Непонятен человеку.
Ассемблер: uses мнемонические обозначения команд (например, MOV, ADD). Трудоемок в использовании, но дает полный контроль над аппаратурой.
Языки высокого уровня — максимально приближены к естественному человеческому языку (часто английскому). Позволяют абстрагироваться от особенностей конкретного процессора.
Примеры: Pascal, Python, C++, Java, JavaScript.
Достоинства: Простота чтения и написания, переносимость между разными компьютерами.
2. По парадигме (стилю) программирования:
Императивные (как делать): алгоритм задается как последовательность команд, изменяющих состояние программы.
Процедурные (Pascal, C): программа состоит из процедур и функций.
Объектно-ориентированные (ООП) (C++, Java, Python): программа представляется как совокупность взаимодействующих объектов.
Декларативные (что делать): программа описывает desired результат, а не способ его достижения.
Функциональные (Haskell, Lisp): программа представляет собой математическую функцию.
Логические (Prolog): программа основана на математической логике.
Процесс выполнения программы компьютером:
Программа на языке высокого уровня с помощью специальной программы — транслятора — переводится в машинный код.
Компилятор — переводит (компилирует) всю программу целиком в машинный код, создавая исполняемый файл (например, .exe). Программа может быть запущена независимо.
Примеры: Pascal, C++, Java (частично).
Интерпретатор — переводит (интерпретирует) и выполняет программу построчно, не создавая отдельного исполняемого файла.
Примеры: Python, JavaScript.
Видео урок по данному уроку от учителя информатики Трашкова Олега Леонидовича