Astronomie

Comment appliquer l'algorithme de pliage rapide ?

Comment appliquer l'algorithme de pliage rapide ?

J'ai un jeu de données d'univers à haute résolution temporelle. J'ai appliqué la dé-dispersion sur cet ensemble de données HTRU, puis j'ai appliqué la fonction de pliage pour plier l'ensemble de données.

Comment puis-je trouver que la périodicité du signal en utilisant un pliage rapide algorithme?


Algorithme quantique économe en ressources pour le repliement des protéines

La prédiction de la structure tridimensionnelle d'une protéine à partir de sa séquence primaire d'acides aminés est connue sous le nom de problème de repliement des protéines. En raison du rôle central des structures des protéines dans les applications de la chimie, de la biologie et de la médecine, ce sujet fait l'objet d'études intensives depuis plus d'un demi-siècle. Bien que les algorithmes classiques fournissent des solutions pratiques pour l'échantillonnage de l'espace de conformation de petites protéines, ils ne peuvent pas s'attaquer à la complexité intrinsèque NP-difficile du problème, même lorsqu'ils sont réduits au plus simple modèle hydrophobe-polaire. D'autre part, alors que les ordinateurs quantiques tolérants aux pannes sont hors de portée des technologies quantiques de pointe, il est prouvé que les algorithmes quantiques peuvent être utilisés avec succès dans des ordinateurs quantiques bruyants de pointe pour accélérer l'optimisation énergétique. dans les systèmes frustrés. Dans ce travail, nous présentons un modèle hamiltonien avec (>(^<4>)) et un algorithme variationnel quantique correspondant pour le repliement d'une chaîne polymère avec N monomères sur un réseau. Le modèle reflète de nombreuses propriétés physico-chimiques de la protéine, réduisant l'écart entre les représentations à gros grains et les simples modèles de réseau. De plus, nous utilisons un schéma d'optimisation robuste et polyvalent, réunissant des algorithmes quantiques variationnels spécifiquement adaptés aux fonctions de coût classiques et des stratégies évolutives pour simuler le repliement des 10 acides aminés Angiotensine sur 22 qubits. La même méthode est également appliquée avec succès à l'étude du repliement d'un neuropeptide de 7 acides aminés à l'aide de 9 qubits sur un ordinateur quantique IBM de 20 qubits. Réunissant les avancées récentes dans la construction d'ordinateurs quantiques basés sur des portes avec des algorithmes classiques quantiques hybrides tolérants au bruit, ce travail ouvre la voie à des expériences scientifiques accessibles et pertinentes sur de vrais processeurs quantiques.


Comment appliquer l'algorithme de pliage rapide ? - Astronomie

Ce projet est un travail en cours. Ce ne sera probablement jamais terminé, mais si c'est le cas, ce sera une seule bibliothèque python avec on La liste. (Cela n'inclut pas les algorithmes figurant sur une liste distincte liée à La liste.)

Une liste de contrôle directement de Wikipédia, montrant nos progrès :

