TY  - THES
A3  - Blömer, Johannes
A3  - Eisenbrand, Friedrich
AB  - Gitter sind klassische Objekte aus der Geometrie der Zahlen. Ein Gitter ist definiert als eine diskrete Untergruppe des n dimensionalen Vektorraumes über den reellen Zahlen. Diese Dissertationsschrift beschäftigt sich mit der algorithmischen Komplexität von vier klassischen Problemen aus der Geometrie der Zahlen, dem Problem des kürzesten Gittervektors, dem Problem der sukzessiven Minima, dem Problem der kürzesten linear unabhängigen Gittervektoren sowie dem Problem des nächsten Gittervektors. Diese Probleme können bezüglich jeder beliebigen Norm definiert werden. Der Schwerpunkt dieser Dissertation liegt auf der Untersuchung der algorithmischen Komplexität dieser oben erwähnten Gitterprobleme mit einem speziellen Fokus auf ihrer Lösbarkeit bezüglich allgemeiner, nicht euklidischer Normen. Aufbauend auf Algorithmen von Ajtai, Kumar und Sivakumar ([AKS01],[AKS02]) für das Problem des kürzesten Gittervektors und das Problem des nächsten Gittervektors beschreiben wir in dieser Arbeit randomisierte Algorithmen mit einfach exponentieller Laufzeit für alle vier erwähnten Gitterprobleme. Diese Algorithmen lösen das Problem des kürzesten Gittervektors sowie wie eingeschränkte Varianten der anderen Gitterprobleme exakt. Für die allgemeinen Varianten des Problems der sukzessiven Minima, des Problems der kürzesten linear unabhängigen Gittervektoren sowie des Problems des nächsten Gittervektors beschreiben wir randomisierte Algorithmen mit einfach exponentieller Laufzeit, die diese Probleme fast optimal lösen. Für das Problem des nächsten Gittervektors entwickeln wir in dieser Arbeit auf Grundlage einer Technik von Lenstra ([Len83]) für ganzzahlige Programmierung einen deterministischen Algorithmus, der das Problem exakt löst und dabei lediglich polynomiellen Platz benötigt.
AU  - Naewe, Stefanie
DA  - 2011
DP  - Universität Paderborn
LA  - eng
N1  - Tag der Verteidigung: 28.10.2011
N1  - Paderborn, Univ., Diss., 2011
PB  - Veröffentlichungen der Universität
PY  - 2011
T2  - Institut für Informatik
TI  - Algorithms for lattice problems with respect to general norms
UR  - https://nbn-resolving.org/urn:nbn:de:hbz:466:2-8047
Y2  - 2024-12-26T18:36:53
ER  -