Cieľom tejto práce je návrh analýzy tvaru haldy vhodnej pre potreby analyzátora 2LS. 2LS je nástroj pre analýzu C programov založený na automatickom odvodzovaní invariantov s použitím SMT solvera. Navrhované riešenie obsahuje spôsob reprezentácie tvaru programovej haldy pomocou logických formulí nad teóriou bitových vektorov. Tie sú následne využité v SMT solveri pre predikátovú logiku prvého rádu na odvodenie invariantov cyklov a súhrnov jednotlivých funkcií analyzovaného programu. Náš prístup je založený na ukazateľových prístupových cestách, ktoré vyjadrujú dosiahnuteľnosť objektov na halde z ukazateľových premenných. Informácie získané z analýzy môžu byť využité na dokázanie rôznych vlastností programu súvisiacich s prácou s dynamickýcmi dátovými štruktúrami. Riešenie bolo implementované v rámci nástroja 2LS. S jeho použitím došlo k výraznému zlepšeniu schopnosti 2LS analyzovať programy pracujúce s ukazateľmi a dynamickými dátovými štruktúrami. Toto je demonštrované na sade experimentov prevzatých zo známej medzinárodnej súťaže vo verifikácii programov SV-COMP a iných experimentoch.

La complexité de la forme de la surface est une caractéristique morphologique des surfaces pliées. Dans cette thèse, nous visons à développer des méthodes spectrales pour quantifier cette caractéristique du cortex cérébral humain reconstruit à partir d'images MR structurales. Tout d'abord, nous suggérons certaines propriétés qu'une mesure standard de la complexité de surface devrait posséder. Ensuite, nous proposons deux définitions claires de la complexité de la surface en fonction des propriétés de flexion de surface. Pour quantifier ces définitions, nous avons étendu la transformée de Fourier à fenêtres illustrée récemment pour transformer en maillage des surfaces. Grâce à certaines expériences sur les surfaces synthétiques, nous montrons que nos mesures basées sur la courbure permettent de surmonter les surfaces classiques basées sur la surface, ce qui ne distingue pas les plis profonds des oscillants ayant une surface égale. La méthode proposée est appliquée à une base de données de 124 sujets adultes en bonne santé. Nous définissons également la complexité de la surface par la régularité de Hölder des mouvements browniens fractionnés définis sur les collecteurs. Ensuite, pour la première fois, nous développons un algorithme de régression spectrale pour quantifier la régularité de Hölder d'une surface brownienne fractionnée donnée en estimant son paramètre Hurst H. La méthode proposée est évaluée sur un ensemble de sphères browniennes fractionnées simulées. En outre, en supposant que le cortex cérébral est une surface brownienne fractionnée, l'algorithme proposé est appliqué pour estimer les paramètres Hurst d'un ensemble de 14 corticus cérébraux fœtaux. / Surface shape complexity is a morphological characteristic of folded surfaces. In this thesis, we aim at developing some spectral methods to quantify this feature of the human cerebral cortex reconstructed from structural MR images. First, we suggest some properties that a standard measure of surface complexity should possess. Then, we propose two clear definitions of surface complexity based on surface bending properties. To quantify these definitions, we extended the recently introduced graph windowed Fourier transform to mesh model of surfaces. Through some experiments on synthetic surfaces, we show that our curvature-based measurements overcome the classic surface area-based ones which may not distinguish deep folds from oscillating ones with equal area. The proposed method is applied to a database of 124 healthy adult subjects. We also define the surface complexity by the Hölder regularity of fractional Brownian motions defined on manifolds. Then, for the first time, we develop a spectral-regression algorithm to quantify the Hölder regularity of a given fractional Brownian surface by estimating its Hurst parameter H. The proposed method is evaluated on a set of simulated fractional Brownian spheres. Moreover, assuming the cerebral cortex is a fractional Brownian surface, the proposed algorithm is applied to estimate the Hurst parameters of a set of 14 fetal cerebral cortices.