Algorithmes combinatoires généraux

  • Algorithme de Brent : trouve un cycle dans les itérations de la valeur de la fonction en utilisant seulement deux itérateurs
  • Algorithme de recherche de cycle de Floyd : trouve un cycle dans les itérations de la valeur de la fonction
  • Algorithme Gale-Shapley : résout le problème du mariage stable
  • Générateurs de nombres pseudo-aléatoires (uniformément distribués) :
    • Blum Blum Shub
    • Générateur de Fibonacci retardé
    • Générateur linéaire congruentiel
    • Tornade Mersenne
    • Algorithme de coloration : algorithme de coloration de graphe.
    • Algorithme Hopcroft-Karp : convertit un graphe bipartite en une correspondance de cardinalité maximale
    • Algorithme hongrois : algorithme pour trouver une correspondance parfaite
    • Codage Prüfer : conversion entre un arbre étiqueté et sa séquence Prüfer
    • Algorithme d'ancêtres communs les plus bas hors ligne de Tarjan : calcule les ancêtres communs les plus bas pour les paires de nœuds dans un arbre
    • Tri topologique : recherche l'ordre linéaire des nœuds (par exemple, les tâches) en fonction de leurs dépendances.
    • Algorithmes basés sur la force (également appelés algorithmes dirigés par la force ou algorithme à ressort)
    • Disposition spectrale
    • Analyse de réseau
      • Analyse des liens
        • Algorithme de Girvan-Newman : détecter les communautés dans les systèmes complexes
        • Analyse de liens Web
          • Recherche de sujet induite par hyperlien (HITS) (également connue sous le nom de hubs et autorités)
          • Classement
          • Classement de confiance
          • Algorithme de Dinic : est un algorithme fortement polynomial pour calculer le débit maximum dans un réseau de débit.
          • Algorithme Edmonds-Karp : implémentation de Ford-Fulkerson
          • Algorithme Ford-Fulkerson : calcule le débit maximum dans un graphe
          • Algorithme de Karger : une méthode de Monte Carlo pour calculer la coupe minimale d'un graphe connexe
          • Algorithme push–relabel : calcule un flux maximum dans un graphe
          • Algorithme d'Edmonds (également connu sous le nom d'algorithme de Chu-Liu/Edmonds) : trouver les branchements maximum ou minimum
          • Arbre couvrant minimum euclidien : algorithmes de calcul de l'arbre couvrant minimum d'un ensemble de points dans le plan
          • Problème du plus court chemin euclidien : trouver le chemin le plus court entre deux points qui ne coupe aucun obstacle
          • Problème du plus long chemin : trouver un chemin simple de longueur maximale dans un graphe donné
          • Arbre couvrant minimal
            • Algorithme de Borůvka
            • L'algorithme de Kruskal
            • L'algorithme de Prim
            • Algorithme de suppression inversée
            • Algorithme de Bellman-Ford : calcule les chemins les plus courts dans un graphique pondéré (où certains des poids de bord peuvent être négatifs)
            • Algorithme de Dijkstra : calcule les chemins les plus courts dans un graphique avec des poids de bord non négatifs
            • Algorithme Floyd-Warshall : résout le problème du plus court chemin de toutes les paires dans un graphe orienté pondéré
            • Algorithme de Johnson : algorithme du chemin le plus court de toutes les paires dans un graphe orienté pondéré clairsemé
            • Problème de fermeture transitive : trouver la fermeture transitive d'une relation binaire donnée
            • Problème de voyageur de commerce
              • Algorithme Christofides
              • Algorithme du plus proche voisin
              • A* : cas particulier de la recherche best-first qui utilise des heuristiques pour améliorer la vitesse
              • B* : un algorithme de recherche de graphe best-first qui trouve le chemin le moins coûteux d'un nœud initial donné à n'importe quel nœud d'objectif (parmi un ou plusieurs objectifs possibles)
              • Backtracking : abandonne les solutions partielles lorsqu'elles s'avèrent ne pas satisfaire une solution complète
              • Beam search : est un algorithme de recherche heuristique qui est une optimisation de la recherche best-first qui réduit ses besoins en mémoire
              • Recherche de pile de faisceaux : intègre le retour en arrière avec la recherche de faisceau
              • Recherche du meilleur premier : parcourt un graphique dans l'ordre d'importance probable à l'aide d'une file d'attente prioritaire
              • Recherche bidirectionnelle : trouvez le chemin le plus court d'un sommet initial à un sommet cible dans un graphe orienté
              • Recherche en largeur d'abord : parcourt un graphe niveau par niveau
              • Recherche par force brute : une méthode de recherche exhaustive et fiable, mais inefficace en termes de calcul dans de nombreuses applications.
              • D* : un algorithme de recherche heuristique incrémentale
              • Recherche en profondeur : parcourt un graphe branche par branche
              • Algorithme de Dijkstra : Un cas particulier de A* pour lequel aucune fonction heuristique n'est utilisée
              • General Problem Solver : un algorithme de démonstration de théorème fondamental destiné à fonctionner comme une machine universelle de résolution de problèmes.
              • Recherche itérative en profondeur d'abord (IDDFS) : une stratégie de recherche dans l'espace d'état
              • Recherche de point de saut : une optimisation vers A* qui peut réduire le temps de calcul d'un ordre de grandeur en utilisant d'autres heuristiques.
              • Recherche lexicographique en largeur d'abord (également connue sous le nom de Lex-BFS) : un algorithme de temps linéaire pour ordonner les sommets d'un graphe
              • Recherche à coût uniforme : une recherche arborescente qui trouve l'itinéraire le moins cher où les coûts varient
              • SSS* : recherche dans l'espace d'états traversant un arbre de jeu selon un mode best-first similaire à celui de l'algorithme de recherche A*
              • Les cliques
                • Algorithme de Bron-Kerbosch : une technique pour trouver des cliques maximales dans un graphe non orienté
                • Algorithme de clique maximale MaxCliqueDyn : trouver une clique maximale dans un graphe non orienté
                • Algorithme de composant fort basé sur le chemin
                • L'algorithme de Kosaraju
                • Algorithme des composants fortement connectés de Tarjan

                Correspondance de séquence approximative

                • Algorithme Bitap : algorithme flou qui détermine si les chaînes sont approximativement égales.
                • Algorithmes phonétiques
                  • Daitch–Mokotoff Soundex : un raffinement Soundex qui permet l'appariement des patronymes slaves et germaniques
                  • Double Metaphone : une amélioration sur Metaphone
                  • Approche de notation de correspondance : un algorithme phonétique développé par Western Airlines
                  • Metaphone : un algorithme pour indexer les mots par leur son, lorsqu'ils sont prononcés en anglais
                  • NYSIIS : algorithme phonétique, améliore Soundex
                  • Soundex : un algorithme phonétique pour indexer les noms par son, tel qu'il se prononce en anglais
                  • La distance Damerau-Levenshtein calcule une mesure de distance entre deux chaînes, améliore la distance de Levenshtein
                  • Coefficient de Dice (également appelé coefficient de Dice) : une mesure de similarité liée à l'indice Jaccard
                  • Distance de Hamming : somme du nombre de positions différentes
                  • Distance Jaro-Winkler : est une mesure de similarité entre deux cordes
                  • Distance d'édition de Levenshtein : calculez une métrique pour la quantité de différence entre deux séquences
                  • Recherche linéaire : trouve un élément dans une séquence non triée
                  • Algorithme de sélection : trouve le kème plus grand élément d'une séquence
                  • Recherche ternaire : une technique pour trouver le minimum ou le maximum d'une fonction qui est soit strictement croissante puis strictement décroissante ou vice versa
                  • Listes triées
                    • Algorithme de recherche binaire : localise un élément dans une séquence triée
                    • Technique de recherche de Fibonacci : recherchez une séquence triée à l'aide d'un algorithme de division pour régner qui réduit les emplacements possibles à l'aide de nombres de Fibonacci
                    • Recherche par saut (ou recherche par bloc) : recherche linéaire sur un sous-ensemble plus petit de la séquence
                    • Recherche prédictive : recherche de type binaire qui prend en compte l'ampleur du terme de recherche par rapport aux valeurs haute et basse de la recherche. Parfois appelée recherche par dictionnaire ou recherche interpolée.
                    • Recherche binaire uniforme : une optimisation de l'algorithme de recherche binaire classique
                    • Algorithme de fusion simple
                    • algorithme de fusion k-way
                    • Union (fusion, avec des éléments sur la sortie non répétés)
                    • Fisher-Yates shuffle (également connu sous le nom de Knuth shuffle) : mélangez au hasard un ensemble fini
                    • Algorithme de Schensted : construit une paire de tableaux de Young à partir d'une permutation
                    • Algorithme de Steinhaus-Johnson-Trotter (également connu sous le nom d'algorithme de Johnson-Trotter) : générer des permutations en transposant des éléments
                    • Algorithme de génération de permutation de Heap : échanger des éléments pour générer la prochaine permutation
                    • Déformation temporelle dynamique : mesure la similarité entre deux séquences qui peuvent varier en temps ou en vitesse
                    • Algorithme de Hirschberg : trouve l'alignement de séquence le moins coûteux entre deux séquences, tel que mesuré par leur distance de Levenshtein
                    • Algorithme Needleman-Wunsch : trouver l'alignement global entre deux séquences
                    • Algorithme de Smith-Waterman : trouver l'alignement de séquences local
                    • Échanger des tris
                      • Tri à bulles : pour chaque paire d'indices, échangez les éléments en cas de désordre
                      • Tri par shaker ou tri à bulles bidirectionnel, un tri à bulles parcourant la liste alternativement d'avant en arrière et d'arrière en avant
                      • Tri en peigne
                      • Trier les gnomes
                      • Tri impair-pair
                      • Tri rapide : divisez la liste en deux, avec tous les éléments de la première liste avant tous les éléments de la deuxième liste. puis triez les deux listes. Souvent la méthode de choix
                      • Bogosort
                      • Trier les Stooges
                      • Tri Flash
                      • Introsort : commencez par un tri rapide et passez au tri par tas lorsque la profondeur de récursivité dépasse un certain niveau
                      • Timsort : algorithme adaptatif dérivé du tri par fusion et du tri par insertion. Utilisé dans Python 2.3 et supérieur, et Java SE 7.
                      • Tri par insertion : déterminez l'emplacement de l'élément actuel dans la liste des éléments triés et l'y insérez
                      • Tri de la bibliothèque
                      • Tri de patience
                      • Tri Shell : une tentative d'amélioration du tri par insertion
                      • Tri d'arbre (tri d'arbre binaire): construire un arbre binaire, puis le parcourir pour créer une liste triée
                      • Tri par cycle : sur place avec un nombre d'écritures théoriquement optimal
                      • Tri par fusion : triez séparément la première et la deuxième moitié de la liste, puis fusionnez les listes triées
                      • Tri des brins
                      • Tri de perles
                      • Tri par godet
                      • Burstsort : créez un trie de rafale compact et efficace en cache, puis parcourez-le pour créer une sortie triée
                      • Tri par comptage
                      • Trier les pigeonniers
                      • Tri Postman : variante du tri Bucket qui tire parti de la structure hiérarchique
                      • Tri par base : trie les chaînes lettre par lettre
                      • Heapsort : convertissez la liste en un tas, continuez à supprimer le plus grand élément du tas et à l'ajouter à la fin de la liste
                      • Tri par sélection : choisissez le plus petit des éléments restants, ajoutez-le à la fin de la liste triée
                      • Tri lisse
                      • Trieur bitonique
                      • Tri des crêpes
                      • Trier les spaghettis
                      • Tri topologique
                      • Tri d'échantillons
                      • Algorithme de Kadane : trouve le sous-tableau maximal de n'importe quelle taille
                      • Problème de sous-séquence commune la plus longue : trouver la sous-séquence la plus longue commune à toutes les séquences dans un ensemble de séquences
                      • Problème de la sous-suite croissante la plus longue : Trouver la sous-suite croissante la plus longue d'une séquence donnée
                      • Problème de superséquence commune la plus courte : trouvez la superséquence la plus courte qui contient deux ou plusieurs séquences en tant que sous-séquences
                      • Problème de sous-chaîne commune la plus longue : recherchez la ou les chaînes les plus longues qui sont une sous-chaîne (ou sont des sous-chaînes) de deux chaînes ou plus
                      • Recherche de sous-chaîne
                        • Algorithme de correspondance de chaînes Aho-Corasick : algorithme basé sur un trie pour trouver toutes les correspondances de sous-chaînes avec l'un des ensembles finis de chaînes
                        • Algorithme de recherche de chaîne Boyer-Moore : algorithme linéaire amorti (sublinéaire la plupart du temps) pour la recherche de sous-chaîne
                        • Algorithme Boyer-Moore-Horspool : Simplification de Boyer-Moore
                        • Algorithme de Knuth-Morris-Pratt : recherche de sous-chaîne qui contourne le réexamen des caractères appariés
                        • Algorithme de recherche de chaîne Rabin-Karp : recherche efficacement plusieurs modèles
                        • Algorithme de correspondance de chaînes Zhu-Takaoka : une variante de Boyer-Moore
                        • Wildmat de Rich Salz : un algorithme récursif open source largement utilisé
                        • Algorithme de correspondance de caractères génériques de Krauss : un algorithme non récursif open source
                        • Recherche Chien : un algorithme récursif pour déterminer les racines de polynômes définis sur un corps fini
                        • Algorithme de Schreier-Sims : calcul d'un groupe électrogène de base et fort (BSGS) d'un groupe de permutation
                        • Algorithme de Todd-Coxeter : Procédure de génération de cosets.
                        • Algorithme de Buchberger : trouve une base de Gröbner
                        • Algorithme de Cantor-Zassenhaus : factoriser des polynômes sur des corps finis
                        • Algorithme Faugère F4 : trouve une base de Gröbner (mentionne aussi l'algorithme F5)
                        • Algorithme de Gosper : trouver des sommes de termes hypergéométriques qui sont eux-mêmes des termes hypergéométriques
                        • Algorithme de complétion Knuth-Bendix : pour la réécriture des systèmes de règles
                        • Algorithme de division multivariée : pour les polynômes à plusieurs indéterminés
                        • Algorithme kangourou de Pollard (également connu sous le nom d'algorithme lambda de Pollard ): un algorithme pour résoudre le problème du logarithme discret
                        • Division longue polynomiale : un algorithme pour diviser un polynôme par un autre polynôme de même degré ou de degré inférieur
                        • Algorithme de Risch : un algorithme pour l'opération de calcul d'intégration indéfinie (c'est-à-dire trouver des primitives)
                        • Problème de la paire la plus proche : trouver la paire de points (à partir d'un ensemble de points) avec la plus petite distance entre eux
                        • Algorithmes de détection de collision : vérifiez la collision ou l'intersection de deux solides donnés
                        • Algorithme de cône : identifier les points de surface
                        • Algorithmes d'enveloppe convexe : détermination de l'enveloppe convexe d'un ensemble de points
                          • Numérisation de Graham
                          • coque rapide
                          • Algorithme d'emballage cadeau ou Jarvis mars
                          • Algorithme de Chan
                          • Algorithme de Kirkpatrick-Seidel
                          • Algorithme de Bentley-Ottmann
                          • Algorithme de Shamos-Hoey
                          • Triangulation de Delaunay
                            • Algorithme de Ruppert (également appelé raffinement de Delaunay) : créer des triangulations de Delaunay de qualité
                            • Deuxième algorithme de Chew : créer des triangulations de Delaunay sous contraintes de qualité
                            • Algorithme Bowyer-Watson : créer un diagramme de Voronoi dans un nombre quelconque de dimensions
                            • Algorithme de Fortune : créer un diagramme de Voronoi

                            Algorithmes de la théorie des nombres

                            • Algorithme GCD binaire : moyen efficace de calculer le GCD.
                            • Algorithme de multiplication de Booth
                            • Méthode Chakravala : un algorithme cyclique pour résoudre des équations quadratiques indéterminées, dont l'équation de Pell
                            • Logarithme discret :
                              • Pas de bébé pas de géant
                              • Algorithme de calcul d'index
                              • Algorithme rho de Pollard pour les logarithmes
                              • Algorithme de Pohlig-Hellman
                              • Congruence des carrés
                              • Algorithme de Dixon
                              • La méthode de factorisation de Fermat
                              • Tamis de champ numéroté général
                              • Factorisation de la courbe elliptique de Lenstra
                              • Pollard p − 1 algorithme
                              • Algorithme rho de Pollard
                              • algorithme de factorisation premier
                              • Tamis quadratique
                              • Algorithme de Shor
                              • Tamis de champ numéro spécial
                              • Section de première instance
                              • Algorithme de Karatsuba
                              • Algorithme de Schönhage-Strassen
                              • Multiplication Toom-Cook
                              • Algorithme de Tonelli-Shanks
                              • Algorithme de Cipolla
                              • Test de primalité AKS
                              • Test de primalité Baillie-PSW
                              • Test de primalité de Fermat
                              • Test de primalité de Lucas
                              • Test de primalité de Miller-Rabin
                              • Tamis d'Atkin
                              • Tamis d'Eratosthène
                              • Tamis de Sundaram

                              Résolution d'équation différentielle

                              • Méthode d'Euler
                              • Méthode d'Euler en amont
                              • Règle trapézoïdale (équations différentielles)
                              • Méthodes linéaires à plusieurs étapes
                              • Méthodes Runge-Kutta
                                • Intégration d'Euler
                                • Méthode des différences finies
                                • Méthode Crank-Nicolson pour les équations de diffusion
                                • Lax-Wendroff pour les équations d'onde

                                Fonctions élémentaires et spéciales

                                • Calcul de :
                                  • Algorithme de Borwein : un algorithme pour calculer la valeur de 1/π
                                  • Algorithme de Gauss-Legendre : calcule les chiffres de pi
                                  • Algorithme de Chudnovsky : une méthode rapide pour calculer les chiffres de
                                  • Formule de Bailey-Borwein-Plouffe : (formule BBP) un algorithme de spigot pour le calcul du nième chiffre binaire de π
                                  • Division longue
                                  • Division restauration
                                  • Division sans restauration
                                  • Division SRT
                                  • Division Newton-Raphson : utilise la méthode de Newton pour trouver l'inverse de D, et multiplie cette réciproque par N pour trouver le quotient final Q.
                                  • Division Goldschmidt
                                  • Algorithme BKM : calculer des fonctions élémentaires à l'aide d'une table de logarithmes
                                  • CORDIC : calcul des fonctions hyperboliques et trigonométriques à l'aide d'une table d'arctangentes
                                  • exponentiation de la chaîne d'addition exponentiation par des puissances entières positives qui nécessite un nombre minimal de multiplications
                                  • L'exponentiation par élévation au carré : un algorithme utilisé pour le calcul rapide de grandes puissances entières d'un nombre
                                  • Algorithme de multiplication de Booth : un algorithme de multiplication qui multiplie deux nombres binaires signés en notation complémentaire à deux
                                  • Algorithme de Fürer : un algorithme de multiplication d'entiers pour de très grands nombres possédant une complexité asymptotique très faible
                                  • Algorithme de Karatsuba : une procédure efficace pour multiplier de grands nombres
                                  • Algorithme de Schönhage-Strassen : un algorithme de multiplication asymptotiquement rapide pour les grands entiers
                                  • Multiplication Toom-Cook : (Toom3) un algorithme de multiplication pour les grands entiers
                                  • La méthode de Newton
                                  • Algorithme Alpha max plus bêta min : une approximation de la racine carrée de la somme de deux carrés
                                  • Méthodes de calcul des racines carrées
                                  • malgorithme racine
                                  • Algorithme changeant de racine n : extraction de racine chiffre par chiffre
                                  • Division binaire : une technique diviser pour régner qui accélère l'évaluation numérique de nombreux types de séries avec des termes rationnels
                                  • Algorithme de sommation de Kahan : une méthode plus précise de sommation de nombres à virgule flottante
                                  • Rétroprojection filtrée : calcule efficacement la transformée de Radon inverse en 2 dimensions.
                                  • Level set method (LSM) : une technique numérique pour le suivi des interfaces et des formes

                                  Interpolation et extrapolation

                                  • Interpolation de Birkhoff : une extension de l'interpolation polynomiale
                                  • Interpolation cubique
                                  • Interpolation Hermite
                                  • Interpolation de Lagrange : interpolation à l'aide de polynômes de Lagrange
                                  • Interpolation linéaire : une méthode d'ajustement de courbe à l'aide de polynômes linéaires
                                  • Interpolation cubique monotone : une variante de l'interpolation cubique qui préserve la monotonie de l'ensemble de données interpolé.
                                  • Interpolation multivariée
                                    • L'interpolation bicubique, une généralisation de l'interpolation cubique à deux dimensions
                                    • Interpolation bilinéaire : une extension de l'interpolation linéaire pour interpoler les fonctions de deux variables sur une grille régulière
                                    • Le rééchantillonnage de Lanczos (« Lanzosh ») : une méthode d'interpolation multivariée utilisée pour calculer de nouvelles valeurs pour toutes les données échantillonnées numériquement
                                    • Interpolation du plus proche voisin
                                    • L'interpolation tricubique, une généralisation de l'interpolation cubique à trois dimensions
                                    • L'algorithme de Neville
                                    • Algorithme de De Boor : B-splines
                                    • Algorithme de De Casteljau : courbes de Bézier

                                    Processus de Gram-Schmidt : orthogonalise un ensemble de vecteurs

                                    • Algorithme de Cannon : un algorithme distribué pour la multiplication matricielle particulièrement adapté aux ordinateurs disposés dans un maillage N × N
                                    • Algorithme Coppersmith-Winograd : multiplication matricielle carrée
                                    • Algorithme de Freivalds : un algorithme aléatoire utilisé pour vérifier la multiplication matricielle
                                    • Algorithme de Strassen : multiplication matricielle plus rapide
                                    • Méthode du gradient biconjugué : résout des systèmes d'équations linéaires
                                    • Gradient conjugué : un algorithme pour la résolution numérique de systèmes particuliers d'équations linéaires
                                    • Élimination gaussienne
                                    • Élimination de Gauss-Jordan : résout des systèmes d'équations linéaires
                                    • Méthode de Gauss-Seidel : résout les systèmes d'équations linéaires de manière itérative
                                    • Récursion de Levinson : résout une équation impliquant une matrice de Toeplitz
                                    • La méthode de Stone : également connue sous le nom de procédure fortement implicite ou SIP, est un algorithme permettant de résoudre un système d'équations linéaires clairsemé
                                    • Sur-relaxation successive (SOR) : méthode utilisée pour accélérer la convergence de la méthode de Gauss-Seidel
                                    • Algorithme matriciel tridiagonal (algorithme de Thomas) : résout des systèmes d'équations tridiagonales
                                    • Algorithme Cuthill–McKee : réduire la bande passante d'une matrice creuse symétrique
                                    • Algorithme de degré minimum : permuter les lignes et les colonnes d'une matrice creuse symétrique avant d'appliquer la décomposition de Cholesky
                                    • Décomposition symbolique de Cholesky : moyen efficace de stocker une matrice creuse
                                    • Échantillonnage de Gibbs : générer une séquence d'échantillons à partir de la distribution de probabilité conjointe de deux ou plusieurs variables aléatoires
                                    • Monte Carlo hybride : générer une séquence d'échantillons en utilisant la chaîne de Markov pondérée hamiltonienne Monte Carlo, à partir d'une distribution de probabilité difficile à échantillonner directement.
                                    • Algorithme Metropolis-Hastings : utilisé pour générer une séquence d'échantillons à partir de la distribution de probabilité d'une ou plusieurs variables
                                    • Algorithme de Wang et Landau : une extension de l'échantillonnage de l'algorithme de Metropolis-Hastings
                                    • Méthode de bissection
                                    • Méthode de fausse position : approxime les racines d'une fonction
                                    • Méthode de Newton : trouve les zéros des fonctions avec le calcul
                                    • Méthode de Halley : utilise les dérivées premières et secondes
                                    • Méthode sécante : 2 points, 1 côté
                                    • Méthode des fausses positions et méthode de l'Illinois : 2 points, bracketing
                                    • Méthode de Ridder : mise à l'échelle exponentielle en 3 points
                                    • Méthode de Muller : interpolation quadratique en 3 points

                                    Élagage alpha-bêta : recherche pour réduire le nombre de nœuds dans l'algorithme minimax

                                    Optimisation combinatoire : problèmes d'optimisation où l'ensemble des solutions réalisables est discret

                                    • Procédure de recherche adaptative randomisée gloutonne (GRASP) : constructions successives d'une solution randomisée gloutonne et améliorations itératives ultérieures de celle-ci grâce à une recherche locale
                                    • Méthode hongroise : un algorithme d'optimisation combinatoire qui résout le problème d'affectation en temps polynomial
                                    • Algorithmes généraux pour la satisfaction de contraintes
                                      • Algorithme AC-3
                                      • Algorithme de carte de différence
                                      • Algorithme de conflits minimum
                                      • Algorithme X : un algorithme non déterministe
                                      • Dancing Links : une implémentation efficace de l'algorithme X

                                      Méthode d'entropie croisée : une approche générale de Monte Carlo pour l'optimisation multi-extrémale combinatoire et continue et l'échantillonnage d'importance

                                      Méthode ellipsoïde : est un algorithme pour résoudre des problèmes d'optimisation convexe

                                      Calcul évolutif : optimisation inspirée des mécanismes biologiques de l'évolution

                                      • Stratégie d'évolution
                                      • Programmation de l'expression génique
                                      • Algorithmes génétiques
                                        • Sélection proportionnelle de remise en forme - également connue sous le nom de sélection de roue de roulette
                                        • Échantillonnage universel stochastique
                                        • Sélection de troncature
                                        • Sélection du tournoi
                                        • Optimisation des colonies de fourmis
                                        • Algorithme des abeilles : un algorithme de recherche qui imite le comportement de recherche de nourriture d'essaims d'abeilles mellifères
                                        • Essaim de particules

                                        recherche de section dorée : un algorithme pour trouver le maximum d'une fonction réelle

                                        Recherche d'harmonie (HS) : un algorithme métaheuristique imitant le processus d'improvisation des musiciens

                                        • Algorithme de Benson : un algorithme pour résoudre des problèmes d'optimisation vectorielle linéaire
                                        • Décomposition de Dantzig-Wolfe : un algorithme pour résoudre des problèmes de programmation linéaire avec une structure spéciale
                                        • Génération de colonne retardée
                                        • Programmation linéaire en nombres entiers : résoudre des problèmes de programmation linéaire où certaines ou toutes les inconnues sont restreintes à des valeurs entières
                                          • Brancher et couper
                                          • Méthode du plan de coupe

                                          Recherche locale : une métaheuristique pour résoudre des problèmes d'optimisation informatiquement difficiles

                                          • Méthode BFGS : Un algorithme d'optimisation non linéaire
                                          • Algorithme de Gauss-Newton : Un algorithme pour résoudre les problèmes des moindres carrés non linéaires.
                                          • Algorithme de Levenberg-Marquardt : Un algorithme pour résoudre les problèmes des moindres carrés non linéaires.
                                          • Méthode de Nelder-Mead (méthode du simplex en descente) : un algorithme d'optimisation non linéaire

                                          Algorithme de cotes (algorithme de Bruss) : Trouve la stratégie optimale pour prédire un dernier événement spécifique dans un événement de séquence aléatoire

                                          • Algorithme Doomsday : jour de la semaine
                                          • La congruence de Zeller est un algorithme pour calculer le jour de la semaine pour n'importe quelle date du calendrier julien ou grégorien
                                          • divers algorithmes de Pâques sont utilisés pour calculer le jour de Pâques
                                          • Outil de recherche d'alignement local de base également connu sous le nom de BLAST : un algorithme pour comparer les informations de séquence biologique primaire
                                          • Algorithme de Kabsch : calcule l'alignement optimal de deux ensembles de points afin de calculer l'écart quadratique moyen entre deux structures protéiques.
                                          • Velvet : un ensemble d'algorithmes manipulant des graphes de Bruijn pour l'assemblage de séquences génomiques
                                          • Tri par renversements signés : un algorithme pour comprendre l'évolution génomique.
                                          • Parcimonie maximale (phylogénétique) : un algorithme pour trouver l'arbre phylogénétique le plus simple pour expliquer une matrice de caractères donnée.
                                          • UPGMA : un algorithme de construction d'arbre phylogénétique basé sur la distance.
                                          • Les formules de Vincenty : un algorithme rapide pour calculer la distance entre deux points de latitude/longitude sur un ellipsoïde
                                          • Geohash : un algorithme du domaine public qui code une paire latitude/longitude décimale sous forme de chaîne de hachage
                                          • Algorithme de Lesk : désambiguïsation du sens des mots
                                          • Algorithme de racine : une méthode de réduction des mots à leur forme racine, base ou racine
                                          • Algorithme de Sukhotin : un algorithme de classification statistique pour classer les caractères d'un texte en voyelles ou en consonnes
                                          • Algorithme ESC pour le diagnostic de l'insuffisance cardiaque
                                          • Critères de Manning pour le syndrome du côlon irritable
                                          • Algorithmes de diagnostic de l'embolie pulmonaire
                                          • Projet d'algorithme de médicament du Texas
                                          • Algorithme de contrainte : une classe d'algorithmes pour satisfaire les contraintes pour les corps qui obéissent aux équations du mouvement de Newton
                                          • Algorithme Demon : une méthode de Monte Carlo pour échantillonner efficacement les membres d'un ensemble microcanonique avec une énergie donnée
                                          • Algorithme de Featherstone : calculer les effets des forces appliquées à une structure de joints et de liens
                                          • Approximation de l'état fondamental
                                            • Méthode variationnelle
                                              • Méthode Ritz
                                              • Simulation de Barnes-Hut : résout le problème à n corps d'une manière approximative qui a l'ordre au lieu de comme dans une simulation à somme directe.
                                              • Méthode multipolaire rapide (FMM) : accélère le calcul des forces à longue distance
                                              • Algorithmes de calcul de la variance : éviter l'instabilité et le débordement numérique
                                              • Algorithme de comptage approximatif : permet de compter un grand nombre d'événements dans un petit registre
                                              • Statistiques bayésiennes
                                                • Algorithme d'échantillonnage imbriqué : une approche computationnelle du problème de comparaison de modèles dans les statistiques bayésiennes
                                                • Clustering à liaison moyenne : un algorithme de clustering agglomérateur simple
                                                • Algorithme de clustering Canopy : un algorithme de pré-clustering non supervisé lié à l'algorithme K-means
                                                • Clustering à liaison complète : un algorithme de clustering agglomérateur simple
                                                • DBSCAN : un algorithme de clustering basé sur la densité
                                                • Algorithme de maximisation des attentes
                                                • Clustering flou : une classe d'algorithmes de clustering où chaque point a un degré d'appartenance à des clusters
                                                  • C-moyen flou
                                                  • Clustering FLAME (Fuzzy clustering by Local Approximation of MEmberships) : définissez des clusters dans les parties denses d'un ensemble de données et effectuez une affectation de cluster uniquement en fonction des relations de voisinage entre les objets
                                                  • Algorithme de maximisation des attentes Une classe d'algorithmes connexes pour trouver des estimations de vraisemblance maximale de paramètres dans des modèles probabilistes
                                                    • Maximisation des attentes des sous-ensembles ordonnés (OSEM) : utilisée en imagerie médicale pour la tomographie par émission de positons, la tomodensitométrie par émission de photons uniques et la tomodensitométrie à rayons X.
                                                    • Algorithme de Baum-Welch : calcul des estimations de vraisemblance maximale et des estimations de mode postérieur pour les paramètres d'un modèle de Markov caché
                                                    • Algorithme avant-arrière un algorithme de programmation dynamique pour calculer la probabilité d'une séquence d'observation particulière
                                                    • Algorithme de Viterbi : trouver la séquence d'états cachés la plus probable dans un modèle de Markov caché
                                                    • Algorithme de Buzen : un algorithme pour calculer la constante de normalisation G (K) dans le théorème de Gordon-Newell
                                                    • Algorithme Tomasulo : permet à des instructions séquentielles qui seraient normalement bloquées en raison de certaines dépendances de s'exécuter de manière non séquentielle
                                                    • Coupure
                                                      • Coupure de ligne
                                                        • Cohen–Sutherland
                                                        • Cyrus–Beck
                                                        • Clipping rapide
                                                        • Liang-Barsky
                                                        • Nicholl–Lee–Nicholl
                                                        • Sutherland–Hodgman
                                                        • Vatti
                                                        • Weiler–Atherton
                                                        • Marching cubes : extraire un maillage polygonal d'une isosurface à partir d'un champ scalaire tridimensionnel (parfois appelé voxels)
                                                        • Carrés de marche : générer des courbes de niveau pour un champ scalaire bidimensionnel
                                                        • Les tétraèdres de marche : une alternative aux cubes de marche
                                                        • Occlusion ambiante
                                                        • Traçage de faisceau
                                                        • Traçage du cône
                                                        • Éclairage basé sur l'image
                                                        • Transports légers de la métropole
                                                        • Traçage de chemin
                                                        • Cartographie des photons
                                                        • Radiosité
                                                        • tracé laser
                                                        • Algorithme de Newell : élimine les cycles de polygones dans le tri en profondeur requis pour l'élimination des surfaces cachées
                                                        • Algorithme de Painter : détecte les parties visibles d'un paysage en 3 dimensions
                                                        • Rendu Scanline : construit une image en déplaçant une ligne imaginaire sur l'image
                                                        • Algorithme de Warnock
                                                        • Algorithme de ligne de Bresenham : trace les points d'un tableau à 2 dimensions pour former une ligne droite entre 2 points spécifiés (utilise des variables de décision)
                                                        • Algorithme de ligne DDA : trace les points d'un tableau à 2 dimensions pour former une ligne droite entre 2 points spécifiés (utilise des calculs à virgule flottante)
                                                        • Algorithme de ligne de Xiaolin Wu : algorithme d'anticrénelage de ligne.
                                                        • Ombrage Gouraud : un algorithme pour simuler les différents effets de lumière et de couleur sur la surface d'un objet en infographie 3D
                                                        • Phong shading : un algorithme pour interpoler les vecteurs normaux de surface pour l'ombrage de surface en infographie 3D
                                                        • Cryptage asymétrique (clé publique) :
                                                          • ElGamal
                                                          • Cryptographie à courbe elliptique
                                                          • MAE1
                                                          • NTRUcrypter
                                                          • RSA
                                                          • DSA et ses variantes :
                                                            • ECDSA et ECDSA déterministe
                                                            • EdDSA (Ed25519)
                                                            • BLAKE
                                                            • MD5 – Notez qu'il existe maintenant une méthode de génération de collisions pour MD5
                                                            • RIPEMD-160
                                                            • SHA-1 – Notez qu'il existe désormais une méthode de génération de collisions pour SHA-1
                                                            • SHA-2 (SHA-224, SHA-256, SHA-384, SHA-512)
                                                            • SHA-3 (SHA3-224, SHA3-256, SHA3-384, SHA3-512, SHAKE128, SHAKE256)
                                                            • Tiger (TTH), généralement utilisé dans les hachages d'arbres Tiger
                                                            • TOURBILLON
                                                            • Blum Blum Shub - basé sur la dureté de la factorisation
                                                            • Fortuna, conçu comme une amélioration de l'algorithme Yarrow
                                                            • Registre à décalage à rétroaction linéaire (remarque : de nombreux algorithmes basés sur LFSR sont faibles ou ont été brisés)
                                                            • Algorithme de millefeuille
                                                            • Échange de clés Diffie–Hellman
                                                            • Courbe elliptique Diffie-Hellman (ECDH)
                                                            • bcrypt
                                                            • PBKDF2
                                                            • crypter
                                                            • Argon2
                                                            • HMAC : authentification par message de hachage à clé
                                                            • Poly1305
                                                            • SipHash
                                                            • Le schéma de Blakey
                                                            • Le schéma de Shamir
                                                            • Advanced Encryption Standard (AES), lauréat du concours NIST, également connu sous le nom de Rijndael
                                                            • Poisson-globe
                                                            • Deux Poisson
                                                            • Trois poissons
                                                            • Data Encryption Standard (DES), parfois DE Algorithm, lauréat du concours de sélection NBS, remplacé par AES dans la plupart des cas
                                                            • IDÉE
                                                            • RC4 (chiffre)
                                                            • Minuscule algorithme de cryptage (TEA)
                                                            • Salsa20, et sa variante mise à jour ChaCha20
                                                            • Minimisation booléenne
                                                              • Algorithme de Quine-McCluskey : Également appelé algorithme Q-M, méthode programmable pour simplifier les équations booléennes.
                                                              • Méthode de Petrick : Un autre algorithme de simplification booléenne.
                                                              • Minimiseur logique heuristique expresso : algorithme rapide pour la minimisation des fonctions booléennes.

                                                              Apprentissage automatique et classification statistique

                                                              • ALOPEX : un algorithme d'apprentissage automatique basé sur la corrélation
                                                              • Apprentissage des règles d'association : découvrez des relations intéressantes entre les variables, utilisées dans l'exploration de données
                                                                • Algorithme a priori
                                                                • Algorithme Éclat
                                                                • Algorithme de croissance FP
                                                                • Règle à un attribut
                                                                • Règle d'attribut zéro
                                                                • AdaBoost : boost adaptatif
                                                                • BrownBoost : un algorithme de boost qui peut être robuste aux ensembles de données bruyants
                                                                • LogitBoost : booster la régression logistique
                                                                • LPBoost : boost de programmation linéaire
                                                                • Grabcut basé sur des coupes graphiques
                                                                • Algorithme C4.5 : une extension à ID3
                                                                • Algorithme ID3 (Iterative Dichotomiser 3) : Utiliser l'heuristique pour générer de petits arbres de décision
                                                                • k-nearest voisins (k-NN) : une méthode de classification des objets basée sur les exemples d'apprentissage les plus proches dans l'espace des caractéristiques
                                                                • Rétropropagation : une méthode d'apprentissage supervisé qui nécessite un enseignant qui connaît ou peut calculer la sortie souhaitée pour une entrée donnée
                                                                • Hopfield net : un réseau de neurones récurrents dans lequel toutes les connexions sont symétriques
                                                                • Perceptron : le type le plus simple de réseau de neurones feedforward : un classificateur linéaire.
                                                                • Réseaux de neurones à couplage d'impulsions (PCNN) : modèles de neurones proposés en modélisant le cortex visuel d'un chat et développés pour le traitement d'images biomimétiques haute performance.
                                                                • Réseau de fonctions de base radiale : un réseau de neurones artificiels qui utilise des fonctions de base radiales comme fonctions d'activation
                                                                • Carte auto-organisée : un réseau non supervisé qui produit une représentation en basse dimension de l'espace d'entrée des échantillons d'apprentissage
                                                                • Q-learning : apprendre une fonction action-valeur qui donne l'utilité attendue de prendre une action donnée dans un état donné et de suivre une politique fixe par la suite
                                                                • State-Action-Reward-State-Action (SARSA) : apprendre une politique de processus décisionnel de Markov
                                                                • Apprentissage de la différence temporelle
                                                                • SVM structuré : permet la formation d'un classificateur pour les étiquettes de sortie structurées générales.

                                                                Théorie du langage de programmation

                                                                • Linéarisation C3 : un algorithme utilisé principalement pour obtenir une linéarisation cohérente d'une hiérarchie d'héritage multiple dans la programmation orientée objet
                                                                • Algorithme de Chaitin : un algorithme d'allocation de registres de coloration de graphe ascendant qui utilise le coût/degré comme métrique de déversement
                                                                • Algorithme d'inférence de type Hindley-Milner
                                                                • Algorithme Rete : un algorithme de filtrage de motifs efficace pour la mise en œuvre de systèmes de règles de production
                                                                • Algorithme Sethi-Ullman : générer un code optimal pour les expressions arithmétiques
                                                                • Algorithme CYK : un algorithme O(n^3^) pour analyser des grammaires sans contexte sous la forme normale de Chomsky
                                                                • Analyseur d'Earley : un autre algorithme O(n^3^) pour analyser n'importe quelle grammaire sans contexte
                                                                • Analyseur GLR : un algorithme pour analyser toute grammaire sans contexte par Masaru Tomita. Il est adapté aux grammaires déterministes, sur lesquelles il effectue un temps presque linéaire et O(n^3^) dans le pire des cas.
                                                                • Algorithme inside-outside : un algorithme O(n^3^) pour ré-estimer les probabilités de production dans les grammaires probabilistes sans contexte
                                                                • Analyseur LL : un algorithme d'analyse temporelle linéaire relativement simple pour une classe limitée de grammaires sans contexte
                                                                • Analyseur LR : un algorithme d'analyse temporelle linéaire plus complexe pour une plus grande classe de grammaires sans contexte. Variantes :
                                                                  • Analyseur LR canonique
                                                                  • Analyseur LALR (Look-ahead LR)
                                                                  • Analyseur de priorité des opérateurs
                                                                  • Analyseur SLR (Simple LR)
                                                                  • Analyseur de priorité simple
                                                                  • Algorithme de Deutsch-Jozsa : critère d'équilibre pour la fonction booléenne
                                                                  • Algorithme de Grover : fournit une accélération quadratique pour de nombreux problèmes de recherche
                                                                  • Algorithme de Shor : fournit une accélération exponentielle (par rapport aux algorithmes non quantiques actuellement connus) pour la factorisation d'un nombre
                                                                  • Algorithme de Simon : fournit une accélération prouvablement exponentielle (par rapport à tout algorithme non quantique) pour un problème de boîte noire

                                                                  Théorie du calcul et automates

                                                                  • Algorithme de Hopcroft, algorithme de Moore et algorithme de Brzozowski : algorithmes pour minimiser le nombre d'états dans un automate fini déterministe
                                                                  • Construction de Powerset : Algorithme pour convertir un automate non déterministe en automate déterministe.
                                                                  • Algorithme de Tarski-Kuratowski : un algorithme non déterministe qui fournit une limite supérieure pour la complexité des formules dans la hiérarchie arithmétique et la hiérarchie analytique

                                                                  Théorie de l'information et traitement du signal

                                                                  Détection et correction des erreurs

                                                                  • Codes BCH
                                                                    • Algorithme de Berlekamp-Massey
                                                                    • Algorithme de Peterson-Gorenstein-Zierler
                                                                    • Correction d'erreur Reed-Solomon
                                                                    • Hamming (7,4) : un code de Hamming qui encode 4 bits de données en 7 bits en ajoutant 3 bits de parité
                                                                    • Distance de Hamming : somme du nombre de positions différentes
                                                                    • Poids de Hamming (nombre de population) : trouver le nombre de bits 1 dans un mot binaire
                                                                    • Adler-32
                                                                    • Contrôle de redondance cyclique
                                                                    • Algorithme de Damm
                                                                    • Somme de contrôle de Fletcher
                                                                    • Contrôle de redondance longitudinale (LRC)
                                                                    • Algorithme de Luhn : une méthode de validation des numéros d'identification
                                                                    • Algorithme Luhn mod N : extension de Luhn aux caractères non numériques
                                                                    • Parité : technique de détection d'erreur simple/rapide
                                                                    • Algorithme de Verhoeff

                                                                    Algorithmes de compression sans perte

                                                                    • Transformée de Burrows–Wheeler : prétraitement utile pour améliorer la compression sans perte
                                                                    • Pondération de l'arbre de contexte
                                                                    • Encodage delta : aide à la compression des données dans lesquelles des données séquentielles se produisent fréquemment
                                                                    • Compression dynamique de Markov : compression utilisant le codage arithmétique prédictif
                                                                    • Codeurs de dictionnaire
                                                                      • Codage de paires d'octets (BPE)
                                                                      • DÉGONFLER
                                                                      • Lempel–Ziv
                                                                        • LZ77 et LZ78
                                                                        • Lempel–Ziv Jeff Bonwick (LZJB)
                                                                        • Algorithme de chaîne de Lempel-Ziv-Markov (LZMA)
                                                                        • Lempel–Ziv–Oberhumer (LZO) : axé sur la vitesse
                                                                        • Lempel–Ziv–Stac (LZS)
                                                                        • Lempel–Ziv–Storer–Szymanski (LZSS)
                                                                        • Lempel–Ziv–Welch (LZW)
                                                                        • LZWL : variante basée sur la syllabe
                                                                        • LZX
                                                                        • Lempel–Ziv Ross Williams (LZRW)
                                                                        • Codage arithmétique : codage entropique avancé
                                                                          • Codage de plage : identique au codage arithmétique, mais considéré d'une manière légèrement différente
                                                                          • Codage adaptatif de Huffman : technique de codage adaptatif basée sur le codage de Huffman
                                                                          • Algorithme de fusion de packages : optimise le codage de Huffman sous réserve d'une restriction de longueur sur les chaînes de code
                                                                          • Codage de Golomb : forme de codage entropique optimale pour les alphabets suivant des distributions géométriques
                                                                          • Codage du riz : forme de codage entropique optimale pour les alphabets suivant des distributions géométriques
                                                                          • Encodage binaire tronqué
                                                                          • Codage unaire : code qui représente un nombre n avec n suivis d'un zéro
                                                                          • Codes universels : encode les entiers positifs en mots de code binaires
                                                                            • Codage Elias delta, gamma et oméga
                                                                            • Codage exponentiel-Golomb
                                                                            • Codage de Fibonacci
                                                                            • Codage Levenshtein

                                                                            Algorithmes de compression avec perte

                                                                            • 3Dc : un algorithme de compression de données avec perte pour les cartes normales
                                                                            • Compression audio et vocale
                                                                              • Algorithme A-law : algorithme de compression-extension standard
                                                                              • Prédiction linéaire excitée par le code (CELP) : compression de la parole à faible débit
                                                                              • Codage prédictif linéaire (LPC) : compression avec perte en représentant l'enveloppe spectrale d'un signal numérique de parole sous forme compressée
                                                                              • Algorithme Mu-law : algorithme standard de compression ou de compression-extension de signal analogique
                                                                              • Codage prédictif linéaire déformé (WLPC)
                                                                              • Block Troncation Coding (BTC) : un type de technique de compression d'image avec perte pour les images en niveaux de gris
                                                                              • Ondelette Zerotree intégrée (EZW)
                                                                              • Algorithmes de transformation en cosinus rapide (algorithmes FCT) : calculez efficacement la transformation en cosinus discrète (DCT)
                                                                              • Compression fractale : méthode utilisée pour compresser des images à l'aide de fractales
                                                                              • Définir le partitionnement dans les arbres hiérarchiques (SPIHT)
                                                                              • Compression par ondelettes : forme de compression de données bien adaptée à la compression d'images (parfois aussi compression vidéo et compression audio)

                                                                              Traitement des signaux numériques

                                                                              • Algorithme adaptatif-additif (algorithme AA) : trouvez la phase de fréquence spatiale d'une source d'onde observée
                                                                              • Transformée de Fourier discrète : détermine les fréquences contenues dans un (segment de a) signal
                                                                                • Algorithme FFT de Bluestein
                                                                                • Algorithme FFT de Bruun
                                                                                • Algorithme FFT de Cooley-Tukey
                                                                                • Transformée de Fourier Rapide
                                                                                • Algorithme FFT à facteur premier
                                                                                • Algorithme FFT de Rader
                                                                                • Amélioration du contraste
                                                                                  • Égalisation de l'histogramme : utilisez l'histogramme pour améliorer le contraste de l'image
                                                                                  • Égalisation d'histogramme adaptative : égalisation d'histogramme qui s'adapte aux changements locaux de contraste
                                                                                  • Diffusion d'erreurs
                                                                                  • Trempage Floyd-Steinberg
                                                                                  • Tramage ordonné
                                                                                  • Riemersma tramage
                                                                                  • Détecteur de bords Canny : détectez une large gamme de bords dans les images
                                                                                  • Transformée de Hough généralisée
                                                                                  • Hough transformer
                                                                                  • Algorithme de Marr-Hildreth : un algorithme de détection précoce des contours
                                                                                  • SIFT (Scale-invariant feature transform) : est un algorithme pour détecter et décrire des caractéristiques locales dans les images.
                                                                                  • SURF (Speeded Up Robust Features) : est un détecteur de caractéristiques locales robuste, présenté pour la première fois par Herbert Bay et al. en 2006, qui peut être utilisé dans des tâches de vision par ordinateur comme la reconnaissance d'objets ou la reconstruction 3D. Il s'inspire en partie du descripteur SIFT. La version standard de SURF est plusieurs fois plus rapide que SIFT et revendiquée par ses auteurs comme étant plus robuste contre les différentes transformations d'images que SIFT.[^2][^3]
                                                                                  • Algorithme GrowCut : un algorithme de segmentation interactif
                                                                                  • Algorithme de marcheur aléatoire
                                                                                  • Région en croissance
                                                                                  • Transformation des bassins versants : une classe d'algorithmes basée sur l'analogie des bassins versants
                                                                                  • Algorithmes de cache
                                                                                  • Conversion CHS : conversion entre les systèmes d'adressage de disque
                                                                                  • Double barbotage : Convertir des nombres binaires en BCD
                                                                                  • Fonction de hachage : convertissez une grande quantité de données, éventuellement de taille variable, en une petite donnée, généralement un seul entier pouvant servir d'index dans un tableau
                                                                                    • Fonction de hachage Fowler–Noll–Vo : rapide avec un faible taux de collision
                                                                                    • Hachage Pearson : calcule la valeur 8 bits uniquement, optimisé pour les ordinateurs 8 bits
                                                                                    • Hachage Zobrist : utilisé dans la mise en place de tables de transposition

                                                                                    Algorithmes des systèmes distribués

                                                                                    • Algorithme Bully : une méthode de sélection dynamique d'un coordinateur
                                                                                    • Tolérance aux pannes byzantine : bonne tolérance aux pannes.
                                                                                    • Synchronisation de l'horloge
                                                                                      • Algorithme de Berkeley
                                                                                      • L'algorithme de Cristian
                                                                                      • Algorithme d'intersection
                                                                                      • Algorithme de Marzullo
                                                                                      • Algorithme de Dijkstra-Scholten
                                                                                      • L'algorithme de Huang
                                                                                      • Algorithme d'exclusion mutuelle distribuée de Lamport
                                                                                      • Algorithme log(n) de Naimi-Trehel
                                                                                      • L'algorithme de Maekawa
                                                                                      • L'algorithme de Raymond
                                                                                      • Algorithme Ricart-Agrawala
                                                                                      • Algorithme de Chandy-Lamport

                                                                                      Algorithmes d'allocation et de désallocation de mémoire

                                                                                      • Allocation de mémoire de copain : algorithme pour allouer de la mémoire de telle sorte que la fragmentation soit moindre.
                                                                                      • Éboueurs
                                                                                        • Algorithme de Cheney : une amélioration du collecteur semi-espace
                                                                                        • ramasse-miettes générationnel : ramasse-miettes rapides qui séparent la mémoire par âge
                                                                                        • Algorithme Mark-compact : une combinaison de l'algorithme Mark-Sweep et de l'algorithme de copie de Cheney
                                                                                        • Marquer et balayer
                                                                                        • Collectionneur semi-spatial : un des premiers collectionneurs de copies
                                                                                        • Algorithme de Karn : résout le problème d'obtenir des estimations précises du temps d'aller-retour des messages lors de l'utilisation de TCP
                                                                                        • Algorithme de Luleå : une technique pour stocker et rechercher efficacement des tables de routage Internet
                                                                                        • La congestion du réseau
                                                                                          • Retard exponentiel
                                                                                          • Algorithme de Nagle : améliorer l'efficacité des réseaux TCP/IP en fusionnant les paquets
                                                                                          • Backoff exponentiel binaire tronqué

                                                                                          Algorithmes des systèmes d'exploitation

                                                                                          • Algorithme du banquier : algorithme utilisé pour éviter les impasses.
                                                                                          • Algorithmes de remplacement de page : sélection de la page victime dans des conditions de faible mémoire.
                                                                                            • Cache de remplacement adaptatif : meilleures performances que LRU
                                                                                            • Horloge avec remplacement adaptatif (CAR) : est un algorithme de remplacement de page dont les performances sont comparables au cache de remplacement adaptatif
                                                                                            • Date limite la plus rapprochée première programmation
                                                                                            • Programmation équitable
                                                                                            • Ordonnancement avec le moins de temps mort
                                                                                            • Ordonnancement de liste
                                                                                            • File d'attente de commentaires à plusieurs niveaux
                                                                                            • Ordonnancement à cadence monotone
                                                                                            • Ordonnancement à tour de rôle
                                                                                            • Travail le plus court suivant
                                                                                            • Temps restant le plus court
                                                                                            • Algorithme top-nodes : gestion du calendrier des ressources
                                                                                            • Algorithme d'ascenseur : algorithme de planification de disque qui fonctionne comme un ascenseur.
                                                                                            • Recherche la plus courte en premier : algorithme de planification de disque pour réduire le temps de recherche.

                                                                                            Exemples de tâches

                                                                                            Rechercher des chaînes en double dans un tableau de chaînes

                                                                                            Problème : Étant donné une liste de $n$ chaînes $s_i$, chacune ne dépassant pas $m$ caractères, trouvez toutes les chaînes en double et divisez-les en groupes.

                                                                                            À partir de l'algorithme évident impliquant le tri des chaînes, nous obtiendrions une complexité temporelle de $O(nm log n)$ où le tri nécessite des comparaisons $O(n log n)$ et chaque comparaison prend $O(m)$ temps . Cependant, en utilisant des hachages, nous réduisons le temps de comparaison à $O(1)$, ce qui nous donne un algorithme qui s'exécute en $O(n m + n log n)$ temps.

                                                                                            Nous calculons le hachage pour chaque chaîne, trions les hachages avec les indices, puis regroupons les indices par hachages identiques.

                                                                                            Calcul de hachage rapide des sous-chaînes d'une chaîne donnée

                                                                                            Problème : Étant donné une chaîne $s$ et les indices $i$ et $j$, trouver le hachage de la sous-chaîne $s [i dots j]$.

                                                                                            Par définition, nous avons : $ ext(s[i dots j]) = somme_^j s[k] cdot p^ mod m$ Multiplier par $p^i$ donne : $egin exte(s[i dots j]) cdot p^i &= sum_^j s[k] cdot p^k mod m \\ &= ext(s[0 dots j]) - ext(s[0 dots i-1]) mod m end$

                                                                                            Ainsi, en connaissant la valeur de hachage de chaque préfixe de la chaîne $s$, nous pouvons calculer le hachage de n'importe quelle sous-chaîne directement à l'aide de cette formule. Le seul problème auquel nous sommes confrontés dans le calcul est que nous devons être capables de diviser $ ext(s[0 dots j]) - ext(s[0 dots i-1])$ par $p^i$. Par conséquent, nous devons trouver l'inverse multiplicatif modulaire de $p^i$, puis effectuer une multiplication avec cet inverse. Nous pouvons précalculer l'inverse de chaque $p^i$, ce qui permet de calculer le hachage de toute sous-chaîne de $s$ en $O(1)$.

                                                                                            Cependant, il existe un moyen plus simple. Dans la plupart des cas, plutôt que de calculer exactement les hachages de la sous-chaîne, il suffit de calculer le hachage multiplié par une puissance de $p$. Supposons que nous ayons deux hachages de deux sous-chaînes, l'une multipliée par $p^i$ et l'autre par $p^j$. Si $i < j$ alors on multiplie le premier hachage par $p^$, sinon, on multiplie le deuxième hachage par $p^$. En faisant cela, nous obtenons les deux hachages multipliés par la même puissance de $p$ (qui est le maximum de $i$ et $j$) et maintenant ces hachages peuvent être comparés facilement sans aucune division.


                                                                                            C-3PO, PhD : Apprentissage automatique en astronomie

                                                                                            Les astronomes travaillent avec beaucoup de données. Une tonne de données sérieuse. Et la vitesse à laquelle les télescopes et les simulations déversent des données augmente rapidement. Prenez le prochain grand télescope d'enquête synoptique, ou LSST. Chaque image prise par le télescope aura une taille de plusieurs Go. Entre les 2 000 images nocturnes, le traitement de plus de 10 millions de sources dans chaque image, puis l'envoi de jusqu'à 100 000 alertes transitoires, l'enquête générera plus de 10 téraoctets de données CHAQUE NUIT ! Tout au long du projet, plus de 60 pétaoctets de données seront générés. À un Go par épisode, il faudrait 6 millions de saisons de Game of Thrones pour obtenir autant de données. C'est beaucoup de science qui sort du LSST.

                                                                                            L'un des plus gros problèmes avec la gestion de telles quantités de données astronomiques est de savoir comment rechercher efficacement des objets transitoires : des choses qui apparaissent et disparaissent. Un défi majeur de l'astronomie transitoire est de savoir comment distinguer quelque chose qui est vraiment devenu plus brillant (comme une supernova) d'un artefact mécanique (comme un pixel défectueux, un rayon cosmique ou un autre défaut). Avec autant d'images entrantes, vous ne pouvez pas les reprendre à chaque fois pour vérifier si une source est réelle.

                                                                                            Avant l'ère du Big Data, les astronomes pouvaient souvent vérifier les images à l'œil nu. Avec ce processus, connu sous le nom de “scanning”, un scientifique qualifié pouvait souvent faire la distinction entre une source réelle et un artefact. À mesure que de plus en plus d'images affluaient, des projets de science citoyenne ont vu le jour pour exploiter le pouvoir des membres enthousiastes du public dans la catégorisation des données. Mais avec le LSST à l'horizon, les astronomes ont désespérément besoin de meilleures méthodes pour classer les images.

                                                                                            Apporter l'apprentissage automatique

                                                                                            Fig. 1 – Un exemple visuel d'un problème de classification d'apprentissage automatique. Ici, les arbres sont triés selon deux caractéristiques : la taille des feuilles et le nombre de feuilles par rameau. L'ensemble d'entraînement (points ouverts) a des classifications connues (Espèces 1, 2 ou 3). Une fois l'ensemble d'apprentissage traité, l'algorithme peut générer des règles de classification (les lignes pointillées). Ensuite, de nouveaux arbres (points remplis) peuvent être classés en fonction de leurs caractéristiques. Image adaptée de http://nanotechweb.org/cws/article/lab/46619

                                                                                            Le papier d'aujourd'hui utilise une technique de calcul connue sous le nom d'apprentissage automatique pour résoudre ce problème. Plus précisément, ils utilisent une technique connue sous le nom de "classification d'apprentissage automatique supervisé". Le but de cette méthode est d'obtenir une classification d'un objet (ici, un artefact ou une source réelle) en fonction de fonctionnalités qui peut être quantifié sur l'objet. La méthode est “supervisée” car elle nécessite un ensemble d'entraînement: une série d'objets et leurs caractéristiques ainsi que des classifications connues. L'ensemble d'apprentissage est utilisé pour enseigner à l'algorithme comment classer les objets. Plutôt que d'avoir un scientifique qui élabore des règles qui définissent une classification, cette technique développe ces règles au fur et à mesure qu'il apprend. Une fois cet ensemble d'apprentissage traité, l'algorithme peut classer de nouveaux objets en fonction de leurs caractéristiques (voir Fig. 1).

                                                                                            Pour mieux comprendre l'apprentissage automatique supervisé, imaginez que vous essayez d'identifier des espèces d'arbres. Un ami bien informé vous dit d'étudier la couleur de l'écorce, la forme des feuilles et le nombre de feuilles sur une brindille. Ce sont les caractéristiques que vous utiliserez pour classer. Votre ami vous montre de nombreux arbres et vous indique le nom de leur espèce (c'est votre ensemble d'entraînement), et vous apprenez à identifier chaque espèce en fonction de ses caractéristiques. Avec un ensemble d'entraînement suffisamment grand, vous devriez être en mesure de classer le prochain arbre auquel vous arriverez, sans avoir besoin d'une classification de votre ami. Vous êtes maintenant prêt à appliquer une méthode d'apprentissage supervisé à de nouvelles données !

                                                                                            Utiliser l'apprentissage automatique pour améliorer les recherches transitoires

                                                                                            Fig. 2 – Les performances de l'algorithme autoScan. Le taux de fausse détection est la fréquence à laquelle un artefact est étiqueté comme une vraie source. Le taux de détection manquée (ou taux de faux négatifs) correspond à la fréquence à laquelle les sources réelles sont étiquetées comme des artefacts. Pour un niveau de tolérance donné (tau), les auteurs peuvent sélectionner dans quelle mesure ils sont disposés à accepter les faux positifs en échange d'un risque plus faible de manquer de vraies sources. Les auteurs ont adopté une tolérance de 0,5 pour leur algorithme final. Ce niveau identifie correctement les sources réelles 96% du temps, avec seulement un taux de 2,5% de faux positifs. La figure 7 de Goldstein et al. 2015.

                                                                                            Les auteurs de l'article d'aujourd'hui ont développé un algorithme d'apprentissage automatique appelé scan automatique, qui classe les objets transitoires possibles comme des artefacts ou des sources réelles. Ils appliquent cette technique aux données d'imagerie du Dark Energy Survey, ou DES. Le programme DES Supernova est conçu pour mesurer l'accélération de l'univers en imageant plus de 3000 supernovae et en obtenant des spectres pour chacune. Installé dans les montagnes des Andes chiliennes, DES s'apparente quelque peu à un exercice d'entraînement pour LSST, en termes de sortie de données.

                                                                                            le scan automatique L'algorithme utilise une longue liste de caractéristiques (telles que le flux de l'objet et sa forme) et un ensemble d'apprentissage de près de 900 000 sources et artefacts. Après le traitement de cet ensemble d'apprentissage, les auteurs ont testé les capacités de classification de l'algorithme par rapport à un autre ensemble de validation : plus d'objets avec des classifications connues qui n'ont pas été utilisés dans l'ensemble d'apprentissage. AutoScan a pu identifier correctement les sources réelles dans l'ensemble de validation 96% du temps, avec un taux de fausse détection (revendiquant un artefact comme source) de seulement 2,5% (voir Fig. 2).

                                                                                            Avec autoScan, les auteurs sont prêts à analyser de nouvelles données provenant du Dark Energy Survey. Ils peuvent grandement améliorer l'efficacité de détection des sources transitoires comme la supernova, en les distinguant facilement des artefacts instrumentaux. Mais de meilleures techniques, telles qu'un développement plus intelligent d'ensembles d'entraînement, continueront de réduire le taux de faux positifs.

                                                                                            Les algorithmes d'apprentissage automatique deviendront essentiels au succès des futures grandes enquêtes comme le LSST, où la puissance humaine à elle seule sera entièrement insuffisante pour gérer les données entrantes. La même chose peut être dite pour Gaia, TESS, la Zwicky Transient Facility et à peu près toute autre enquête astronomique à venir. Les projets de science citoyenne auront encore de nombreuses utilisations pratiques, et l'œil exercé d'un astronome professionnel sera toujours essentiel. Mais à l'ère du Big Astro, les ordinateurs continueront à faire de plus en plus partie intégrante de la gestion des opérations quotidiennes de recherche et de découverte.


                                                                                            Il est courant d'évaluer les modèles d'apprentissage automatique sur un ensemble de données à l'aide de la validation croisée k-fold.

                                                                                            La procédure de validation croisée à k plis divise un ensemble de données limité en k plis ne se chevauchant pas. Chacun des k plis a la possibilité d'être utilisé comme un ensemble de test retenu, tandis que tous les autres plis sont collectivement utilisés comme un jeu de données d'apprentissage. Un total de k modèles sont ajustés et évalués sur les k ensembles de tests de résistance et la performance moyenne est rapportée.

                                                                                            Pour en savoir plus sur la procédure de validation croisée k-fold, consultez le tutoriel :

                                                                                            La procédure de validation croisée k-fold peut être implémentée facilement à l'aide de la bibliothèque d'apprentissage automatique scikit-learn.

                                                                                            Tout d'abord, définissons un ensemble de données de classification synthétique que nous pouvons utiliser comme base de ce didacticiel.

                                                                                            La fonction make_classification() peut être utilisée pour créer un ensemble de données de classification binaire synthétique. Nous allons le configurer pour générer 100 échantillons chacun avec 20 caractéristiques d'entrée, dont 15 contribuent à la variable cible.

                                                                                            L'exemple ci-dessous crée et résume l'ensemble de données.

                                                                                            L'exécution de l'exemple crée l'ensemble de données et confirme qu'il contient 100 échantillons et 10 variables d'entrée.

                                                                                            La graine fixe pour le générateur de nombres pseudo-aléatoires garantit que nous obtenons les mêmes échantillons chaque fois que l'ensemble de données est généré.

                                                                                            Ensuite, nous pouvons évaluer un modèle sur cet ensemble de données en utilisant la validation croisée k-fold.

                                                                                            Nous évaluerons un modèle LogisticRegression et utiliserons la classe KFold pour effectuer la validation croisée, configurée pour mélanger l'ensemble de données et définir k=10, une valeur par défaut courante.

                                                                                            La fonction cross_val_score() sera utilisée pour effectuer l'évaluation, en prenant la configuration de l'ensemble de données et de la validation croisée et en renvoyant une liste de scores calculés pour chaque pli.

                                                                                            L'exemple complet est répertorié ci-dessous.

                                                                                            L'exécution de l'exemple crée l'ensemble de données, puis évalue un modèle de régression logistique à l'aide d'une validation croisée 10 fois. La précision moyenne de la classification sur l'ensemble de données est ensuite rapportée.

                                                                                            Noter: Vos résultats peuvent varier en raison de la nature stochastique de l'algorithme ou de la procédure d'évaluation, ou des différences de précision numérique. Envisagez d'exécuter l'exemple plusieurs fois et comparez le résultat moyen.

                                                                                            Dans ce cas, nous pouvons voir que le modèle a atteint une précision de classification estimée à environ 85,0%.

                                                                                            Maintenant que nous sommes familiarisés avec la validation croisée k-fold, voyons comment configurer la procédure.


                                                                                            6.849 : Algorithmes de pliage géométrique : liens, origami, polyèdres (automne 2010)

                                                                                            Côté design, nous verrons à quel point des plis simples suffisent pour plier n'importe quelle forme 2D, et avec des plis un peu plus généraux, nous pouvons plier n'importe quelle forme 3D même avec un motif bicolore en surface.

                                                                                            Côté pliabilité, nous verrons comment déterminer efficacement si un motif de pli avec des montagnes et des vallées indiqués peut être plié à plat dans deux cas intéressants : des morceaux de papier 1D (c'est-à-dire des plis parallèles dans une bande de papier) et 2D cartes rectangulaires. L03 15 septembre

                                                                                            [+] Motifs de plis à sommet unique : Caractérisations de motifs de plis pliables à plat et de motifs de vallées de montagne, combinatoire de ces derniers, la pliabilité locale à plat est facile.
                                                                                            Méthode arborescente de conception d'origami : Introduction, base uniaxiale, démo. [Remarques] [Diapositives] [Vidéo] --> Ce cours porte sur le comportement local du pliage à plat autour de chaque sommet d'un motif de pli. En d'autres termes, nous étudions chaque sommet individuellement, en caractérisant tous les motifs de plis à sommet unique et les motifs de vallée de montagne qui sont pliables à plat. Ensuite, nous examinons comment combiner plusieurs sommets dans un motif de pli « localement pliable ».

                                                                                            Nous commençons également à utiliser la méthode arborescente de la conception d'origami, développée par de nombreux concepteurs d'origami japonais au fil des ans, et transformée en un algorithme et un programme informatique TreeMaker par Robert Lang. Cette méthode a été la plus efficace dans la transformation de la conception complexe de l'origami, et nous en parlerons davantage lors de la prochaine conférence. L04 20 septembre

                                                                                            [+] Conception d'origami efficace : méthode Tree, TreeMaker, base uniaxiale, chemin actif, molécule d'oreille de lapin, molécule universelle, pliage de cube Margulis Napkin Problem, pliage en damier Origamizer, étanche, proxy de repli. [Remarques] [Diapositives] [Vidéo] --> Cette conférence porte sur la conception efficace de l'origami. Nous avons vu dans la leçon 2 comment plier quoi que ce soit de manière peu pratique. Nous allons maintenant voir comment plier plusieurs formes de manière pratique.

                                                                                            Tout d'abord, la méthode de l'arbre, dont j'ai présenté l'implémentation logicielle TreeMaker à la fin de la leçon 3. Je décrirai comment elle nous permet de plier une base d'origami en forme de bâton (arbre) optimale, bien que le calcul de cet optimum soit en fait NP-complet ( comme nous le verrons dans le cours 5). Cet algorithme est utilisé dans toute la conception d'origami complexe moderne. Je vais montrer quelques exemples de Robert Lang et de notre propre Jason Ku.

                                                                                            Deuxièmement, nous examinerons un cas simple et bien compris : le plus petit carré pour plier un cube.

                                                                                            Troisièmement, nous examinerons un problème classique sur lequel nous avons progressé récemment : plier un damier n & fois n à partir du plus petit carré bicolore.

                                                                                            Enfin, nous examinerons la méthode la plus récente et la plus générale, Origamizer, pour plier n'importe quel polyèdre de manière raisonnablement efficace. Ici, nous n'avons pas de garantie théorique intéressante sur l'optimalité, mais la méthode fonctionne bien dans la pratique, fonctionne toujours de manière prouvée et présente d'autres fonctionnalités intéressantes telles que l'étanchéité à l'eau. L05 22 septembre

                                                                                            [+] Modèles de charnières universelles : plis creux, pliage labyrinthe orthogonal polycubes.
                                                                                            Dureté NP : introduction, réductions pliabilité simple motif de pli pliabilité à plat emballage disque (pour la méthode de l'arbre). [Remarques] [Diapositives] [Vidéo] --> Cette conférence porte sur deux thèmes principaux :

                                                                                            Tout d'abord, poursuivant notre thème de la conférence 4 sur la conception efficace de l'origami, nous verrons comment des sous-ensembles d'un seul motif de charnière suffisent pour plier n'importe quelle forme orthogonale composée de cubes, alors que d'autres approches utilisent un ensemble de plis complètement différent pour chaque modèle d'origami. vous voulez. En général, nous pouvons plier n cubes à partir d'un carré de papier O ( n ) &fois O ( n ). Dans le cas particulier des &ldquoorthogonaux labyrinthes&rdquo, nous ne pouvons gaspiller presque pas de papier, avec le pliage seulement un petit facteur constant plus petit que le morceau de papier d'origine. Vous pouvez essayer cela vous-même.

                                                                                            • pliage d'un motif de pli donné via une séquence de plis simples
                                                                                            • pliage à plat d'un motif de pli donné (en utilisant n'importe quel état plié)
                                                                                            • conception optimale d'une base uniaxiale, même lorsque l'arbre n'est qu'une étoile.

                                                                                            [+] Conception artistique de l'origami : échantillonnage de la méthode de l'arbre de l'art de l'origami représentationnel et de son utilisation.
                                                                                            (conférence invitée par Jason Ku) [Diapositives] [Vidéo]--> Il s'agit d'une conférence invitée par Jason Ku, président d'OrigaMIT (le club d'origami du MIT), étudiant au doctorat en génie mécanique et éminent concepteur d'origami.

                                                                                            Sa conférence portera sur ses perspectives sur la conception artistique de l'origami. La conférence 4 a décrit l'algorithme de la méthode arborescente de la conception d'origami. Nous allons maintenant voir comment cette méthode s'applique dans des exemples réels.

                                                                                            La première moitié de la conférence présentera le côté artistique de l'origami figuratif. En origami, comme dans de nombreuses disciplines, la familiarité avec le canon du travail qui existe déjà peut être très utile pour comprendre les pistes de développement créatif futur. Ainsi, nous couvrirons les œuvres et les styles d'un échantillon des chemises papier les plus renommées au monde.

                                                                                            La seconde moitié de la conférence se concentrera sur la conception réelle de l'art de l'origami représentationnel. Nous passerons brièvement en revue la théorie des arbres, peserons le pour et le contre de cette méthode de conception et soulignerons les relations entre un arbre, un tassement cercle/rivière et le lieu d'un possible pli de charnière dans une base uniaxiale. Enfin, nous passerons par le processus de conception d'un modèle d'origami avec, puis sans, l'aide de TreeMaker. L07 28 septembre

                                                                                            [+] Pli et une coupe : histoire, méthode du squelette droit, méthode du disque-packing, plis simples, dimensions supérieures, aplatissement des polyèdres. [Remarques] [Diapositives] [Vidéo] --> Cette conférence porte sur mon premier travail en origami informatique : plier un morceau de papier à plat de sorte qu'une coupe droite complète crée un motif de coupes souhaité (et les formes polygonales résultantes). Le problème a une longue histoire (remontant aux années 1700) et des applications possibles au pliage des airbags via un problème appelé aplatissement. Nous verrons deux méthodes différentes pour ce problème, chacune avec des connexions à la méthode de l'arbre de conception d'origami : la première généralise la molécule universelle aux polygones non convexes, mais perd la capacité de contrôler l'arbre d'ombre la seconde utilise l'emballage de disque (mais pas de rivières ) et des molécules universelles pour les triangles et les quadrangles. Je parlerai aussi d'un tout nouveau résultat qui a commencé à partir de cette classe il y a trois ans : quelles formes peut-on faire uniquement avec des plis simples ? L08 4 octobre

                                                                                            [+] Mouvements de pliage : états pliés vs mouvements pliabilité universelle du papier polygonal.
                                                                                            Liens pour signer votre nom : graphiques vs liens vs configurations, espace de configuration théorème d'universalité de Kempe, preuve originale, bug, corrections, généralisations et renforcements. [Remarques] [Diapositives] [Vidéo] --> Cette conférence donne le coup d'envoi au début du pliage des liaisons. Nous sortirons de l'origami en pensant aux mouvements de pliage de morceaux de papier et prouverons qu'il est toujours possible d'atteindre n'importe quel état plié d'un morceau de papier polygonal. De combien de plis supplémentaires avons-nous besoin ? Cette question non résolue conduit à des problèmes dans le domaine de la liaison-repliement.

                                                                                            Ensuite, nous nous concentrerons sur le théorème d'universalité de Kempe : il existe un lien pour signer votre nom, ou plus mathématiquement, tracer n'importe quelle courbe polynomiale. Cette preuve présente un tas de gadgets sympas, en particulier pour ajouter des angles et multiplier (ou diviser) les angles par des facteurs constants. L09 6 octobre

                                                                                            [+] Théorie de la rigidité : Rigidité, rigidité générique, rigidité générique minimale, caractérisation de Henneberg, caractérisation de Laman, algorithme en temps polynomial, polyèdres convexes. [Remarques] [Diapositives] [Vidéo] --> Cette conférence porte sur la théorie de la rigidité, qui consiste à dire quand une liaison peut se plier. Ce domaine remonte à l'ingénierie mécanique des XVIIIe et XIXe siècles, avec des applications à l'ingénierie structurelle et à l'architecture (faire tenir des bâtiments et des ponts), à la biologie (comprendre quelles parties d'une protéine bougent encore après le repliement) et au repliement des liaisons (au-delà de &ldquo est-ce qu'il bouge du tout ?&rdquo, comme nous le verrons dans la prochaine leçon).

                                                                                            Nous aborderons deux théorèmes principaux caractérisant les graphes rigides &ldquogénériquement&rdquo en 2D. Le théorème de Henneberg, de 1911, donne une caractérisation agréable et directe, mais il est difficile de le transformer en algorithme. Le théorème de Laman, de 1970, est intuitivement plus difficile à travailler, mais se transforme en un algorithme rapide (en temps quadratique).

                                                                                            Malheureusement, tout cela est uniquement pour la 2D, et nous ne connaissons pas de bonnes caractérisations pour la rigidité générique en 3D. Je vais cependant décrire brièvement quelques théorèmes intéressants sur la rigidité des polyèdres convexes en 3D, qui expliquent en particulier pourquoi les dômes géodésiques de Buckminster Fuller tiennent debout. L10 13 octobre

                                                                                            [+] Théorie de la rigidité : Rigidité infinitésimale, matrice de rigidité.
                                                                                            Théorie de la tenségrité : tenségrités, contrainte d'équilibre, dualité, soulèvement polyédrique, théorème de Maxwell-Cremona.
                                                                                            Liens verrouillés : Théorème de la règle de Carpenter. [Remarques] [Diapositives] [Vidéo] --> Cette conférence poursuit notre visite à travers la théorie de la rigidité, en introduisant deux autres grandes idées : la rigidité infinitésimale et les tenségrités. La rigidité infinitésimale est un bon moyen de capturer le cas générique en utilisant l'algèbre linéaire, et elle se généralise bien (et est efficacement calculable) dans n'importe quelle dimension. Les tenségrités (un terme inventé par Buckminster Fuller) permettent d'ajouter des entretoises (qui empêchent la compression) et des câbles (qui empêchent l'expansion) en plus des barres (qui empêchent les deux, c'est ce à quoi nous avons surtout pensé). Les &ldquospider webs&rdquo sont un bon cas particulier de tenségrités, qui se rapportent à la conception algorithmique des pavages en origami.

                                                                                            Bien qu'ils ne soient pas évidemment liés, les outils de rigidité que nous construisons nous permettent de prouver l'existence de mouvements de pliage réels entre deux configurations de &ldquochain links&rdquo (dont les graphes sont des chemins ou des cycles) dont les bords ne sont pas autorisés à se croiser. Ce théorème de la règle de Carpenter (qui était essentiellement ma thèse de doctorat) lance notre étude de la compréhension du moment où les liens peuvent &ldquolock&rdquo. L11 18 octobre

                                                                                            [+] Liens verrouillés : algorithmes de dépliage de chaînes 2D, pseudotriangulation, pliage rigide en énergie d'arbres verrouillés en origami à un seul sommet, liens verrouillés infiniment, chaînes 3D verrouillées Règles 1 et 2, aiguilles à tricoter. [Remarques] [Diapositives] [Vidéo] --> Cette conférence porte sur les liens verrouillés. Poursuivant le théorème de la règle de Carpenter de la dernière conférence, qui dit que les chaînes 2D ne peuvent pas se verrouiller, nous verrons trois algorithmes différents pour plier les chaînes 2D. Chaque algorithme a différents niveaux d'expansion, de symétrie et d'efficacité, avec des applications à la planification de mouvement de bras de robot 2D. Nous verrons également une application d'une version sphérique du problème de la règle de charpentier au pliage rigide de l'origami à un seul sommet. Ensuite, nous visiterons le monde des arbres 2D verrouillés, qui a connu des progrès significatifs récemment. À cette fin, je décrirai la technologie étendue pour prouver que les liaisons 2D sont verrouillées. Enfin, nous examinerons brièvement les chaînes 3D verrouillées, qui se rapportent au repliement des protéines. L12 20 octobre

                                                                                            [+] Dissections articulées : chaînes verrouillées et déverrouillées de formes planes, chaînes ornées, ornements minces, mince implique non verrouillée, théorème de Kirszbaun, triangles verrouillés avec angle au sommet > 90° existence de dissections articulées, raffinement. [Remarques] [Diapositives] [Vidéo] --> Cette conférence porte sur des chaînes de polygones, ou d'autres formes 2D, reliées entre elles par des charnières en 2D. Ces structures sont classiquement appelées &ldquohinged dissections&rdquo. Du côté de la pliabilité, nous verrons des situations étonnamment générales, appelées & ldquoslender ornaments&rdquo, où ces chaînes ne peuvent pas se verrouiller, s'appuyant sur le théorème de la règle de charpentier et l'expansivité (Conférence 10). Nous verrons également quelques exemples qui se verrouillent, en s'appuyant sur notre théorie des liens infiniment verrouillés et les règles 1 et 2 (Leçon 11). Du côté de la conception, nous montrerons que nous pouvons réellement concevoir des dissections articulées qui se replient dans n'importe quelle collection finie de formes polygonales souhaitées, en utilisant des ornements minces pour garantir des mouvements pliables. L13 25 octobre

                                                                                            1. Tout polyèdre convexe a-t-il une arête qui se déplie ? C'est aussi le problème le plus ancien, implicite remontant à 1525.
                                                                                            2. Tout polyèdre (sans frontière) a-t-il un déroulement général ? C'est l'un de mes problèmes ouverts préférés.

                                                                                            [+] Dépliage de polyèdres : Dépliage de sommets, chemins de facettes, dépliage général de polyèdres orthogonaux, dépliage de grille, raffinement, tours Manhattan, orthopiles, orthotubes, orthoarbres.
                                                                                            Pliage de polyèdres : théorème de rigidité de Cauchy, l'unicité du pliage d'Alexandrov. [Remarques] [Diapositives] [Vidéo] --> Cette conférence poursuit le thème du dépliage des polyèdres et lance notre couverture du pliage des polygones en polyèdres.

                                                                                            Du côté du dépliage, nous couvrirons &ldquovertex unfolding&rdquo, qui est une variante du dépliage des bords un peu comme les dissections articulées. Nous allons montrer que ce type de dépliement existe, même pour des polyèdres non convexes, pourvu que chaque face soit un triangle. Ensuite, nous couvrirons les avancées récentes dans le développement général, pour les polyèdres orthogonaux.

                                                                                            Côté pliage, nous allons prouver le théorème de rigidité de Cauchy : les polyèdres convexes ont exactement une réalisation convexe (vue des faces comme rigides et des arêtes comme des charnières). Ensuite, nous montrerons comment étendre cela au théorème d'unicité d'Alexandrov : si vous collez la limite d'un polygone, vous pouvez créer au plus un polyèdre convexe. (La prochaine conférence, nous verrons comment en obtenir un.) L15 1er novembre

                                                                                            [+] Pliage de polyèdres : problème de décision, problème d'énumération, problème combinatoire, solution non convexe, métrique polyédrique convexe, collages d'Alexandrov, théorème d'Alexandrov, preuve constructive de Bobenko-Izmestiev, algorithme pseudopolynomial, polygones non encollables, division de périmètre, arbre de collage, courroies roulantes. [Remarques] [Diapositives] [Vidéo] --> Cette conférence plonge dans le problème du pliage de polygones en polyèdres. L'accent est mis ici sur le pliage des polyèdres convexes, bien qu'il y ait un bon résultat sur le cas non convexe de Burago & Zalgaler.

                                                                                            L'outil principal dans ce domaine s'appelle le théorème d'Alexandrov, de 1941, qui caractérise quand un collage de la frontière d'un polygone donnera un polyèdre convexe plus, comme nous l'avons vu la dernière leçon, ce résultat convexe est toujours unique. Nous allons esquisser une preuve de ce théorème ainsi que des algorithmes récents pour trouver le polyèdre convexe.


                                                                                            3 réponses 3

                                                                                            Il existe 2 types de méthodes de pliage utilisées Pli décalage et Pli limite .

                                                                                            Vous divisez la clé en parties dont la taille correspond à la taille de l'adresse requise. Les pièces sont simplement ajoutées pour obtenir l'adresse requise.

                                                                                            Clé : 123456789 et la taille de l'adresse requise est de 3 chiffres.

                                                                                            123+456+789 = 1368. Pour réduire la taille à 3, soit 1 soit 8 est supprimé et par conséquent la clé serait 368 ou 136 respectivement.

                                                                                            Plier la limite

                                                                                            Vous divisez à nouveau la clé en parties dont la taille correspond à la taille de l'adresse requise. Mais maintenant, vous appliquez également le pliage, à l'exception de la partie centrale, si elle est là.

                                                                                            Clé : 123456789 et la taille de l'adresse requise est de 3 chiffres

                                                                                            321 (pliage appliqué)+456+987 (pliage appliqué) = 1764(rejeter 1 ou 4)

                                                                                            Étant donné 424-124-9675, vous décidez où vous voulez le diviser en groupes. Par example:

                                                                                            tous les 3 chiffres à partir de la gauche : dièse = 424 + 124 + 967 + 5

                                                                                            tous les 3 chiffres en partant de la droite : dièse = 675 + 249 + 241 + 4

                                                                                            où les tirets sont : hash = 424 + 124 + 9675

                                                                                            C'est un moyen terriblement faible de hacher - très sujet aux collisions.

                                                                                            Suite aux réponses de Tony et Sumeet, j'ai fait quelques recherches supplémentaires sur le pliage des chiffres et j'ai décidé de mettre en œuvre la technique expliquée par Robert Lafore dans son livre Data Structures.

                                                                                            Par exemple, supposons que vous vouliez hacher des numéros de machine à 10 chiffres. Si la taille du tableau est de 1 000 , vous diviseriez le nombre à 10 chiffres en trois groupes de trois chiffres et un groupe d'un chiffre. Dans l'exemple en question, le numéro de machine est 424-124-9675 , vous devez donc calculer une valeur clé de 424 + 124 + 967 + 5 = 1520 . Vous pouvez utiliser l' opérateur % pour rogner ces sommes afin que l' index le plus élevé soit 999 . Dans ce cas, 1520 % 1000 = 520 .

                                                                                            Si la taille du tableau est de 100 , vous devrez diviser la clé à 10 chiffres en cinq nombres à deux chiffres : 42 + 41 + 24 + 96 + 75 = 278 et 278 % 100 = 78 .

                                                                                            Il est plus facile d'imaginer comment cela fonctionne lorsque la taille du tableau est un multiple de 10. Cependant, pour de meilleurs résultats, il doit s'agir d'un nombre premier.

                                                                                            Voici le code Java de la technique de pliage des chiffres que j'ai implémenté :

                                                                                            J'ai trouvé la méthode de création de groupe ici. Mais ça fait des groupes de droite à gauche. J'ai donc utilisé la méthode String#subString() pour créer des groupes de gauche à droite.


                                                                                            FFT en 2 dimensions

                                                                                            Ce qui suit décrit brièvement comment effectuer des transformations de Fourier en 2 dimensions. Le code source est donné à la fin et un exemple est présenté où un simple filtrage passe-bas est appliqué à une image. Le filtrage dans le domaine fréquentiel spatial est avantageux pour les mêmes raisons que le filtrage dans le domaine fréquentiel est utilisé dans l'analyse de séries temporelles, le filtrage est plus facile à appliquer et peut être nettement plus rapide.

                                                                                            On suppose que le lecteur est familiarisé avec les transformées de Fourier unidimensionnelles ainsi que les paires de transformées temps/fréquence clés.

                                                                                            Dans la situation la plus générale, une transformation à 2 dimensions prend un tableau complexe. L'application la plus courante est le traitement d'images où chaque valeur du tableau représente un pixel, donc la valeur réelle est la valeur du pixel et la valeur imaginaire est 0.

                                                                                            Les transformées de Fourier à 2 dimensions impliquent simplement un certain nombre de transformées de Fourier à 1 dimension. Plus précisément, une transformation en 2 dimensions est obtenue en transformant d'abord chaque ligne, en remplaçant chaque ligne par sa transformation, puis en transformant chaque colonne, en remplaçant chaque colonne par sa transformation. Ainsi, une transformation 2D d'une image 1K par 1K nécessite des transformations 2K 1D. Ceci découle directement de la définition de la transformée de Fourier d'une variable continue ou de la transformée de Fourier discrète d'un système discret.

                                                                                            Les paires de transformations qui sont généralement dérivées en 1 dimension peuvent également être dérivées pour la situation en 2 dimensions. Les paires à 2 dimensions peuvent souvent être dérivées simplement en considérant la procédure d'application de transformations aux lignes puis aux colonnes du tableau à 2 dimensions.


                                                                                            La fonction delta se transforme en un plan CC 2D


                                                                                            La ligne de fonctions delta se transforme en une ligne de fonctions delta


                                                                                            Impulsion carrée

                                                                                            Fonction sinc 2D

                                                                                            L'exemple ci-dessus a réorganisé les quadrants de manière à placer DC (freq = 0) au centre de l'image. L'organisation par défaut des quadrants de la plupart des routines FFT est comme ci-dessous

                                                                                            Exemple

                                                                                            Afin d'effectuer la FFT (Fast Fourier Transform) au lieu de la DFT (Discrete Fourier Transfer) beaucoup plus lente, l'image doit être transformée de sorte que la largeur et la hauteur soient une puissance entière de 2. Ceci peut être réalisé de deux manières, à l'échelle l'image à la puissance entière de 2 la plus proche ou le zéro pad à la puissance entière de 2 la plus proche. La deuxième option a été choisie ici pour faciliter les comparaisons avec l'original. L'image résultante est de 256 x 256 pixels.

                                                                                            Un traitement d'image peut maintenant être effectué (par exemple un filtrage) et l'image reconvertie dans le domaine spatial. Par exemple, le filtrage passe-bas consiste à réduire les composantes haute fréquence (celles radialement éloignées du centre de l'image ci-dessus). Deux exemples utilisant différentes fréquences de coupure sont illustrés ci-dessous.


                                                                                            Stratégies de modélisation intelligentes pour la prévision des séries chronologiques sur la qualité de l'air : une revue

                                                                                            Hui Liu, . Chao Chen , dans Applied Soft Computing , 2021

                                                                                            4 Méthode auxiliaire I : Optimisation métaheuristique

                                                                                            Bien que les modèles prédictifs simples et les méthodes de traitement des données puissent grandement améliorer les capacités des modèles intelligents, les performances de prévision peuvent être encore améliorées dans la structure et les hyperparamètres. Les algorithmes d'optimisation métaheuristique visent à optimiser davantage les données d'origine. L'ensemble du processus de données d'entrée est une sélection de caractéristiques typique, dans laquelle des algorithmes métaheuristiques sont utilisés pour générer des données d'entrée et les données seront utilisées comme échantillons d'apprentissage pour la prévision des résultats.

                                                                                            4.1 Algorithme heuristique et métaheuristique

                                                                                            Les algorithmes heuristiques sont une sorte d'algorithmes construits de manière intuitive ou empirique qui donnent une solution réalisable pour des problèmes spécifiques à résoudre. Les algorithmes métaheuristiques sont l'amélioration des algorithmes heuristiques, qui sont la combinaison d'algorithmes aléatoires et d'algorithmes de recherche locale en tant que stratégies heuristiques générales. De nombreux algorithmes métaheuristiques simulent les phénomènes biologiques ou physiques de la nature en structures mathématiques pour résoudre des problèmes [157] . Certains algorithmes métaheuristiques utilisés dans les modèles de prévision de la qualité de l'air sont illustrés à la figure 13 .

                                                                                            Les algorithmes heuristiques sont les méthodes qui dépendent du problème. Par conséquent, ils s'adaptent généralement au problème actuel et essaient de tirer pleinement parti de la particularité de ce problème. Cependant, ils tombent généralement dans un état optimal local et ne peuvent donc généralement pas obtenir une solution globalement optimale. Bien que les algorithmes métaheuristiques soient différents dans le mécanisme, ce sont des méthodes indépendantes du problème. Ils ne sont pas si gourmands qu'ils leur permettent d'explorer l'espace des solutions de manière plus approfondie et de répéter jusqu'à ce que le critère de convergence soit suffisamment bon pour obtenir les solutions optimales [158] . Il est encore nécessaire de faire quelques ajustements à ses paramètres internes en particulier les hyperparamètres, tels que le nombre d'itérations, le nombre de couches cachées, le nombre de neurones dans chaque couche, le taux d'apprentissage, etc. [86] .

                                                                                            L'algorithme génétique (AG) est une méthode pour rechercher des solutions optimales en simulant la sélection évolutive naturelle, visant tous les individus de la population. L'optimisation par essaim de particules (PSO) est également une méthode d'optimisation basée sur la population développée en simulant le comportement collectif des oiseaux pour obtenir la solution optimale [59,159] . Dans Réf. [160] , similaire à GA, l'algorithme d'évolution différentielle (DE) est utilisé pour la recherche globale d'optimisation dans les modèles hybrides. D'autres algorithmes métaheuristiques, tels que la recherche de coucou (CS) [62,161] , l'algorithme de chauve-souris (BA) [162] et l'optimiseur de loup gris (GWO) [90] , ont également été couramment utilisés pour améliorer les performances de prédiction. La combinaison d'algorithmes métaheuristiques peut encore améliorer les paramètres en fonction de la complexité des modèles hybrides, tels que l'algorithme d'optimisation des essaims de particules et de recherche gravitationnelle (PSOGSA) et l'algorithme de recherche de coucou modifié et d'évolution différentielle (MCSDE).