Home

Vorlesung Informatik 2 - Teil B: Theorie

1.1 Einfache Algorithmen

Algorithmus: Anleitung zur Lösung einer Aufgabe in endlich vielen Schritten.

Beispiele:

  • Kochrezept
  • Bedienungsanleitung
  • Checkliste im Cockpit
  • Verfahren zum Erzeugen eines Huffman-Codes

Eigenschaften von Algorithmen:

  • Korrektheit: führt er immer zu einem richtigen Ergebnis? Formaler Beweis für größere Programme in der Praxis schwierig bis unmöglich.
  • Aufwand: wieviel Speicher und Rechenzeit benötigt die Lösung? Dazu befassen wir uns später mit dem Konzept der Komplexität 

Beschreibungen von Algorithmen:

  • Text
  • Struktogramme (Nassi-Shneidermann)
  • Flussdiagramme
  • Pseudosprache
  • Programmiersprache

Beispiel: Ist ein bestimmtes Element in einer Menge vorhanden?

Gegeben: eine Menge A = {a1, a2, a3, ..., an}  von Elementen, z.B. Zahlen sowie das gesuchte Element x

Verfahren:

  1. Vergleiche das erste Element a1i  mit x
  2. Bei Gleichheit: beende Algorithmus mit 'gefunden' 
  3. Bei Ungleichheit: 
    • gibt es noch ein weiteres Element?
    • wenn ja: wiederhole Schritt 1 mit dem nächsten Element
    • wenn nein: beende Algorithmus mit 'nicht gefunden'

Das nennt man auch lineare Suche.

In Java kennen wir bisher die  LinkedList um mehrere Elemente zu speichern:

boolean lineareSuche(LinkedList<Integer> a, Integer x){
         for(Integer s:a){
              if(s.equals(x)) return true;
        }
        return false;
}

Oder wir verwenden einen Array, dessen Elemente man mit einem Index zwischen 0 und n-1 adressiert (Arrays werden wir demnächst ausführlich behandeln):

boolean lineareSuche(int[] a, int x){
         for(int s:a){
              if(s==x) return true;
        }
        return false;
}
Ratschläge zu Entwurf und Impementierung:

  • Jeder Algorithmus basiert auf einer Idee. Versuche zunächst, die Idee in wenigen Schritten grob darzustellen, so dass auch Fachfremde (Chef, Kunden) sie verstehen.
  • Zerlege den Algorithmus in Teilschritte und prüfe, ob es dafür schon Lösungen gibt - die meisten Probleme hat schon jemand vor Dir gelöst!
  • Prüfe vor der Implementierung ob der Teilalgorithmus geeignet und effizient genug ist. 
  • Prüfe für jeden Teil-Algorithmus den gültigen Wertebereich der Eingabeparameter und übernimm diese Prüfungen in die spätere Implementierung.
  • Stelle vor der Implementierung eine Liste der möglichen Schwachpunkte auf: Extreme Parameter, Spezialfälle bei den Daten, was ist wenn ... , gibt es Fälle in denen der Algorithmus nicht terminiert, ...
  • Erstelle eine Liste von Test-Datensätzen, sowohl für die Teile als auch für den gesamten Algorithmus. Wenn später ein Problem auftritten, erweitere die Test-Datensätze, so kannst Du nach Änderungen verifizieren, dass das Programm noch funktioniert. 
  • Dokumentiere Änderungen am Code in geeigneter Weise.
  • Sei die bewusst, dass alles, was schief gehen kann, auch irgendwann schiefgehen wird!

Software gehört inzwischen zu der Art Wirtschaftsgut, in die weltweit das meiste Kapital investiert wird. 

Lehrvideo  (YouTube)