HSG

Aktuelle Seite: HSG/Fächer/Informatik/Material/Berechenbarkeit
Folgende Schritte eines Unterrichtsgangs beruhen auf einem Konzept von Dr.K.Becker, Kaiserslautern aus der Lehrerweiterbildung. Eine zugehörige Präsentation kann hier (ca. 1,2 MB) heruntergeladen werden.
  • Problem: Gibt es für die Möglichkeiten von Software prinzipielle Grenzen?
  • Hinter jeder Software stehen Algorithmen. Gibt es Grenzen für Algorithmen?
  • Erinnerung: Intuitiver Algorithmusbegriff (Begriff ist nicht präzise!)
  • verschiedene Möglichkeiten, den Algorithmusbegriff im mathematischen Sinn präzise zu fassen.
  • Festlegung auf eine Präzisierung, z.B. "Kara als Berechnungsmodell"
  • Umgang mit Kara

    • "Baumumrundung" (S.18)

      kara1.kara
    • "an Baumreihe vorbei" (S.20)
    • "vertikales Baumumrundungsproblem" (S.21)
  • präzise Beschreibung eine Kara-Algorithmus
  • Beweis, dass es einen Kara-Algorithmus zur Lösung des "vertikalen Baumumrundungsproblems" gibt.
  • Beweis, dass es keinen Read-Only-Kara-Algorithmus zur Lösung des "vertikalen Baumumrundungsproblems" gibt.
  • Probleme, die Kara-berechenbar sind:
    • Addition (S.29)
    • Subtraktion (S.30)
    • Verdoppeln (S.32)
    • Multiplikation (S.33)
  • präzise Definition von "Kara-berechenbar"
  • eine weitere Möglichkeit, "berechenbar" zu präzisieren: Turing-Maschinen
  • Variation der Turing-Maschine
  • ...