- Fachgruppe Algorithmen und Datenstrukturen (ADS)
- Fachgruppe Algorithmische Geometrie (AG)
- Fachgruppe Parallele und verteilte Algorithmen (PARVA)
- Fachgruppe Komplexität (KP)
- Fachgruppe Automaten und Formale Sprachen (AFS)
- Fachgruppe Logik in der Informatik (LogInf)
- Fachgruppe Computeralgebra (CA)
- Fachgruppe Neuronale Netze (NN)
- Fachgruppe Petrinetze (PN)
Fachgruppe Algorithmen und Datenstrukturen (ADS)
Sprecher: 
Prof. Dr. Klaus Jansen
Stellvertretender Sprecher: Prof. Dr. Martin Dietzfelbinger
Der Entwurf, die Analyse und Implementation von Algorithmen für verschiedene Anwendungsgebiete ist eine zentrale Aufgabe der Informatik. Algorithmen manipulieren mehr oder weniger komplexe Daten. Das erfordert geeignete Methoden zur Strukturierung, Speicherung und Manipulation von Daten. Es geht in diesem Gebiet also sowohl um den Entwurf effizienter Algorithmen und Datenstrukturen als auch um die Analyse ihres Verhaltens.
Man kann das Gebiet Algorithmen und Datenstrukturen auf verschiedene Arten gliedern: nach den Algorithmen oder Problembereichen, nach den Datenstrukturen oder Werkzeugen und nach den Entwurfsprinzipien oder Methoden. Einige Teile dieses Gebietes haben inzwischen eine so großle Bedeutung erhalten, daß sie in eigene Fachgruppe organisiert werden, aber eng mit dieser Fachgruppe zusammenarbeiten sollen. Dies gilt insbesondere für die Fachgruppen 0.1.2 Algorithmische Geometrie und der Fachgruppe 0.1.3 Parallele und verteile Algorithmen.
Zu den Problembereichen, die nicht einer eigenen Fachgruppe sondern dieser Fachgruppe zugeordnet werden sollen, gehören:
- elementare Datenstrukturen: Listen Bäume, etc.
- grundlegende Algorithmen: Suchen, Sortieren, etc.
- Graphenalgorithmen
- Algorithmen zur Zeichenkettenverarbeitung
- numerische und algebraische Algorithmen
Das Gebiet Algorithmen und Datenstrukturen gehört zum Kern eines jeden Informatikstudiums. Es hat sich in den letzten Jahren beachtlich entwickelt und war Thema überregionaler Forschungsprogramme (DFG-SPP Datenstrukturen und effiziente Algorithmen).
Fachgruppe Algorithmische Geometrie (AG)
Sprecher: Prof. Dr. Christian Knauer
Stellvertretender Sprecher: Dr. Joachim Giesen
Die algorithmische Geometrie hat sich in den letzten fünzehn Jahren als aktives Forschungsgebiet innerhalb der theoretischen Informatik etabliert. Ziel dieser Fachgruppe ist es, ein Forum für diese Interessenten - wenn möglich auch über Deutschland hinaus - zu bilden, und durch mehrere Aktivitäten die Forschungen auf diesem Gebiet zu unterstützen. Neben der Förderung der Grundlagenforschung soll diese Fachgruppe auch stärkere Verbindungen zu den zahlreichen Anwendungsgebieten der algorithmischen Geometrie - wie etwa Computer Graphik, Robotik, VLSI-Design, Operation Research, etc. - sowie zu verwandten Gebieten der Mathematik - wie etwa Geometrie, Kombinatorik, kombinatorische Optimierung, etc. - ermöglichen.
Die algorithmische Geometrie beschäftigt sich traditionellerweise mit Problemen auf großen Mengen geometrischer Objekte in kleinen Dimensionen. Die Algorithmen und Methoden lassen sich zwar oft auf beliebig hohe Dimensionen verallgemeinern, verlieren aber sehr schnell an Effizienz. In letzter Zeit wird auch in diesem Gebiet zunehmend Augenmerk auf höhere Dimensionen und Implementierungsgesichtspunkte bei elementaren Operationen gelegt.
Typische Probleme sind etwa die Berechnung konvexer Hüllen, Konstruktion von Voronoi-Diagrammen, Schnittprobleme auf geometrischen Objekten (welche Paare von n Liniensegmenten schneiden sich?), Bereichsabfrageprobleme (welche von gegebenen n Objekten liegen in einem Abfragerechteck?), etc.
Im folgenden sollen - ohne Anspruch auf Vollständigkeit - kurz einige Schwerpunkte benannt werden, wie sie derzeit am aktivsten untersucht werden.
-
Grundlegende Methoden und Verfahren
Allgemeine geometrische Algorithmen und Datenstrukturen, Such- und Abfrageprobleme, Berechnung von Durchschnitten, geometrische Transformationen, Arrangements von Hyperebenen, konvexe und nichtkonvexe nichtnumerische geometrische Optimierungsprobleme, lineares (und konvexes) Programmieren mit wenig Variablen, randomisierte Algorithmen.
-
Anwendungsgebiet: Robotik
Bewegungsplanung, Sichtbarkeitsprobleme, Kollisionsvermeidung, Distanzprobleme, Probleme, bei Greifen mit Roboterhänden.
-
Anwendungsgebiet: Computergraphik
Hidden Surface Removal, Strahlungsverfolgungsalgorithmen.
-
Anwendungsgebiet: Computerunterstütztes Entwerfen (CAD)
Zerlegung von Polytopen, Triangulierung im Raum, (Re-)Konstruktion von Objekten.
-
Anwendungsgebiet: Geodatenbanken
Externspeicherung großer Mengen geometrischer Daten, effiziente Zugriffe über geometrische und Standardattribute. -
Implementierung geometrischer Datenstrukturen und Algorithmen
Beschreibung geometrischer Objekte, Perturbierungstechniken, Testdatenerstellung, Rechnen mit unendlicher Genauigkeit (infinite precision), Vergleich und Bewertung von Software.
Es ist geplant, Kontakte zu mehreren Fachgruppen der GI zu knüpfen, um die Anwendung der erzielten Ergebnisse zu forcieren und neue interessante und wichtige Fragestellungen kennenzulernen. Es bieten sich hier an: FG1.0.3 (Robotersysteme), FG 1.5.3 (Planen und Konfigurieren), FG 4.1.5 (German Chapter of Eurographics), FG 4 (Rechnerunterstütztes Entwerfen und Konstruieren (CAD)). In diesem Zusammenhang sind Seminare mit Anwender vorgesehen. Weitere Kooperationen bieten sich mit der Gesellschaft für Operations Research und der DMV an (auf gebieten wie kombinatorische Optimierung, Kombinatorik, Geometrie). Weiterhin ist geplant, bestehende Veranstaltungen wie den Workshop über Computational Geometry (CG), oder etwa das Dagstuhl-Seminar über algorithmische Geometrie in Kooperation mit der Fachgruppe zu organisieren.
Fachgruppe Parallele und verteilte Algorithmen (PARVA)
Sprecher: Prof. Dr. Peter Sanders
Stellvertretender Sprecher: Prof. Dr. Rolf Wanka
Die theoretische Informatik, insbesondere die Algorithmentheorie, die Theorie der Modellierung und Semantik paralleler und verteilter Systeme, und die parallele Komplexitätstheorie (auch im FB 3 werden zahlreiche Aktivitäten im Bereich der Parallelrechnung und paralleler Systeme durchgeführt, die im allgemeinen jedoch stärker anwendungsorientiert sind und oft auch mehr sich im Bereich der technischen Informatik und der Architekturen von Rechenesystemen bewegen), hat im hier angesprochenen Bereich im Rahmen des letzten Jahrzehntes sehr große Fortschritte erzielt und viele neuen Fragestellungen und Forschungseinrichtungen eröffnet. Diese sollen, soweit die Theorie betroffen ist und in enger Zusammenarbeit insbesondere mit PARS (der FG 3.1.2) und entsprechenden Gruppen innerhalb der ITG, in der Fachgruppe vertreten und gefördert werden.
Inhaltliche Schwerpunkte dieser Fachgruppe werden unter anderem auf den folgenden gebieten liegen:
- Parallele und verteilte Algorithmen,
- Parallelisierung von Algorithmen,
- Komplexität paralleler und verteilter Berechnungen,
- Modelle für paralleles Rechnen,
- Parallele Programmiersprachen,
- Semantik paralleler Programmiersprachen,
- Programmiersysteme für Parallelrechner,
- Mathematische Modellierung paralleler Architekturen,
- Mathematische Evaluierung von Netzwerken,
- Theorie verteilter Systeme,
- Programmiermethoden für verteilte Systeme.
Der durch die Fachgruppe abzudeckende Themenbereich spielte bisher bereits für zahlreiche Veranstaltungen eine wesentliche oder zentrale Rolle: Der Workshop für Komplexitätstheorie, effiziente Algorithmen, und Datenstrukturen, der turnusmäßig drei- oder viermal im Jahr stattfindet, hat in den letzten Jahren stets eine sehr starke aktive Beteiligung als dem allgemeinen Bereich der Parallelrechnung aufzuweisen. Eine ähnliche Beobachtung trifft auf den langjährigen International Workshop on Graph-Theoretic Concepts in Computer Science zu, und in noch viel stärkerem Maße auf den PASA-Workshop (Parallele Systeme und Algorithmen), der zusammen mit der PARS veranstaltet wird und eine Brücke zwischen Theorie und Anwendung in der Parallelrechnung schlagen soll.
Fachgruppe Komplexität (KP)
Sprecher: Prof. Dr. Heribert Vollmer
Stellvertretender Sprecher: Prof. Dr. Thomas Schwentick
Diese Fachgruppe beschäftigt sich mit komplexitätstheoretischen Fragestellungen, insbesondere
- Komplexitätsklassen, Hierarchien,
- untere und obere Komplexitätsschranken für spezielle Probleme,
- Strukturfragen, Äquivalenzuntersuchungen,
- Einweg-, Falltürfunktionen, Kryptographie,
- Interaktive Beweissysteme,
- Komplexität logischer Entscheidungsprobleme,
- logisch-deskriptive Komplexitätsklassen,
- Kolmogorov-Komplexität,
- Nichtuniforme Berechnungsmodelle (spezielle Automaten, Schaltkreise, Branching-Programme, Formeln).
Manche der Themen sind eng gekoppelt an, bzw. werden gemeinsam bearbeitet mit anderen Fachgruppen, insbesondere sind dies die FG 0.1.1 Algorithmen und Datenstrukturen (Thema: Obere Schranken), FG 0.1.5 Automaten und formale Sprachen (Thema: spezielle Berechnungsmodelle, Abschlußeigenschaften von Klassen) FG 0.1.6 Logik in der Informatik (Thema: Komplexität logischer Entscheidungsprobleme, Komplexität des logischen Programmierens, subrekursive Hierarchien).
Ein Workshop über Komplexitätstheorie, effiziente Algorithmen und Datenstrukturen, gemeinsam mit den Fachgruppen 0.1.1, 0.1.2, 0.1.3 findet drei bis viermal jährlich statt.
Weitere Veranstaltungen: Ellwangen-Treff, ein regelmäßiges, in ca. dreiwöchigem Turnus stattfindendes Treffen der Komplexitätstheoriegruppen der Universitäten Würzbug, Ulm, Stuttgart und München. (Ansprechpartner: Prof. Schöning (Ulm), Prof. Wagner (Würzburg)).
Fachgruppe Automaten und Formale Sprachen (AFS)
Sprecher: Prof. Dr. Friedrich Otto
Stellvertretender Sprecher: Dr. Martin Kutrib
Diese Fachgruppe ist ein Forum der GI für die an der Thematik Automaten und formale Sprachen interessierten Informatiker. Mit anderen Fachgruppen des Fachbereichs GInf bestehen enge Bindungen.
Inhaltliche Schwerpunkte liegen unter anderem auf folgenden Gebieten:
- Automaten und Klassen formaler Sprachen (über Wörtern, Bäumen, Spuren, Graphen, Bildern, etc.). Bezüge zur Komplexitäts-, Rekursions- und Schaltkreistheorie.
- Zeichen- und Term-Ersetzungssysteme, Graph-Grammatiken, L-Systeme und verwandte Modelle.
- Verteilte Automatenmodelle, darunter zelluläre Automaten, systolische Automaten, Petrinetze, neuronale Netze.
- Algebraische Methoden (u.a. Halbgruppen, formale Potenzreihen).
- Automaten und Logik bzw. Semantik (u.a. Transitionssysteme in Semantik und Spezifikation verteilter Systeme, Programmverifikation, dynamische Logiken).
- Kombinatorische und algorithmische Fragen (u.a. Codes, Pattern Matching).
- Automatentheorie und Programmierung (u.a. Übersetzerbau, Programmschemata).
Zu den Zielen dieser Fachgruppe gehören:
- die Förderung der Kommunikation durch Treffen und Mitteilungen,
- die Bündelung von Aktivitäten durch spezifische Veranstaltungen und Koordinierung von Forschungsprojekten,
- die Vertretung des Gebietes innerhalb und außerhalb der GI,
- die Förderung der Lehre in diesem Gebiet.
Die Fachgruppe unterstützt Veranstaltungen und andere Aktivitäten zur Thematik der Automaten und formalen Sprachen. Sie veranstaltet in regelmäßigen, wenigstens einmal jährlich, einen Theorietag Automaten und formale Sprachen. Sie fühlt sich mitverantwortlich für regelmäß stattfindende einschlägige Konferenzen wie die STACS sowie für entsprechende Seminare im Internationalen Begegnungs- und Forschungszentrum Schloß Dagstuhl.
Fachgruppe Logik in der Informatik (LogInf)
Sprecher: Prof. Martin Hofmann, Ph.D.
Stellvertretender Sprecher: Dr. Carsten Lutz
Viele Fragestellungen in der Informatik sind logischer Natur und können mit Methoden der Logik beschrieben und gelöst werden. In der Tat war die Logik (z.B. mit den Arbeiten von Hilbert, Gödel, Church und Turing) an der Entstehung der Informatik wesentlich beteiligt. An vielen Orten hat daher die Logik ihren Platz in der Informatikgrundausbildung. Trotzdem hat sich die "Logik in der Informatik" als eigenes Gebiet erst vor relativ kurzer Zeit etabliert. Neben einer Vielzahl von speziellen Konferenzen zu Teilbereichen (wie der "Conference on Automated Deduction (CADE)" und der "Computer-Aided Verification (CAV)") gibt es seit Mitte der 1980er jährliche Tagungen, die sich explizit der ganzen Breite dieses Gebietes widmen (die europäische Tagung "Computer Science Logic (CSL)" seit 1987 und die internationale Tagung "Logic in Computer Science (LICS)" seit 1986).
Beispiele für Anwendungsgebiete der Logik in der Informatik sind
- Computer-Mathematik
- Datenbanksysteme
- Hardware-Entwurf
- Komplexitätstheorie
- Künstliche Intelligenz
- Programmiersprachen
- Software Engineering
- Spezifikation und Verifikation
- Verteilte Systeme
Durch diese Anwendungen entstanden teilweise ganz neue Teilgebiete der Logik, aber auch klassische Gebiete (wie Modelltheorie und Beweistheorie) erhielten dadurch neue Impulse und Ausrichtungen. Es wird auch in Zukunft eine wichtige Rolle der Logik in der Informatik bleiben, bei neuen, teilweise sehr schwierigen praktischen Problemstellungen die nötige Formalisierung sowie Lösungsansätze zu liefern.
Ziel der Fachgruppe ist es, den Informatikern mit Interesse an logischen Methoden und den Logikern mit Interesse an Informatikanwendungen eine organisatorische Heimat zu geben. Hierzu sollen Kontakte zu anderen GI Fachgruppen, in denen Logik eine Rolle spielt, gepflegt und intensiviert werden, z.B. durch gemeinsame Veranstaltungen. Es ist außerdem Aufgabe der Fachgruppe, für einen festen Platz der Logik in der Informatikgrundausbildung einzutreten und an der Fortschreibung und Neuentwicklung von Curricula in diesem Gebiet aktiv mitzuwirken. Eine weitere wichtige Funktion der Fachgruppe ist es, die Sichtbarkeit der Logik in der Informatik zu erhöhen, ihre praktische Relevanz herauszustellen und die Logik im Kontext ihrer Anwendungen in der Informatik weiterzuentwickeln.
Fachgruppe Computeralgebra (CA)
Sprecher: Prof. Dr. Wolfram Koepf
Stellvertretende Sprecherin: Prof. Dr. Elkedagmar Heinrich
Die Fachgruppe sieht es als ihre Aufgabe an, Forschung, Lehre und Entwicklung, Anwendungen, Informationsaustausch und Zusammenarbeit auf dem Gebiet der Computeralgebra zu fördern. Die Computeralgebra ist ein Wissenschaftsgebiet, das sich mit Methoden zum Lösen mathematisch formulierter Probleme durch Algorithmen zum symbolischen und algebraischen Rechnen und deren Umsetzung in Soft- und Hardware sowie ihren Anwendungen beschäftigt. Die Computeralgebra beruht auf der exakten endlichen Darstellung endlicher oder unendlicher mathematischer Objekte und Strukturen und ermöglicht deren symbolische und formelmäßige Behandlung durch einen Computer.
Die Fachgruppe gibt den "Computeralgebra-Rundbrief" heraus.
Fachgruppe Neuronale Netze (NN)
Sprecher (kommissarisch): Jun-Prof. Dr. - Ing. Tim Nattkemper
Stellvertretender Sprecher: Prof. Dr. Helge Ritter
Es ist das Ziel der Fachgruppe, das Feld der künstlichen neuronalen Netze innerhalb der GI neu und zeitgemäß zu repräsentieren und für viele Seiten sichtbar zu machen.
Das Forschungs- und Entwicklungsgebiet der künstlichen neuronalen Netze hat sich in den letzten 20 – 30 Jahren sehr dynamisch entwickelt. Im Zusammenspiel mit den allgemeinen Fortschritten in der Informationstechnik wurden mehrere Aspekte neuronaler Informationsverarbeitung unter dem Label "Neuronale Netze" sowohl als Forschungsgegenstand als auch als praktische Ingenieurstechnik entwickelt. Um die Kommunikation der beteiligten oder auch "nur" interessierten Informatiker zu fördern wollen wir hier eine Plattform entwickeln, welche helfen soll Standorte zu vernetzen und Medien auszutauschen.
Zwei Kommunikationskanäle stehen dabei im Vordergrund: Zum einen wollen wir Studenten und junge Wissenschaftler dabei unterstützen, eine Rolle in der Zukunft der Neuronalen Netze zu spielen. Dazu soll unter der Rubrik "Medien" ein Pool aus öffentlich verfügbaren Filmen, Vorträgen und Demos entstehen. Des Weiteren soll unter der Rubrik "Adressen" ein Überblick für deutsche Standorte (Universitäten, Fachhochschulen, Institute) mit Bezug zu Neuronalen Netzen entstehen, der durch die Rubrik "Stellenbörse" ergänzt wird.
Ein weiterer Kommunikationskanal soll sowohl zwischen der Industrie und der Forschung als auch innerhalb der Forschung unterstützt werden. Hierzu sollen die entsprechenden Informationen unter den Rubriken "Events" und "Fachliteratur" beitragen.
Fachgruppe Petrinetze (PN)
Sprecher: Prof. Dr. Karsten Wolf
Stellvertretender Sprecher: Prof. Dr. Jörg Desel
Die Fachgruppe "Petrinetze und verwandte Systemmodelle"
widmet sich den Themen der Modellierung, der Darstellung
und der werkzeuggestützten Analyse und Synthese von verteilten und
kommunizierenden Sytemen, vor allem auf Basis des von C.A. Petri
begründeten Formalismus der Petrinetze.
Die Fachgruppe gibt den "Petri Net Newsletter" heraus und veranstaltet
unter anderem jährlich den Workshop "Algorithmen und Werkzeuge für Petrinetze".
