12A.1 Informatik, Datenstrukturen, Array, struct, Warteschlange, Stack, Baum
Jörn Loviscach
https://www.youtube.com/watch?v=UDMFnf3Hbqk

Transkript (automatisch erstellt)

0:00 letztes Jahr ging es ja um programmieren hauptsächlich wie man der Sprache C irgendwas mitteilen kann oder genauer gesagt dem Rechner in der Sprache C
0:08 etwas mitteilen kann die letzten Termine dieses Jahr wollte ich dann eben noch benutzen um ihn tatsächlich was über Informatik zu
0:15 erzählen nicht übers nicht so sehr übers programmieren man hat immer als Randthema das Programmieren dabei aber hauptsächlich soll jetzt Informatik
0:22 werden meine Idee soll noch mal erzählen meine Idee was der Zusammenhang zwischen programmieren und Informatik ist
0:33 programmieren auf der einen Seite und Informatik ist für mich so ähnlich wie rechnen und Mathematik wenn man in der Grundschule
0:44 sagt einmal ein das ist schon Mathematik dann ist das sehr gewagt Mathematik sollte eigentlich eher sein wie man rechnet die Theorie hinter
0:56 dem Rechnen Effizienz zu rechnen was man wie ausrechnen kann mit welchen Fehlern und ähnliche gesach ähnliche Sachen die höheren Weihen sozusagen des Rechnens
1:07 und so ähnlich würde ich das auch zwischen programmieren und Informatik sehen programmieren ist das was sie einhacken in das Entwicklungssystem C
1:17 oder Java oder was es auch immer nun gerade sein mag und Informatik ist das was dahinter passiert die Theorie wie programmiere ich etwas effizient wartbar
1:27 wie programmiere ich so dass ich drei Tage später noch verstehe Seen kann oder andere Leute ein Jahr später noch verstehen können was ich da gemacht habe
1:34 wie gehe ich vor um ein Problem informatisch zu lösen was ist der Ansatz in welche Teilprobleme zerlege ich ein Problem und ähnliche Geschichten das
1:43 wäre für mich dann Informatik das reine programmieren braucht man dann zwar um das tatsächlich dann umzusetzen aber das große Ganze dahinter wäre die Informatik
1:52 und ja die restlichen Termine jetzt wollte ich ein bisschen was zu Informatik erzählen
1:59 äh erstes große Thema in der Informatik sind typischerweise die Datenstrukturen dass man sich Gedanken macht wie man seine Daten ablegt s dass
2:13 man sie später auch wiederfinden kann in vernünftiger Form was wir schon kennen und was in C ja eingebaut ist ist das
2:22 Array das heißt sie haben z.B eine beim eindimensionalen Array quasi Sie eine Liste von Sachen und können dann einfach mit der Nummer drauf zugreifen sie
2:36 können sagen gib mir 01 2 3 Gib mir die Nummer 4 Name des errays eckige Klammern 4 gib mir die Nummer 4 aus dieser Liste raus und damit was veranstalten sie
2:49 können aber auch umgekehrt sagen in die Nummer 4 in dieser Liste gleich schreibe irgendwas rein und analog dann mit dem zweidimensionalen und dreidimensionalen
2:59 und so weiter in C das ist relativ weitgehend in die Sprache eingebaut mit diesen eckigen
3:07 Klammern was auch noch eingebaut ist haben wir gesehen dieser Verbund struct structure dass sie mehrere verschiedene Sachen in dasselbe Objekt reinkippen
3:21 können wten das bei der Bestellung z.bi dass sie sagen können oh meine Bestellnummer ist so und zu viel und dann gibt's vielleicht einen Titel des G
3:30 was eine Zeichenkette ist und dann gibt's vielleicht noch eine Anzahl wie oft das bestellt ist vielleicht noch ein Preis und so weiter all das giip ich
3:36 zusammen in einen Verbund und kann dann gezielt die einzelnen Sachen wieder rausholen das war ja in C dass man Punkt schreibt der Name dieses Verbunds der
3:46 Variable die die so ein Verbund ist der Name dieser Variablen Punkt und dann der Name des jeweiligen members des jeweiligen Eintrags
3:57 hier so ging da der Zugriff in C für sich war das immer ein bisschen blödsinnig warum soll ich wenn ich diese Sachen einzeln habe das jetzt
4:08 in den Kasten Gießen viel sinnvoller sind diese Verbünde wenn ich viele davon habe z.B wenn ich ein Array aus straks habe das kam ja auch schon in den
4:19 Praktiker vor ein Array aus strakt dann ist das viel sinnvoller dieser Verbund so tritt es typischerweise auf nicht alleine sondern ich habe gleich eine
4:29 ganze Sammlung davon z.B eine Datenbank können Sie sich so vorstellen als Sammlung von strak steht die Vorname über steht der Vorname drin überall
4:38 steht der Nachname drin überall steht die Telefonnummer drinen überall steht die Adresse drin in jedem Datensatz und jeder dieser Verbünde wäre dann ein
4:49 Datensatz okay aber der nackte Verbund ist tatsächlich nur so ein Ding von dieser Sorte und man baut dann gerne kompliziertere Sachen draus das sind die
4:59 wes Datenstrukturen die in C eingebaut sind in anderen Programmiersprachen sind nch weitere Datenstrukturen mehr oder minder eingebaut zumindest
5:06 bibliotheksmäßig verfügbar kam ja schon in den Videos vor das was
5:15 man häufiger braucht ist die Warteschlange die Q so eine schöne Schreibweise UE UE Warteschlange Q das ist im Endeffekt sowas wie ein
5:30 diesay allerdings variabler Länge da passen gerade so viel rein wie vor dem Schalter stehen in der Warteschlange es gibt eine Funktion um
5:45 jemanden in die Warteschlange zu stellen NQ heißt die dann typischerweise weiß kein schönes deutsches Wort einschlangen an die
5:56 Schlange stellen an die Schlange hängen und gibt eine Funktion um den ersten vor dem Schalter zu bedienen DQ sie wollen entschlangen so NQ
6:08 einschlangen anschlangen und DQ entschlangen das sind so die beiden wesentlichen Funktionen die man dann für so eine
6:17 Datenstruktur hat bei Array und bei der strak war das in C mehr oder minder eingebaut wenn sie im reay sagen wollen oh ich möchte in die Nummer vi was
6:27 reinschreiben dann schreiben Sie so Nummer vi was rein und lich beim strakt mit dem Punkt irgendwas gleich das ist von der Sprache schön
6:38 abgebildet wenn man sowas haben will wie eine Warteschlange ist das in den meisten Sprachen nicht so direkt abgebildet man muss den wirklich
6:45 Funktionen aufrufen NQ DQ und zu sagen jetzt bitte einen in die Schlange stellen und dann hin und wieder natürlich auch mal einen
6:53 abholen die wartschlange sehen sie sehr häufig wenn es um irgendwelche Datenübertragungen geht ich habe vielleicht ein Modul in meinem Programm
7:05 das Sachen verschickt druckt speichert und ich habe ein Modul in meinem Programm das Sachen einliest und um diese beiden halbwegs
7:17 unabhängig zu halten setzt man da gerne eine rein eine Warteschlange dieses Modul was die Daten liest füttert die wadeschlange mit NQ
7:28 und das Modul was die Daten verarbeitet weiterschickt was auch immer liest die Daten mit DQ raus und welchem Tempo das jeweils passiert wird durch diese
7:38 Warteschlange unabhängig voneinander es muss nicht dieses Modul das Daten verarbeitet genau einen Datensatz lesen wenn das Modul das Daten erzeugt
7:48 diesen einen Datensatz liefert der Datensatz kann dann einfach hier in der Warteschlange stehen wie Weihnachten mit dem Päckchen bei der Post im Effekt
7:59 sollte natürlich auf lange Sicht sollte genauso viel hier an Daten verarbeitet werden wie hier an Daten erzeugt wird sonst heißt das ja dass diese dass in
8:09 der Warteschlange noch ein paar Leute stehen bleiben das wäre dann keine gute Idee also auf lange Sicht sollte das Tempo dann schon dasselbe sein oder das
8:18 Tempo hier des datenverarbeiters eigentlich noch ein bisschen schneller sein als das Tempo des datenerzeugers dass Sie sicher sein
8:25 können dass diese Warteschlange irgendwann auch tatsächlich leer läuft und nicht irgendwer noch drin hängen bleibt das ist die Warteschlange mit
8:34 ihren beiden wesentlichen Funktionen NQ DQ verwandt damit ist der Stack der Stapel ich lege einfach Datensätze auf den
8:48 Tisch und arbeite immer mit dem obersten dann gibt's dann auch für diese Datenstruktur zwei übliche Funktionen für den
8:58 Zugriff zur Erinnerung noch mal beim beim Array schreiben sie ja zum Lesen einfach nur a von 4 und machen das mit a von 4 mal irgendwas und machen was damit
9:09 und zum schreiben schreiben Sie beim Array in C A von 4 ist gleich irgendwas das ist alles nett in die Sprache
9:18 eingebaut bei der Q verwenden Sie zum Schreiben eine Funktion NQ und zum Lesen eine Funktion DQ und bei dem Stack brauchen wir auch dann eine Funktion zu
9:29 zum Schreiben die heißt Push typischerweise hat man sich dann über die Jahrzehnte drauf geeinigt und eine Funktion zum Lesen die heißt Pop
9:38 typischerweise der Unterschied zwischen steack und Warteschlange ist dass beim steack immer das allerletzte Element hier betrachtet wird sie legen das
9:48 letzte Element drauf und wenn sie was holen vom steack kriegen sie auch das letzte wieder sollte sagen das jüngste ist vielleicht klarer bei der
9:58 Warteschlange kriegen sie das älteste Element wieder denjenigen der sich vor Uhrzeiten in die wadeschlange gestellt hat der wird hier wieder rausgeholt als
10:08 Erster das ist first in first out das ist noch so eine wesentliche Abkürzung bei diesen ganzen Techniken gibt's dann auch in Hardware first in first out
10:18 der erste der reinkommt in den Laden ist auch der erste der wieder rausgeht aus dem Laden und der Stack ist eben andersrum das ist Last in first out der
10:30 letzte der reinkommt Last in first out der letzte der reinkommt ist der erste der rausgeht der letzte der reinkommt ist der erste der dann auch wieder
10:39 rausgeht im Verlauf zeigen wenn der erste reinkommt jemand ruft Push auf dann kommt vielleicht noch jemand mit Push da drauf gelegt und noch jemand mit
10:49 Push da drauf gelegt wenn sie jetzt Pop aufrufen ist der erste der rausgeht der letzte der reingekommen ist der jüngste der oberste das ist anders beim steck
11:00 als bei der Warteschlange im wahren Leben kommt der steck sehr häufig vor man sieht ihn nur
11:07 nicht der arbeitet im Hintergrund im Rechner z.B wenn es drum geht die Rücksprünge aus den Funktionsaufrufen zu organisieren der Rechner legt sich auf
11:17 einem Stck ab aus welcher Funktion er gerade gekommen ist und wenn er aus der Funktion in der er gerade ist in andere Funktion spricht legt ab wo er wieder
11:26 zurück muss und so weiter und so weiter bei jedem Sprung in ine Funktion legt ab wo er wieder zurück muss an der Stelle kommt ein steck ganz prominent in den
11:34 ganzen Microchips vor man sieht ihn aber seltener beim Programmieren und ja was man dann tatsächlich auch
11:46 noch sehr häufig sieht anders als den Stack ist der Baum oder tree z.B bei Dateisystemen es gibt eine Wurzel des Dateisystems bei bei ist das
11:59 dann immer gerne Laufwerk C oder ähnliches eine Wurzel des Dateisystems und dann liegen auf der obersten Ebene z.B Ordner in dem
12:13 dateilystem vielleicht auch schon Dateien wer weiß und in den Ordnern können wieder Ordner liegen oder Dateien liegen ne W
12:25 das was oder auch noch mehr Ordner und so weiter und so weiter sowas wäre ein Baum sie sehen eine ganz typische
12:36 Verwendung Dateisysteme haben Bäume ich kann hier zu diesem Knoten das nennt sich dann Knoten ich gehe von meinem Wurzelknoten zu diesem Knoten
12:46 dieser Knoten ist ein Ordner hat kann damit weitere Kinder enthalten Kindknoten enthalten also das hier wären jetzt Kinder von
12:54 diesem Knoten Kindknoten von dem Knoten diese Kindknoten könnten auch selbst wieder Kindknoten enthalten zumindest wenn es Ordner
13:05 sind und das ganze sieht aus wie ein umgekehrter Baum die Wurzel ist oben man malt das typischerweise in der Informatik so dass die Wurzel des Baums
13:12 oben ist und der Baum dann nach unten aufgefächert ist wenn Sie hier irgendwo ans Ende geraten da wird das mal was wenn Sie hier irgendwo ans Ende
13:22 geraten ich mal hier vielleicht noch mal ein Ordner rein der noch irgendwas hat und hier mal ich mal ein einzelnes Dokument rein wenn Sie hier ans Ende
13:30 geraten dann haben sie ein Blatt so nennt sich das dann wenn es nicht mehr weiter verzweigt also es startet oben mit der Wurzel und irgendwo unten ändert
13:40 es dann mit Blättern das ist die Analogie zum zum Baum und insbesondere gibt es hier keine Zyklen also es
13:49 gibt im echten Baum sollte ich sagen im echten Baum gibt es nicht diese Situation dass eine Datei in zwei Ordnern liegt im wahren Dateisystem
14:00 gibt's das dann lustigerweise doch weil es an einigen Stellen eleganter ist in der strengen Theorie des Baums gibt's das nicht dass ein Ast mit dem anderen
14:09 verwachsen ist also hier können Sie nirgendswo mchten informatischen Baum können Sie nirgendswo im Kreis rumlaufen der ist azyklisch es gibt keinen Zyklus
14:18 keinen Zykel kein geschlossenen Kreis im richtigen Baum im wahren Leben macht man es dann gerne zumindest bei den derteien doch
14:27 ähm andere Beispiele für Bäume wären HTML Dateien dass sie auf einer Webseite mehrere Abschnitte haben in den
14:38 Abschnitten sitzt Text und dann ein Foto und eine Liste und in der Liste sitzt gelleicht was an Links oder noch mal ein Foto und so weiter und so fort also auch
14:47 diese Struktur von Webseiten ist dann automatisch ein Baum offensichtlich etwas das ser häufig vorkommt im wahren Leben