17
Informatik (Fach) / FINAL ABI (Lektion)
kekw
Diese Lektion wurde von adolfhitler2 erstellt.
Diese Lektion ist leider nicht zum lernen freigegeben.
Anzeige
- Quick Sort Haskell qSort :: Ord a => [a] -> [a]qSort [] = []qSort (x:xs) = qSort [y | y<-xs, y<=x] ++ [x] ++ qSort [y | y<-xs, y> x]
- Insertion Sort Haskell einfuegen :: Ord a => a -> [a] -> [a]einfuegen x [] = [x]einfuegen x (y:ys) | x<=y = x:y:ys | otherwhise = y:einfuegen x ysiSort :: ord a => [a] -> [a]iSort [] = []iSort (x:xs) = einfuegen x (iSort xs)
- Breitensuche Pseudocode markiere alle knoten als micht besuchtmarkiere den Startknoten als besuchtfüge den startknoten in eine (zunächst leere) schlange s einsolange s nicht leer ist wiederhole: entnehme den vordersten knoten k aus s für alle nachbarknoten n von k wiederhole falls n als nicht besucht markiert ist, dann markiere n als besucht füge n in s ein ende falls ende wiederholeende wiederhole
- Tiefensuche Pseudocode besuche(Knoten k) Markiere k als besucht für alle Nachbarknoten n von k wiederhole falls n nicht bereits als besucht markiert ist dann nesuche (n) ende fallsende wiederholen
- Haskell rekursiv ohneletzes ohneletztes :: [a] -> [a]ohneletztes [x] = []ohneletztes (x:xs) = x:ohneletztes xs
- Haskell rekursiv letztes letztes :: [a] -> aletztes [x] = xletztes (_:xs) = letztes xs
- Haskell Fakultät rekursiv fakul x = if x<=1 then = 1 else x*(fakul(n-1))
- Insertion Sort Laufzeiten Best case= O(n) Worst and Average Case = O(n^2)
- Quick Sort Laufzeit Best und Average Case = O(n*log(n)) Worst Case = O(n^2)
- Insertion Sort erklärung Teile-und-Herrsche-Prinzip: In jeder Rekursionsvertiefung, beginnend mitder gesamten Liste, wird die Liste in ihr erstes Element x und dierestlichen Elemente xs aufgespalten. Sodann wird InsertionSort auf xsangewandt und in dessen Ergebnis x mittels einer Hilfsfunktion einfuegeneingefügt.Als Rekursionsabbruch wird im Falle einer leeren Liste eine leere Listezurück geliefert.Die Hilfsfunktion einfuegen arbeitet ebenfalls nach demTeile-und-Herrsche-Prinzip: Das einzufügende Element sei x. AlsRekursionsvertiefung wird die Liste in ihr erstes Element y und den Restys aufgespalten. Wenn dann x<=y, wird die Ergebnisliste in derReihenfolge x,y,ys gebildet. Andernfalls muss y an vorderster Positionstehen. Daher wird x rekursiv mittels einfuegen in ys eingefügt und ydavorgesetzt.Als Rekursionsabbruch wird im Falle des Einfügens von x in eine leereListe eine Liste mit nur x als Inhalt geliefert.
- Anzeige
- Quick Sort Erklärung Teile und Herrsche-Prinzip: In jeder Rekursionsvertiefung, beginnend mitder gesamten Liste, wird die Liste in 3 Teile aufgeteilt: ihr erstesElement als Pivotelement; alle Elemente, die kleiner oder gleich demPivotelement sind als linke Liste und alle größeren Elemente als rechteListe. Auf die Teillisten wird rekursiv qSort angewandt und dieErgebnisse werden in der Reihenfolge sortierte linke Teilliste,Pivotelement, sortierte rechte Teilliste zusammengesetzt. AlsRekursionsabbruch liefert qSort für eine leere Liste sinnvollerweiseeine leere Liste.
- 1. Normalform Alle Attribute Atomar
- 3. Normalform Alle Nichtschlüsselattribute voneinander unabhängig
- 2. Normalform Alle Nichtschlüsselattribut von jedem Schlüsselkandidaten voll funktional abhängig
- public void herauswinken { if (!kolonneQueue.isEmpty()) { kontrolleQueue.enqueue(kolonneQueue.front()); kolonneQueue.dequeue(); fahrzeugeInKolonne--; fahrzeugeInKontrolle++; } else { System.out.println("Keine Fahrzeuge mehr in der Kolonne."); }}
- private void fahrzeugeInDieKolonne() { kolonneQueue.enqueue(auto1); fahrzeugeInKolonne++; }
- public void kolonneAufloesen() { while(!kolonneQueue.isEmpty()) { kolonneQueue.dequeue(); fahrzeugeInKolonne--; } }