Krautkanal.com

Veröffentlicht am 2016-12-12 15:30:06 in /prog/

/prog/ 9623: Wie inzu algorithmisches Denken?

chris_frees Avatar
chris_frees:#9623

Bernd studiert Informatik im 3. Semester und hat immer sehr viel Spaß an Programmieren, Systemadministration, Trinkering mit irgendwelchen Geräten (z.B. hat sich Bernd übers Wochenende einfach so einen NES zu USB Adapter mittels Teensy gebastelt) usw. und hat das auch mit großem Erfolg gemacht.

Jetzt ist Bernd bereits 2 Monate im aktuellen Semester drin und hängt in der Vorlesung betreffend Algorithmen und Datenstrukturen mächtig hinterher und schafft es nicht sich aufzuraffen um den Kram zu durchdringen und eventuell zu verstehen; Bernd prokrastiniert nur bei diesem Fach.

Nach einigem Insichgehen und Versuchen Freund des Faches zu werden erkennt Bernd, dass er daran scheitert "algorithmisch" zu denken, das heißt Bernd weiß zwar, dass O(n)>O(log n), aber nicht was das bedeutet und kann auch nach einigem Versuchen nicht erklären weshalb ein Algorithmus O(log n) ist, oder wie man es beweist. Es sollte doch eigentlich total logisch sein, aber Bernd hat da irgendwie keinen Zugang zu.

Kann Bernd Bernd helfen?

marciotoledo Avatar
marciotoledo:#9624

>und kann auch nach einigem Versuchen nicht erklären weshalb ein Algorithmus O(log n) ist, oder wie man es beweist
Wie wärs wenn du dich erstmal an die Definition hälst? Theoretische Informatik ist quasi Mathematik, insofern wäre es vielleicht auch nicht verkehrt wenn du da nochmal deine Kenntnisse auffrischt, falls nicht alles hängengeblieben ist. Wie gesagt, am besten näherst du dich der Sache erstmal streng formal bevor du versuchst irgendwelche "einfachen" Bedeutungen/Erklärungen zu finden.

necodymiconer Avatar
necodymiconer:#9626

Lies das Skript. Bearbeite die Aufgaben. Fertig.

ninjad3m0 Avatar
ninjad3m0:#9628

Was die anderen Bernde gesagt haben. Man braucht einfach ein paar Semester, bis einem mathematische Beweise in Fleisch und Blut übergehen. Das muss man ähnlich wie Algebra immer wieder üben, bis man genug davon gesehen hat. Dafür studierst du ja auch.

ggavrilo Avatar
ggavrilo:#9629

Hallo,
Informatik Bernd hier der sich sowohl mit theoritscher Informatiker
also auch mit angewandten Dingen und Softwareentwicklung wohl fühlt.

Ich glaube ich kann dir ein wenig helfen, berndi.

> weiß zwar, dass O(n)>O(log n), aber nicht was das bedeutet und kann auch nach einigem Versuchen nicht erklären weshalb ein Algorithmus
> O(log n) ist,

Was es bedeutet: (vereinfacht)
O(n): lineare laufzeit : doppelt so viel input -> programm braucht doppelt so lang. 10 facher input -> programm braucht 10 mal so lang.
Diese input-größe ist meistens recht einfach erfassbar, sowas wie "wie viele Elemente hat das Eingabearray" etc.

O(log n): doppelter input , laufzeit + 1 $Zeiteinheit , vierfacher input -> laufzeit + 2 $zeiteinheit (also sehr geil)

Jetzt wobei ich darüber nachdenke, das ich das erklären muss. Entweder, dein Skript ist sehr sehr schlecht, oder du hast es noch nicht
gelesen. Wenn es schlecht ist kannst du dir in der Bibliothek das Buch von Robert Sedgewick holen ("Algorithmen und Datenstrukturen" IIRC)
Das ist das standardwerk und empfehlenswert. du musst ja auch nicht alles lesen sondern nur die für die relevanten Abschnitte.
Da sind auch die Grundbegriffe schön erklärt.

yehudab Avatar
yehudab:#9639

Wenn das keine Pflichtvorlesung ist, dann belege ein anderes Fach. Wichtig ist nur, dass du am Ende genügend CP (also Credit Points) hast.

Ansonsten, was >>9626 schreibt. Dozenten sind zudem auch dafür da, deine Fragen zu beantworten. Entweder per Mail oder einfach ansprechen.

