|
|
Distance Estimation in Wireless Ad-hoc Network
Botta, Miroslav ; Mráz, Ľubomír (oponent) ; Šimek, Milan (vedoucí práce)
The work deals with processing of radio received signal strength in IEEE 802.15.4 which communicates in 2.4 GHz ISM band. The signal is processed by the three approximation methods. They are tested for their effectiveness for measuring in different radio environments. Furthermore, the work deals with calculation of the most efficient coefficients for distance calculating by radio transmission fucntions. It defines the issues of such solutions on practical examples. The work also deals with the experimental algorithm for implementing dynamic calibration of the coefficients. It describes the design, processing and verification of this system in practice.
|
|
| |
|
|
Strongly Connected Steiner Subgraphs with small number of Steiner vertices
Kemény, Tamás Dávid ; Feldmann, Andreas Emil (vedoucí práce) ; Suchý, Ondřej (oponent)
Title: Strongly Connected Steiner Subgraphs with Small Number of Steiner Vertices Author: Tamás Dávid Kemény Department: Department of Applied Mathematics Supervisor: Dr. Andreas Emil Feldmann, Department of Applied Mathematics Abstract: Two well-established methods of dealing with hard optimization problems have been to develop approximation and parameterized algorithms. Recent results have shown that for some problems, it is only by combining these two approaches, into so-called pa- rameterized approximation algorithms, that we are able to efficiently find solutions that are of reasonable quality. This is the viewpoint from which we study the problem known as the Strongly Connected Steiner Subgraph problem, where a set of terminal vertices of an edge-weighted directed graph needs to be strongly-connected in the cheapest way possible. Keywords: Strongly Connected Steiner Subgraphs, Parameterized Algorithms, Approxi- mation Algorithms, Bidirected Graphs iii
|
|
|
Online Bin Stretching: Algorithms and Computer Lower Bounds
Böhm, Martin ; Sgall, Jiří (vedoucí práce) ; Durr, Christoph (oponent) ; Kellerer, Hans (oponent)
Online Bin Stretching: algoritmy a strojové dolní odhady Autor: Martin Böhm Abstrakt: Zabýváme se problémem v oblasti semi-online algoritmů, který se nazývá Online Bin Stretching. Můžeme tento problém chápat jako pro- blém opětovného pakování předmětů: cílem algoritmu je zapakovat před- měty různých velikostí do m kontejnerů identické kapacity R > 1. Objekty na vstupu přicházejí jeden po druhém a algoritmus musí přiřadit předmět do kontejneru dříve, než se objeví předmět další. Zvláštnost tohoto konkrétního problému je existence zaručené vlastnosti vstupu, kterou algoritmus zná. Algoritmus totiž už od začátku vstupu má zaručeno, že existuje pakování celého vstupu do m kontejnerů kapacity 1. Naším cílem je navrhnout algoritmy, které pakují jeden objekt po dru- hém a kterým se podaří vstup zapakovat do co nejmenší možné kapacity R. V této dizertační práci představíme několik nových výsledků kolem On- line Bin Stretchingu. Zaprvé, navrhneme algoritmus, který napakuje všechny objekty do m kontejnerů s kapacitou 1,5, a to pro libovolnou počáteční hodnotu m. Zadruhé se soustředíme na podproblém, ve kterém je počet kontejnerů nízký a pevný, například 3. Pro tento model představíme algo- ritmus, který zapakuje vstup do 3 binů s kapacitou 1,375. Nakonec navrhneme a naimplementujeme počítačový program, který bude...
|
|
|
Algoritmické problémy související s průnikovými grafy
Ivánek, Jindřich ; Pergel, Martin (vedoucí práce) ; Rytíř, Pavel (oponent)
V práci studujeme dva problémy pokrytí klikami, které mají zajímavé aplikace při reprezentaci tzv. k -bendovými průnikovými grafy: problém stupně pokrytí hran klikami a problém vrstevnatého pokrytí hran klikami. Zaměřujeme se na složitost těchto problémů a polynomiální algoritmy pro omezené třídy grafů. Hlavními výsledky práce je NP-úplnost problému vrstevnatého pokrytí hran klikami, polynomiální algoritmus pro tento problém na podtřídě grafů bez diamantů a také některé horní odhady pro konkrétní třídy grafů.
|
|
| |
|
|
Distance Estimation in Wireless Ad-hoc Network
Botta, Miroslav ; Mráz, Ľubomír (oponent) ; Šimek, Milan (vedoucí práce)
The work deals with processing of radio received signal strength in IEEE 802.15.4 which communicates in 2.4 GHz ISM band. The signal is processed by the three approximation methods. They are tested for their effectiveness for measuring in different radio environments. Furthermore, the work deals with calculation of the most efficient coefficients for distance calculating by radio transmission fucntions. It defines the issues of such solutions on practical examples. The work also deals with the experimental algorithm for implementing dynamic calibration of the coefficients. It describes the design, processing and verification of this system in practice.
|
|
| |
host ::
RSS.