Seminář o dynamických datových strukturách - NTIN032

• Anglický název: Seminar on Dynamic Data Structures
• Zajišťuje: Katedra teoretické informatiky a matematické logiky (32-KTIML)
• Fakulta: Matematicko-fyzikální fakulta
• Platnost: od 2015
• Semestr: letní
• E-Kredity: 3
• Rozsah, examinace: letní s.:0/2, Z [HT]
• Počet míst: neomezen
• Minimální obsazenost: neomezen
• 4EU+: ne
• Virtuální mobilita / počet míst pro virtuální mobilitu: ne
• Stav předmětu: vyučován
• Jazyk výuky: čeština
• Způsob výuky: prezenční
• Garant: Mgr. Vladan Majerech, Dr.
• Vyučující: Mgr. Vladan Majerech, Dr.
• Třída: Informatika Mgr. - volitelný
• Kategorizace předmětu: Informatika > Teoretická informatika
• Prerekvizity : NTIN023

Anotace

čeština

Referativní seminář navazující na problematiku probíranou v TIN023.

Poslední úprava: T_KTI (10.04.2001)

angličtina

Report seminar concerning problems from TIN023.

Poslední úprava: T_KTI (10.04.2001)

Cíl předmětu

Referovat o nových a aktuáních výsledcích z dynamických datových struktur

Poslední úprava: T_KTI (23.05.2008)

Podmínky zakončení předmětu

Podmínkou udělení zápočet je aktivita na semináři (například ve formě referátu přiděleného článku).

Poslední úprava: Majerech Vladan, Mgr., Dr. (06.10.2017)

Sylabus

čeština

Plně dynamické (jak Insert, tak Delete) udržování bridgebloků a bloků v amortizovaném polylogaritmickém čase s použitím Top trees. Plně dynamické udržování komponent v amortizovaném čase $O(\log^2 n)$.

Globální vyhledávání v Top trees a jeho aplikace při udržování centra stromu v čase $O(\log n)$.

Obdobné problémy pro rovinné a/nebo orientované grafy. Závisí na aktuálním stavu výzkumu týkajícího se dynamických grafových problémů.

Poslední úprava: T_KTI (24.05.2004)

angličtina

Fully dynamic maintainance (both inserts and deletes) of bridge blocks and blocks in amortized polylog time using Top trees. Fully dynamic maintainance of components in $O(\log^2 n)$ amortized time.

Global search on Top trees and its application on maintaing tree center in $O(\log n)$ time.

Simillar problems for plan(e/ar) and/or directed graphs. Depends on current state of art dealing with dynamic graph problems.

Poslední úprava: T_KTI (24.05.2004)