COMBINATORIAL ANALYSE

Autor: ELIZALDE TORRENT SERGI.
Jahr: 2003.
Universität: POLITÉCNICA DE CATALUÑA [www.upc.edu].
Ort der Lesung: SALA D'ACTES DE LA FME.
Ort der Vorbereitung: U FACULTAT DE MATEMATIQUES I ESTADISTICA SUD.

Autor: HIDALGO DOBLADO MARIA JOSE.
Jahr: 2003.
Universität: SEVILLA [www.us.es].
Ort der Lesung: FACULTAD DE MATEMATICAS.
Ort der Vorbereitung: FACULTAD DE MATEMATICAS.

Inhaltsangabe: Die Hauptziele der Diplomarbeit ist die Formalisierung der mathematischen Theorien in der Argumentation automatisierten Systemen, formale Verifikation solcher Theorien und Algorithmen, die solche Prüfung, so dass die Beweise in dem System entsprechen im Wesentlichen mit den üblichen. Zu diesem Zweck haben wir ein System der Argumentation, PVS, und zwei Theorien als Objekte der Formalisierung, Programmierung Logik preposicional und formale Analyse der Konzepte. Darüber hinaus der Wunsch nach einer natürlichen Argumentation auf die Spezifikationen führt zu dem Problem der Wahl der Grundlagenforschung in der Gebäude-Spezifikationen. In diesem Sinne, Datentypen formell gewählt, um die Konzepte der Theorien zu den engsten möglich, solche Begriffe. In beiden Fällen ist die Art der am nächsten zu dem Objekt, das Sie vertreten werden möchten, in der Sprache der PVS ist die Art von Finite-Sets. Allerdings, auch wenn die Wahl des gemeinsamen PVS als Grundlage für die Art der Daten ermöglicht smart auf der gleichen Argumentation, gibt es das Problem, dass diese Spezifikationen sind nicht quantifizierbar sein. Die Lösung, die wir vorschlagen, um dieses Problem ist methodische. Zu diesem Zweck haben wir in PVS einen generischen Rahmen, in dem die Verbindung verschiedener Spezifikationen, formal definiert, wenn zwei verschiedene Spezifikationen entsprechen dem gleichen Konzept. Innerhalb dieses Rahmens haben wir untersucht die Eigenschaften von allgemeiner Natur, die konserviert zwischen den Spezifikationen von der gleichen Algorithmus. Dies hat es uns ermöglicht, die Arbeit auf zwei Ebenen. Auf der einen Seite führen die Argumentation auf der Ebene, wo die Distanz zwischen einer Idee und ihrer formalen Spezifikation ist minimal, aber es ist nicht abschätzbar. Und zweitens, nur auf bestimmte Spezifikationen, erhalten auswertbare anderen für die gleiche Konzept, und mit den gleichen Eigenschaften (einschließlich Eigentum an einer Korrektur Algorithmus). Im Zusammenhang mit den Theorien als: * Wir haben eine Formalisierung der Logik preposicional Programmplanung, die Prüfung der Gleichwertigkeit zwischen den verschiedenen Interpretationen der semantischen Software. Außerdem haben wir getestet, die Vollständigkeit starke Resolution SLD, wobei eine abstrakte Darstellung der Faktoren, die in den Prozess der Auflösung. Schließlich haben wir gebaut auswertbare Verfeinerungen der Algorithmen proportional Logik-Programmierung. * Wir haben formalisierte die Theorie der formalen Analyse von Konzepten, in den abstrakten und wir bekamen auswertbare Verfeinerungen der Algorithmen, dass die Theorie.

Autor: GIMENEZ LLACH OMER.
Jahr: 2004.
Universität: POLITÉCNICA DE CATALUÑA [www.upc.edu].
Ort der Lesung: SALA D'ACTES FME.
Ort der Vorbereitung: U FACULTAT DE MATEMATIQUES I ESTADISTICA SUD.

