Algorithmen anwenden Beispiele

Aufrufe: 976     Aktiv: 15.01.2021 um 10:23

0

Hallo zusammen,

Nun haben wir verschiedene Algos gesehen, ich weiss wie die meisten theoretisch funktionieren. Gibt hierzu ein Beispiel, welches Algorithmen für welche Probleme angewendet werden? Bei welchen Fragenstellungen werden diese Algos verwendet?

Shortest Problem: Dijkstra, Bellman-Ford Merge Sort, Insertion Sort, Quicksort? Flow Problem: Ford Fulkerson Max-Heap Strassen'smatrix Binary Search, BST, hash Table Union Find, priortiy queue, Linked List Max-flow, Min cut, probabilitstic analysis Minimum Spanning Tree (Kruskal, Prims)

Vielen Dank!

Diese Frage melden
gefragt

Student, Punkte: 66

 
Kommentar schreiben
1 Antwort
1

Hey :-)

Grundsätzlich ist es schon einmal wichtig dass du theoretisch und grundsätzlich verstehst wie die Algorithmen funktionieren und arbeiten. Gerade bei den Sortier- und Suchalgorithmen geht es den meisten Professoren mehr um den Designprozess und die Arbeitsweise (Divide&Conquer, Laufzeitevaluation etc.) als um den Algorithmus selbst.

Zur konkreten Frage wo diese Algorithmen oft benutzt werden:

  • Dijkstra/Bellman-Ford: Werden benutzt um kürzeste Wege in Graphen zu finden. (Wie viele Busstationen ist mein Ziel entfernt, was ist der schnellste Übertragungsweg in einem Netzwerk...). Dijkstra ist asymptotisch gesehen schneller, kann aber im gegensatz zu Bellman-Ford nicht mit negativ gewichteten Kanten umgehen.
  • Sortieralgorithmen: Zum Sortieren von irgendwelchen Daten. In der Praxis oft Quicksort/Mergesort. Die langsameren Algorithmen wie Bubblesort oder Insertionsort werden eher weniger gebrauch, ausser du hast sehr wenige Daten, dann kann es sein dass der Overhead von z.Bsp. Quicksort grösser ist als der asymptotische Unterschied
  • Suchalgorithmen: Suche in Daten. Zum Beispiel bei einem Onlineshop etc.
  • Max-flow/Min-cut: Ebenfalls zur Netzwerkanalyse (Durchsatz). Gerade bipartite Modelle wie Matchings lassen sich gut als Flowprobleme darstellen.
  • Datenstrukturen: Kannst du bei einer Vielzahl von begebenheiten nutzen. Der Phantasie sind quasi keine Grenzen gesetzt. Stacks zum Beispiel spielen eine zentrale Rolle bei der Speicherverwaltung von Programmen.

Falls du noch mehr Beispiele möchtest oder an Einzelheiten interessiert bist dann kann ich dir das Buch "Algorithms - Jeff Erickson" empfehlen. Dieses ist kostenlos und im Web als PDF zu finden.

VIel Erfolg beim lernen.

Diese Antwort melden
geantwortet

Punkte: 15

 

Hallo Sven,
vielen herzlichen Dank für deine Antwort. Wann wird DFS und BFS verwendet oder Union-Find, Graphen(Adjency List, Adjency Marix)

Bei Binary Search gibt es inorder, postorder und preorder. Es sind 3 verschiedene Möglichkeiten, wie man einen BST ausgeben kann oder?

Directed Acylic Graph, wann braucht man dies?

Bei DFS gibt es noch cross-edge etc. wann macht es sinn die zu benutzen?

Vielen Dank für deine Antwort!

  ─   sayuri 15.01.2021 um 10:23

Kommentar schreiben