Gegenstand der vorliegenden Dissertation ist die Entwicklung von Algorithmen und Methoden mit dem Ziel, Archäologen bei der täglichen wissenschaftlichen Arbeit zu unterstützen. Im Teil I werden Ideen präsentiert, mit denen sich die extrem zeitintensive und stellenweise stupide Funddokumentation beschleunigen lässt. Es wird argumentiert, dass das dreidimensionale Erfassen der Fundobjekte mittels Laser- oder Streifenlichtscannern trotz hoher Anschaffungskosten wirtschaftlich und vor allem qualitativ attraktiv ist. Mithilfe von nicht fotorealistischen Visualisierungstechniken können dann wieder aussagekräftige, aber dennoch objektive Bilder generiert werden. Außerdem ist speziell für Gefäße eine vollautomatische und umfassende Merkmalserhebung möglich. Im II. Teil gehen wir auf das Problem der automatisierten Gefäßklassifikation ein. Nach einer theoretischen Betrachtung des Typbegriffs in der Archäologie präsentieren wir eine Methodologie, in der Verfahren sowohl aus dem Bereich des unüberwachten als auch des überwachten Lernens zum Einsatz kommen. Besonders die letzteren haben sich dabei als überaus praktikabel erwiesen, um einerseits unbekanntes Material einer bestehenden Typologie zuzuordnen, andererseits aber auch die Struktur der Typologie selbst kritisch zu hinterfragen. Sämtliche Untersuchungen haben wir beispielhaft an den bronzezeitlichen Gräberfeldern von Kötitz, Altlommatzsch (beide Lkr. Meißen), Niederkaina (Lkr. Bautzen) und Tornow (Lkr. Oberspreewald-Lausitz) durchgeführt und waren schließlich sogar in der Lage, archäologisch relevante Zusammenhänge zwischen diesen Fundkomplexen herzustellen. / The topic of the dissertation at hand is the development of algorithms and methods aiming at supporting the daily scientific work of archaeologists. Part I covers ideas for accelerating the extremely time-consuming and often tedious documentation of finds. It is argued that digitizing the objects with 3D laser or structured light scanners is economically reasonable and above all of high quality, even though those systems are still quite expensive. Using advanced non-photorealistic visualization techniques, meaningful but at the same time objective pictures can be generated from the virtual models. Moreover, specifically for vessels a fully-automatic and comprehensive feature extraction is possible. In Part II, we deal with the problem of automated vessel classification. After a theoretical consideration of the type concept in archaeology we present a methodology, which employs approaches from the fields of both unsupervised and supervised machine learning. Particularly the latter have proven to be very valuable in order to assign unknown entities to an already existing typology, but also to challenge the typology structure itself. All the analyses have been exemplified by the Bronze Age cemeteries of Kötitz, Altlommatzsch (both district of Meißen), Niederkaina (district of Bautzen), and Tornow (district Oberspreewald-Lausitz). Finally, we were even able to discover archaeologically relevant relationships between these sites.

Tato práce se zaměřuje na konečné automaty nad konečnými slovy a konečnými stromy, a použití těchto automatů při formální verifikaci nekonečně stavových systémů. Práce se nejdříve věnuje rozšíření existujícího přístupu pro verifikaci programů které manipulují s haldou (konkrétně programů s dynamickými datovými strukturami), jenž je založen na stromových automatech. V práci je navrženo několik rozšíření tohoto přístupu, jako například jeho plná automatizace či jeho rozšíření o podporu uspořádaných dat. V práci jsou popsány nové rozhodovací procedury pro dvě logiky, které jsou často používány ve formální verifikaci: pro separační logiku a pro slabou monadickou druhořádovou logiku s následníkem. Obě tyto rozhodovací procedury jsou založeny na převodu jejich problému do automatové domény a následné manipulaci v této cílové doméně. Posledním přínosem této práce je vývoj nových algoritmů k efektivní manipulaci se stromovými automaty, s důrazem na testování inkluze jazyků těchto automatů a manipulaci s automaty s velkými abecedami, a implementace těchto algoritmů v knihovně pro obecné použití. Tyto vyvinuté algoritmy jsou použity jako klíčová technologie, která umožňuje použití výše uvedených technik v praxi.

