Was ist ein Algorithmus? Eigenschaften von Algorithmen | Algorithmen und Datenstrukturen Teil 1
Turing Informatik
https://www.youtube.com/watch?v=VjKPsHYepaw

Transkript (automatisch erstellt)

0:00 hallo und herzlich willkommen zum ersten video einer neuen videoserie über algorithmen und datenstrukturen in der wir uns die eigenschaften grundlegender
0:07 datenstrukturen der informatik sowie die verschiedenen algorithmen die darauf operieren anschauen wollen und die erste frage die sich stellt ist natürlich was
0:15 ist eigentlich ein algorithmus und die definition ist das ist eine allgemeine vorgehensweise zur lösung eines problems bestehen aber es endlich fielen
0:24 eindeutig definierten schritten und diese definierte und das natürlich wenig intuitiv deshalb schauen wir uns ein beispiel an und anhand dessen dann die
0:31 eigenschaften die algorithmen allgemein haben wir haben folgendes problem wir haben eine menge von zahlen xxl und aus dieser menge wollen wir die kleine zahl
0:40 finden und ein alfa und auch nicht der effizienteste ansatz wäre dass man eine variable einführt die die aktuell kleinste bekannte zahl speichert und
0:50 dann geht man der reihe nach alle zahlen aus dieser zahl menge durch und schaut ob die aktuell betrachtete zahl kleiner ist als die aktuell kleinste bekannte
0:58 zahl und ist das der fall dann ersetzt man eben die zahl mit dieser neuen kleinsten zahl und wenn man am ende ist hat man die kleinste zahl gefunden und
1:06 der algorithmus sie dann ungefähr so aus wir führen eben x-men ein und setzten das auf unendlich und x-men speichert die aktuell kleinste bekannte zahl und
1:15 wir haben eine index variable in diesem fall genannt die setzen wir auf null und die beschreibt welches element wir gerade betrachten also am anfang geben
1:23 x0 dann schauen wir ob das aktuell betrachtete element xi kleiner als das aktuell klein zum element x-men ist am anfang ist das der fall denn x0 ist in
1:33 jedem fall kleiner als unendlich und ist das der fall so aktualisieren wir x-men auf eben die neue kleinste zahl dann in kommentieren wir uns also hat ihren
1:43 einfach eins drauf oben das nächste element zu betrachten da müssen wir natürlich erstmal schauen ob wir vielleicht schon alle zahlen betrachtet
1:49 haben also wenn die größer als es dann sind wir bereits alle zahlen durch gegangen wir sind fertig falls wir eben noch nicht alle zahlen betrachtet haben
1:57 dann springen wir zurück zu schritt 2 und schauen ob die nächste zeit kleiner ist als die aktuell kleinste zahl und sind wir eben fertig dann springen wir
2:05 zu schritt 5 und schritt 5 falls wir haben alle zahlen betrachtet x-men enthält nun die kleinste zahl auf 60 bis xl
2:12 es gibt noch eine andere darstellungsform von algorithmen das sogenannte flussdiagramm und dass es eben der algorithmus von gerade als
2:19 flussdiagramm dargestellt einfach kurz pausieren und durchgehend das sieht man halt sehr häufig diese darstellung solltest du diesen algorithmus noch
2:25 fragen geben so kann ich gerne noch mal ein video dazu machen aber grundsätzlich ist es eben einer der sehr einfachen algorithmen und an diesem
2:32 algorithmus sehen wir schon ein paar grund konstrukte von programmiersprache und auch algorithmen um allgemeinen variablen also einfach platz hatte die
2:39 dann werte beinhalten und diese werte kann man ändern im laufe des algorithmus oder des programms man sieht hier bedingte anweisungen also falls eine
2:48 bedingung war es dann tue das sonst tue dass man sieht berechnungen ganz klar das braucht man immer und wir haben auch bedingte sprünge und mit diesen wenigen
2:57 grundideen kann man jetzt endlich jeder einen algorithmus der welt beschreiben und anhand dieses algorithmus sieht man außerdem einige wichtige eigenschaften
3:04 von algorithmen im allgemeinen und zwar einmal die allgemeingültigkeit der algorithmus löst alle probleme eine problemklasse unser algorithmus von
3:13 gerade eben löst für egal welche menge von zahlen das problem die kleinste zahl zu finden es ist nicht spezifische eine bestimmte eingabe sondern der
3:23 algorithmus funktioniert für eine ganze klasse von eingaben es ist völlig egal welche zahlen nicht rein steckt zudem die eindeutigkeit das
3:30 heißt wir haben viele eindeutige schritte es ist immer klar was zu tun ist und bei uns durch die mathematische definition von vergleichs und rechen
3:37 operatoren sind alle operatoren wohl definiert und jeder schritt ist eben eindeutig außerdem muss jeder schritt aus führer seien ein beispiel wo das
3:47 nicht der fall wäre wäre ein schritt indem man zb alle bestellen von people rechnen müsste und da die unendlich viele stellen hat kann der schritt nie
3:55 ausgeführt werden bei unseren biorhythmus war aber eben jeder schritt problemlos ausführbar dann gibt es noch die sogenannte
4:01 statische findet oder endlichkeit das heißt der algorithmus ist durch eine endliche anzahl von schritten beschrieben in unserem fall waren das
4:09 genau fünf beachtet dass eine endliche beschreibung noch nicht bedeutet dass der algorithmus auch in endlicher zeit ändert ein beispiel wäre zum beispiel
4:16 eine endlosschleife eine endlosschleife kann in einem einzigen schritt beschreiben nämlich schritt 1 wiederhole schritt 1 eine beschreibung von der
4:24 länge 1 der algorithmus läuft aber eben unendlich durch außerdem darf ein algorithmus zu jedem zeitpunkt nur endlich viel speicherplatz benötigen
4:32 wir haben in der realität immer nur endlich ein speicherplatz und somit seine algorithmen mit unendlichem speicher bedarf einfach nutzlos und
4:39 nicht ausführbar und auch dieses kriterium haben wir bei unserem algorithmus erfüllt wir speichern nur die endliche eingabe und
4:46 zwei weitere variablen also endlicher speicherplatz und das nennt man eben dynamische finito und letztendlich ist ein algorithmus nur sinnvoll wenn er
4:55 irgendwann terminiert also nach endlich vielen schritten ein ergebnis liefert bei uns ist das der fall denn wir gehen nur einmal die endliche menge von zahlen
5:03 durch und führen für jede davon eine endliche anzahl von berechnung schritten aus bis wir das ergebnis haben und es gibt aber auch mathematische verfahren
5:12 die unendlich lange laufen bis sie das perfekte ergebnis liefern zum beispiel gradienten abstiegs verfahren usw bei diesem verfahren erfüllt man die
5:19 eigenschaft der terminiert häufig dadurch dass man dann ein abbruch kriterium einführt das heißt nach iks schritten höre ich einfach auf und
5:27 nehmen dann das ergebnis was vielleicht nicht perfekt ist aber relativ nahe an perfekt oder wenn das ergebnis nahe genug am optimum liegt dann höre ich auf
5:36 das heißt ich terminieren die algorithmen und letztendlich künstlich es gibt noch zwei weitere sehr wichtige eigenschaften für die beschreibung von
5:42 algorithmen nämlich einmal die determiniert haid und die besagt dass ein algorithmus bei gleicher eingabe stets dasselbe ergebnis liefert man dank
5:50 vielleicht erst mal dass alle algorithmen determiniert sind aber es gibt eine ganze klasse von algorithmen die stochastischen algorithmen die
5:56 intern mit zufall arbeiten und gegebenenfalls bei derselben eingabe andere ergebnisse liefern dass es dann meistens annäherungs verfahren
6:03 und dann gibt es noch den determinismus und ein algorithmus ist determiniert wenn zu jedem zeitpunkt der ausführung der nachfolgende arbeitsschritt
6:11 eindeutig festgelegt ist hier ist also zum beispiel eine zufällige wahl von werten oder schritten nicht erlaubt die schrittfolge es immer
6:18 dieselbe für dieselbe eingabe aus determinismus folgt immer determiniert hat das ist auch irgendwie logisch denn wie soll bei derselben eingabe und
6:26 derselben abfolge von schritten ein anderes ergebnis rauskommen und aus der terminiert hat folgt aber nicht immer determinismus und das sieht man ganz gut
6:34 an einer kleinen variation unseres algorithmus von gerade eben wir wollen nun das ein element aus zwei zahlen mengen
6:41 finden dazu können wir einen algorithmus schreiben der zuerst das teils element aus der ersten menge sucht dann das teils aus der zweiten menge und dann von
6:49 diesen beiden ergebnisse neben das kleinste nimmt unter salzergebnis ausspuckt und hier haben wir immer dieselbe abfolge von schritten das heißt
6:56 wir haben einen deterministischen algorithmus jetzt können wir aber auch eine nicht deterministische version davon schreiben zugegeben sehr
7:01 konstruiert wo wir erst eine zufalls zahl null oder eins erzeugen und dann abhängig vom wert dieser zahl erst das kleines element aus der ersten menge und
7:12 dann aus der zweiten menge oder eben umgekehrt suchen und dann suchen wir wieder am ende die kleinste von diesen beiden zahlen und haben das ergebnis
7:19 und hier ist eben die abfolge der schritte abhängig von der zufalls zahl das heißt es handelt sich um einen nicht deterministischen algorithmus aber am
7:27 ende kommt natürlich immer noch bei derselben eingabe dasselbe ergebnis raus weil das natürlich völlig egal ist ob er ist das kleinste elemente der ersten
7:34 menge oder das kleinste element der zweiten menge berechnen der rhythmus ist hier also determiniert und ein reales beispiel für so ein
7:41 algorithmus ist der quick sword mit zufällige wahl des parlaments und hier dann sieht man eben ganz gut dass die terminiert hat nicht immer determinismus
7:49 folgt das war es auch schon wieder vielen dank fürs zuschauen bei fragen oder video wünschen schreibt einfach einen kommentar über ein like oder abo
7:57 würde ich mich natürlich sehr freuen außerdem könnt ihr mich bei katrin unterstützen ein link dafür findet in der video beschreibung
8:03 bis zum nächsten mal [Musik]