GI-Radar 323: Ausgezeichnete Grundlagenforschung

Liebe Leserinnen und Leser,

in dieser Ausgabe befassen wir uns unter anderem mit dem Metaversum (Kurzmitteilungen) und Mastodon (GI-Meldungen). Im Thema im Fokus stellt einer der Preisträger des diesjährigen GI-Dissertationspreises seine Forschung vor. Zum Abschluss frönen wir im Fundstück dann der Kunst. 

Wir wünschen Ihnen viel Spaß mit dieser Ausgabe!

auf gi-radar.de weiterlesen

KURZMITTEILUNGEN

Japan baut Chipproduktion aus (FAZ). Dass Abhängigkeiten fatal sind, lässt sich derzeit sehr gut beobachten. Japan baut deshalb eine nationale Allianz für die Chipproduktion auf, nachdem die landeseigene Fertigung in den letzten 30 Jahren rapide gesunken ist. Nun fördert die Regierung ein Forschungszentrum in Tokyo.  weiterlesen

Webseiten-Registrierung künftig nicht mehr anonym möglich (Heise). Derzeit lässt sich eine Domain anonym registrieren. Das hat Vor- und Nachteile, erschwert die Strafverfolgung, bietet aber auch Schutz. Nun hat das EU-Parlament beschlossen, dass für die Registrierung von Top Level Domains detaillierte Daten der Betreibenden gespeichert werden müssen.  weiterlesen

Soziale Medien: Umziehen leicht gemacht (Netzpolitik). Ein häufiges Ärgernis bei der Nutzung sozialer Medien ist Nicht-Kompatibilität. Seitdem ein beliebter Zwitscherdienst negative Schlagzeilen macht, sucht man nach Alternativen. Wie ein Umzug, ein Portieren der Daten oder eine Doppelnutzung gelingen kann, hat Netzpolitik eruiert.  weiterlesen

Der Rechner (und sein Innerstes) – das unbekannte Universum (SZ). Machen pinke Socken per se verdächtig, wenn 90% der Zahlungssäumigen pinke Socken tragen? Legt der Rechner Wahrscheinlichkeiten zugrunde, könnte dieser Schluss entstehen. Aber ist das gerecht und richtig? Was ist, wenn ein Mensch zu einem anderen Schluss kommt, weil alle Säumigen, die er kennt, blaue Socken tragen? Inwieweit ist der Mensch überhaupt noch in der Lage, selbstlernende Systeme zu kontrollieren, ihre Entscheidungen nachzuvollziehen und die Verantwortung für die Entscheidungen der Maschine zu übernehmen? Der Spagat zwischen Technik und Juristerei ist da nicht immer einfach.  weiterlesen

Metaversum: was ist das und wie geht das (NZZ). Wie bei vielen neuen Schlagworten ist bei „Metaversum“ erst einmal schwammig, was dahintersteckt. Auch wird das Metaversum häufig fälschlicherweise einzelnen Konzernen zugeordnet. Dabei bezeichnet es eine virtuelle Welt, in der sich die unterschiedlichsten Unternehmen und Institutionen ansiedeln und in der wir künftig möglicherweise als Avatar Hosen kaufen gehen können. Eine Kurzerläuterung.  weiterlesen

THEMA IM FOKUS

Das heutige Thema im Fokus befasst sich mit der Dissertation „Advanced Tools and Methods for Treewidth-Based Problem Solving“ (tuwien.at). Verfasst hat es Dr. Markus Hecher, einer der Gewinner des diesjährigen GI-Dissertationspreises (gi.de).

Strukturelle Eigenschaften beim Lösen kombinatorischer Probleme und ihre Einschränkungen. In den frühen Kinderschuhen der Informatik hat man damit begonnen, wichtige, wiederkehrende Aufgabenstellungen (Probleme) anhand ihrer Komplexität zu klassifizieren, was vor allem dazu geführt hat, eine Partitionierung dieser in „praktisch lösbar“ und „eher nicht praktisch lösbar“ zu erhalten. Mittlerweile ist die Kategorie „eher nicht praktisch lösbar“ noch viel weiter unterteilt, genauer erforscht und es gibt neben schnellen Computerprogrammen (Solvern; zum Beispiel jku.at) inzwischen sogar allgemeine und gut untersuchte Methoden, um solche Probleme dennoch praktisch lösen zu können.

