08.11.2012, Seminarraum ITCS2021, 14:00 Uhr c.t.
We introduce the concept of knowledge states; many well-known algorithms can be viewed as knowledge state algorithms. The knowledge state approach can be used to to construct competitive randomized online algorithms and study the tradeoff between competitiveness and memory.
We give new results for the two server problem and the paging problem. We present a knowledge state algorithm for the two server problem over Cross Polytope Spaces with a competitive ratio of 19/12, and show that it is optimal against the oblivious adversary.
Regarding the paging problem, Borodin and El-Yaniv had listed as an open question whether there exists an H_k-competitive randomized algorithm which requires O(k) memory for k-paging. We have answered this question in the affirmative using knowledge state techniques.
Am 27.09.2012 wurde Dr. Johannes Textor als bester Nachwuchsepidemiologe 2012 von der Deutschen Gesellschaft für Epidemiologie ausgezeichnet.Titel seiner Arbeit "Adjustment Criteria in Causal Diagrams: An Algrithmic Perspective" (mit Co-Autor Maciej Liskiewicz).
Renommiertester Dissertationspreis Deutschlands in der Informatik für Dr. Johannes Textor
Neue Forschungsergebnisse aus der Theoretischen Informatik verbessern die Methoden und Resultate der Molekularbiologie. Der Lübecker Dr. Johannes Textor erhielt den Preis der Gesellschaft für Informatik (GI) für die beste Informatik-Dissertation im deutschsprachigen Raum 2011. Der mit 5.000 Euro dotierte Preis wurde ihm auf der Jahrestagung der GI verliehen, die vom 16. – 21. September in Braunschweig stattfand.
In seiner Arbeit befasst sich Dr. Textor mit der analytischen Modellierung molekularbiologischer Vorgänge im menschlichen Immunsystem. Er hat sie am Institut für Theoretische Informatik der Universität zu Lübeck unter Betreuung von Prof. Dr. Rüdiger Reischuk sowie Prof. Dr. Jürgen Westermann, Institut für Anatomie, angefertigt.
Die Arbeit trägt den Titel „Search and Learning in the Immune System: Models of Immune Surveillance and Negative Selection“. Darin entwickelt Dr. Textor seine Modellierung als stochastische Suchprozesse sowie als Klassifikationsprobleme. Er analysiert diese de-tailliert und in ausgesprochen überzeugender Weise und entwickelt effiziente algorithmische Lösungsverfahren. Dabei sind seine Resultate zum Teil überraschend und widerlegen bisherige Erwartungen. Darüber hinaus zeigt er eindrucksvoll, dass die gefundenen Ergebnisse unmittelbar in der Molekularbiologie angewendet werden können und dort zu neuen, den bisherigen Stand der Technik erheblich verbessernden Methoden und Resultaten führen.
Mit der Arbeit von Johannes Textor zeichnet die GI damit erstmals eine stark interdisziplinäre Arbeit aus. Die Tatsache, dass hier Grundlagenergebnisse der Informatik auf wichtige Fragestellungen der Molekularbiologie angewendet wurden, ist kein Zufall, sondern ein Ergebnis der konsequenten Ausrichtung der Lübecker Universität auf die Kooperation von technischen Disziplinen (MINT = Mathematik, Informatik, Naturwissenschaft, Technik) und den Lebenswissenschaften. Die Preisverleihung ist damit eine weitere Bestätigung dieser neuen Ausrichtung. Anfang des Jahres war in Lübeck der Wissenschaftscampus „BioMedTec“ gegründet worden.
Dr. Johannes Textor, 1979 in Göttingen geboren, studierte Informatik mit Anwendungsfach Medizinische Informatik an der Lübecker Universität. 2006 erwarb er das Diplom in Informatik mit Auszeichnung. Seine Diplomarbeit „Ein hybrides Automatenmodell zur Simulation des Immunsystems“ wurde von seinem jetzigen Doktorvater Prof. Reischuk betreut. Seit seiner Promotion im August 2011, die mit dem Prädikat „summa cum laude“ ausgezeichnet wurde, arbeitet Dr. Textor als Postdoktorand an der Universität Utrecht im Institut für Theoretische Biologie und Bioinformatik unter der Leitung von Prof. Rob de Boer.
Die Gesellschaft für Informatik e.V. (GI) ist die größte Vereinigung von Informatikerinnen und Informatikern im deutschsprachigen Raum. Sie versteht sich als Plattform für Informatikfachleute aus Wissenschaft und Wirtschaft, Lehre und öffentlicher Verwaltung. Kernthemen der Arbeit der GI sind unter anderem die Nachwuchsförderung, der Wissenstransfer von der Forschung in die Anwendung, Fragen des Datenschutzes und der Sicherheit von Informatiksystemen. Die GI hat rund 20.000 persönliche Mitglieder, darunter 1.500 Studierende und knapp 300 Unternehmen und Institutionen Quelle.
Dozentinnen/Dozenten Prof. Dr. math. Rüdiger K. Reischuk, Oliver Witt, M.Sc.
Angaben Kurs, Anmeldung bis 24.9.2012 bei [email protected] Zeit und Ort: Blockveranstaltung 26.9.2012 9:00 - 10.10.2012 18:00, ITCS 2021
Voraussetzungen / Organisatorisches Bachelor-Absolventen, die das Masterstudium Informatik an der Universität zu Lübeck beginnen wollen, und im Bereich der Theoretische Informatik über geringere Kenntnisse verfügen als im Lübecker Bachelorstudiengang vermittelt wird 10-tägige LV, jeweils 2 x 1,5h vormittags und 2 x 1,5h nachmittags teils als Vorlesung, teils seminaristisch, teils als Übung
Inhalt kurze Auffrischung: Formale Sprachen, Grammatiken und Automaten das Turing-Maschinenmodell, (Un-)Entscheidbarkeit und Aufzählbarkeit Halteproblem, Church-Turing These, Satz von Rice Platz- und Zeitmaße, Effizienz, Komplexitätsklassen Polynomialzeitreduktion, NP-Vollständigkeit Erfüllbarkeitsproblem, graphtheoretische Optimierungsprobleme Modellierung und Analyse algorithmischer Konzepte beherrschen Möglichkeiten und Grenzen der Informatik beurteilen können algorithmische Probleme nach ihrer Komplexität klassifizieren können
Empfohlene Literatur J. Hopcroft, R. Motwani, J. Ullman, Introduction to Automata Theory, Languages and Computation, Addison-Wesley S. Arora, B. Barak, Computational Complexity, Cambridge University Press
Wir gratulieren ganz herzlich Michael Elberfeld zum Dr. rer. nat.
66 Teams aus 12 Universitäten (Karlsruhe, Ulm, Halle, Rostock, Erlangen, Lübeck, Hamburg-Harburg, Bonn, Wolfenbuettel, Saarbrücken, TU München, Uni München) traten am 30. Juni 2012 in dem auf Deutschland beschränkten GCPC'12 (German Collegiate Programming Contest) der ACM (Association for Computing Machinery) gegeneinander an. Der GCPC ist ein offizieller Vorwettbewerb zu dem regionalen Wettbewerb für Nord-West-Europa (NWERC), der am 25.11.2012 in Delft stattfindet.
Gewonnen hat das Team der Universität Erlangen (das Team hat 10 Probleme gelöst), Platz 2 ging an das Team der Uni München und Platz 3 an Uni Karlsruhe (beide Teams haben 9 Probleme gelöst). Unser Team "f(){ f|f& };f" (Alexander Idelberger, Norman Freier, Fabian Klötzl) erreichte mit 4 gelösten Problemen Platz 18, Team "Teammate" (Paul Ketelsen, Ruben Beyer, Malte Skambath) hat 3 Probleme gelöst und Platz 22 erreicht. Wir gratulieren ganz herzlich zu dieser Leistung. Betreut werden die beiden Lübecker Teams durch Prof. Dr. Maciej Liskiewicz und M.Sc. Tim Kunold, Institut für Theoretische Informatik.
Die Problemstellungen des Vorwettbewerbes vom 30. Juni 2012 sind hier nachzulesen.
Die Final Standings wurden hier veröffentlicht.
Öffentliches Experiment des Instituts für Theoretische Informatik am 23. Juni aus Anlass des 100. Geburtstages von Alan Turing, dem Erfinder des Computers
23.06.2012
Werden Maschinen jemals die Intelligenz von Menschen erreichen? Alan Turing, am 23. Juni 1912 in London geboren, hat hierzu ein Testverfahren vorgeschlagen, den nach ihm benannten Turing-Test, bei dem es herauszufinden gilt, ob man mit einer Maschine oder einem Menschen kommuniziert. Wenn die Maschine so geschickt antwortet, dass die Entscheidung schwierig ist, hat sie den Turing-Test bestanden - ihr "Denkvermögen" scheint dem Menschen ebenbürtig (Künstliche Intelligenz).
2012 ist weltweit das Turing-Jahr zur Erinnerung an seine genialen Ideen und zugleich Lübecks Wissenschaftsjahr. In einer öffentlichen Veranstaltung anlässlich seines 100. Geburtstages wird am 23. Juni 2012 um 18.15h im Institut für Medizingeschichte und Wissenschaftsforschung (Königstraße 42) über sein Wirken berichtet.
Gleichzeitig wird ein Demonstrator für den Turing-Test vorgestellt, den Informatik-Studenten im Rahmen eines Studienprojektes am Institut für Theoretische Informatik der Universität Lübeck entwickelt haben. Besucher können zu verschiedenen Themenbereichen Gespräche führen mit unserem JONAS, der - jeweils zufällig gewählt - entweder ein realer Student oder das von den Studenten entwickelte Chat-Programm ist, und sollen dann eine Vermutung äußern. Wie gut wird sich der künstliche JONAS schlagen? Wann ist JONAS soweit, dass er seinen eigenen Facebook-Account unterhält?
aktuell
Hilfe !!!! Mein Computer hat seinen eigenen Facebook-Account......
Können Maschinen jemals die Intelligenz von Menschen erreichen?
Alan Turing, der Erfinder des Computers hat hierzu ein Testverfahren vorgeschlagen, den nach ihm benannten Turing-Test.
2012 ist weltweit das Turing-Jahr zur Erinnerung an seine genialen Ideen.
2012 ist die Hansestadt Lübeck die Stadt der Wissenschaften.
Im Rahmen eines Bachelor-Projektes soll ein Demonstrator für den Turing-Test realisiert und im Rahmen einer Veranstaltung des Wissenschaftsjahres an seinem 100. Geburtstag am 23. Juni 2012, den Lübecker Bürgern vorgestellt werden.
Gesucht werden 3 - 5 Studierende mit guten Programmierkenntnissen, um dieses Projekt im Zeitraum März - Mitte Juni 2012 durchzuführen.
Vorbesprechung: Do, 23.02.2012, 14:30h im Seminarraum 2021 des ITCS.
aktuell