Inhaltsangabe: Diese Arbeit ist ein Beitrag zur Untersuchung der asymptotischen Aufzählung und der Komplexität der Bewertung des Polynoms Tutte auf bestimmte Familien von Graphen und matroids. Das wichtigste Ergebnis ist die obtention einer kompletten asymptotische Ausdruck für die Anzahl der beschrifteten planaren Graphen mit den Methoden der Analyse Singularität. Als Konsequenz aus unserer Arbeit, die wir erhalten, die Grenze Wahrscheinlichkeit Verteilung der viele interessante Parameter der zufälligen planaren Graphen auf n Ecken, wie die Anzahl der Kanten und der Anzahl der angeschlossenen Komponenten. In Bezug auf unser Beitrag zu der Studie der Komplexitätstheorie der Bewertung des Tutte Polynom, konzentrieren wir uns auf drei Familien von Strukturen: die Klasse der beschränkten Clique Breite - Diagramme (eine Verallgemeinerung der beschränkten Baum - Breite Grafiken) und zwei Untergruppen Klassen Transversaler matroids, mehrere Pfad matroids, die wir in der Klasse der verallgemeinernden Gitter - Pfad matroids, und bicircular matroids. Wir beweisen, dass die Bewertung der Tutte Polynom für bicircular matroids ist # P - hart in jedem Punkt der Fläche mit Ausnahme von zwei Linien und eine Hyperbel. Die Situation ist das Gegenteil für mehrere Pfad matroids, für die wir zeigen, dass Algorithmen berechnen das Tutte Polynom in Polynom. Wie für begrenzt Clique - Breite Grafiken wird gezeigt, wie man berechnen ihre Tutte Polynom in Unterkategorien exponentielle Zeit, ein starkes Indiz dafür, dass sich das Problem nicht # P - hart.

Autor: MOLINERO ALBAREDA XAVIER.
Jahr: 2005.
Universität: POLITÉCNICA DE CATALUÑA [www.upc.edu].
Ort der Lesung: SALA D'ACTES DE L'FME.
Ort der Vorbereitung: U FACULTAT DE MATEMATIQUES I ESTADISTICA SUD.

