Back

ⓘ Čejtinov algoritam




                                     

ⓘ Čejtinov algoritam

Čejtinov algoritam je odozdo-nagore algoritam za bojenje grafova koji koristi alokaciju registara, a kao meru za pražnjenje registara koristi jedinicu cena/stepen. Ovaj algoritam osmislio je Gregori Čejtin, po kome nosi ime. Čejtinov algoritam je bio prvi algoritam, koji koristi alokaciju registara, koji je iskoristio bojenje grafova kako za alokaciju registara tako i za njihovo pražnjenje.

Čejtinov algoritam je predstavljen i objavljen 1982. na SIGPLAN Simpozijumu o konstrukciji kompilatora. To je bio nastavak ranijeg rada iz 1981. godine koji se bavio bojenjem grafova za alokaciju registara. Čejtinov algoritam predstavlja osnovu velikog dela istraživanja koja se bave alokacijom registara.

                                     

1. Pseudokod

Neka je dat graf G, koji sadrži čvorove N stepena manjeg od R. Graf G je R-bojiv ukoliko graf G gde je G graf G sa uklonjenim čvorom N R-bojiv.

Dokaz je očigledan.

  • Pretpostavimo da je graf G R-bojiv. Onda nam je i graf G sigurno R-bojiv.
  • Pretpostavimo da nam je graf G R-bojiv. Pošto nam je čvor N stepena manjeg od R mora postojati bar jedna boja kojom nije obojen nijedan susedni čvor čvora N. Tom bojom možemo obojiti N. Dakle G je R-bojiv.

Pseudokod algoritma glasi:

While G cannot be R-colored While graph G has a node N with degree less than R Remove N and its associated edges from G and push on a stack S End While If the entire graph has been removed then the graph is R-colorable While stack S contains a node N Add N to graph G and assign it a color from the R colors End While Else graph G cannot be colored with R colors Simplify the graph G by choosing an object to spill and remove its node N from G spill nodes are chosen based on object’s number of definitions and references End While

Složenost Čejtinovog algoritma je: O − n − 2 {\displaystyle O-{n}-^{2}}

                                     
  • функција која излази на цифре, а не за израчунавање броја, као што су Чејтинова константа. Слично томе, већина подгрупа природних бројева нису израчунљиве

Users also searched:

...