Informatik Prüfung 3 - PDF

Informatik Prüfung 3 ECAP **4.1** Stapel: benutzt das LIFO prinzip es ist geignet für z, B: search history wieder finden. Mit push addiert man und mit pop wird das letzte Element entfernt. Schlange: benutzt das FIFO prinzip es ist geignet für prozesse die der Reine folge nach verarbeitet werden. S...

Informatik Prüfung 3 ECAP **4.1** Stapel: benutzt das LIFO prinzip es ist geignet für z, B: search history wieder finden. Mit push addiert man und mit pop wird das letzte Element entfernt. Schlange: benutzt das FIFO prinzip es ist geignet für prozesse die der Reine folge nach verarbeitet werden. Sie werden mit enque addiert und mit deque - entfernt. Man jeles Element der Reihenach untersucht bis es ran jeles Element der Reihenach untersucht bis es ran jeles Element der Reihe **4.2** Lineare suche ist sinnvoll wenn es eine Weine Menge die Daten ungeordnet sind, es. keine wiederholungen dabei sind. Es ist gut wenn die Daten Daten gibt oder keine wiederholungen dabei sind. Worst Case $O(n)$ Binäre suche schaut an das Mittlere Element und wenn die Suche kleiner oder grösser ist, dann wieder in dieser hälfte bis es gefunden wird. Es geht nur von Elevente Daten geordnet sind, siegt 0(log n) (es wired gleich Binärer such baum: ist eine Datenstruktur die für effiziente suchen an es mittleren Element wieder in optimvisiert Es ist gut für jrave datermages, optimvisiert zur Suchzeite Worst case O(log n) Binärer such baum: ist eine Datenstruktur die für effiziente suchen Bäume. sie bestehe aus Krate (Parents) die maximal es ermöglichen. Sie bestehe aus Krate (Parents) die maximal es ermöglicht schneel verwendet werden. Such Bäurme. Sie bestehe aus Krate (Parents) die maximal es ermö öglicht schneel logarith logarith sche Suche O(log n) bei dverage-Case das kleinere "Kind" links und das grössere rechts. oft ist das kleinere "Kind" **4.3** Dubble sort: vergleiche, 25 E-marsucht ver-2520-rechts Element und wenes grosser ist, es mit den Werneren Element, tauscht es mit den kleineren Element, bis 25-30-links es nicht mehr geht, darach wird das wiederholt bis die Liste sottiert ist. O(n) Selection sort: Funktioniert in den man die kleinste findet anderer extren legt. d.h. Element nimmt und an an jeder Stelle, Danach geht man zum7 (oder grösste) das kleinste Element macht, es mit der 2. kleinsten Element unsw. vertauscht es cachster Element obwahl es schneller ist : $O(n^2)$ (immer O(n²)) 8,2,3 7,5. **4.4** Effizienziist wenn ein algorythmus ein problem schneller efficient mit weniger aufwand Löser kan Rotation gemessen: O(n) = das Problem bleibt gleich egal was "Odrotation gemessen: O(log n) lauszeit wächst langsamer weil die zeit pro Schritt halb so gross wird O(n) = wächst wächst direkt proportional zur Eingabe grösse. O(n^2) = wächst quadmtisch mit der eingabe grössen. Inefficient O(n!) = wächst exponential zur Pus NP problem: P = polynomiale Zeita Zeit die ein CPU braucht um ein probler | | 1 | 2 | 4 | 8 | 16 | 32 | 64 | 128 | 256 | 512 | 1024 | | :---- | :-: | :-: | :-: | :--- | :--- | :--- | :--- | :----- | :----- | :---- | ----- | | $N^2$ | 1 | 4 | 16 | 64 | 256 | 1024 | 4096 | 16384 | 65536 | 262 | 441 | | $2^n$ | 2 | 4 | 16 | 256 | 65536 | 1024 | 4096 | 16384 | *65536* | 2621 | 441 | | *N!?* | | 2 | 24 | 4022 | 209 | | | *41 908* | | | | koun (probleme die schnell gelöst werden könne.) NP = probleme dieser art sind einfach. - zu übeprofen aber nicht einfach lösen (rubiks cube). PNP: die frage ist; ist jedes Problen welches man schnell überprüfen kann (NP) auch schnell lösbar (P)