Iterowane działanie dwuargumentowe – konstrukcja algebraiczna polegająca na wielokrotnym stosowaniu danego działania dwuargumentowego do skończonego lub nieskończonego ciągu argumentów. Umożliwia zwarty zapis wielokrotnego zastosowania tej samej operacji do elementów pewnego ciągu lub zbioru.
Definicja formalna Niech będzie strukturą algebraiczną składającą się ze zbioru i łącznego działania dwuargumentowego .
Dla dowolnego ciągu elementów ze zbioru , iterowane działanie definiuje się indukcyjnie:
Dla :
Dla :
Dzięki założeniu o łączności działania wynik nie zależy od sposobu rozmieszczenia nawiasów, co pozwala na stosowanie uproszczonego zapisu Jeżeli działanie jest dodatkowo przemienne, kolejność elementów w ciągu nie wpływa na wynik końcowy.
Podstawowe operacje iterowane +Działania iterowane Dział matematykiSumaIloczynNazwaDziałanieDefinicjaSymbolNazwaDziałanieDefinicjaSymbolArytmetyka Suma Dodawanie Suma liczb. Iloczyn iterowanyMnożenieIloczyn liczb.Teoria mnogościSuma ciągu zbiorówSuma zbiorówWszystkie elementy zbiorów.Iloczyn ciągu zbiorówIloczyn zbiorówCzęść wspólna zbiorów.LogikaKwantyfikator egzystencjalnyAlternatywaAlternatywa ciągu zdań.Kwantyfikator ogólnyKoniunkcjaKoniunkcja ciągu zdań.Teoria podzielnościNajmniejsza wspólna wielokrotnośćNajmniejsza wspólna wielokrotnośćNajmniejsza liczba będąca wielokrotnością wszystkich wyrazów.Największy wspólny dzielnikNajwiększy wspólny dzielnikNajwiększa liczba będąca dzielnikiem wszystkich wyrazów.Teoria kategoriiKoproduktSuma rozłącznaKoprodukt obiektów w kategorii.ProduktIloczyn kartezjańskiProdukt obiektów w kategorii.
Notacja Ogólne iterowane działanie dwuargumentowe zapisuje się najczęściej w postaci:
gdzie symbol oznacza iterację pewnego działania dwuargumentowego .
Poszczególne elementy notacji mają następujące znaczenie: Fragment zapisu Znaczenie Symbol iterowanego działania dwuargumentowego. Zmienna iteracyjna (indeks). Wartość początkowa indeksu iteracji. lub Górna granica iteracji. Element odpowiadający indeksowi .
Przykładowo zapis
oznacza:
Jeżeli nad symbolem operatora nie występuje żadna wartość, np.
oznacza to iterację po wszystkich indeksach należących do zbioru .
Możliwe jest również stosowanie warunków ograniczających zakres iteracji, np.
co oznacza iterację wyłącznie po parzystych wartościach indeksu z przedziału od do .
W przypadku iteracji nieskończonej stosuje się zapis:
oznaczający iterację po nieskończonym ciągu elementów. Taki zapis wymaga jednak dodatkowych założeń dotyczących istnienia granicy lub zbieżności.
Jeżeli zakres iteracji wynika z kontekstu, dolny i górny indeks operatora mogą zostać pominięte:
Wówczas sposób iteracji musi być określony w otaczającym tekście. Własności Niech będzie strukturą algebraiczną z działaniem dwuargumentowym . Dla iterowanego działania zachodzą następujące własności: Dla jednego elementu:
Rozwinięcie definicji:
Rekurencyjność:
dla . Równoważna postać prawostronna:
Łączenie sąsiednich fragmentów iteracji:
dla . Iteracja po podziale indeksów:
jeżeli zbiory indeksów i tworzą rozłączny podział zbioru i zachowana jest kolejność elementów. Niezależność od nawiasowania:
co wynika z łączności działania . W przypadku działania przemiennego:
dla dowolnej permutacji zbioru indeksów . Dla monoidu :
gdzie jest elementem neutralnym działania . Idempotentność iteracji (gdy działanie jest idempotentne):
dla każdego . Stały ciąg argumentów:
(co odpowiada -krotnemu zastosowaniu działania do elementu ). Element neutralny i zbiór pusty Jeśli struktura jest monoidem (posiada element neutralny ), definicję można rozszerzyć na przypadek pustego ciągu argumentów (). Przyjmuje się wówczas, że wynik działania na zbiorze pustym jest równy elementowi neutralnemu, na przykład:
Suma pustego ciągu wynosi . Iloczyn pustego ciągu wynosi .
Informatyka W programowaniu funkcyjnym koncepcja iterowanego działania dwuargumentowego jest realizowana przez funkcje wyższego rzędu znane jako fold lub reduce. Funkcje te przyjmują działanie dwuargumentowe oraz listę elementów, a następnie „zwijają” je do pojedynczej wartości zgodnie z logiką iterowania. Szczególne przypadki Szereg – iterowane dodawanie dla nieskończonej liczby składników: . Silnia – szczególny przypadek iterowanego mnożenia liczb naturalnych: . Przypisy