|
Minimum Weight Triangulation (MWT)
Charvát, Pavel ; Kolingerová, Ivana (advisor) ; Ferko, Andrej (referee)
For a long time, it has been neither known whether MWT is solvable in a polynomial time nor whether it belongs to NP. As we now, its status still remain unknown. We present severalknown approaches to MWT such as modifications of the problem with known time complexity or various heuristics and approximations which allow us to find an exact or at least an approximate solution in a reasonable time. We compare the approximations in some particular situations. The main part of the work is devoted to a description and implementation of an efficient heuristic with (almost?) linear expected complexity for points uniformly distributed in some convex shape. The algorithm is a modification of Drysdale's algorithm for finding GT candidates and Beurouti's computation of the modified LMT-skeleton, where we add some proofs of the correctness. We are able to complete MWT from the graph of candidate edges in O(n · d3 + n · d2+k), where d is the the maximum degree and k is the maximum number of inner components of some skeleton face. Further, we suggest a new approximation of MWT with polynomial complexity in the worst case and (almost?) linear expected complexity, which only rarely differs from the optimal triangulation and has O(1) approximation factor in the worst case. This approximation combines the LMT-skeleton...
|
|
Two-dimensional Cutting Problems
Rada, Miroslav ; Fábry, Jan (advisor) ; Jablonský, Josef (referee)
The thesis first addresses the typology of cutting problems and their relationship to the packing problems. These are categorized (Wascher et al (2005)) according to 5 basic kriteria into the so-called "refined problem types", which is the sufficiently detailed and practical segmentation of cutting problems. The thesis deals with a selected sample of some of the most interesting algorithms from the wide range of those used to solve the cutting problems. The Viswanathan-Bagchi algorithm for the exact solution of constrainted two-dimensional orthogonal Cutting stock probléme with gillotine cuts is briefly described. It enables to process a wide range of additional problem constraints. The body of the thesis concentrates on heuristic algorithms used to solve orthogonal Open dimension problems. The Best-fit algorithm according to Burke et al. (2004) is described in detail. The work introduces two modifications of this algorithm that helped improve the solution in 42 out of the 89 benchmark problems, while a worse solution was achieved only in 10 of them. Moreover, new and more effective data structures and procedures that enable to solve the testing exercise with approx 50 000 rectangles in just about 2,5 seconds have been introduced.
|
|
Posouzení stylů vedení lidí a jejich dopadů na pracovní skupinu
Kinc, Petr
This bachelor thesis is dealing with issue, how the leadership style influ-ence employees and its impact on general satisfaction. Using data collected by questionnaire investigation, the leadership style and its impact on employees was found. On the base of empoyees and managers responses was identified strengts and weaknesses in leadership style of the manager. Afterwards, the proposals on modification of the leadership style, which will lead to better satisfaction of the working team, was recomended.
|
|
Algorithms for browsing 2D maze
Chvíla, Lukáš ; Jelínek, Aleš (referee) ; Žalud, Luděk (advisor)
This thesis describes an automatic path finding method in a 2D maze defined by bitmap evidence grids. The problem was solved in the programming language C# with the help of the straight line decomposition algorithm used for creating a network of potential routes. The algorithm assumes approximation of obstacles by vector polygons. The resulting path was found by the means of algorithm A*. The result is a path described by line segments. After some modifications, the path could be used for robot navigation.
|
|
Webmining
Ljubopytnov, Vladimír ; Húsek, Dušan (referee) ; Pokorný, Jaroslav (advisor)
This thesis focuses on mapping latest knowledge in the area of web mining with emphasis on document clustering. Most attention is given to the DOC projective clustering algorithm, a modification is presented for data with weighted dimensions. Algorithm is used for web search engine result clustering. Also, a clustering package with Google interface and phrase evaluation tool is implemented.
|
|
Analysis of transportation problem with bounded variables
Klasová, Petra ; Kalčevová, Jana (advisor) ; Šmídová, Milada (referee)
This bachelor thesis introduces the transportation problem with bounded variables, methods design and practical application of these methods on fictive data. The examples demonstrate the algorithm of optimal solution calculation. This thesis describes the modification of the north-west corner method, index method and Vogel's approximation method for problems with bounded variables, as well as the distribution and modified distribution method.
|
|
Artificial neural networks and their application in the assessment of insurance risks
Macek, Karel ; Jiroutek, Pavel (referee) ; Mrázová, Iveta (advisor)
The present work studies applicability of artificial neural networks in the assessment of insurance risk. Structure and function of multilayer perceptrons, Kohonen maps, Fuzzy ART networks, and Fuzzy ARTMAP networks are described. Concept of insurance risk is defined and the ratemaking by generalized linear models is introduced. Neural networks' methods for reduction of input space's dimension, knowledge extraction, and visualization are summed up. Data describing traffic accidents are acquainted and results achieved on them are presented. The work successfully demonstrates theoretically and experimentally that multilayer perceptrons approximate better than generalized linear models. Modification of multilayer perceptron estimated distribution function of total claim. Analysis performed by Kohonen map and by subsequent visualization detected two significant clusters. Analysis by Fuzzy ART network is presented as a part of new algorithm for reduction of input space's dimension. New algorithm inspired by Fuzzy ARTMAP network discovered a group of accidents where the claim is above average. This group is delimited by interpretable rules. Attached CD contains scripts for Matlab and MySQL that was used for mentioned analyses.
|
|
Professional Burden on Members of Crews Emergency Medical Service
VELDA, Jakub
Professional load of the Emergency medical service (EMS) workers is the topic of this bachelor?s work, and one of those so far not deeply-mapped themes. The aim of the work was to reveal the crucial factors arousing the professional load, their individual experiencing and handling by the EMS workers. Another goal was to find out about the rescuers? opinions and experience with the psychological help and its modifications. The research was realized qualitatively, using the semi-structured interviews with the members of the EMS rescue crews ? paramedics ? coming from the Central and Southern Bohemian Regions.The research proved the rescuers? personal experience with the critical events which the rescuers felt considerably influenced and distressed by, for a period of time. The respondents also perceive the psychological support provided by the regional EMS as highly-important factor, influencing their psychic stamina; one of the crucial premises for the rescuers? effective and flawless working. The psychological support is sensed as important in both, prevention and intervention. To improve the psychological comfort of the EMS workers, there might be the legislative duty of the employers, who should be obligatory to take care of the psychological side and comfort of their employees with the hazardous occupation.
|
|
Flow-shop Problems
Dyntar, Tomáš ; Tegze, Miron (advisor) ; Červinka, Michal (referee)
A description of flow shop and lot streaming including an example is given. Methods and algorithms ofr solving various modifications of the single job two-machine flow shop transfer lot sizing problem are shown. It starts with the calsulation of two lots (discrete), three lots (continuous) problem and then Trietsch s polynomial algorithm or an arbitrary number of sublots is introduced. This alogithm is then used for solving modifications with finding the proper number of sublots for given makespan, with constant or linear transfer times including variants with limited number of transfer machines or their limited capacity, with constant or linear set up times. A domed with both transfer and setup times is then developed and Trietschs algorithm modified. A theoreme by R. G. Vickson for solving multiple job lot streaming problem by treating the lot streaming problem for each job separately and then using Johnsons alogorithm is proposed to extend the results of the single job cases to those of multiple jobs. A known way to extend results to the three machine problem by treating each pair of successive machines separately or developing Trietschs algorithm for three machines is shown. Most of the procedures are illustrated in examples.
|
|
Route optimization for the parcels distribution
Ptáčková, Michaela ; Borovička, Adam (advisor) ; Čížek, Ondřej (referee)
This thesis deals with optimization problems of the parcels distribution. This issue can be solved on the ground of traveling salesman problem whose mathematical and economic model, including their modifications, are presented in the theoretical part of the thesis. We can solve these problems by using exact methods, heuristic and metaheuristic algorithms. In the theoretical part are described traveling salesman problem, traveling salesman problem with time windows, traveling salesman problem with multiple time windows and dynamic traveling salesman problem including possible ways of solution. In the practical part we can find application of problems on the real example, when we are finding the shortest possible route for the PPL's employee under different assumptions. The solution is obtained by using solver Gurobi within the modelling system MPL for Windows. In conclusion of the thesis the results are summarized and models are compared with each other.
|
guest ::
