Dovetailing (informatyka)
Jaskółczy ogon w projektowaniu algorytmów to technika, która przeplata różne obliczenia , wykonując je zasadniczo jednocześnie. Algorytmy wykorzystujące dovetailing są czasami określane jako dovetailers .
Przykłady
Rozważmy drzewo , które potencjalnie zawiera ścieżkę o nieskończonej długości (ale każdy węzeł ma tylko skończoną liczbę dzieci): jeśli w tym środowisku przeprowadzane jest przeszukiwanie w głąb , wyszukiwanie może przesunąć się wzdłuż nieskończonej ścieżki i nigdy nie powrócić, potencjalnie pozostawiając część drzewo niezbadane. Jeśli jednak przeszukiwanie wszerz , istnienie nieskończonej ścieżki nie stanowi już problemu: każdy węzeł jest odwiedzany w sposób rozgałęziony zgodnie z jego odległością od korzenia, więc nieskończona ścieżka wpłynie tylko na część szukaj podróżując tą ścieżką.
Możemy uznać to drzewo za analogiczne do zbioru programów; w tym przypadku podejście w głąb odpowiada uruchamianiu jednego programu na raz, przechodząc do następnego tylko wtedy, gdy bieżący program zakończy działanie. W przypadku, gdy jeden z programów działa przez nieskończoną ilość czasu, to przejście nigdy nie nastąpi. Podejście „wszerz” polegające na odwiedzaniu każdego dziecka na tym samym poziomie drzewa jest przykładem „jaskółczego ogona”, w którym dla każdego programu wykonywany jest jeden krok przed przejściem do następnego. W ten sposób postęp jest dokonywany w każdym programie, niezależnie od potencjalnego istnienia niekończącego się programu.
Innym przykładem jest symulowanie niedeterministycznej maszyny Turinga M przez deterministyczną (np. uniwersalną maszynę Turinga ). W takim przypadku musimy użyć jaskółczego ogona, jeśli jedna z gałęzi obliczeniowych M zawiera nieskończoną pętlę.
Nieskończenie wiele jednoczesnych obliczeń
W przypadku nieskończonej liczby programów, z których wszystkie potencjalnie są nieskończenie długie, ani wszerz, ani w głąb nie wystarczyłyby do zapewnienia postępu we wszystkich programach. Zamiast tego można zastosować następującą technikę: wykonać pierwszy krok pierwszego programu; następnie wykonaj drugi krok pierwszego programu i pierwszy krok drugiego programu; następnie wykonaj trzeci krok pierwszego programu, drugi krok drugiego programu i pierwszy krok trzeciego programu; i tak dalej. Jest to zatem znane również jako diagonalizacja (jak jest używane np. w pakiecie „wszechświata” Haskella lub monadzie „Omega”).
Etymologia
Analogia z przeplatającymi się końcami połączenia na jaskółczy ogon w obróbce drewna .