This thesis deals with the distributed and stochastic algorithms, including testing their convergence in networks. The theoretical part briefly describes above mentioned algorithms, including their division, problems, advantages and disadvantages. Futhermore, two distributed algorithms and two stochastic algorithms are chosen. The practical part is done by comparing the speed of convergence on various network topologies in MATLAB.

The presented diploma thesis deals with the division of points into homogeneous groups. The work provides a broad overview of the current state in this topic and a brief explanation of the main segmentation methods principles. From the analysis of the articles are selected and programmed five algorithms. The work defines the principles of selected algorithms and explains their mathematical models. For each algorithm is also given a code design description. The diploma thesis also contains a cross comparison of segmentation capabilities of individual algorithms on created as well as on measured data. The results of the curves extraction are compared with each other graphically and numerically. At the end of the work is a comparison graph of time dependence on the number of points and the table that includes a mutual comparison of algorithms in specific areas.

Sight-reading is the act of performing a piece of music at first sight. This can be a difficult task to master, because it requires extensive knowledge of music theory, practice, quick thinking, and most importantly, a wide variety of musical material. A musician can only effectively sight-read with a new piece of music. This not only requires many resources, but also musical pieces that are challenging while also within a player's abilities. This thesis presents PiaNote, a sight-reading web application for pianists that algorithmically generates music based on human performance. PiaNote's goal is to alleviate some of the hassles pianists face when sight-reading. PiaNote presents musicians with algorithmically generated pieces, ensuring that a musician never sees the same piece of music twice. PiaNote also monitors player performances in order to intelligently present music that is challenging, but within the player's abilities. As a result, PiaNote offers a sight-reading experience that is tailored to the player. On a broader level, this thesis explores different methods in effectively creating a sight-reading application. We evaluate PiaNote with a user study involving novice piano players. The players actively practice with PiaNote over three fifteen-minute sessions. At the end of the study, users are asked to determine whether PiaNote is an effective practice tool that improves both their confidence in sight-reading and their sight-reading abilities. Results suggest that PiaNote does improve user's sight-reading confidence and abilities, but further research must be conducted to clearly validate PiaNote's effectiveness. We conclude that PiaNote has potential to become an effective sight-reading application with slight improvements and further research.

Tato práce je psaná v angličtině a je zaměřená na problematiku ekvalizace v digitálních komunikačních systémech. Teoretická část zahrnuje stručné pozorování různých způsobů návrhu ekvalizérů. Praktická část se zabývá implementací nejčastěji používaných ekvalizérů a s jejich adaptačními algoritmy. Cílem praktické části je porovnat jejich charakteristiky a odhalit činitele, které ovlivňují kvalitu ekvalizace. V rámci problematiky ekvalizace jsou prozkoumány tři typy ekvalizérů. Lineární ekvalizér, ekvalizér se zpětnou vazbou a ML (Maximum likelihood) ekvalizér. Každý ekvalizér byl testován na modelu, který simuloval reálnou přenosovou soustavu s komplexním zkreslením, která je složena z útlumu, mezisymbolové interference a aditivního šumu. Na základě implenentace byli určeny charakteristiky ekvalizérů a stanoveno že optimální výkon má ML ekvalizér. Adaptační algoritmy hrají významnou roli ve výkonnosti všech zmíněných ekvalizérů. V práci je nastudována skupina stochastických algoritmů jako algoritmus nejmenších čtverců(LMS), Normalizovaný LMS, Variable step-size LMS a algoritmus RLS jako zástupce deterministického přístupu. Bylo zjištěno, že RLS konverguje mnohem rychleji, než algoritmy založené na LMS. Byly nastudovány činitele, které ovlivnili výkon popisovaných algoritmů. Jedním z důležitých činitelů, který ovlivňuje rychlost konvergence a stabilitu algoritmů LMS je parametr velikosti kroku. Dalším velmi důležitým faktorem je výběr trénovací sekvence. Bylo zjištěno, že velkou nevýhodou algoritmů založených na LMS v porovnání s RLS algoritmy je, že kvalita ekvalizace je velmi závislá na spektrální výkonové hustotě a a trénovací sekvenci.

This thesis deals with detection of the natural frequencies in the material structures using algorithms working in real-time. It is used for detection of material damage. Is described physic of material, issue of discrete signals and their spectrums and methods for the calculation of the spectral components of the signal. These metods are implemented to Matlab programming environment. Methods are tested with simulated data and real signal.

The main topic of this thesis is the practical use of OpenCL at AVG company. AVG is looking for ways to decrease hardware requirement of their security product and also to decrease computation time of some algorithms. Using OpenCL is one way to achieve this requirement. Significant part of this thesis deals with optimization strategies for AMD and NVIDIA graphics cards as they are most common cards among users. Practical part of the thesis describes parallelization of two algorithms, their analysis and implementation. After that, the obtained results are presented and cases in which the use of OpenCL is beneficial are identified. As a part of implementation, library containing various utility functions which can aid programmers to implement OpenCL based code was developed.

