IK Prüfung 3 PDF - Informatik, Datenstrukturen und Algorithmen

IK Prüfung 3 **3.13. Listen** **Listen** sind Datenstrukturen, die mehrere Werte speichern. In vielen Programmiersprachen, wie Python, können Listen unterschiedliche Datentypen enthalten und sind flexibel in der Größe. Sie sind sehr nützlich, um eine Sammlung von Werten zu speichern, auf die späte...

IK Prüfung 3 **3.13. Listen** **Listen** sind Datenstrukturen, die mehrere Werte speichern. In vielen Programmiersprachen, wie Python, können Listen unterschiedliche Datentypen enthalten und sind flexibel in der Größe. Sie sind sehr nützlich, um eine Sammlung von Werten zu speichern, auf die später zugegriffen werden kann. - **Einsatz von Listen:** Listen werden verwendet, um mehrere Werte zu speichern, die miteinander in Beziehung stehen, z. B. eine Liste von Zahlen, Namen oder Objekten. - **Schleifen mit Listen:** Schleifen, wie die for-Schleife, werden verwendet, um durch alle Elemente einer Liste zu iterieren und Operationen auf jedem Element anzuwenden, wie z. B. eine Berechnung oder Ausgabe. **3.14. Unterprogramme** **Unterprogramme** (auch als Funktionen oder Methoden bezeichnet) sind Codeblöcke, die eine bestimmte Aufgabe ausführen. Sie helfen, ein Programm in kleinere, verständlichere Teile zu gliedern und die Wiederverwendbarkeit von Code zu fördern. - **Einsatz von Unterprogrammen:** Unterprogramme strukturieren ein Programm und ermöglichen es, gleiche Aufgaben an mehreren Stellen im Code auszuführen, ohne sie jedes Mal neu schreiben zu müssen. - **Parameter:** Unterprogramme können Eingabewerte (Parameter) erhalten, die sie in ihren Berechnungen oder Prozessen verwenden. So können Unterprogramme flexibel mit verschiedenen Daten arbeiten. **3.15. Funktionen** **Funktionen** sind eine spezielle Art von Unterprogrammen, die einen **Rückgabewert** an das Hauptprogramm zurückgeben. Funktionen sind nützlich, wenn eine Berechnung oder Verarbeitung durchgeführt wird und das Ergebnis an das Hauptprogramm zurückgegeben werden soll. - **Rückgabewerte:** Funktionen liefern ein Ergebnis, das durch das Schlüsselwort return zurückgegeben wird. Dieses Ergebnis kann dann im Hauptprogramm weiterverarbeitet oder gespeichert werden. - **Verarbeitung im Hauptprogramm:** Der Rückgabewert einer Funktion kann im Hauptprogramm verwendet werden, um weiter Berechnungen anzustellen oder in Bedingungen zu integrieren. Diese Konzepte sind entscheidend, um ein strukturiertes und effizientes Programm zu schreiben. Sie ermöglichen es, Programme übersichtlicher zu gestalten und den Code modular zu halten. 4.1 [Stapel]: ist eine datenstruktur welches das LIFO prinzip benutzt (last in first out), die letzte Daten die addiert wurden sind die ersten die entfernt werden. Es ist geeignet um z.B: search history wiederfinden oder «ctrl z» funktion. Mit «push» welden Elemte addiert, mit «pop» werden die Element wieder entfernt. [Schlange:] ist eine Datenstruktur welches das FIFO prinzip benutzt (first in first out), das erste Element wird auch als erster entfernt. Man kann es z.B; bei warteschlangen mit packetensendung (man verschickt Information und die Informationen die zuerst geschickt wurden sind die ersten die ankommen.) benötigen. Daten werden mit «enque» addiert und mit «deque» entfernt. 4.2 [Lineare Suche:] ist eine Suchalgorythmus welches jedes Element durchsucht bis es das richtige gefunden hat. Es kann bei ungeordnete daten benutzt werden und ist auch gut bei kleine Datenstrukturen. Worst case O(n). [Binäre Suche;] ist ein Suchalgrythmus welches in der Mitte anfängt und sieht, ob das Element grösser, oder kleiner ist, dann geht zur kleineren/grösseren hälfte und halbiert es wieder um zu zu schauen b das Elemt grösser oder kleiner als die mitte ist unsw. Binäre Suche geht leider nur bei geordnete Daten. Worst case O(log n). [Binärer Suchbaum;] ist eine Datenstruktur welches aus knoten besteht. Alle Knoten haben höchstens zwei Kinder, das kleinere Element links, das grössere rechts. Es ermöglicht schnelle suche bei einer average case von O(log n). 4.3 [Bubble Sort;] ist ein Sortieralgrythmus, es vergleicht das erste Element um zu sehen ob es grösser ist als das Element nebem ihm, wenn ja dann werden die Element vertauscht, wenn nicht wird das grössere Element als nächstes verglichen. Die erste runde endet mit dem grössten element an letzter Stelle und danach beginnt eine neue Runde bis die Liste Sortiert ist. Es ist nicht seht praktisch und hat ein Worst case von O(n\^2)\  [Selection Sort;] ist ein anderer Sortieralgorythmus. Man geht durch die Liste, nimmt das kleinste Element und vertauscht es mit ersten Element der Liste, bis man die Liste sortiert hat. Es ist schneller als Bubble sort aber hat trotzdem ein worstcase von O(n\^2). 4.4 [Effizienz;] ist wenn man ein programm so ändert, dass es weniger zeit braucht und weniger resourcen. In der informatik wird es mit der O notation gemessen:\ O(1) = bleibt statisch, es ändert sich nicht. O(log n) = die laufzeit wird langsamer weil die zeit pro schritt halb so gross wird. O(n) = wächst genau prportional zur Eingabegrösse. N = 6=\> 6 O(n\^2) = wächst quadratisch. N= 5 =\>25 O(2\^n) = wächst exponentiell zur eingabe. N = 4 =\> 16 O(n!) = wächst faktoriell. 5! =\> 5\*4\*3\*2\*1 = 120 [P = NP problem;] ist eins der schwierigsten prbleme der Informatik und Matemathik, es will sehen ob jedes problem welches schnell überprafbar ist (wie ein Rubiks cube) auch schnell lösbar ist. P = polynomiale Zeit (bezeichnet die Laufzeit eines Algorithmus, die mit einem Polynom der Eingabedatengrösse wächst) NP = die Menge von Entscheidungsproblemen, deren Lösungen in polynomieller Zeit verifiziert werden können.