Vorlesung 1 - 19.10. 10:15

Organisatorisches:

Aktive Teilnahme:

• 60% aller Punkte auf den Übungszetteln
• auf (n-2) Zetteln mehr als 20% der Punkte
• 2x Vorstellen einer Lösung im Tutorium
• 1x erstellen eines kahoot-Quiz

Regelmäßige Teilnahme:

• (n-2) mal anwesend im Tutorium

Note

• 120 Minutenklausur am Ende des Semesters (i.A. nicht differenziert bewertet)

Inhaltliches:

• Programmierparadigmen imperativ vs funktional (Einhornreiten)
• GHCi als Taschenrechner
• vordefinierte arithmetische Funktionen
• eigene Funktionen schreiben
• Typsignaturen

• Vergleichoperationen und Wahrheitswerte
• Fallunterscheidung
• Syntaxregeln
• Polymorphie
• Typklassen
• Tupel und Listen
• Listengeneratoren
• Pattern Matching

------------------------------------------------

Errata:

 Folie 23: Signatur von f ist falsch. Müsste sein:

f :: (Integer,Integer) -> Float

• Pattern Matching und Guards
• case.. of
• where, let .. in
• Rekursion - Fakultätsfunktion
• Rekursion und Listen

----------------------------------------------------------

Errata Folien:

Folie 1: Siehe Folie 23 in VL 2

Folie 11: Bei dreheUm fehlt der rekursive Aufruf. Richtig wäre:

dreheUm :: [a] -> [a]
dreheUm [] = []
dreheUm (x:xs) = dreheUm xs ++ [x]

Folie 16: Bei quickfib wird im Anker der falsche Wert zurückgegeben. Richtig wäre:

quickfib a b 0 = quickfib a

• Rekursion -- Türme von Hanoi
• Auswertungstrategien
• Normalformen
• Striktheit
• Referentielle Transparenz
• Suchen in Listen

--------------------------------------------

Errata:

Folie 13: Bei einer unendlichen Liste würde die Funktion nicht terminieren. Für das Beispiel müsste sie wie folgt definiert sein:

myfunc a [] = a
myfunc 0 _  = 0
myfunc a (x:xs) = (a-1) myfunc (a-1) xs

• Suchen in Listen (Wiederholung)
• Sortieren
  • Selectionsort
  • Inserionsort
  • Mergesort
  • Quicksort
• Motivation Komplexitätsanalyse

• Einführung O-Notation
• Bedeutung O-Notation
• Beispiele Laufzeitanalyse (max1, max2, sum)

• Analyse Sortieralgorithmen
• Funktionen höherer Ordnung
  • Funktionen als Ein- und Ausgabe
  • Currying

• Funktionen höherer Ordnung
• Currying
• Anonyme Funktionen
• map
• filter
• takeWhile, dropWhilezip, zipWith
• Funktionsapplikation und Funktionskomposition

• Typinferenz
• all, any, flip
• Faltung

• Fibonacci mit scanl und zipWith
• Endrekursion
• seq, $! und foldl'
• Korrektheitsbeweise mittels struktureller Induktion

• Weitere Beispiele zur strukturellen Induktion

Algebraische Datentypen

• Motivation
• Einfache Beispiele
• Algebraische Datentypen und Typklassen
• Algebraische Datentypen und Polymorphie

• Maybe
• Rekursive algebraische Datentypen
• Binärbäume
  • Motivation
  • Definitionen
  • erste Funktionen

• Eigenschaften von Binärbäumen
• Traversierung von Binärbäumen
• Laufzeitanalyse auf Binärbäumen
• Induktion auf Binärbäumen

Binäre Suchbäume, siehe Videos

================================

Folie 16: Die 7 muss das linke Kind der 8 sein.

Module

Typklassen

• Eq
• JaNein
• Stacklike
• Queuelike

Anwendungen von Stacks

Eingabe und Ausgabe

Huffmann Codes

(Erweiterte) Backus-Naur Form

Lambda-Kalkül

• Motivation
• Syntax
• alpha-Konversion und beta-Reduktion
• Wahrheitswerte
• Tupel

Lambda-Kalkül

• Zahlen
• Arithmetik
• Listen
• Rekursion

-----------------------------------------------

Folien 10 und 12: Die Funktion zum Testen auf 0 sollte isZero sein.

Folie 11: in der ersten Zeile des linken Blocks, fehlt eine Klammer vor dem x:

Y x = (λf.(λy.f(yy))(λy.f(yy))) x