Geheimnisse teilen – Protokolle zum Verstecken von Informationen Kryptographische Techniken ermöglichen es uns, Informationen mit anderen zu teilen und dennoch ein überraschend hohes Maß an Privatsphäre zu bewahren. Diese Aktivität veranschaulicht eine Situation, in der Informationen geteilt werden, und dennoch wird nichts davon preisgegeben: Eine Gruppe von SchülerInnen wird ihr Durchschnittsalter berechnen, ohne dass jemand […]

Eisstraßen – Steinerbäume Manchmal löst eine kleine, scheinbar unbedeutende Änderung in der Beschreibung eines Problems einen großen Unterschied aus, der schwerer zu lösen ist. In dieser Aktivität geht es ähnlich wie beim Problem in der Schlammstadt (Aktivität 9) zu, wo es darum geht kurze Wege durch Netzwerke zu finden. Der Unterschied in dieser Aktivität besteht […]

Die Touristenstadt – Absorptionsmengen Viele reale Situationen können in der Form eines Netzwerkes oder „Graphen“ dargestellt werden, wie es in der Aktivität 14 verwendet wird. Netzwerke bieten viele Möglichkeiten für die Entwicklung von praktischen, nützlichen Algorithmen. In dieser Aktivität möchten wir einige der Knotenpunkte oder „Knoten“ so markieren, dass alle anderen Knoten höchstens einen Schritt […]

Der arme Kartograph – Färbung von Bildern Viele Optimierungsprobleme beinhalten Situationen, in denen bestimmte Ereignisse nicht gleichzeitig auftreten können oder bestimmte Elemente einer Gruppe von Objekten nicht benachbart sein können. Zum Beispiel wird jeder, der versucht hat, Stunden oder Treffen zu planen, auf das Problem gestoßen sein, die Beschränkungen für alle beteiligten Personen zu erfüllen. […]