Les travaux de recherche de cette thèse concernent l'encadrement de la constante de Markov Bernstein pour la norme L2 associée aux mesures de Jacobi et Gegenbauer généralisée. Ce travail est composé de deux parties : dans la première partie, nous avons développé une généralisation de l'algorithme qd pour les matrices symétriques définies positives à largeur de bande $\ell$ et nous avons construit l'algorithme qd pour les matrices de Jacobi par blocs. Ensuite, nous l'avons généralisé aux cas des matrices par bloc à largeur de bande $\ell$. Ces algorithmes nous permettent de trouver un majorant de la constante. Enfin, nous avons développé le déterminant caractéristique d'une matrice symétrique définie positive pentadiagonale, ce qui nous permet d'obtenir un minorant de la constante en utilisant la méthode de Newton. La deuxième partie est consacrée à l'application de tous les outils développés à l'encadrement de la constante de Markov Bernstein pour la norme L2 associée à la mesure de Gegenbauer généralisée. / The aim of this thesis is to find the lower and upper bounds of the constant whichappears in the Markov Bernstein inequalities in L2 norm associated to the Jacobiand generalized Gegenbauer measures. In this work the qd algorithm is studied forobtaining some properties about the asymptotic behavior of some eigenvalues ofband matrices and block band matrices. These eigenvalues are linked to the MarkovBernstein constant. The application of all the tools developed for obtaining lowerand upper bounds of the Markov Bernstein constant in L2 norm associated to thegeneralized Gegenbauer measure is given.

A grid graph is a finite embedded subgraph of the infinite integer grid. A solid grid graph is a grid graph without holes, i.e., each bounded face of the graph is a unit square. The reconfiguration problem for Hamiltonian cycle or path in a sold grid graph G asks the following question: given two Hamiltonian cycles (or paths) of G, can we transform one cycle (or path) to the other using some "operation" such that we get a Hamiltonian cycle (or path) of G in the intermediate steps (i.e., after each application of the operation)? In this thesis, we investigate reconfiguration problems for Hamiltonian cycles and paths in the context of two types of solid graphs: rectangular grid graphs, which have a rectangular outer boundary, and L- shaped grid graphs, which have a single reflex corner on the outer boundary, under three operations we define, flip, transpose and switch, that are local in the grid. Reconfiguration of Hamiltonian cycles and paths in embedded grid graphs has potential applications in path planning, robot navigation, minimizing turn costs in milling problems, minimizing angle costs in TSP, additive manufacturing and 3D printing, and in polymer science. In this thesis, we introduce a complexity measure called bend complexity for Hamiltonian paths and cycles in grid graphs, and using those measures we measure complexity of a grid graph G and give upper and lower bounds on the maximum bend complexity of an mxn grid graph. We define three local operations, flip, transpose and switch, where local means that the operations are applied on vertices that are close in the grid graph but may not be close on the path or cycle. We show that any Hamiltonian cycle or path can be reconfigured to any other Hamiltonian cycle or path in an mxn rectangular grid graph, where m <= 4, using O(|G|) flips and transposes, regardless of the bend complexities of the two cycles. We give algorithms to reconfigure 1-complex Hamiltonian cycles in a rectangular or L-shaped grid graph G using O(|G|) flips and transposes, where the intermediate steps are also 1-complex Hamiltonian cycles. Finally, we establish the structure of 1-complex Hamiltonian paths between diagonally opposite corners s and t of a rectangular grid graph, and then provide a strategy, based on work in progress, for designing an algorithm to reconfigure between any two 1-complex s, t Hamiltonian paths using switch operations. / Graduate

Cette thèse étudie la détection de communautés dans le contexte des réseaux sociaux. Un réseau social peut être modélisé par un graphe dans lequel les sommets représentent les membres et les arêtes représentent les relations entre les membres. En particulier, j'étudie quatre différentes définitions de communauté. D'abord, une structure en communautés peut être définie par une partition des sommets telle que tout sommet a une plus grande proportion de voisins dans sa partie que dans toute autre partie. Cette définition peut être adaptée pour l'étude d'une seule communauté. Ensuite, une communauté peut être vue comme un sous graphe tel que tout couple de sommets sont à distance 2 dans ce sous graphe. Enfin, dans le contexte des sites de rencontre, je propose d'étudier une définition de communauté potentielle dans le sens où les membres de la communauté ne se connaissent pas, mais sont liés par des connaissances communes. Pour ces trois définitions, j'étudie la complexité computationnelle et l'approximation de problèmes liés à l'existence ou la recherche de telles communautés dans les graphes. / This thesis deals with community detection in the context of social networks. A social network can be modeled by a graph in which vertices represent members, and edges represent relationships. In particular, I study four different definitions of a community. First, a community structure can be defined as a partition of the vertices such that each vertex has a greater proportion of neighbors in its part than in any other part. This definition can be adapted in order to study only one community. Then, a community can be viewed as a subgraph in which every two vertices are at distance 2 in this subgraph. Finally, in the context of online meetup services, I investigate a definition for potential communities in which members do not know each other but are related by their common neighbors. In regard to these proposed definitions, I study computational complexity and approximation within problems that either relate to the existence of such communities or to finding them in graphs.

This thesis deals with factors influencing the average speed on Czech roads. Curvature and inclination of the slopes were selected among the main factors influencing the average speed. Until now, these factors have been considered at discrete intervals, not as continuous functions. The function for calculating the curvature is based on ČSN 73 6101, where the equation with all variables is directly defined. The functional relationship for the movement of vehicles in sloping terrain was created from data from scientific articles. Therefore, an algorithm was implemented in this thesis, which can automatically evaluate the average speed on the road network. Python was used to implement this algorithm. Furthermore, there is a testing section for travel times, which is validated using route planners and also supported by extensive field research. Testing took place in GIS using network analysis methods. Testing has shown that the inclusion of curvature and inclination will significantly improve the calculation of travel times. key words: network analyst, curvature, gis, algorithm