Algorithmen

Question 1

Definition Alogrithmus

Answer 1

• “Ein Algorithmus ist die Beschreibung eines exakten Verfahrens zur Lösung eines Problems”
• Algorithmus →
• (wird durch Implemetierung zu einem)
• Programm (konkrete Umsetzung eines Algorithmus mittels maschinenlesbare Sprache)
• bewirkt Zustandsänderungen an Objekten

Question 2

Bestandteile

Answer 2

• abstrakte/konkrete Objekte (darauf soll Wirkung ausgeübt werden)
• Handlungen: Wirken in einer best. Reihenfolge ausgeführt in gewünschter Weise auf Objekte ein

⇒​ Algorithmus bewirkt Zustandsänderungen an Objekten

Question 3

Eigenschaften

Answer 3

• Endlichkeit (E1 und E2)
• Eindeutigkeit (global und lokal)
• Rekursion
• Universalität

Question 4

Eigenschaften - Endlichkeit

Answer 4

• Erste Endlichkeitsbedingung (Statische Fenitheit): endlich beschreibbar =durch endlichen Text formulierbar
• Zweite Endlichkeitsbedingung (Terminiertheit): in endlicher Zeit ausführbar = für jede Eingabe terminiert Algo nach endlicher Zeit

⇒ Computerprogramm erfüllt E1 automatisch, da endlicher Speicherplatz

Question 5

Eigenschaften - Eindeutigkeit

Answer 5

• Determiniertheit (Globale Eindeutigkeit): determiniert, wenn eindeutige Abhängigkeit der Ausgabedaten von den Eingabedaten
• Determinismus (Lokale Eindeutigkeit): deterministisch, wenn Wirkung bzw. Ergebnis jeder Anweisung und an jeder Stelle des Ablaufs nächster Schritt eindeutig

⇒ Jeder deterministische Algo ist determiniert, umgekehrt nicht immer

Question 6

Eigenschaften - Rekursion

Answer 6

• rekursiv, wenn selbst wieder aufruft (mit anderen Parametern)
  
  • direkte Rekursion: ruft sich beim Ausführen selbst auf
  • indirekte Rekursion: Ein/mehrere Algo werden aufgerufen → Ausgangsalgo

​⇒ rekursiver Algo nicht zwangsläufig effizienter (aber oft kürzer)

Question 7

Eigenschaften - Universalität

Answer 7

• Wiederverwendbarkeit: Algo löst möglichst allgemeine Problemklasse

Question 8

Programmierparadigma