Für den InformatiCup 2007 gab es drei Aufgaben zur Auswahl.
Kreuzzahlrätsel
Ein immer beliebter werdendes Spiel sind Kreuzzahlrätsel. Ein solches Rätsel ist ähnlich aufgebaut wie das bekanntere Kreuzworträtsel: Gegeben ist ein Rechteck von Zellen, die mit Ziffern von 0 bis 9 belegt werden können. Einige Zellen enthalten Markierungen, die mit Bedingungen für die nachfolgenden Zellen (horizontal oder vertikal) verknüpft sind. Eine Lösung des Rätsels muss alle Bedingungen erfüllen. In dieser Aufgabe soll ein Programm, das Kreuzzahlrätsel, die nach obigem Schema aufgebaut sind, löst und die Erstellung neuer Rätsel unterstützt, entwickelt werden.
E-Mail-Client
Trotz Spam und Phishing sind E-Mails immer noch das Hauptkommunikationsmedium im Internet-Zeitalter. Seit der Einfuhrung des IMAP-Protokolls ist es möglich, E-Mails auf verschiedenen Rechnern (z.B. im Büro, zu Hause, auf dem Laptop, via Web-Mail) zu lesen und dennoch die gleichen Ordnerstrukturen in allen Clients zu benutzen. Allerdings betrifft dies nur die E-Mails selbst. Einstellungen des verwendeten E-Mail-Clients liegen jeweils lokal auf dem Rechner unter dem aktuell verwendeten Betriebssystem. Bei der Nutzung mehrerer Clients auf unterschiedlichen Systemen (z.B. Desktop und Laptop bzw. Dual-Boot auf einem Computer) müssen alle Systemeinstellungen jeweils auf allen beteiligten Systemen geändert werden, um diese synchron zu halten. In dieser Aufgabe soll ein E-Mail-Client mit einer einfachen GUI entwickelt werden. Dieser E-Mail-Client soll es dem Benutzer erlauben, transparent über verschiedene Systeme auf ihre E-Mails zugreifen zu können. Dabei sollen über Systemgrenzen hinweg Einstellungen und Adressbücher konsistent bleiben. Dies soll ohne eine Änderung des verwendeten E-Mail-Servers, d.h. ohne Änderung des IMAP-Protokolls erfolgen.
Subsumption
Relationale Datenbanksysteme (RDBMS) sind die vorherrschende Form zur Speicherung und Anfrage großer Mengen strukturierter Daten. In relationalen Datenbanken werden Daten in Form von Tabellen gespeichert. Eine Zeile einer Tabelle nennt man Tupel. Ein Tupel setzt sich aus einer Menge von Attributwerten (einer in jeder Spalte) zusammen. Um Anfragen an die Daten beantworten zu können, stehen dem Nutzer in einem RDBMS eine Reihe von Operatoren zur Verfügung, etwa die Selektion, die Projektion, der Join, aber auch Mengenoperatoren wie die Vereinigung oder die Schnittmenge.
Ist ein bestimmter Attributwert für ein Tupel nicht bekannt, wird anstelle eines Wertes ein NULL-Wert eingetragen. Beispielsweise kann eine Kundentabelle eine Spalte für die E-Mail-Adresse eines Kunden vorsehen. Allerdings ist nicht davon auszugehen, dass für jeden Kunden eine E-Mail-Adresse bekannt ist, oder dass gar jeder Kunde überhaupt eine solche besitzt. Der entsprechende NULL-Wert an der Stelle kann also verschiedene Bedeutungen haben, zum Beispiel “nicht bekannt”, “nicht vorhanden” oder “trifft nicht”. Bei der Integration von Datenbeständen, z.B. Kundendatenbestände aus mehreren Abteilungen oder Kundendatenbestände aus mehreren Unternehmen bei einer Unternehmensfusion, gilt es, überflüssige Informationen zu eliminieren, also z.B. doppelte Informationen über einen Kunden.
Die Schwierigkeit dieser Eliminierung besteht darin, dass die zu eliminierenden Daten oft nicht exakt doppelt vorhanden sind. Vielmehr unterscheiden sich die Einträge: Ein Datensatz kann mehr Informationen über einen bestimmten Kunden haben als ein anderer Datensatz. Oder aber zwei Datensätze können voneinander abweichende, also widersprüchliche Informationen speichern. Das Finden solcher Bestände nennt man Duplikaterkennung. In dieser Aufgabe soll nur der erste Fall betrachtet werden, also der Fall, dass ein Datensatz reicher an Informationen ist als ein anderer - er subsumiert den anderen. Es sollen drei effiziente Algorithmen, die überflüssige Informationen aus einer oder mehreren Tabellen entfernen, entworfen und implementiert werden.