Wikipedia

Algorytm Sethi-Ullmana: Różnice pomiędzy wersjami

Przeglądaj historię interaktywnie
[wersja nieprzejrzana][wersja nieprzejrzana]
← poprzednia edycjanastępna edycja →
Usunięta treść Dodana treść
WizualnieWikikod
Stv.bot (dyskusja | edycje)
79 787 edycji
m językowe
Linia 6:
Kod:
x = a + (b + (c + (d + x)))
można przekształcić zgodnie z zasadą „wyliczaj„obliczaj najpierw lewą stronę” na:
t1 = a
t2 = b
Linia 15:
t1 = t1 + t2
x = t1
lub też zgodnie z zasadą „wyliczaj„obliczaj najpierw prawą stronę” na:
t1 = d + x
t1 = c + t1
Linia 26:
=== Algorytm ===
Algorytm Sethi-Ullmana pozwala nam zawsze znaleźć optymalną postać.
Krok pierwszy polega na wyliczeniuobliczeniu ile co najmniej rejestrów tymczasowych jest potrzebnych do wyliczeniaobliczenia poddrzewa:
* każdy liść otrzymuje wartość 0;
* jeśli węzeł ma 2 podwęzły o różnych wartościach, otrzymuje wartość większego z nich;
Linia 47:
* w przeciwnym razie:
** generujemy kod dla poddrzewa o większym numerze,
** wykorzystujemy jeden z rejestrów, które zaalokowaliśmy na potrzeby wyliczaniaobliczania pierwszego poddrzewa,
** generujemy kod dla drugiego poddrzewa,
** scalamy wynik.
 
Algorytm ten ustali „optymalną” kolejność wykonywania obliczeń.
Oczywiście w praktyce możliwe są inne optymalizacje – możemy przekształcić drzewo korzystając z praw [[Łączność (matematyka)|łączności]] i [[przemienność|przemienności]] działań, wyliczyćobliczyć w trakcie kompilacji stałe części drzewa, oddzielić wyliczanieobliczanie [[wspólne podwyrażenie|wspólnych podwyrażeń]] itd.
 
[[kategoria:algorytmy|Sethi-Ullmana]]
Źródło: „https://pl.wikipedia.org/wiki/Algorytm_Sethi-Ullmana”