Das Video kommt von YouTube: erst beim Abspielen verbindet sich die Seite mit YouTube (Google).
Was ist ein Algorithmus? Eigenschaften von Algorithmen | Algorithmen und Datenstrukturen Teil 1
Das Wichtigste aus dem Video
Tipp auf eine Zeit – das Video springt genau dorthin.
Transkriptautomatisch erstellt · 63 Zeilen
- hallo und herzlich willkommen zum ersten video einer neuen videoserie über algorithmen und datenstrukturen in der wir uns die eigenschaften grundlegender
- datenstrukturen der informatik sowie die verschiedenen algorithmen die darauf operieren anschauen wollen und die erste frage die sich stellt ist natürlich was
- ist eigentlich ein algorithmus und die definition ist das ist eine allgemeine vorgehensweise zur lösung eines problems bestehen aber es endlich fielen
- eindeutig definierten schritten und diese definierte und das natürlich wenig intuitiv deshalb schauen wir uns ein beispiel an und anhand dessen dann die
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- zu schritt 5 und schritt 5 falls wir haben alle zahlen betrachtet x-men enthält nun die kleinste zahl auf 60 bis xl
- es gibt noch eine andere darstellungsform von algorithmen das sogenannte flussdiagramm und dass es eben der algorithmus von gerade als
- flussdiagramm dargestellt einfach kurz pausieren und durchgehend das sieht man halt sehr häufig diese darstellung solltest du diesen algorithmus noch
- 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
- algorithmus sehen wir schon ein paar grund konstrukte von programmiersprache und auch algorithmen um allgemeinen variablen also einfach platz hatte die
- dann werte beinhalten und diese werte kann man ändern im laufe des algorithmus oder des programms man sieht hier bedingte anweisungen also falls eine
- 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
- grundideen kann man jetzt endlich jeder einen algorithmus der welt beschreiben und anhand dieses algorithmus sieht man außerdem einige wichtige eigenschaften
- von algorithmen im allgemeinen und zwar einmal die allgemeingültigkeit der algorithmus löst alle probleme eine problemklasse unser algorithmus von
- 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
- algorithmus funktioniert für eine ganze klasse von eingaben es ist völlig egal welche zahlen nicht rein steckt zudem die eindeutigkeit das
- 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
- 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
- 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
- ausgeführt werden bei unseren biorhythmus war aber eben jeder schritt problemlos ausführbar dann gibt es noch die sogenannte
- statische findet oder endlichkeit das heißt der algorithmus ist durch eine endliche anzahl von schritten beschrieben in unserem fall waren das
- 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
- eine endlosschleife eine endlosschleife kann in einem einzigen schritt beschreiben nämlich schritt 1 wiederhole schritt 1 eine beschreibung von der
- 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
- wir haben in der realität immer nur endlich ein speicherplatz und somit seine algorithmen mit unendlichem speicher bedarf einfach nutzlos und
- nicht ausführbar und auch dieses kriterium haben wir bei unserem algorithmus erfüllt wir speichern nur die endliche eingabe und
- zwei weitere variablen also endlicher speicherplatz und das nennt man eben dynamische finito und letztendlich ist ein algorithmus nur sinnvoll wenn er
- 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
- 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
- die unendlich lange laufen bis sie das perfekte ergebnis liefern zum beispiel gradienten abstiegs verfahren usw bei diesem verfahren erfüllt man die
- 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
- 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
- das heißt ich terminieren die algorithmen und letztendlich künstlich es gibt noch zwei weitere sehr wichtige eigenschaften für die beschreibung von
- algorithmen nämlich einmal die determiniert haid und die besagt dass ein algorithmus bei gleicher eingabe stets dasselbe ergebnis liefert man dank
- vielleicht erst mal dass alle algorithmen determiniert sind aber es gibt eine ganze klasse von algorithmen die stochastischen algorithmen die
- intern mit zufall arbeiten und gegebenenfalls bei derselben eingabe andere ergebnisse liefern dass es dann meistens annäherungs verfahren
- und dann gibt es noch den determinismus und ein algorithmus ist determiniert wenn zu jedem zeitpunkt der ausführung der nachfolgende arbeitsschritt
- eindeutig festgelegt ist hier ist also zum beispiel eine zufällige wahl von werten oder schritten nicht erlaubt die schrittfolge es immer
- dieselbe für dieselbe eingabe aus determinismus folgt immer determiniert hat das ist auch irgendwie logisch denn wie soll bei derselben eingabe und
- derselben abfolge von schritten ein anderes ergebnis rauskommen und aus der terminiert hat folgt aber nicht immer determinismus und das sieht man ganz gut
- an einer kleinen variation unseres algorithmus von gerade eben wir wollen nun das ein element aus zwei zahlen mengen
- 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
- diesen beiden ergebnisse neben das kleinste nimmt unter salzergebnis ausspuckt und hier haben wir immer dieselbe abfolge von schritten das heißt
- wir haben einen deterministischen algorithmus jetzt können wir aber auch eine nicht deterministische version davon schreiben zugegeben sehr
- 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
- 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
- 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
- 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
- menge oder das kleinste element der zweiten menge berechnen der rhythmus ist hier also determiniert und ein reales beispiel für so ein
- 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
- 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
- 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
- bis zum nächsten mal [Musik]
Zum Nachlesen
AlgorithmusAlgorithmen bestehen aus endlich vielen, wohldefinierten Einzelschritten. ... Damit können sie zur Ausführung in ein Computerprogramm implementiert, aber auch in …
InformatikAls einfache Rechengeräte leisteten Abakus und später der Rechenschieber unschätzbare Dienste. 1641 konstruierte Blaise Pascal eine mechanische …
DeterminismusDer Determinismus (von lateinisch determinare ‚festlegen', ‚Grenzen setzen', ‚begrenzen') ist die Auffassung, dass alle – insbesondere auch zukünftige …