Jetzt zu deinem Problem. Das "O" ist die Laufzeit, den ein Algorithmus hat, wenn er durchläuft. Ehrlich gesagt, habe ich das auch nie komplett verstanden, habe aber trotzdem meinen Master of Science geschafft. Ein Dozent hat mal versucht genau die Frage uns erklären, nachdem einer der Kollegen das nicht verstanden hatte und gefragt hat. Wir haben dann einen Algorithmus angeschaut und untersucht, wie viele Anweisungen bei vom Algorithmus gemacht werden müssen, wenn er mehr Eingaben bekommt. Beispiel vom BubbleSort. Entscheidend bei dem ist die doppelte for-schleife. Deswegen hat der O(n^2) als Laufzeit, während du bei einer einfachen Schleife über n Elemente nur eine Laufzeit von O(n) hast. Und Anweisungen, die gar nicht von den Eingaben abhängen haben eine Laufzeit von O(1).

rawdiggie Avatar
rawdiggie:#9641

Die "Laufzeit" eines Algorithmus' ist der aufsummierte Zeitaufwand aller Operationen, die bei der vollständigen Abarbeitung des Algorithmus in Abhängigkeit der Eingabedaten ausgeführt werden.

Nehmen wir als Beispiel folgenden Algorithmus (na, was tut er?):
Eingabe: ein 2D-Array a der Größe m*n
Eingabe: ein Array b der Länge n
Ausgabe: ein Array y der Länge m

1) reserviere Array y der länge m
2) for i = 1, ..., m
2.1) x = 0
2.2) for j = 1, ..., n
2.2.1) x = x + a[ i][j]*b[ i]
2.3) y[ i] = x


Wie viel Zeit muss dafür aufgewendet werden?

Zeile 1): Ein Aufruf zu malloc(). Wir wissen nicht genau, wie lange das dauert, aber nehmen wir an, dass das System dafür unabhängig von n immer die Zeit c benötigt. Wir gehen außerdem davon aus, dass die Elemente von y nicht automatisch auf 0 gesetzt werden. Der Leser kann als Übung ja mal ausrechnen, was rauskommt, wenn man y zusätzlich noch auf 0 setzt.

Zeile 2): Die Schleife läuft insgesamt m mal durch. Dabei wird in Zeile 2) die Variable i m-mal um eins erhöht, die Variable i wird m-mal mit m verglichen und es wird m-mal vom Ende der Schleife wieder zu deren Anfang gesprungen. Nehmen wir an, alle drei beschriebenen Operationen dauern genau eine Zeiteinheit, dann ist die totale Laufzeit des Schleifen-Overheads 3*m.

Zeile 2.1): Diese Zeile wird m-mal ausgeführt. Wieder unter der Annahme, dass die Zuweisung eine Zeiteinheit dauert, ist der Zeitaufwand insgesamt m.

Zeile 2.2): Gleiche Argumentation wie bei Zeile 2), also 3*n Zeiteinheiten. Zusätzlich müssen wir berücksichtigen, dass Zeile 2.2) im Rumpf der äußeren Schleife steht, also zusätzlich noch m-mal wiederholt wird. Gesamtaufwand für den Overhead der inneren Schleife: 3*m*n

Zeile 2.2.1): Eine Addition, eine Multiplikation, drei Loads (a, b, x) und ein Store (x). Alles dauert wieder jeweils eine Zeiteinheit. Außerdem befindet sich die Zeile gleich in zwei verschachtelten Schleifen. Die Zeile wird also m*n-mal ausgeführt. Totaler Zeitaufwand: 6*m*n

Zeile 2.3): Ein Store innerhalb der äußeren Schleife: m Zeiteinheiten.

Macht zusammen: c + 3m + m + 3mn + 6mn + m
Als Funktion der Eingabegrößen ausgedrückt: f(a, b, m, n) = f(m, n) = c + 5m + 9mn

Die O-Notation ist nun dazu da, diese i. d. R. relativ langen Ausdrücke für die Laufzeit eines Algorithmus' kompakter darzustellen. Recherchiere hierfür verdammt nochmal im Internet, was genau O bedeutet (und lerne klein o und Theta gleich mit). Es ist nicht die Schuld deines Dozenten, wenn du es nach dem ersten Mal erklären nicht verstehst aber dann unwillig bist, es selbstständig nachzulernen. Die O-Notation ist relativ simpel, man muss nur ein bisschen üben, um eine Intuition für ihre Anwendung zu bekommen.

