Visualisations des algorithmes du monde réel
Aperçu
Ce référentiel contient des visualisations de plusieurs algorithmes complexes que j'ai créés dans le cadre de ma classe d'algorithmes du monde réel, en utilisant l' API Bridges . Les visualiseurs montrent comment divers algorithmes fonctionnent dans la pratique, fournissant une approche interactive et visuelle pour comprendre leur comportement et leurs performances. Vous pouvez explorer les visualisations chez Bridges-CS.
Algorithmes couverts
Tout au long du cours, j'ai implémenté et visualisé les algorithmes suivants:
1. Tri des algorithmes
- Tour de fusion : un algorithme de tri divisé et conquis avec une complexité temporelle de O (n log n).
- QuickSort : un autre algorithme de tri efficace qui fonctionne en partitionnant le tableau et en tri les partitions récursivement.
2. Représentation de graphiques et traversées
- Recherche de largeur (BFS) : explore tous les nœuds à la profondeur actuelle avant de passer aux nœuds au niveau de la profondeur suivante.
- Recherche en profondeur d'abord (DFS) : explore autant que possible le long de chaque branche avant de revenir en arrière.
- Application : implémentée BFS pour calculer les numéros de bacon et explorer la représentation des graphiques à l'aide de listes et de matrices d'adjacence.
3. Algorithmes graphiques
- L'algorithme de chemin le plus court de Dijkstra : trouve le chemin le plus court entre les nœuds d'un graphique.
- Arbre couvrant minimum de Prim (MST) : calcule l'arbre couvrant minimum d'un graphique.
- Projets : Analyse de chemin la plus courte appliquée sur les données d'OpenStreetMap et les lignes centrales extraites des structures tubulaires à l'aide de MST.
4. correspondance des cordes
- Algorithme de Horspool : un algorithme de correspondance de cordes efficace utilisé dans les projets d'alignement de séquences de gènes, permettant l'alignement global et local.
5. Recherche et indexation
- Recherche binaire : un algorithme de recherche temporelle logarithmique pour trouver des éléments dans un tableau trié.
- PageRank : a implémenté un algorithme PageRank à l'aide de données d'acteur / film Wikipedia pour indexer et classer les pages Web.
- Arbres de recherche spatiale : structures de données spatiales explorées comme les quadrets.
6. Autres algorithmes
- Problème de vendeur itinérant : a utilisé le MST de Prim pour approximer la visite des vendeurs itinérants des villes américaines.
- Problème de sac à dos : Techniques de programmation dynamique appliquées pour résoudre ce problème d'optimisation.
Projets et visualiseurs
Chacun des algorithmes ci-dessus a été implémenté et visualisé à l'aide de l' API Bridges . Les visualiseurs peuvent être explorés via la plate-forme Bridges-CS. Ces projets démontrent l'application du monde réel d'algorithmes complexes et fournissent une compréhension intuitive de leur exécution.
Projets:
- Visualiseur de traversée BFS et DFS
- Finder de chemin le plus court de Dijkstra
- Fusion de visualiseurs de tri et de quicksort
- Algorithme PageRank sur les données Wikipedia
- Visualiseur d'alignement de séquence de gènes
Comment courir
- Cloner ce référentiel:
git clone https://github.com/sudo-amancodes/real-world-algorithms-visualizers.git
- Exécutez les fichiers de laboratoire pour un laboratoire spécifique:
Technologies utilisées:
- Python: Démarrage du langage de programmation pour l'implémentation d'algorithme.
- Java: Langage de programmation de base pour l'implémentation d'algorithme.
- API Bridges: Utilisé pour la création de visualisations des algorithmes.
Démo:
Capture d'écran de l'interface de recherche Quadtree et Quadtree.