Inhaltsangabe: Es gibt vier verschiedene, aber eng miteinander verbundenen Probleme über die Generation der kombinatorischen Objekte: Zeichnen (erzeugen Sie ein gelegentliches kombinatorische Objekt einer bestimmten Klasse und Größe), Ranking (berechnen den Rang eines bestimmten Gegenstand aus einer kombinatorischen Klasse, die nach Ansicht einiger zuvor festgelegten Reihenfolge ), Unranking (kombinatorische ein Objekt, dessen Rang und Größe sind, nach einem festen bestimmten Reihenfolge) und Iteration oder Vollständigkeit Generation (kombinatorische generieren alle Objekte einer bestimmten Klasse und Größe, nach einigen festgelegten Reihenfolge). In dieser Arbeit kombinieren wir einige bekannte Prinzipien und neue Ideen in eine allgemeine Rahmen für die Gestaltung effizienter Lösungen für die letzten drei Probleme. Unsere Algorithmen sind Generika in dem Sinne, dass ihre Beiträge der Ansicht, eine endliche Spezifikation der Klasse, deren kombinatorische Objekte wir mit. Wir bieten Algorithmen für unranking und Rang Objekte von der Größe n mit durchschnittlichen Kosten von O (n -sqrt n) für die lexikographische Ordnung und von O (n Benutzerzugang n) für die boustrophedonic bestellen. Im Fall der iterativen Klassen (Klassen, in denen die Rekursion nicht verwendet wird, um ihnen), die Kosten Theta (n '). Darüber hinaus haben wir auch studierte mehrere Heuristiken zur Verbesserung der Leistung der unranking Algorithmen, und die Wahrscheinlichkeit, Verteilung der Kosten der unranking beschriftet Klassen mit lexikographische Ordnung. Für die Iteration Problem, wir haben Algorithmen mit konstanter fortgeführten Anschaffungskosten für eine große Familie von zulässig Klassen, einschließlich der interessantesten Klassen (wir nennen sie superexpoentiallabelled zulässig Klassen, und superpolynomial unmarkierter zulässig Klassen). Wir haben auch verschiedene Techniken (zB die Verwendung von Finger Zeiger) zur Verbesserung der Leistung. Die Flexibilität unserer generischen Algorithmen macht sie attraktiv für Rapid Prototyping und für ihre Eingliederung in großen kombinatorische Bibliotheken, wie zB die COMBSTRUCT Paket für MAPLE oder die MUPAD - CombINAT Paket für MUPAD.

Autor: BARAJAS TOMAS JAVIER.
Jahr: 2006.
Universität: POLITÉCNICA DE CATALUÑA [www.upc.edu].
Ort der Lesung: SALA D'ACTES FME.
Ort der Vorbereitung: U FACULTAT DE MATEMATIQUES I ESTADISTICA SUD.

Inhaltsangabe: Das allgemeine Problem zu finden, die chromatische Zahl einer bestimmten Grafik ist so alt wie die Graphentheorie. Ein wichtiger Teil der zeitgenössischen Konzepten oder Graphentheorie entstand aus den verschiedenen Versuche zur Lösung des Vier-Farb-Problem, einer der bekanntesten Probleme in der Region. Probleme im Zusammenhang mit Grafik Färbungen sind nach wie vor eine aktive und produktive Forschungsgebiet, zum Beispiel das Buch von Jensen und Toft (Graph Coloring Probleme) zitieren JG (), wo die Autoren beschreiben den Zustand - - - Kunst Mehr als zweihundert offenen Probleme in der Region. Insbesondere das Problem zu finden, die chromatische Zahl der so - Distanz Graphen genannt wird, die in diesem Buch. Dieses Problem ist eines der wichtigsten Motive für die Forschung entwickelt, und diese These. Entfernung Grafiken und Schaubilder circulant Cayley Graphen (Graphen mit einem transitiven und regelmäßige Gruppe von automorphisms) von zyklischen Gruppen. Die Ermittlung der Zahl der Distanz bunten Grafiken und Diagramme circulant hat erhebliches Interesse in der Literatur, und es ist eines der wichtigsten Themen dieser These. Eine häufig verwendete Methode zur Einfärbung circulant Graphen bezieht sich dieses Problem mit dem so - genannt (Lonely Runner Problem /), ist auch eines der Themen dieser Arbeit. Einer der wichtigsten Beiträge dieser Arbeit ist ein Werkzeug, das algebraische rufen wir die Prime Filtering Thema. Es ermöglicht die Elemente zu verteilen durch den Ring der ganzen Zahlen modulo n $ $ angeeignet durch Multiplikatoren. Dieses Werkzeug wird intensiv genutzt, um sich mit Problemen im Abstand circulant bunten Grafiken und Schaubilder. Zuerst haben wir die positive Lösung in der ersten offenen Falle einer Vermutung von Zhu (8 Grad), die besagt, dass eine Entfernung Diagramm können die maximale Anzahl chromatische nur, wenn es eine große Clique (im Gegensatz zu der Situation, für die allgemeine Graphen.) Außerdem halten wir den nächsten Fall (von 10 Grad), wo die Vermutung in seiner allgemeinen Form hat sich als falsch erwiesen, und es uns gelingt, eine fast komplette Charakterisierung der Distanz Graphen mit maximaler chromatische Reihe. Die Techniken verwendet, um diesen Angriff Probleme sind im Zusammenhang mit dem so - Lonely Runner Problem genannt, die mehrere Anwendungen zur Zahl der Theorie (diophantine Angleichung) Geometrie (view Obstruktion Probleme) matroid Theorie (nirgendwo Null-Flows) zusätzlich zu den Anwendungen Chromatische Probleme als hier. Mit einer Reihe von Beiträgen von verschiedenen Autoren, das Problem wurde soved bis zu sechs Läufer. Hier lösen wir die erste offene Fall mit sieben Läufer mit einer relativ kompakten Nachweis (im Vergleich mit dem ehemaligen). Die Thesis abgeschlossen durch die Anwendung der oben genannten Ergebnisse für die Berechnung der chromatischen Zahl in circulant Graphen. Das Problem ist schwierig, aus der algorithmischen point of view (es ist NP-hard), aber einige wichtige Fälle berücksichtigt werden können. Wir geben ein Fall für die Charakterisierung von bis zu sechs Grad, die Vollendung bestehenden Teilergebnisse. Wir erwägen auch strukturierten Sets von Generatoren, einschließlich der quasiminimal Stromerzeugungsaggregate, und spärlich Sets von Generatoren (wenn als Integer). Schließlich geben wir ein dichtes asymptotische Schranke für die chromatische Zahl, die im Wesentlichen die Hälfte der Grad.