Kurz gesagt: Man sucht sich eine Funktion g, die mindestens genauso schnell wächst wie f und sagt dann "f ist ein Element der Menge O(g)" oder (als Konvention, die sich so eingebürgert hat) f = O(g).

Als sinnvolle Wahl von g bietet sich hier g=m*n an, also f = O(m*n).

Zwei Anmerkungen:
- die Bestimmung der Laufzeit und das anschließende Umrechnen in O-Notation sind zwei verschiedene Dinge
- der Overhead einer Schleife mit m Durchläufen ist nicht exakt 3*m, weil der Sprung u. U. nicht genau m-mal ausgeführt wird und weil zu Beginn der Schleife der Zähler i noch initialisiert werden muss. Das macht aber letztlich nichts aus, weil die O-Notation solche kleinen Fehler sofort schluckt. Deswegen ist es auch unerheblich, wie lang die einzelnen Instruktionen (Sprung, Addition, Load, etc.) konkret brauchen. Lerne mindestens so lange, bis dir der letzte Punkt klar ist.

mat_stevens Avatar
mat_stevens:#9644

>>9623
Es ist Krebs und du wirst es wahrscheinlich eh nie wieder brauchen

drinbevor "hurrdurr meine laufzeitkomplexität"
Die Leute die damit ankommen, beherrschen meistens nicht einmal irgendwelche Programmiersprachen ordentlich

Leider kann ich dir bei dem Thema selbst nur wenig helfen, da ich darin auch relativ fersagt habe, allerdings ist dies nicht unbedingt eine Schande. Man kann trotzdem noch guter Informatiker werden drinbevor haha alsob.

Bei dem Weg: Wenn du jetzt schon 2 Semester drin bist, und nicht einmal die Grundlagen der ersten Vorlesung ferstanden hast, solltest du WIRKLICH versuchen, jetzt sofort aufzuholen. A&D ist z.T. eines der schwersten Fächer.

antonkudin Avatar
antonkudin:#9645

Das wird normalerweise über Mengen definiert. O(X) ist die Menge der Aufwand(Problemgröße) Funktionen (muß keine Laufzeit sein, auch Speicher usw.) die in derselben Klasse wie X sind, d.h. sich asymptotisch (Problemgröße -> inf) unter F*X drücken lassen wobei F ein fester Faktor ist.

Nicht daß das nicht in dem Skript stehen würde du fauler Sack!

Daher 1 € O(log n)

Wenn man zu doof ist das mit den Mengen zu kapieren sollte man zumindest wissen daß O(n²) irgendwie scheisse ist wenn auch ein Baum mit O(ld n) geht

syntetyc Avatar
syntetyc:#9665

OP hat gerade seine .java für einen maximalen Fluss nach Edmonds Karp Methode erfolgreich fertiggestellt, aber ich kann niemandem bis heute sagen, warum dieser Algorithmus den maximalen Fluss berechnet. (Klar, er sucht sich halt immer einen Weg, aber warum ist das am Ende der maximalste?)

Obwohl Bernd sich die Sachen also anschaut und lernt, wie Bernd es ihm empfohlen hat, Bernd nicht wirklich versteht was er da macht. Ich glaube, der einzige Weg wie ich die Matheklausuren bestanden habe ist, indem ich wie ein Jurist die Regeln auswendig gelernt habe ohne wirklich zu begreifen, was dahinter steckt. Ich habe keinen Plan wie das so weitergehen kann, denn es wird ja nur noch schwerer.

>>9644
Nicht? Nachdem ich mit ein paar höheren Semestern gesprochen habe dachte ich, dass es DAS Informatikerding ist. Am Ende des Studiums an einer Universität würde jeder gute Informatiker auf Zuruf die Komplexität eines Problems abschätzen können und es in die Problemklassen modellieren können.

m_kalibry Avatar
m_kalibry:#9666

>>9665
>Am Ende des Studiums an einer Universität würde jeder gute Informatiker auf Zuruf die Komplexität eines Problems abschätzen können und es in die Problemklassen modellieren können.
kek, das kann man auch so, da braucht man kein Semester Algorithmen und Datenstrukturen für
Vor allem werdet ihr - so wie ich die Vorlesungen kenne - eh total an der Praxis vorbei lernen. Wer von Pseudokot Laufzeitkomplexität berechnet kann eh gleich wieder in den Keller gehen.
So merke er: dreifach verschachtelte for-Schleifen sind meistens schlecht

Das soll jetzt aber nicht heißen, dass du nicht für die Klausur lernen solltest

