Einführung Informatik II: Weiterführte Programmierung mit Java

Wichtige Themen:

• Schwieriges und theoretisches Thema
• Wichtig für technische Grundlagen in Programmiertechniken und Algorithmenbewertung
• Bewertung von Algorithmen hinsichtlich Speicherplatz und Rechenzeit

Aufwand eines Algorithmus

Bewertungskriterien:

• Speicherplatzbedarf
  • Unterscheiden zwischen Programm selbst und den Daten
  • Speicherkomplexität: Platzbedarf abhängig von Datenmengen
• Rechenzeit:
  • Verarbeitung großer Datenmengen benötigt mehr Rechenzeit (Rechenkomplexität)

Auseinanderklassen des Aufwands:

• Unterschiedliche Algorithmen haben verschiedene Speicher- und Zeitbedarfe
• Qualitative Aussagen wichtiger als exakte Zahlen
• Grössenordnungen und die Auswirkungen von Eingabevergrößerungen

Abstrakte Maschine für Berechnungen:

• Jede Operation kostet eine Zeiteinheit
• Alle Daten benötigen gleichen Speicherplatz
• Dimensionen sind wichtig, Präzision weniger bedeutend

Relevante Informationen zur Berechnung:

• Anzahl der Elemente in Datenstrukturen
• Schleifendurchläufe und -bedingungen
• Anzahl von Funktionsaufrufen

Beispiel 1: Potenzberechnung

• Basis: beliebige Zahl, Exponent: beliebige Zahl
• Lineare vs. logarithmische Berechnung
  • Lineare: Schleifendurchläufe proportional zum Exponenten
  • Logarithmische: exponent wird halbiert, weniger Schleifendurchläufe
• Aufwandsklassen (Komplexitäten): linear, logarithmisch

Veranschaulichung von

• Unterschied zwischen lineare und logarithmus durch grafische Darstellung

Datensuchbaum

• Wurzel, Kinderknoten und Blätter
• Tiefe des Baumes: Logarithmisch abhängig von der Anzahl der Knoten

Landau-Notation

• Beschreibt Wachstumsverhalten von Funktionen (O-Notation)
• Formale Begrenzung des Wachstums: Vergleichen mit Referenzfunktion

Komplexitätsklassen:

• Konstante Zeit O(1)
• Logarithmische Zeit O(log n)
• Lineare Zeit O(n)
• Quadratische Zeit O(n²)
• Kubische Zeit O(n³)
• Exponentielle Zeit O(2^n)

Anwendung der Komplexitätsklassen:

• Einfache Zuweisungen: konstant
• Sequenzen von Operationen: Summe der einzelnen Komplexitäten
• Geschachtelte Schleifen: Produkte der Komplexitäten (wachsend bei inneren Schleifen)
• Worst-case Szenarien

Entscheidungsprobleme

• Entscheidende vs. optimierende Algorithmen
• Unterschiede in der Berechenbarkeit: polynomial lösbare vs. NP-schwere Probleme

Beispiel komplexer Aufgaben: Stundenplan- und Reiseprobleme

• Polynomielle Zeit: Lösbare Algorithmen (P-Klasse)
• NP: Lösungen in polynomischer Zeit prüfbar, nicht berechenbar

Heuristische Methoden

• Nähe zur optimalen Lösung mit begrenztem Wissen und Zeit
• Beispiel: Finanzmarktvorhersagen

Klassen von Problemen und ihre Komplexität:

• Polynomialzeit: Algorithmen der Klasse P
• Nicht-polynomialzeit: Algorithmen der Klasse NP
• Unterscheiden zwischen lösbaren und unscheinar lösbaren Problemen

Zusammenfassung

• Verstehen und Anwenden der Landau-Notation
• Erkennen der Komplexität von Algorithmen
• Verständnis für logarithmische Skalierung und ihre Bedeutung