Galerie de cartes mentales Introduction aux algorithmes
Résumé des connaissances introductives sur les algorithmes, qui introduit le concept d'algorithmes, les expressions d'algorithmes, l'analyse de la complexité des algorithmes, les étapes de conception d'algorithmes, etc. Il constitue la base de la conception et de l'analyse d'algorithmes informatiques et jette les bases permettant aux apprenants de maîtriser divers algorithmes spécifiques dans le l’avenir. Il s’agit d’un contenu important qui doit être appris dans le processus d’apprentissage des algorithmes.
Modifié à 2024-03-02 22:28:38Cent ans de solitude est le chef-d'œuvre de Gabriel Garcia Marquez. La lecture de ce livre commence par l'analyse des relations entre les personnages, qui se concentre sur la famille Buendía et raconte l'histoire de la prospérité et du déclin de la famille, de ses relations internes et de ses luttes politiques, de son métissage et de sa renaissance au cours d'une centaine d'années.
Cent ans de solitude est le chef-d'œuvre de Gabriel Garcia Marquez. La lecture de ce livre commence par l'analyse des relations entre les personnages, qui se concentre sur la famille Buendía et raconte l'histoire de la prospérité et du déclin de la famille, de ses relations internes et de ses luttes politiques, de son métissage et de sa renaissance au cours d'une centaine d'années.
La gestion de projet est le processus qui consiste à appliquer des connaissances, des compétences, des outils et des méthodologies spécialisés aux activités du projet afin que celui-ci puisse atteindre ou dépasser les exigences et les attentes fixées dans le cadre de ressources limitées. Ce diagramme fournit une vue d'ensemble des 8 composantes du processus de gestion de projet et peut être utilisé comme modèle générique.
Cent ans de solitude est le chef-d'œuvre de Gabriel Garcia Marquez. La lecture de ce livre commence par l'analyse des relations entre les personnages, qui se concentre sur la famille Buendía et raconte l'histoire de la prospérité et du déclin de la famille, de ses relations internes et de ses luttes politiques, de son métissage et de sa renaissance au cours d'une centaine d'années.
Cent ans de solitude est le chef-d'œuvre de Gabriel Garcia Marquez. La lecture de ce livre commence par l'analyse des relations entre les personnages, qui se concentre sur la famille Buendía et raconte l'histoire de la prospérité et du déclin de la famille, de ses relations internes et de ses luttes politiques, de son métissage et de sa renaissance au cours d'une centaine d'années.
La gestion de projet est le processus qui consiste à appliquer des connaissances, des compétences, des outils et des méthodologies spécialisés aux activités du projet afin que celui-ci puisse atteindre ou dépasser les exigences et les attentes fixées dans le cadre de ressources limitées. Ce diagramme fournit une vue d'ensemble des 8 composantes du processus de gestion de projet et peut être utilisé comme modèle générique.
Introduction aux algorithmes
Notion d'algorithme
La signification fondamentale de l'algorithme
une méthode pour résoudre un certain problème
Définition de l'algorithme
description informelle
Un algorithme est un ensemble fini de règles bien formées. Il spécifie une série d'opérations pour résoudre un type spécifique de problème. C'est une méthode ou un processus pour résoudre un problème. C'est une séquence d'instructions qui satisfont l'entrée, la sortie et la certitude. , et la finitude.
Entrée : il existe zéro ou plusieurs quantités externes qui servent d'entrée à l'algorithme.
Sortie : L'algorithme produit au moins une quantité en sortie.
Déterministe : Chaque instruction qui compose l’algorithme est claire et sans ambiguïté.
Finitude : chaque instruction de l'algorithme a un nombre limité d'exécutions et le temps d'exécution de chaque instruction est limité.
Algorithmes et programmes
Un programme est l’implémentation spécifique d’un algorithme dans un certain langage de programmation.
Le programme n'a pas besoin de satisfaire la propriété de l'algorithme (4), c'est-à-dire la finitude, comme un système d'exploitation.
Programme = structure de données de l'algorithme du langage de programmation
La portée de la recherche sur les algorithmes
Calculs numériques
Equations linéaires non linéaires, interpolation, différentielle intégrale
calculs non numériques
Tri, optimisation, coloration, chemin, parcours, machine learning, data mining
propriétés des algorithmes
exactitude
Si, pour une entrée valide donnée, l’algorithme donne toujours la bonne réponse au problème dans un temps limité, alors l’algorithme permettant de résoudre le problème est dit correct.
Cela fait principalement référence à l’exactitude mathématique de l’algorithme. Parce que l’exactitude mathématique est la base de l’exactitude d’un programme. Lors de la formulation d’un algorithme, donnez une preuve mathématique de son exactitude.
charge de travail
Mesuré par le temps d'exécution
Cela dépend de la machine d'exécution spécifique, pas bon
Mesuré par le nombre d'opérations de base
Indépendant de l'ordinateur sur lequel il est exécuté
Utilisation de l'espace
L'espace requis à l'exception de l'espace de stockage des programmes et des données d'entrée
Fonctionne sur place : l'utilisation de l'espace supplémentaire est une fonction constante de la taille de l'entrée
simplicité
L'algorithme doit être intuitif, clair et facile à lire. Un algorithme simple doit être facile à prouver son exactitude et à analyser la charge de travail.
optimalité
Un mécanisme abstrait pour exprimer des algorithmes
Abstraction au niveau du langage
langage de programmation de haut niveau
1. Proche du langage algorithmique, facile à apprendre et à maîtriser
2. Fournir aux programmeurs un environnement et des outils de programmation structurés. Le programme a une bonne lisibilité, une bonne maintenabilité et une grande fiabilité.
3. Ne repose pas sur le langage machine, a une bonne portabilité du programme et une grande réutilisabilité
4. Le compilateur gère des questions triviales, donc le degré d'automatisation est élevé, le cycle de développement est court et la qualité du programme est élevée.
abstraction au niveau des données
type de données abstrait
Un type de données abstrait est un modèle de données d'un algorithme ainsi qu'un ensemble d'opérations définies sur le modèle qui servent de blocs de construction de l'algorithme.
avantage
(1) La conception de niveau supérieur de l'algorithme est séparée de la mise en œuvre de niveau inférieur ;
(2) La conception de l'algorithme est séparée de la conception de la structure des données, permettant le libre choix de la structure des données ;
(3) Le modèle de données et les opérations sur le modèle sont unifiés dans ADT, ce qui facilite le compromis entre la consommation d'espace et de temps ;
(4) Les algorithmes exprimés dans des types de données abstraits ont une bonne maintenabilité ;
(5) L'algorithme est naturellement modulaire ;
(6) Fournir des moyens et des outils efficaces pour un raffinement et une modularisation progressifs de haut en bas ;
(7) L'algorithme a une structure claire et des couches distinctes, ce qui facilite la preuve de l'exactitude de l'algorithme et l'analyse de la complexité.
Décrire l'algorithme
Java
Structure du programme
type de données
méthode
anormal
Cours Java
méthode générale
collecte des ordures
récursivité
Étapes de la conception d'un algorithme
Étapes de base de la conception d'algorithmes
1. énoncé du problème
2. La modélisation
3. conception d'algorithmes
4. Preuve de l'exactitude de l'algorithme
5. Implémentation de l'algorithme
6. Analyse de la complexité des algorithmes
7. Test expérimental
8. Documentation
Analyse de la complexité des algorithmes
Raison de l'analyse
Pour qu'un algorithme traite avec succès une entrée spécifique, l'espace mémoire et le temps d'exécution requis par l'algorithme doivent être estimés ou limités.
Peut comparer quantitativement l’efficacité de différents algorithmes pour le même problème
Classification de complexité
Algorithme de complexité temporelle polynomiale
Algorithme de complexité temporelle exponentielle
Tests et analyses expérimentaux
raison
Expérience pour vérifier l'exactitude de l'algorithme
Déterminer la qualité expérimentale des algorithmes
Déterminer les limites de calcul d'un algorithme
méthode
Question à choix : Que tester, but du test
Estimer le temps d'exécution asymptotique moyen d'un algorithme
Comparez les performances d'algorithmes similaires pour une entrée donnée
Expérience pour déterminer les paramètres de l'algorithme
Pour les algorithmes d'approximation, dans quelle mesure les résultats des tests sont-ils proches de la valeur optimale
Déterminer les métriques
Temps de fonctionnement réel
facteurs d'interférence
Autres programmes exécutés sur votre ordinateur
impact sur le cache
utilisation de la mémoire
Générer des données de test
quantité suffisante
différentes échelles
répartition différente
Programmer et exécuter
la programmation
Assurer la cohérence du niveau de programmation
courir
Garantir un environnement informatique propre et réduire le bruit des données
l'analyse des données
test de rapport
Test de puissance
Documentation
Description et analyse du problème
Modélisation et résolution
Conception d'algorithmes et processus de preuve d'exactitude
Analyse de la complexité des algorithmes
Rapport d'enregistrement et d'analyse des résultats des tests
Exigences d’entrée/sortie et description du format
Analyse de la complexité des algorithmes
Utilisez T(N,I) pour représenter la complexité temporelle de l'algorithme A sur un ordinateur abstrait.
N : la taille du problème à résoudre
DN : l’ensemble de toutes les entrées possibles de taille N
P(DN) : distribution de probabilité de DN
I : entrée de l'algorithme, I∈DN
mesure de complexité temporelle
Symbole Description
Ô
définition
définition formelle mathématique
O(g(n)) sont toutes des fonctions avec g(n) comme limite supérieure
compréhension symbolique
Règles arithmétiques
Preuve pour (1)
Ω
définition
définition formelle mathématique
θ
définition
définition formelle mathématique
o
définition