>ohne wirklich zu begreifen, was dahinter steckt. Ich habe keinen Plan wie das so weitergehen kann, denn es wird ja nur noch schwerer.
oh weh ;_;

cmzhang Avatar
cmzhang:#9669

>>9665
>maximalste
Überreiz nicht deine Karten.
>Ich habe keinen Plan wie das so weitergehen kann, denn es wird ja nur noch schwerer.
Nö, Höhepunkt ist so im 3.-4. Semester erreicht. Wenn du nicht vorhast in die Forschung zu gehen (das würde ich dir anhand deiner Beiträge wirklich nicht empfehlen) brauchst du den ganzen Kram eh nie wieder, daher ist dein Vorgehen eigentlich völlig in Ordnung.

chris_frees Avatar
chris_frees:#9676

>MaxFluss

Das beweist man meistens über irgendwelche Invarianten oder über vollständige Induktion über die Nummer von Knoten.


Eigentlich sollte es noch schwerer werden. O-Notation ist ja nur die SPRACHE in der komplizierte Sachen ausgedrückt werden. Darauf aufbauend könnte man dann Sachen untersuchen, neue Algorithmen finden, Komplexitätstheorie betreiben oder Quantencomputer bauen.

Oder sich auf die Anwendungen werfen, da gibt es doch schon so einige deren Mathematik nicht ganz einfach ist, sagen wir mal alles mit DCT.

Aber da dafür eh kein Markt da ist und der typische "Informatiker" Windows installiert und Webshop aufsetzt, macht es auch nichts.

mat_walker Avatar
mat_walker:#9677

>>9676
Haldol mal wieder vergessen?

wtrsld Avatar
wtrsld:#9680

>>9676
>Der typische "Informatiker" tut nur Webshop aufsetzen
Bernd schafft es immer wieder mit seinem Zynismus anderen die Laune zu verderben. Glaubst du etwa ernsthaft deinen eigenen Scheiß? Geh zurück nach /b/.

abdots Avatar
abdots:#9681

>>9680
Ob man jetzt einen WebShop aufsetzt oder irgendwelche Mapper für die Transformation von Transportobjekten für Enterprise WebLogic Architekturen zusammenwürfelt ist jetzt auch kein so großer Unterschied

t. anderer Bernd

aiiaiiaii Avatar
aiiaiiaii:#9684

>>9681
Scheinst wohl keinen Spaß an deinem Beruf zu haben, was?

xspirits Avatar
xspirits:#9685

>>9684
Es tut mir ja weh das zuzugeben, aber nach Ende des Studiums (und vielleicht noch einer Promotion) ist das anspruchsvollste was die meisten von uns im Berufsleben erwartet tatsächlich auf dem Niveau des "Webshop-Aufsetzens" angesiedelt. Dieser Bernd sucht sein Heil in der zwanghaften Performance-Optimierung seiner Programme (ist allerdings nicht unbedingt gut darin), wenn der Chef grad nicht hinsieht. Bitte beweist mich mit euren Erfolgsgeschichten falsch.

t.

noch ein anderer Bernd

doooon Avatar
doooon:#9686

>>9685
Jenes.

Und seien wir ehrlich: Die paar "anspruchsvollen" Dinge wie irgendwelche DAWs oder Cum Piler sind auch nicht besser, weil man so gut wie nie einen neuen beginnt sondern immer irgendeinen Legacykram warten/erweitern muss wobei sich Krebs angehäuft hat. Immer.

Krebs alleine ist schon genug, aber das möchte man nicht unbedingt mit zusätzlicher Komplexität der Domäne vermischt sehen. Als Beispiel stelle Bernd sich vor, er müsste den ABAP-Cum Piler um ein Web-Rückende erweitern.

Und in so Konsortien wie OGC oder W3C zu sein und Tag für Tag über Jahre miese Kompromisslösungen zusammenzupfuschen kann auch so toll nicht sein.

nelshd Avatar
nelshd:#9687

>>9685
>>9686
>weil man so gut wie nie einen neuen beginnt sondern immer irgendeinen Legacykram warten/erweitern muss wobei sich Krebs angehäuft hat. Immer.
DIES!

Muss gerade ein altes Java-Tool mit JPA und hibernate erweitern nachdem es irgendein Azubi mal in den 2000ern halbfertig zusammengewichst hat

tötet mich

ein Rewrite wäre einfacher

Neuste Fäden in diesem Brett: