Datové struktury a složitost algoritmů

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216305%3A26210%2F05%3APU53767" target="_blank" >RIV/00216305:26210/05:PU53767 - isvavai.cz</a>

Výsledek na webu

—

DOI - Digital Object Identifier

—

Jazyk výsledku

čeština

Název v původním jazyce

Datové struktury a složitost algoritmů

Popis výsledku v původním jazyce

Při řešení problémů operačního výzkumu, teorie grafů a dalších oblastí je potřebné navrhnout vhodný algoritmus, který řešení problému dokáže najít a navíc bude dostatečně efektivní. Řadu problémů lze řešit různými algoritmy, např. problém seřazení číselných položek podle vzestupného nebo sestupného uspořádání můžeme např. řešit algoritmem bublinového třídění s časovou složitostí O(n*n), kde n je počet seřazovaných položek, nebo mnohem sofistikovanějšími algoritmy QuickSort, HeapSort či MergeSort apod.,které mají časovou složitost O(n log n). Efektivitu algoritmu nemusí však určovat jen jeho procedurální část, ale lze ji ovlivnit i volbou datových struktur. Z důvodu omezeného rozsahu se zaměříme pouze problém hledání minimální kostry grafu a jeho efektivní implementaci pomocí speciálních datových struktur disjunktní množina a binární halda

Název v anglickém jazyce

Data Structures and Time Complexity of Algorithms

Popis výsledku anglicky

Solving problems of operations research, graph theory, and many others areas means to find a suitable and efficient algorithm. Many problems can be solved by various algorithms, e.g. sorting items in ascending or descending order can be solved by the BubbleSort algorithm with O(n*n) time complexity where n is a number of items, or by much more sophisticated algorithms such QuickSort, HeapSort or MergeSort that run O(n log n) time. The efficiency of algorithms, besides their procedural part, can also becontrolled by used data structures. In this paper, we present a simple algorithm for solving the minimum spanning tree problem and their more efficient implementation using a binary heap and disjoint sets.

Druh

D - Stať ve sborníku

CEP obor

BB - Aplikovaná statistika, operační výzkum

OECD FORD obor

—

Projekt

—

Návaznosti

Z - Vyzkumny zamer (s odkazem do CEZ)

Rok uplatnění

2005

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název statě ve sborníku

Sborník ze 14. semináře Moderní matematické metody v inženýrství 3mi

ISBN

80-248-0951-6

ISSN

—

e-ISSN

—

Počet stran výsledku

5

Strana od-do

198-202

Název nakladatele

VŠB-TU Ostrava

Místo vydání

Dolní Lomná u Jablunkova

Místo konání akce

Dolní Lomná u Jablunkova

Datum konání akce

30. 5. 2005

Typ akce podle státní příslušnosti

EUR - Evropská akce

Kód UT WoS článku

—