Eine dieser Methoden nennt sich dynamische Programmierung (youtube.com), welche dem Prinzip „Teile-und-Herrsche“ (divide and conquer) folgt. Dabei werden Probleme so lange in kleinere Teilprobleme zerlegt (aufgeteilt), bis diese praktisch lösbar sind, sodass die Teillösungen kombiniert werden können, um eine Gesamtlösung des ursprünglichen Problems zu erhalten. Nehmen wir als Beispiel eine Logistikaufgabe, bei der ein Transportnetzwerk zwischen Wien und Berlin bedient werden soll, um Waren zu bestimmten Lagerhallen auf der Strecke zu bringen. Aufgrund horrender Treibstoffpreise sollen kostengünstige Transportwege erreicht werden, indem Lösungen von Teilaufgaben über potenzielle Zwischenlager entsprechend kombiniert werden. Natürlich gibt es verschiedene Möglichkeiten, wie man diese Teilaufgaben erhält.

Ein sehr allgemeines Maß ist die sogenannte Baumweite (pacechallenge.org); ein struktureller Parameter, der die strukturelle Abhängigkeit von solchen Netzwerken misst. Dabei ist dieser Parameter sehr vielseitig einsetzbar und gibt in gewisser Weise den Abstand zu einfachen Strukturen, nämlich zu sogenannten Bäumen, welche zumeist strukturell einfachere Teilprobleme erlauben. Jetzt möchte man meinen, dass strukturell einfachere Teilprobleme (von kleiner Baumweite) immer einfacher zu lösen sind, als Teilprobleme größerer Baumweite. Nun, das kann man so allgemein nicht behaupten, denn zusätzlich hängt der erforderliche Lösungsaufwand der Teilprobleme auch immer von der Art des Problems ab. So gibt es beispielsweise Fragestellungen, bei denen sich viele Forschende einig sind, dass sie sehr viel aufwändiger zu lösen sind, als das oben erwähnte Logistikproblem. Wie verhalten sich denn nun strukturelle Abhängigkeit und Lösungsaufwand zueinander und was genau ist jetzt mein Beitrag?

Mein Forschungsthema befasst sich mit dem Lösen schwieriger bzw. kombinatorisch harter Probleme durch Aufteilung, bei Verwendung struktureller Eigenschaften wie der Baumweite. Im Konkreten konnte ich für eine Familie an kanonischen Problemen beweisen, dass unter üblichen Annahmen in der Komplexitätstheorie für jedes dieser Probleme ein gewisser Teilproblemlösungsaufwand in der Baumweite notwendig ist (youtu.be). Eine Bestätigung dieser Vermutung ist eigentlich seit beinahe 20 Jahren offengeblieben. Dabei habe ich einen neuen Ansatz entwickelt, um gezielt hohe strukturelle Abhängigkeit in der Form von Baumweite gegen höheren Teilproblemlösungsaufwand (und retour) zu tauschen. Das hat aber auch weitreichende Konsequenzen für eine Vielzahl an Problemen in der Logik, Wissensrepräsentation und der künstlichen Intelligenz. Es hat sich gezeigt, dass mein Ansatz zu einer Vielzahl neuer Resultate (untere Laufzeitschranken) und einer Klassifikation, die Probleme entsprechend des Teilproblemlösungsaufwandes bei Verwendung von Baumweite einteilt, führen.

Alles nur theoretisch, meinen Sie? Eigentlich nicht! Ich habe des Weiteren noch konkrete Ansätze gebaut, wie man aufwändige Probleme auf diese Art auch praktisch lösen kann, und das funktioniert noch dazu erstaunlich gut. Kanonische Probleme in der Aussagenlogik (Zählprobleme, mccompetition.org)  beim quantitativen Schließen können damit bis zu Baumweiten von ca. 200 praktisch gelöst werden, was in etwa einem worst-case Aufwand von 2^200 entspricht. Aufwändigere Erweiterungen davon können bis Baumweite von ca. 100 gelöst werden. Allerdings wird hier bereits im Allgemeinen ein Aufwand von 2^2^100 erwartet. Mittels einer hybriden Technik können bestehende Solver substanziell erweitert und verbessert werden, indem strukturelle Abhängigkeiten gezielt ausgenutzt werden. Man sieht also, dass entsprechende Forschung nicht nur wesentliche Beiträge zur Klassifikation von Problemen liefern kann. In weiterer Folge kann dies zu neuen, kompetitiven Lösungsansätzen führen, sodass die theoretische Klassifikation bereits entsprechende Erwartungen andeutet bzw. Erfolgsaussichten bereitstellt. Für mehr Details, verweise ich auf eine Kurzfassung in englischer Sprache (arxiv.org) sowie auf die Dissertation (tuwien.at) und Folgearbeiten (tuwien.ac.at).

