Kontextfreie Suche auf Graphen
Untersuchung, Optimierung und Erweiterung des CFLR-Algorithmus von David Meslki und Thomas Reps
Versandkostenfrei!
Versandfertig in 6-10 Tagen
49,00 €
inkl. MwSt.
PAYBACK Punkte
0 °P sammeln!
David Melski und Thomas Reps haben Ende der Neunziger einen Algorithmus entwickelt, der es ermöglicht nach Knotenpaaren zu suchen zwischen denen ein Pfad existiert, der einer gegebenen kontextfreien Grammatik genügt.Dies ist beispielsweise dann interessant, wenn man einen Kontrollflussgraphen einer Applikation betrachtet und herausfinden möchte, ob alle von einem Prozess beanspruchten Ressourcen auch wieder frei gegeben werden. Da ein solcher Graph wegen der Methodenaufrufe im Normalfall eine geschachtelte Struktur aufweist, reicht ein Algorithmus, der mit einfachen Pfadbeschreibungen (wie ...
David Melski und Thomas Reps haben Ende der Neunziger einen Algorithmus entwickelt, der es ermöglicht nach Knotenpaaren zu suchen zwischen denen ein Pfad existiert, der einer gegebenen kontextfreien Grammatik genügt.Dies ist beispielsweise dann interessant, wenn man einen Kontrollflussgraphen einer Applikation betrachtet und herausfinden möchte, ob alle von einem Prozess beanspruchten Ressourcen auch wieder frei gegeben werden. Da ein solcher Graph wegen der Methodenaufrufe im Normalfall eine geschachtelte Struktur aufweist, reicht ein Algorithmus, der mit einfachen Pfadbeschreibungen (wie einem regulären Ausdruck) arbeitet, nicht aus.Der Autor Tim Steffens überträgt den genannten Algorithmus auf weitere Problemstellungen, beweist seine Korrektheit, gibt Laufzeitabschätzungen und beschreibt Möglichkeiten der Optimierung. Um die Praxistauglichkeit zu zeigen, werden die Ergebnisse von Performanzmessungen einer Beispielimplementierung vorgestellt.Das Buch richtet sich an jeden, der sich für Software Technik und/oder Graphentheorie interessiert.
Andere Kunden interessierten sich für
