Bäume in der Informatik
frankjuchim
https://www.youtube.com/watch?v=CYHnYPKYMLw

Transkript (automatisch erstellt)

0:00 neun leute können uns mit den bäumen in der informatik beschäftigen dazu habe ich das ganze ein bisschen unterteilt zuerst schauen und sind
0:08 aufbau eines baumes haben dann noch ein paar fachbegriffe und am ende nach buch für benutzt man die bäume der informatik eigentlich aber wir starten mit dem
0:18 aufbau eines baumes das ist das typische dann an einen baum sieht in informatik sehen die meistens so aus
0:25 dort gibt es unterschiedliche sachen die wichtig sind einmal diese schwarze striche das sind die kranken dann gibt es die gelben weil sich hier
0:33 dargestellt das sind die klo wichtig die sind natürlich nicht immer geld und gestelle sind nicht mehr schwarz und dann gibt es noch die wurzel die wurzel
0:43 ist auch ein knoten aber ein ganz besonderer ja wir sehen schon von den tropen weg können kanten gehen und in die knoten
0:52 von oben reinigen kann gehen außerdem wurde bei der wurzel wird keine eingehenden kann genauso gibt es blätter dass zum beispiel ein bisschen blatt
1:06 beim blatt gibt es keine ausgehenden kann also wir merken uns knoten generell und zwei besondere knoten einmal die wurzel keine eingehende kanten und
1:17 blätter keine ausgehenden kannten es kann immer nur eine wurzel geben bei uns aber es kann beliebig viele blätter bei bäumen kanten gibt es sowieso ganz
1:30 ganz viele auch okay wir machen weiter der fahrt in einem baum hier ist mal so einfach rot dargestellt der vater ist eigentlich nur der weg von
1:41 einem knoten zu einem andere wichtig in dem fall hier würden wir uns immer von oben nach unten bewegen ja das heißt hier von der wurzel
1:50 hinunter zu einem schon wichtig dabei wir können uns niemals im kreis bewegen wollen wir können nicht so aufgebaut sein dass ich irgendwann behandlungen
2:01 starte und wieder bei diesen knoten angekommen das geht nicht der grat eines knoten ja eben schon drüber gesprochen es gibt eingehende und
2:12 ausgehende kann der grad eines knoten wird über die ausgehenden kanten bestellt heißt die anzahl der ausgehenden kannten bis der grabesruhe
2:24 nehmen uns mal diesen knoten jetzt beispiel dort habe ich drei ausgehende kann also ist der grad des clubs 3 bei dem knoten
2:35 hier unten habe ich nur zwei ausgehende kannten somit ist der grad des klubs 2 ich hatte auch schon gesagt letter sind ja auch
2:46 knoten haben aber immer null ausgehen bekannten damit ist ja gerade eines jeden staates ist immer nur noch ein ganz wichtiger punkt und zwar der
2:58 geraden eines baumes steht dort ganz oben rechts der grat eines baumes ist immer der grad der knoten mit dem höchsten grad in den
3:10 ganzen baum bestimmt den grad des baumes das heißt ich muss mir den ganzen baum an den knoten mit den meisten ausgängen kanten und das ist der grad des baus in
3:22 dem empfang ist genau dieser clown er hat drei ausgänge kanten und damit ist der grad des baumes 3 die tiefe eines baumes
3:33 wir haben gerade schon über fahrer gesprochen die tiefe eines baumes ist der längste fahrt heißt nichts anderes als meistens längster part wird
3:45 wahrscheinlich bei der wurzel starten und zum weitesten entfernten land gehen in dem fall ist es dieses könnte aber auch dieses sein
3:55 wir sind beide gleich lang entfernt haben beide die bartling 3 somit ist die tiefe des baumes 3 ja dieses blatt hat auch die tiefe drei dann also die tiefe
4:14 des baums ist der längste mögliche fatih nicht in den baum bauen kann oder laufen kann
4:24 kommen wir noch zu den ebenen das hängt sehr eng damit zusammen wir sehen eine ebene 30 21 und ganz oben geben 000 ist immer die wurzel und danach können
4:38 beliebig viele proben auf ebene eins folgen ob er zwei können wieder beliebig viele folgen wird eben drei ab das heißt nicht
4:48 dass jeder knoten oder jeder fahrt bis zur maximalen ebene gehen müssen wir sehen auch hier können noten schon eher
4:58 ich hab mal abbrechen ja das ist keine weiteren möglichkeiten gebiet meine dingen wir einen spiel betrachten würden wir es an dieser stelle vorbei
5:07 da kommen wir gleich mal zu also es gibt verschiedene ebenen aber nicht jeder fahrt muss bis zur letzten ebene geht warum die ebenso
5:24 wichtig sind und wo sie anwendung finden da kommen wir auch kleiner unruhe zu beenden zuerst punkten ist noch mal teil dollar
5:31 an das ist eigentlich auch nichts besonderes herr basiert wieder auf dem teil und herrscher prinzip was wir ganz
5:38 viel aus der informatik kennen und warum man das macht also erstmal wie macht man es man nimmt sich einen teil eines baumes einen teil
5:49 bau und betrachtet ihn als eigenen baum ja jeder 1 markiert teil eins und drüben teil 2 da fehlt noch die 2 die könnt ihr euch zu bedenken warum macht man das
6:04 letzte detail bauen mit alle warum macht man das mit diesen teil wollen bäumen neigen sehr dazu sehr sehr groß zu werden und sehr sehr unübersichtlich und
6:19 dann es ist nicht sinnvoll teile und herrsche der das ganze oder den ganzen baum in verschiedenen teile zu zerlegen um dann die übersicht behalten und in
6:33 teil baum operieren zu können ich habe versprochen wir machen noch ein anwendungsbeispiel alle wo findet eigentlich so etwas wie
6:41 ein baum oder einen baum prinzip anwendungen dazu kann man sich beispielsweise das spiel hoffen ich kenne es jeder tic tac toe nehmen hier
6:51 habe ich mal nur einen teil des ganzen genommen warum naja wenn wir uns überlegen das ist zwar die wurzel dort oben aber wenn wir die
7:01 erste kurze nehmen würden hätte sie ja nein oder grad 9 ja also der oberste knoten hat gerade neun werden uns mal so einfällt hier
7:12 angucken dann hat das neue möglichkeiten wo ich mein kreuz beziehungsweise kreis je nachdem was ich für ein symbol habe setzen könnte
7:24 das heißt neuen möglichkeiten grad neu zweiter ebene zu ebene 1972 wenn es dann nur nur noch acht aber acht proben das heißt achtmal neuen und so weiter
7:43 und so fort wenn dir dieser teil baum und wollen wir ganz baum unglaublich groß werden wir nehmen uns jetzt mal nur noch das
7:50 beispiel wo wir nur noch drei möglichkeiten haben zu setzen wo es jetzt die anwendung wenn wir zum beispiel einen computer geht nach vorn
8:04 und jetzt mit diesen bäumen arbeiten können wir an dieser stelle hier in schweigen jürgen treffen und zwar die entscheidung wo der computer sein kreuz
8:14 setzt oder in dem fall oder cognac oder computer sein kreuz ist in diesem fall hat er kommt wieder super das kommt ja und zwar wenn wir das hinnehmen
8:24 also wir setzen das kreuz hier an dieser stelle rechts in der mitte dann haben wir danach folgende möglich was ich machen könnte wir könnten als
8:34 computer verlieren oder gewinnen 50 50 wir wissen ja nicht was der spieler macht alte 50 50 shops setzen wir das letzte zeichen des kreuzes jetzt
8:46 unten rechts dann haben wir folgende möglichkeiten wir können verlieren oder naja oder spielt unentschieden aus das heißt
9:00 gewinnen kann der computer nicht mehr jetzt könnte man sagen na ja damit ist diese option hier ja schon deutlich interessanter als die zweite option
9:09 gucken wir uns die option ganz trüben an wir setzen unser kreuz links in der mitte dann gibt es folgende möglichkeiten entweder ist das spiel
9:19 unentschieden aus oder der computer gewinnt so der auswertung nach wir können die dritte variante da ganz schön wir
9:29 hin dann können wir als computer nicht mehr verlieren wir können nur noch im schlechtesten fall gibt es unentschieden aus oder wir gewinnen
9:38 das heißt wenn der computer hätten anhand dieses baumes dann entscheiden würde würde er die option ganz da drüben gehen und das spiel wahrscheinlich für
9:48 sich entscheiden oder es geht unentschieden aus und so würden bäume zum beispiel bei der entwicklung eines algorithmus für das
9:59 gittertor spiel genutzt werden können sicherlich das jetzt noch keine ki aber es zumindest ein algorithmus wie ein computer oder einen computergegner
10:07 funktionieren könnte das war ein kurzer überblick zu bäumen oder bäumen informatik ich hoffe das war verständlich wenn ihr fragen habt meldet
10:16 euch gerne ansonsten bis zum nächsten mal