It is known that fission yeast Schizosaccharomyces pombe maintains its nuclear envelope during mitosis and it undergoes an interesting shape change during cell division - from a spherical via an ellipsoidal and a peanut-like to a dumb-bell shape. However, the biomechanical system behind this amazing transformation is still not understood. What we know is, that the shape must change due to forces acting on the membrane surrounding the nucleus and the microtubule based mitotic spindle is thought to play a key role. To estimate the locations and directions of the forces, the shape of the nucleus was recorded by confocal light microscopy. But such data is often inhomogeneously labeled with gaps in the boundary, making classical segmentation impractical. In order to accurately determine the shape we developed a global parametric shape description method, based on a Fourier coordinate expansion. The method implicitly assumes a closed and smooth surface. We will calculate the geometrical properties of the 2-dimensional shape and extend it to 3-dimensional properties, assuming rotational symmetry. Using a mechanical model for the lipid bilayer and the so called Helfrich-Canham free energy we want to calculate the minimum energy shape while respecting system-specific constraints to the surface and the enclosed volume. Comparing it with the observed shape leads to the forces. This provides the needed research tools to study forces based on images.

It is known that fission yeast Schizosaccharomyces pombe maintains its nuclear envelope during mitosis and it undergoes an interesting shape change during cell division - from a spherical via an ellipsoidal and a peanut-like to a dumb-bell shape. However, the biomechanical system behind this amazing transformation is still not understood. What we know is, that the shape must change due to forces acting on the membrane surrounding the nucleus and the microtubule based mitotic spindle is thought to play a key role. To estimate the locations and directions of the forces, the shape of the nucleus was recorded by confocal light microscopy. But such data is often inhomogeneously labeled with gaps in the boundary, making classical segmentation impractical. In order to accurately determine the shape we developed a global parametric shape description method, based on a Fourier coordinate expansion. The method implicitly assumes a closed and smooth surface. We will calculate the geometrical properties of the 2-dimensional shape and extend it to 3-dimensional properties, assuming rotational symmetry. Using a mechanical model for the lipid bilayer and the so called Helfrich-Canham free energy we want to calculate the minimum energy shape while respecting system-specific constraints to the surface and the enclosed volume. Comparing it with the observed shape leads to the forces. This provides the needed research tools to study forces based on images.

Tato práce se věnuje vylepšení současného stavu formalní analýzy a verifikace založené na automatech a zaměřené na systémy s nekonečnými stavovými prostory. V první části se práce zabývá dvěma rozhodovacími procedurami pro logiku WS1S, které jsou založené na korespondenci mezi formulemi logiky WS1S a konečnými automaty. První metoda je založena na tzv. antiřetězcích, ale, je limitována pouze na formule v prenexním normálním tvaru. Následně je tento přístup zobecněn na libovolné formule, jsou zavedeny tzv. jazykové termy a na jejich základě je navržena nová procedura, která pracuje za běhu a zpracovává tyto termy "líným" způsobem. Abychom získali efektivní rozhodovací proceduru, je dále navržena sada optimalizací (přičemž některé nejsou limitovány pouze pro naše přístupy). Obě metody jsou srovnány s ostatními nástroji implementujícími různé známé rozhodovací procedury. Získané výsledky jsou povzbuzující a ukazují, že použitelnost logiky WS1S je možno rozšířit na širší třídu formulí. V druhé části se práce zabývá analýzou mezí zdrojů programů manipulujících s haldou. Je zde navržena nová třída tzv. tvarových norem založených na délkách cest mezi význačnými místy na haldě, které jsou automaticky odvozovány z analyzovaného programu. Na základě této třídy norem je dále navržen kalkul, který je schopen přesně odvodit změny odvozených normů a použít je k vygenerování odpovídající celočíselné reprezentace vstupního programu, která je následně využita pro následovanou dedikovanou analýzou mezí zdrojů. Tato metoda byla implementována nad analýzou tvaru založenou na tzv. lesních automatech, implementovanou v nástroji Forester, a dále byl použit dobře zavedený analyzátor mezí zdrojů, implementovaný v nástroji Loopus. V experimentální evaluaci bylo ukázáno, že je opravdu takto získán silný analyzátor, který je schopen odvodit meze programů, které ještě nikdy plně automatizovaně odvozené nebyly.