Detail publikace

Datové struktury a složitost algoritmů

ŠEDA, M.

Originální název

Datové struktury a složitost algoritmů

Anglický název

Data Structures and Time Complexity of Algorithms

Typ

článek ve sborníku ve WoS nebo Scopus

Jazyk

čeština

Originální abstrakt

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

Anglický abstrakt

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 be controlled 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.

Klíčová slova v angličtině

disjoint set, priority queue, binary heap, spanning tree

Autoři

ŠEDA, M.

Rok RIV

2005

Vydáno

30. 5. 2005

Nakladatel

VŠB-TU Ostrava

Místo

Dolní Lomná u Jablunkova

ISBN

80-248-0951-6

Kniha

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

Strany od

198

Strany do

202

Strany počet

5

BibTex

@inproceedings{BUT15921,
  author="Miloš {Šeda}",
  title="Datové struktury a složitost algoritmů",
  booktitle="Sborník ze 14. semináře Moderní matematické metody v inženýrství 3mi",
  year="2005",
  pages="5",
  publisher="VŠB-TU Ostrava",
  address="Dolní Lomná u Jablunkova",
  isbn="80-248-0951-6"
}