Wir freuen uns sehr, dass sich Herr Hecher Zeit genommen hat, uns im GI-Radar einen Einblick in seine Forschung zu geben! Vielen Dank!

GI-MELDUNGEN

GI bei Mastodon. Als neuen Kommunikationskanal bieten wir ab sofort auch Mastodon an. Hier veröffentlichen wir Inhalte, die wir auch auf anderen Plattformen verbreiten. Wer also entsprechende Vorlieben und Abneigungen hat, findet uns hier.  weiterlesen

Ihre Selbstdarstellung auf der GI-Webseite. Wussten Sie schon, dass Sie sich mit Ihrer Expertise auf unserer Webseite ein Profil anlegen und freischalten können? Hier können Sie sich mit Ihrem Fachgebiet und Ihren Aktivitäten in der der GI vorstellen. Die ausfüllbare Profilvorlage finden Sie nach dem Einloggen in Ihren Stammdaten. Ein erstes Stöbern macht vielleicht Lust, dabei zu sein?  weiterlesen

Digitale Souveränität stärken: Positionspapier veröffentlicht. Unter der Leitung des GI-Präsidiumsmitglieds Kirsten Messer-Schmidt hat der Kooperationsbeirat des Vereins „Charta Digitale Vernetzung“ ein Positionspapier zum Thema Digitale Vernetzung herausgegebenen. In dem Papier werden vier Hauptrisiken skizziert und Handlungsempfehlungen aufgezeigt.  weiterlesen

GI in Bild und Ton. Normalerweise kommunizieren wir mit Ihnen via E-Mail, am Telefon oder live. Über unseren YouTube-Kanal können Sie jedoch Veranstaltungen der GI auch asynchron verfolgen. Wir stellen Ihnen hier Aufzeichnungen unserer Webtalks bereit, außerdem Interviews, Grußworte und Mitschnitte interessanter Vorträge.  weiterlesen

Kennen Sie eigentlich den GI-Pressespiegel? Dort sammeln wir die Berichterstattung über unsere Fachgesellschaft in Zeitungs-, Radio- und Fernsehbeiträgen. In der letzten Woche gab es beispielsweise Berichte über die Forderung der GI nach der Unabhängigkeit des Bundesamtes für Sicherheit in der Informationstechnik (all-about-security.de). Schauen Sie rein, es gibt da immer wieder Neues oder auch ältere Fundstücke.

FUNDSTÜCK

Verliebte Roboter als Komponisten und Maler. Eigentlich hat ja eine Maschine keine Gefühle. Oder doch? In einem als Oper konzipierten Projekt verleihen eine Regisseurin, ein Musiker und ein Informatiker zwei Robotern so etwas wie eine Seele, die sie miteinander agieren lässt. Ein malender Industrieroboter trifft dabei in der Nacht (Nessun Dorma: niemand schlafe!) in einer Galerie auf einen Putzroboter und beginnt mit diesem ein Techtelmechtel. Zu Opernarien treten die beiden in Beziehung miteinander, sie tanzen, sprechen, lieben und machen Randale. Wirklich keine Seele?  Zum Fundstück (nessundnorma.de)

Welches Fundstück hat Sie zuletzt inspiriert? Senden Sie uns Ihre Ideen!

Dies war Ausgabe 323 des GI-Radars vom 18.11.2022. Zusammengestellt wurde diese Ausgabe von Dominik Herrmann, der Ihnen versichert, dass diese Ausgabe ohne künstliche Emotionen entstanden ist. GI-Geschäftsführerin Cornelia Winter hat die Mitteilungen und Meldungen zusammengetragen. Das nächste GI-Radar erscheint am 02. Dezember 2022.

Im GI-Radar berichten wir alle zwei Wochen über ausgewählte Informatik-Themen. Wir sind sehr an Ihrer Meinung interessiert. Für Anregungen und Kritik haben wir ein offenes Ohr, entweder per E-Mail (redaktion@gi-radar.de) oder über das Feedback-Formular bei SurveyMonkey. Links und Texte können Sie uns auch über Twitter (@informatikradar) zukommen lassen.