Title: Sub-optimal algorithms for solving sliding puzzles Author: Petr Michalík Department: Department of Theoretical Computer Science and Mathematical Logic Supervisor: RNDr. Pavel Surynek, Ph.D. Supervisor's e-mail address: Pavel.Surynek@mff.cuni.cz In the present work techniques for solving the so-called sliding tiles puzzles, which generate optimal or sub-optimal solution, are studied. This thesis focuses especially on a specific variant of the puzzle: the (n^2-1)-puzzle. This work shows and compares current methods for solving this type of problem. A choosen method is a subject to a close analysis of complexity and is also implemented so that theoretical and experimental results could be confronted. An alternative sub-optimal algorithm is proposed and its theoretical analysis is presented. This algorithm is implemented as well and is compared with the existing algorithm. Both the theoretical analysis and the test results show that better (shorter) solutions can often be obtained using this alternative algorithm.

Nous décrivons une procédure numérique pour le recalage d'IRM cérébrales 3D. Le problème d'appariement est abordé à travers la distinction usuelle entre le modèle de déformation et le critère d'appariement. Le modèle de déformation est celui de l'anatomie computationnelle, fondé sur un groupe de difféomorphismes engendrés en intégrant des champs de vecteurs. Le décalage entre les images est évalué en comparant les lignes de niveau de ces images, représentées par un courant différentiel dans le dual d'un espace de champs de vecteurs. Le critère d'appariement obtenu est non local et rapide à calculer. On se place dans l'ensemble des difféomorphismes pour rechercher une déformation reliant les deux images. Pour cela, on minimise le critère en suivant le principe de l'algorithme sous-optimal. L'efficacité de l'algorithme est renforcée par une description eulérienne et périodique du mouvement. L'algorithme est appliqué pour le recalage d'images IRM cérébrale 3d, la procédure numérique menant à ces résultats est intégralement décrite. Nos travaux concernent aussi l'analyse des propriétés de l'algorithme. Pour cela, nous avons simplifié l'équation représentant l'évolution de l'image et étudié l'équation simplifiée en utilisant la théorie des solutions de viscosité. Nous étudions aussi le problème de détection de rupture dans la variance d'un signal aléatoire gaussien. La spécificité de notre modèle vient du cadre infill, ce qui signifie que la distribution des données dépend de la taille de l'échantillon. L'estimateur de l'instant de rupture est défini comme le point maximisant une fonction de contraste. Nous étudions la convergence de cette fonction et ensuite la convergence de l'estimateur associé. L'application la plus directe concerne l'estimation de changement dans le paramètre de Hurst d'un mouvement brownien fractionnaire. L'estimateur dépend d'un paramètre p > 0 et nos résultats montrent qu'il peut être intéressant de choisir p < 2. / We present a numerical procedure for the matching of 3D MRI. The problem of image matching is addressed through the usual distinction between the deformation model and the matching criterion. The deformation model is based on the theory of computational anatomy and the set of deformations is a group of diffeomorphisms generated by integrating vector fields. The discrepancy between the two images is evaluated through comparisons of level lines represented by a differential current in the dual of a space of vector fields. This representation leads to a quickly computable non-local criterion. Then, the optimisation method is based on the minimization of the criterion following the idea of the so-called sub-optimal algorithm. We take advantage of the eulerian and periodical description of the algorithm to get an efficient numerical procedure. This algorithm can be used to deal with 3d MR images and numerical experiences are presented. In an other part, we focus on theoretical properties of the algorithm. We begin by simplifying the equation representing the evolution of the deformed image and we use the theory of viscosity solutions to study the simplified equation. The second issue we are interested in is the change-point estimation for a gaussian sequence with change in the variance parameter. The main feature of our model is that we work with infill data and the nature of the data can evolve jointly with the size of the sample. The usual approach suggests to introduce a contrast function and using the point of its maximum as a change-point estimator. We first get an information about the asymptotic fluctuations of the contrast function around its mean function. Then, we focus on the change-point estimator and more precisely on the convergence of this estimator. The most direct application concerns the detection of change in the Hurst parameter of a fractional brownian motion. The estimator depends on a parameter p > 0, generalizing the usual choice p = 2. We present some results illustrating the advantage of a parameter p < 2.