1.1 Основні визначення: алгоритм, вхід, результат; поняття правильного і неправильного алгоритму; псевдокод
Алгоритм - це формально описана обчислювальна процедура, яка отримує вихідні дані (вхід) і повертає результат (вихід). Алгоритми будуються для вирішення тих чи інших обчислювальних задач, при цьому вони повинні відповідати таким, що суперечить одне одному вимогам:
1) Бути простим для розуміння, перекладу в програмний код і налагодження;
2) Ефективно використовувати обчислювальні ресурси.
Алгоритм вважають правильним (correct), якщо на будь-якому допустимому вході він закінчує роботу і видає результат, що задовольняє вимогам завдання. У цьому випадку говорять, що алгоритм вирішує (solve) дану обчислювальну задачу. Неправильний алгоритм для деякого входу може взагалі не зупинитися або дати неправильний результат. Алгоритм може бути описаний різними способами, в тому числі і за допомогою псевдокоду, що належить вищому рівню абстракції порівняно з мовами програмування високого рівня (C #, Pascal, Basic і т.д.). В математичному пакеті MathCAD при написанні коду функцій, визначених користувачем, використовується нотація, що нагадує описуваний нижче псевдокод.
Таблиця 1.1 - Угоди, що лежать в основі псевдокоду
Відступ від лівого поля вказує на рівень вкладеності (це дозволяє відмовитися від застосування begin і end)
Цикли while, for, repeat і умовні конструкції мають таке ж значення, що і в мові Pascal.
Символ "¬" має сенс оператора присвоювання.
Змінна, що позначає масив або об'єкт, вважається покажчиком на складові його дані.
Всі змінні (за замовчуванням) - локальні.
Оператор доступу до елементу масиву пишеться в квадратних дужках [].
Доступ до поля (field) об'єкта (object): field [object].
Параметри в підпрограму передаються по-значенням (by value), але при передачі об'єкта його властивості копіюються у вигляді покажчиків. Тобто якщо в якості параметра передається об'єкт x. то присвоювання x ¬ y зовні помітити не можна, а f [x] ¬ 5 можна.
Як приклад, що дозволяє оцінити відмінності між псевдокодом і алгоритмічною мовою, розглянемо сортування вставками.
Лістинг 1.1 - Псевдокод алгоритму сортування вставками
procedure InsertSort (n: integer;
var A: array [1..n] of integer);
i, j, Tmp: integer;
for i: = 2 to n do begin