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

[wersja przejrzana][wersja przejrzana]
Usunięta treść Dodana treść
Jakas1 (dyskusja | edycje)
T3 = T1 + T4 zamieniłem na T3 = T3 + T4
 
Linia 1:
'''Algorytm SethiSethiego-Ullmana''' – algorytm konwersji [[drzewo (matematyka)|drzewa]] na taki szereg prostych instrukcji w którym zostanie użyta minimalna liczba rejestrów (lub zmiennych tymczasowych jeśli rejestry się wyczerpią). Jest to bardzo ważne, ponieważ większość współczesnych komputerów ma relatywnie niewielką ilość rejestrów.
 
Jego autorami są [[Ravi Sethi]] oraz [[Jeffrey Ullman]] (stąd nazwa).
Linia 25:
 
== Algorytm ==
Algorytm SethiSethiego-Ullmana pozwala nam zawsze znaleźć optymalną postać.
Krok pierwszy polega na obliczeniu ile co najmniej rejestrów tymczasowych jest potrzebnych do obliczenia poddrzewa:
* każdy liść otrzymuje wartość 0;
Linia 54:
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ń, obliczyć w trakcie kompilacji stałe części drzewa, oddzielić obliczanie [[wspólne podwyrażenie|wspólnych podwyrażeń]] itd.
 
[[Kategoria:Algorytmy|SethiSethiego-Ullmana]]