Algorithme et Structures de Données

Plan de cours

• Itroduction aux algorithme
• Les structures itératifs
• Les structures conditionelles
• Algorithme de trie
• Les piles et les files
• Algorithme des arbres
• La programmation des listes
• Structures de données
• Listes liées
• Liste individuellement liée
• Insertion
• Recherche
• Effacement
• Liste doublement liée
• Insertion
• Inverser la traversée
• Résumé
• Arbre de recherche binaire
• Atteindre une référence à un noeud
• Trouver les valeurs les plus petites et les plus grandes dans l’arbre de recherche binaire
• Parcourir les arbres
• Largeur d’abord
• Résumé
• Files d’attente
• Une file d’attente standard
• File d’attente de priorité
• Double file d’attente
• Résumé

Ce tutoriel fournit des implémentations d’algorithmes communs et peu courants dans le pseudocode qui est indépendant du langage et permet un portage facile vers la plupart des langages de programmation impératifs. Ce n’est pas un livre définitif sur la théorie des structures de données et des algorithmes.

Pour la plupart, ce livre présente des implémentations conçues par les auteurs eux-mêmes, basées sur les concepts sur lesquels sont basés les algorithmes respectifs, il est donc plus que possible que nos implémentations diffèrent de celles considérées comme la norme.Vous devriez utiliser ce livre avec un autre sur le même sujet, mais qui contient des preuves formelles des algorithmes en question. Dans ce livre, nous utilisons la notation abstraite Oh pour décrire la complexité des algorithmes en termes de temps d’exécution, afin que le livre attire un plus large public.

Profitez de ce manuel de formation en PDF pour comprendre mieux le algorithm et enrichir votre connaissance.

Commencez à télécharger ce cours adapté pour vous et à apprendre algorithm.

10 Exercice avec O(N) (3) Exercice avec O(N) (3) • montrer que 3Nn’est pas O(2N)• Supposons qu’il existe 2 constantes c et N 0 tel que N ≥N 0 pour lesquelles l’inégalité suivante est vérifiée : 3N≤c*2N •alors c ≥(3/2)N , c peut devenir arbitrairement grand pour N grand, donc il n’existe pas de constante supérieure (3/2) N quelque soit N Exercice avec O(N) (4.1) Exercice avec O(N) (4.1) • Algorithme : – Initialisation exécutée 1 fois (temps : a1 ns)– une boucle interne parcourue 2N*H N (temps : a2 ns; avec HNle nombre harmonique)– une section supplémentaire exécutée N fois(temps : a3 ns) • Temps moyen d’exécution de l’algorithme?•a 1+ 2a2N*HN+ a3*N ns N NN H N 121ln1…3 12 11+ + ≈+ + + + =γ Exercice avec Exercice avec O(N) (4.2) O(N) (4.2) • Avec la notation O(N) que devient cette estimation ? a 1+ 2a2N*HN+ a3*N ns•2a 2N*HN + O(N)• Une forme plus simple qui indique que ce n’est pas la peine de chercher a 1et a3 • Temps d’exécution exprimé en notation « grand-O » ?•H N=ln(N) + O(1) on obtient ainsi 2a2N*Ln(N)+ O(N)• l’expression asymptotique du temps total d’exécution : temps proche de 2a 2N*Ln(N) pour des N grands NNN H N 121ln1…3 12 11+ + ≈+ + + + =γ Exercice avec O(N) (4.3) Exercice avec O(N) (4.3) • l’expression asymptotique du temps total d’exécution : temps proche de 2a 2N*Ln(N) pour des N grands• que se passe-t-il si N double : taille 2N?• sans connaître a 2on peut prédire que le temps doublera pour le traitement des données de taille 2N )ln1( 2) 1 ( ln) 1 ( ) 2 ln( 2) ( ln 2) 2 ( ) 2 ln( ) 2 ( 2 2 2 NOO NO NN O N N aN O N N a+ =+ +=++ 2a2N en facteur