AD - Algorithmen FS17
HSLU Informatik - Algorithmen & Datenstrukturen - Teil Algorithmen - FS17
HSLU Informatik - Algorithmen & Datenstrukturen - Teil Algorithmen - FS17
Kartei Details
| Karten | 62 |
|---|---|
| Lernende | 23 |
| Sprache | Deutsch |
| Kategorie | Informatik |
| Stufe | Universität |
| Erstellt / Aktualisiert | 20.06.2017 / 14.06.2023 |
| Weblink |
https://card2brain.ch/box/20170620_ad_algorithmen_fs17
|
| Einbinden |
<iframe src="https://card2brain.ch/box/20170620_ad_algorithmen_fs17/embed" width="780" height="150" scrolling="no" frameborder="0"></iframe>
|
Ist Mergesort stabil?
Ja
Was sind die Best-, Worst- und Average Case Werte für Mergesort?
Best Case = O(n log n)
Worst Case = O(n log n)
Average Case = O(n log n)
Implementiere Mergesort in Java.
Nach welchem Lösungsprinzip arbeitet Mergesort?
Teile und Herrsche
Definiere die Datenstruktur Heap.
Ein Heap ist ein binärer Baum, der:
- eine strukturelle Bedingung erfüllt, d.h. voll ist
- eine inhaltliche Bedingung erfüllt, d.h. jeder innere Knoten ≥ als seine Söhne ist,
- in einem Array abgespeichert ist.
Was haben die Funktionen getMax() und insert() auf der Datenstruktur Heap für eine Ordnung?
O(log2 n)
Ist Heapsort stabil?
Nein
Was sind die Best-, Worst- und Average Case Werte für Heapsort?
- Best Case = O(n log n)
- Worst Case = O(n log n)
- Average Case = O(n log n)
Implementiere Heapsort in Java.
Wie funktioniert das Prinzip "Teile und Herrsche"?
Ein komplexes Problem durch Zerlegen in einfachere Teilprobleme lösen:
- Problem in Teilprobleme zerlegen.
- Teilprobleme lösen.
- Teillösungen zur Gesamtlösung zusammensetzen.
Was kann man mit dem Prinzip "Teile und Herrsche" erreichen?
- eine Lösungsfindung
- einen rekursiven Lösungsansatz
- parallelisierbare Lösungen (falls Teilprobleme unabhängig lösbar)
- eine Reduktion des Lösungsaufwandes
Welche Methoden von Object sollten für Elemente einer Collection überschrieben werden?
- boolean equals(Object obj)
- int hashCode()
Welche Sortiermethoden bietet die Klasse java.util.Arrays?
- static void sort(int[] a)
- static void sort(Object[] a)
- static <T> void sort(T[] a, Comparator<? super T> c)
Welche Sortiermethoden bietet die Klasse java.util.Collections?
- static <T extends Comparable<? super T>> void sort(List<T> list)
- static <T> void sort(List<T> list, Comparator<? super T> c)
Nennen sie Nützliche Hilfsmethoden um Arrays und Listen umzuwandeln.
Collection in Array umwandeln:
Interface java.util.Collection<E>
- Object[ ] toArray()
- <T> T[ ] toArray(T[] a)
Array in Liste umwandeln:
Klasse java.util.Arrays
- static <T> List<T> asList(T... a)
Nenne nützliche Hilfsmethoden für Geordnete Collections und geordnete binäre Bäume.
für ungleiche Objekte, deshalb Set:
Klasse java.util.TreeSet<E>
- TreeSet()
- TreeSet(Comparator<? super E> comparator)
Klasse java.util.Collections
- static <T> SortedSet<T> synchronizedSortedSet(SortedSet<T> s)
für Key/Value-Paare, deshalb Map:
Klasse java.util.TreeMap<K,V>
- TreeMap()
- TreeMap(Comparator<? super K> comparator)
Klasse java.util.Collections
- static <K,V> SortedMap<K,V> synchronizedSortedMap(SortedMap<K,V> m)
Nenne einige Anwendungsgebiete von Automaten.
- Steuerungsautomaten (Ampelsteuerung, Billettautomat, Waschmaschine, Prozessor)
- Lexikalische Analyse (Gehört ein vorliegendes Wort zur Sprache?)
- Textsuche (Kommt ein bestimmtes Muster in einem Text vor?)
- Kommunikationsprotokolle
- Verarbeiten von Ereignisfolgen
- Verhaltensmodellierung (Steuerung, System, Dialog)
Wie heissen die drei Automaten-Grundtypen?
- Allgemeiner-Automat
- Mealy-Automat
- Moore-Automat
Was bewirkt ein Ereignis in einem Allgemeinen Automaten?
Ein Zustandswechsel ohne expliziete Ausgabe.
Was bewirkt ein Ereignis in einem Mealy-Automaten?
Ein Zustandswechsel (Zustandsübergang), der selber eine Ausgabe bewirkt.
Was bewirkt ein Ereignis in einem Moore-Automaten?
Ein Zustandswechsel. Jeder Zustand bewirkt selber eine Ausgabe.
Wie kann man einen Automaten implementieren?
Verschachtelte Switch statements.
