Forbedring af prioritetskørstrukturers effektivitet: Anvendelse af datastrukturelle transformationer og talsystemer

Ph.d.-afhandling af Claus Jensen

Abstrakt

I denne afhandling undersøger vi sammenligningskompleksiteten for de operationer som bruges til at manipulere værstefaldseffektive datastrukturer. Studiet har fokuseret på design og analyse af prioritetskøer og min-max prioritetskøer. En prioritetskø er en datastruktur som indeholder en samling af elementer og som understøtter operationerne find-min, insert, extract, decrease, delete og meld; en min-max prioritetskø understøtter også operationen find-max.

Værstefaldseffektiviteten af prioritetskøer og min-max prioritetskøer forbedres ved hjælp af strukturelle transformationer og talsystemer. Studiet har været koncentreret om at forbedre den førende konstant i værstefaldssammenligningskompleksiteten for delete operationen, samtidigt med at værstefaldsomkostningen for en delmængde af andre operationer holdes konstant. Afhandlingens hovedresultater er:

• Vi har udviklet en priotetskø som for find-min, insert, og delete har en sammenligningskompleksitet som er optimal op til de konstante additive faktorer, samtidig med at værstefaldsomkostningen for find-min og insert er konstant
• Vi introducerer en prioritetskø som for delete har en sammenligningskompleksitet som er konstant-faktor optimal (dvs. faktorkonstanten for det dominerende led er optimal), samtidig med at værstefaldsomkostningen for find-min, insert og decrease er konstant
• Vi beskriver to nye strukturelle transformationer til at konstruere min-max prioritetskøer med udgangspunkt i prioritetskøer
• Vi introducerer tre nye talsystemer

Det er muligt at downloade følgende filer:

• Afhandlingsteksten
• Præsentationen fra det mundtlige forsvar

Denne side på engelsk