L4 Complexity: Komplexität

Autoren: Beat Trachsler und Paul Miotti

Innerhalb der Schranke der Berechenbarkeit lässt sich eine Klassifikation des Berechnungsaufwands von Problemen gewinnen. Diese Resultate sind besonders wichtig für gewisse praktische Programmierprobleme (TSP).

1. Ich entwickle ein Bewusstsein für die Klassifikation von algorithmischen Problemen.
2. Ich erkenne, was mit vernünftigem Aufwand berechnet werden kann.

1. Ich kann die Komplexität eines algorithmischen Problems bestimmen.
2. Ich kenne wenige repräsentative Beispiele für die Methode der Reduktion.
3. Ich beherrsche die O-Notation.

• Clique
• TSP
• Rucksack