Сортировка обменом.

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

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

Итерацией называется такой способ организации обработки данных, при котором некоторые действия многократно повторяются, не приводя при этом к рекурсивным вызовам программ (функций).

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

I) условие продолжения рекурсии (шаг рекурсии);

II) условие окончания рекурсии.

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

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

Машину Тьюринга можно описать:

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

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

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

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

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

Служебные слова алгоритмического языка

алг (алгоритм)

арг (аргумент)

рез (результат)

нач (начало)

кон (конец)

цел (целый)

вещ (вещественный)

сим (символьный)

лит (литерный, строка)

лог (логический)

таб (таблица)

На сегодняшний день имеются четыре основные парадигмы языков программирования

Императивная;

Функциональная;

Декларативная;

Объектно-ориентированная

Императивные (процедурные) языки— это языки программирования, управляемые командами, или операторами языка

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

Декларативные языки программирования - это языки программирования, в которых операторы представляют собой объявления или высказывания в символьной логике

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

29) Компьютерная программа представляет собой логически упорядоченную последовательность команд, предназначен­ных для управления компьютером