Итерация

Итерация — это повторение процесса с целью создания (возможно, неограниченной) последовательности результатов. Каждое повторение процесса представляет собой одну итерацию, а результат каждой итерации является отправной точкой следующей итерации.

В математике и информатике итерация (наряду со связанным с ней методом рекурсии ) является стандартным элементом алгоритмов .

Математика

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

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

Вычисление

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

Реализации

Циклы представляют собой наиболее распространенные языковые конструкции для выполнения итераций. Следующий псевдокод трижды «итерирует» строку кода между началом и концом в цикле for и использует значения i в качестве приращений.

a := 0
for i := 1 to 3 do       { loop three times }
begin
    a := a + i;          { add the current value of i to a }
end;
print(a);                { the number 6 is printed (0 + 1; 1 + 2; 3 + 3) }

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

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

Итераторы — это чисто функциональные языковые конструкции, которые принимают или отклоняют данные во время итераций.

Связь с рекурсией

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

Некоторые типы языков программирования, известные как функциональные языки программирования , спроектированы таким образом, что в них не создается блок операторов для явного повторения, как в случае цикла for . Вместо этого эти языки программирования используют исключительно рекурсию . Вместо того, чтобы вызывать блок кода, который должен быть повторен заранее определенное количество раз, исполняемый блок кода вместо этого «делит» работу, которую необходимо выполнить, на несколько отдельных частей, после чего блок кода выполняется на каждой отдельной части. . Каждая часть работы будет многократно делиться до тех пор, пока «объем» работы не станет настолько маленьким, насколько это возможно, и в этот момент алгоритм выполнит эту работу очень быстро. Затем алгоритм «переворачивает» и собирает части в единое целое.

Классический пример рекурсии — алгоритмы сортировки списков, такие как сортировка слиянием . Рекурсивный алгоритм сортировки слиянием сначала многократно разделит список на последовательные пары; Затем упорядочивается каждая пара, затем каждая последовательная пара пар и т. д., пока элементы списка не окажутся в желаемом порядке.

Код ниже представляет собой пример рекурсивного алгоритма на языке программирования Scheme , который выводит тот же результат, что и псевдокод под предыдущим заголовком.

(let iterate ((i 1) (a 0))
  (if (<= i 3)
    (iterate (+ i 1) (+ a i))
    (display a)))

Образование

В некоторых педагогических школах итерации используются для описания процесса обучения или направления учащихся к повторению экспериментов, оценок или проектов до тех пор, пока не будут найдены более точные результаты или пока учащийся не овладеет техническими навыками. Эта идея содержится в старой поговорке: «Практика ведет к совершенству». В частности, «итеративный» определяется как «процесс обучения и развития, включающий циклические исследования, дающий людям множество возможностей пересмотреть идеи и критически осмыслить их последствия». ^[1]

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

См. также

Ссылки

^ Хелен Тимперли ; Аарон Уилсон; Хизер Баррар; Ирен Фунг. «Профессиональное обучение и развитие учителей: лучшая итерация синтеза фактических данных [BES]» (PDF) . ОЭСР . п. 238. Архивировано из оригинала (PDF) 26 июня 2013 года . Проверено 4 апреля 2013 г.

[1] Хелен Тимперли ; Аарон Уилсон; Хизер Баррар; Ирен Фунг. «Профессиональное обучение и развитие учителей: лучшая итерация синтеза фактических данных [BES]» (PDF) . ОЭСР . п. 238. Архивировано из оригинала (PDF) 26 июня 2013 года . Проверено 4 апреля 2013 г.

[1]