# Complex systems and AI

> Everyone in a complex system has a slightly different interpretation.


## Posts

- [Théories et Algorithmes](https://complex-systems-ai.com/2020/04/03/theories-et-algorithmes/): Théories Page d’accueil TensorFlow Théories et Algorithmes Les théories et algorithmes de l’intelligence artificielle, de l’apprentissage machine et des bases mathématiques. Cliquez sur une section pour afficher toutes les théories liées. I. Maths Logique mathématique Recherche opérationnelle : Optimisation combinatoire Optimisation linéaire Problème de planification Problème de recherche de chemin Problème de flot II. Analyse systémique Aide à la décision Algorithmique Analyse logicielle Problèmes industriels et réduction polynomiale Théorie des graphes Théorie des jeux Théorie des langages Processus stochastique III. Analyse des données Analyse des données (dimensions et classifications) Analyse descriptive Inférence statistique Corrélation et régressions Data visualization IV. Apprentissage automatique Apprentissage […]
- [Contacter Guillaume GUERARD](https://complex-systems-ai.com/2016/01/20/le-createur-du-modele-guerard-guillaume/): Vous pouvez aussi contacter Guillaume GUERARD via les Réseaux sociaux de Guillaume GUERARD  Liens : LinkedIn : https://www.linkedin.com/in/guillaumeguerardsmartgrid ResearchGate : https://www.researchgate.net/profile/Guillaume_Guerard Académia : https://esilv.academia.edu/GuillaumeGu%C3%A9rard Facebook : https://www.facebook.com/smartgridmodelling/ Twitter : https://twitter.com/SmartGrid_Model

## Pages

- [Déterminisation e-AFI vers AFD](https://complex-systems-ai.com/theorie-des-langages/determinisation-e-afi-vers-afd/): Théorie des langages Page d’accueil Wiki Difficulté Moyen 50% e-AFI vers AFD Nous voulons maintenant montrer que le langage reconnu par un automate avec transitions vides peut également l’être par un automate non-déterministe sans transitions vides (déterminisation e-AFI vers AFD). Cette opération va nécessiter l’addition de nouvelles transitions dans l’automate. Tout langage reconnu par un AFN avec ε–transitions peut être reconnu par un AFN (sans ε–transitions) ayant le même nombre d’états. Construction de l’AFN équivalent à un automate avec ε–transitions, en prolongeant δ en δ1 (la fermeture transitive est tous les états qui peuvent être atteint par un état par une […]
- [Automate avec transition vide](https://complex-systems-ai.com/theorie-des-langages/automate-avec-transition-vide/): Théorie des langages Page d’accueil Wiki Difficulté Facile 25% Automate avec transition vide On a l’habitude de dessiner un automate avec transition vide, en figurant les états par des cercles, en indiquant l’état initial par une flèche entrante, les états acceptants par un double cercle ou une flèche sortante, et la transition de l’état q à l’état q’ en lisant la lettre α par une flèche allant de q vers q’ et étiquetée par α. Un automate fini A avec epsilon transition (ou automate avec transition vide) est un triplet (Vt, Q, T) où Vt est le vocabulaire de l’automate ; […]
- [Automate fini non-déterministe](https://complex-systems-ai.com/theorie-des-langages/automate-fini-non-deterministe/): Théorie des langages Page d’accueil Wiki Difficulté Facile 25% Automate fini non-déterministe On a l’habitude de dessiner un automate fini non-déterministe, en figurant les états par des cercles, en indiquant l’état initial par une flèche entrante, les états acceptants par un double cercle ou une flèche sortante, et la transition de l’état q à l’état q’ en lisant la lettre α par une flèche allant de q vers q’ et étiquetée par α. Un automate fini non-déterministe A est un triplet (Vt, Q, T) où Vt est le vocabulaire de l’automate ; Q est l’ensemble fini des états de l’automate ; […]
- [Déterminisation AFI vers AFD](https://complex-systems-ai.com/theorie-des-langages/determinisation-afi-vers-afd/): Théorie des langages Page d’accueil Wiki DIfficulté Facile 25% AFI vers AFD Le théorème de Rabin-Scott dit que tout langage reconnu par un automate fini indéterministe peut être reconnu par un automate fini déterministe (déterminisation AFI vers AFD). Il est donc possible de représenter un automate indéterministe par un automate déterministe, ce processus s’appelle la déterminisation. Considérons par exemple l’automate fini non-déterministe (K, T, M, I, F) suivant :K = {S1, S2, S3, S4}T = {a, b, c}M = {(S1, a, S1),(S1, a, S3),(S2, b, S2),(S2, b, S3),(S3, c, S3),(S3, c, S4)}I = {S1, S2}F = {S4}correspondant au graphe suivant : […]
- [Automate fini déterministe](https://complex-systems-ai.com/theorie-des-langages/automate-fini-deterministe/): Théorie des langages Page d’accueil Wiki Difficulté Facile 25% Automate fini déterministe On a l’habitude de dessiner un automate fini déterministe, en figurant les états par des cercles, en indiquant l’état initial par une flèche entrante, les états acceptants par un double cercle ou une flèche sortante, et la transition de l’état q à l’état q’ en lisant la lettre α par une flèche allant de q vers q’ et étiquetée par α. Un automate fini déterministe A est un triplet (Vt, Q, T) où Vt est le vocabulaire de l’automate ; Q est l’ensemble fini des états de l’automate ; […]
- [Langages réguliers et expressions régulières](https://complex-systems-ai.com/theorie-des-langages/langages-reguliers-et-expressions-regulieres/): Théorie des langages Page d’accueil Wiiki Difficulté Facile 25% Langages réguliers et expressions régulières Il existe deux types d’expressions régulières. On rappelle qu’une grammaire G1 = (T, N, S, R) est une expression régulière à droite si les règles de R sont de la forme : A → aB ou A → a avec A, B ∈ N et a ∈ T. On rappelle qu’une grammaire G2 = (T, N, S, R) est une expression régulière à gauche si les règles de R sont de la forme : A → Ba ou A → a avec A, B ∈ N et […]
- [Types de grammaires](https://complex-systems-ai.com/theorie-des-langages/types-de-grammaires/): Théorie des langages Page d’accueil Wiki Difficulté Difficile 80% Grammaires En introduisant des critères plus ou moins restrictifs sur la forme des règles de grammaire, on obtient des classes de grammaires hiérarchisées (des types de grammaires), ordonnées par inclusion. La classification des grammaires, définie en 1957 par Noam Chomsky,  distingue quatre classes. Classification de Chomsky Type 0 : pas de restriction sur les règles. Type 1 : grammaires sensibles au contexte ou contextuelles. Les règles de R sont de la forme : uAv → uwv avec A ∈ N, u, v ∈ (N ∪ T)∗ et w ∈ (N ∪ T)+ Autrement […]
- [ILV - Promo 2018 - SMART CITY&ENERGY](https://complex-systems-ai.com/algorithmique/ilv-promo-2018-smart-cityenergy/): Cours en version PDF et exemples. Introduction au multi-agent et réflexion sur la smart house Introduction à la modélisation et écriture des agents Exemple d’un agent réflexe simple Exemple d’un agent apprenant « simplifié » Définition de la maison intelligente et rapport final
- [M1 NE Second Half 2016](https://complex-systems-ai.com/programmation-lineaire/m1-ne-second-half-2016/): lecture1: simplex method, primal and dual, degeneracy Practice1_1:  shadow cost and example Practice1_2: complementary slackness theorem and example Tutorial1: simplex method Tutorial1-correction LPP graphical method Video Solving min problem with dual Video  § in this course, we use CS and strong duality to find a primal solution § Using CS to find a specific solution Video lecture2: transportation problem, north west corn, minimum matrix, vogel’s corner, Stepping stone and special cases Practice2_1: degeneracy Practice2_2: modified distribution method Practice2_3: network flow model Tutorial2: transportation problems Tutorial2-correction Linear programming system of a transportation problem Video How to solve Transportation problem with Excel Video […]
- [M1 NE First Half 2016](https://complex-systems-ai.com/theorie-des-graphes/m1-ne-first-half-2016/): lecture0: Introduction to decision making, design, implementation, complexity lecture1: Graph theory, Eulerian, Hamiltonian, Spanning tree & Graph coloring Practice1_1: Basic examples on graph theory Practice1_2: Minimal spanning tree (Prim) Practice1_3: Minimal Spanning tree (Kruskal) Practice1_4: graph coloring, Sudoku Tutorial1: Modelling and basics Tutorial1-solutions Prim’s Algorithm Video Kruskal’s Algorithm Video lecture2: Paradigm, Divide&Conquer, Dynamic programming Practice2_1: Divide&Conquer Binary search algorithm Practice2_2: Dynamic programming, the coin changing problem (simple and all combinations) Tutorial2: Paradigm Tutorial2-solutions lecture3: Shortest path problem, Dijkstra, DAG, Ford-Bellman, Floyd-Warshall Practice3_1: Step by step Dijkstra’s algorithm Practice3_2: Step by step Ford-Bellman’s algorithm Practice3_3: Step by step transitive closure and Floyd-Warshall’s […]
- [Recherche dispersée](https://complex-systems-ai.com/optimisation-combinatoire/recherche-dispersee/): Algorithmes stochastiques Page d’accueil Wiki Recherche dispersée La recherche dispersée (SS) est une méthode d’évolution qui a été proposée par (Glover et Laguna 1997). Elle a été proposée dans le cadre de la résolution des problèmes combinatoire. Cette métaheuristique se distingue des algorithmes évolutionnistes classiques par l’utilisation d’une procédure de recherche locale et par la généralisation de l’opérateur de croisement. Tout comme les algorithmes génétiques, elle est basée sur une population de solutions qui évolue dans le temps à l’aide à la fois d’un opérateur de sélection, de la combinaison linéaire de solutions de la population pour créer une nouvelle solution […]
- [Optimisation combinatoire 101](https://complex-systems-ai.com/optimisation-combinatoire/): Théories Page d’accueil Wiki I. Méthodes exactes (optimisation combinatoire) Cutting-plane Branch & bound Branch & cut Programmation dynamique Programmation par contraintes Programmation par contraintes, Méthodes de résolution Génération de colonnes Branch and Price II. Critères d’exactitude Théorème du No-Free-Lunch Evaluation des heuristiques III. Heuristiques et métaheuristiques Algorithmes stochastiques Algorithmes d’évolution Algorithmes physiques Algorithmes probabilistes Algorithmes d’essaim Algorithmes immunitaires Algorithmes neuronaux IV. Optimisation non linéaire sans contraintes Golden-section search Interpolation methods Line search Nelder–Mead method Successive parabolic interpolation Trust region Wolfe conditions Berndt–Hall–Hall–Hausman Broyden–Fletcher–Goldfarb–Shanno and L-BFGS Davidon–Fletcher–Powell Symmetric rank-one (SR1) Conjugate gradient Gauss–Newton Gradient Mirror Levenberg–Marquardt Powell’s dog leg method Truncated Newton Newton’s method […]
- [Programmation par contraintes](https://complex-systems-ai.com/optimisation-combinatoire/programmation-par-contraintes-2/): Optimisation combinatoire Page d’accueil Wiki Programmation par contraintes La programmation par contraintes permet de résoudre des problèmes décisionnels. Un problème d’optimisation se résout successivement après plusieurs problèmes de décision. Par exemple pour déterminer un plus court chemin, nous chercherons a trouver un chemin de moins de 100 (possible), puis moins de 50 (impossible), puis moins de 75, etc. jusqu’à trouver la solution optimale. La PPC a un champ d’action plus large que les méthodes exactes ou les méta-heuristiques. Définition La PPC résout un problème de satisfaction de contraintes (CSP). Ce dernier est défini par un triplet <X,D,C> avec X l’ensemble de […]
- [Théorie des langages 101](https://complex-systems-ai.com/theorie-des-langages/): Théories Page d’accueil Wiki I. Langages, grammaires et automates (théorie des langages) Types de grammaires Langages réguliers et expressions régulières Automate fini déterministe Automate fini indéterministe Automate fini indéterministe à epsilon transition Automate à pile et grammaire hors contexte II. Etude des automates Automate de Thompson Automate de Glushkov Optimisation de Brüggemann-Klein Optimisation de Chang-Paige Automate d’Antimirov Lemme d’Arden III. Calcul sur les automates Calcul d’expression régulière par McNaughton et Yamada Calcul d’expression régulière par Brzozowski et McCluskey Calcul d’expression régulière par Conway Déterminisation AFI vers AFD Déterminisation e-AFI vers AFD Minimisation d’un automate déterministe Union, intersection et complémentaire IV. Analyseur […]
- [Théorie des jeux 101](https://complex-systems-ai.com/theorie-des-jeux/): Théories Page d’accueil Wiki I. Bases de la théorie des jeux Congestion game Cooperative game Determinacy Escalation of commitment Extensive-form game First-player and second-player win Game complexity Game description language Graphical game Hierarchy of beliefs Information set Normal-form game Preference Sequential game Simultaneous game Simultaneous action selection Solved game Succinct game II. Equilibres et solutions Nash equilibrium Subgame perfection Mertens-stable equilibrium Bayesian Nash equilibrium Perfect Bayesian equilibrium Trembling hand Proper equilibrium Epsilon-equilibrium Correlated equilibrium Sequential equilibrium Quasi-perfect equilibrium Evolutionarily stable strategy Risk dominance Core Shapley value Pareto efficiency Gibbs equilibrium Quantal response equilibrium Self-confirming equilibrium Strong Nash equilibrium Markov perfect equilibrium […]
- [Processus de Markov 101](https://complex-systems-ai.com/processus-de-markov/): Théories Page d’accueil Wiki I. Généralité sur processus de Markov Marche aléatoire Martingale Mouvement brownien II. Ordre 1 temps discret Chaines de Markov en temps discret Récurrence et transcience Loi invariante et comportement asymptotique Temps d’atteinte d’un état Probabilité d’absorption d’un état III. Ordre 1 temps continu Chaines de Markov en temps continu Régime permanent Processus de Poisson Files d’attente (généralisation) File M/M/1 IV. Automate Stochastique et Hidden Markov Model Rappel Stochastique et Automate Hidden Markov Model Viterbi Backward-Forward Baum-Welch Probabiliste finite automaton Transformation HMM vers PFA Algorithme de Merge & Fold Merge & Fold avec mot interdit Inférence grammaticale Processus […]
- [Diagramme de temps](https://complex-systems-ai.com/analyse-logicielle/diagramme-de-temps/): Analyse logicielle Page d’accueil Wiki Diagramme de temps Le diagramme de temps ou Courbe à 45° est un outil de suivi d’avancement (délais et décalages) utilisée en gestion de projet. Elle informe à tout moment sur le degré de respect des jalons du projet. Le diagramme de temps est un graphique possédant deux axes : l’axe des abscisses correspond aux dates de mise à jour des jalons, et l’axe des ordonnées aux dates prévisionnelles des jalons. Chaque point porté sur le graphique représente la date prévue de réalisation d’un jalon (Y) telle qu’elle était estimée à un moment donné du projet […]
- [Diagramme de paquetages](https://complex-systems-ai.com/analyse-logicielle/diagramme-de-paquetages/): Analyse logicielle Page d’accueil Wiki Diagramme de paquetages Le diagramme de paquetages est un diagramme structurel (statique) d’UML qui représente les paquetages (ou espaces de noms) composant un système, ainsi que les relations qui lient ces différents paquetages. Lorsque nous sommes en présence d’un système de grande taille, il peut être intéressant de le décomposer en plusieurs parties (appelées paquetage). Un paquetage est donc un regroupement de différents éléments d’un système (regroupement de classes, diagrammes, fonctions, interfaces…). Cela permet de clarifier le modèle en l’organisant. Il est représenté par un dossier avec son nom à l’intérieur. Les paquetages peuvent s’imbriquer (décomposition […]
- [Diagramme de communication](https://complex-systems-ai.com/analyse-logicielle/diagramme-de-communication/): Analyse logicielle Page d’accueil Wiki Diagramme de communication Le diagramme de communication est similaire au diagramme de temps. La différence entre ces deux diagrammes est que le premier ne possède pas de ligne de vie. Le diagramme place les objets (les participants) et les interactions entre eux. Cela permet de visionner le comportement collectif d’objets en vue de réaliser une opération. Le diagramme de communication représente les collaborations (collection d’objets) : les relations, les fonctionnalité et les communications. On utilise le diagramme de communication lorsqu’on débute un projet, cela permet de clarifier le domaine d’étude, de cadrer le projet. Il est […]
- [Analyse logicielle 101](https://complex-systems-ai.com/analyse-logicielle/): Théories Page d’accueil Wiki I. UML – Analyse logicielle Algèbre relationnel Vue Logique Diagramme de classes Diagramme d’objets Diagramme d’état-transition Vue des processus Diagramme de séquence Diagramme de communication Diagramme d’activité Diagramme d’interaction Diagramme de temps Vue de développement Diagramme de composants Diagramme de paquetages Vue physique Diagramme de déploiement Vue cas d’utilisation Diagramme de cas d’utilisation II. SysML Contenu de va-et-vient III. Linked Data Contenu de va-et-vient IV. AUML Contenu de va-et-vient Analyse logicielle L’objectif principale de l’analyse logicielle est de maitriser la complexité. La modélisation est une abstraction de la réalité pour mieux comprendre le système à réaliser/ réalisé. […]
- [Diagramme de cas d'utilisation](https://complex-systems-ai.com/analyse-logicielle/diagramme-de-cas-dutilisation/): Analyse logicielle Page d’accueil Wiki Diagramme de cas d’utilisation La première question à se poser est : « A quoi va servir le logiciel ? ». Le diagramme de cas d’utilisation. Le diagramme de cas d’utilisation comprend des acteurs et des cas d’utilisation. Il est important de fournir avec un diagramme d’utilisation une description détaillée si possible incluant un scénario nominal (enchainement typiques) et des enchainements alternatifs sur les cas particuliers. Acteur Les premiers sont représentés par des bonhommes. Un acteur est une entité extérieure au système modélisé et qui interagit directement avec lui. Les acteurs sont les utilisateurs du système : des […]
- [Essaim de particules](https://complex-systems-ai.com/algorithmes-dessaims/essaim-de-particules/): Algorithmes d’essaims Page d’accueil Wiki Optimisation par Essaim de Particules L’Optimisation par Essaim de Particules (OEP, ou PSO en anglais) a été proposée par Kennedy et Eberhart. Cette méthode est inspirée du comportement social des animaux évoluant en essaim. Au départ, ils cherchaient à simuler la capacité des oiseaux à voler de façon synchrone et leur aptitude à changer brusquement de direction tout en restant en une formation optimale. Les particules sont les individus et elles se déplacent dans l’hyperespace de recherche en se basant sur des informations limitées : Chaque particule est dotée d’une mémoire qui lui permet de mémoriser […]
- [Génération de colonnes](https://complex-systems-ai.com/optimisation-combinatoire/generation-de-colonnes/): Optimisation combinatoire Page d’accueil Wiki Génération de colonnes Lorsqu’un programme linéaire possède beaucoup de variables, il n’est pas envisageable de le résoudre par un simplexe. La génération de colonnes permet de générer les variables utiles au fur et à mesure jusqu’à obtenir une solution optimale. L’objectif de cette méthode est de résoudre un problème réduit avec un ensemble limité de variables. Le problème initial d’une génération de colonnes est appelé problème maître, et le problème réduit est appelé problème restreint. Le problème restreint d’une génération de colonnes est plus simple à résoudre, mais si l’ensemble de ses variables ne contient pas […]
- [Cutting-Plane](https://complex-systems-ai.com/optimisation-combinatoire/cutting-plane/): Optimisation combinatoire Page d’accueil Wiki Méthode de coupes planes (cutting-plane) La méthode de coupes planes (cutting-plane) a été développée par Schrijver, elle est destinée à résoudre des problèmes d’optimisation combinatoire (POC) qui se formulent sous la forme d’un programme linéaire (PL) : Dans le cas, où le POC est de grande taille pour le représenter explicitement en mémoire ou pour qu’il tient dans un solveur de programmation linéaire, on utilise une technique qui consiste à enlever une partie de ces contraintes et de résoudre le problème relaxé (POCR). La solution optimale de (PL) est contenue dans l’ensemble de solutions réalisables de […]
- [Diagramme de séquence](https://complex-systems-ai.com/analyse-logicielle/diagramme-de-sequence/): Analyse logicielle Page d’accueil Wiki Diagramme de séquence Le diagramme de séquence est la représentation graphique des interactions entre les acteurs et le système selon un ordre chronologique dans la formulation Unified Modeling Language : Les diagrammes de séquences sont des diagrammes d’interaction comme les diagrammes de collaboration. Ils sont adaptés à la modélisation des aspects dynamiques des systèmes temps réels et des scénarios complexes mettant en œuvre peu d’objets. Une interaction se traduit par un envoi de message entre objets. Le diagramme de séquence permet de faire apparaître les objets intervenant dans l’interaction; la description de l’interaction et les interactions […]
- [Diagramme de classe](https://complex-systems-ai.com/analyse-logicielle/diagramme-de-classe/): Analyse logicielle Page d’accueil Wiki Diagramme de classe Le diagramme de classe est un schéma utilisé en génie logiciel pour présenter les classes et les interfaces des systèmes ainsi que les différentes relations entre celles-ci. Une classe décrit les responsabilités, le comportement et le type d’un ensemble d’objets. Les éléments de cet ensemble sont les instances de la classe. Une classe est un ensemble de fonctions et de données (attributs) qui sont liées ensemble par un champ sémantique. Les classes sont utilisées dans la programmation orientée objet. Elles permettent de modéliser un programme et ainsi de découper une tâche complexe en […]
- [Problèmes industriels et réduction polynomiale 101](https://complex-systems-ai.com/problemes-industriels-et-reduction-polynomiale/): Théories Page d’accueil Wiki I. Réduction et présentation des 21 problèmes de Karp Satisfiability Clique Set packing Vertex cover Set covering Feedback arc set Feedback node set Directed hamiltonian circuit Undirected hamiltonien circuit 0-1 interger programming 3-SAT Chromatic number Clique cover Exact cover Matching 3D Steiner tree Hitting set Knapsack Job sequencing Partition Max-cut Réduction polynomiale Les problèmes de la recherche opérationnelle, et plus généralement de l’aide à la décision sont souvent Np-complet, c’est-à-dire que l’on ne connaît pas d’algorithmes permettant de trouver une solution optimale en temps polynomial, mais on sait obtenir une solution réalisable en temps polynomiale (par réduction […]
- [Cycle-canceling algorithme](https://complex-systems-ai.com/probleme-de-flot-maximum/cycle-canceling-algorithm/): Problème de flot maximum Page d’accueil Wiki Cycle-canceling algorithme Le cycle-canceling algorithme commence par une résolution de flot maximum. Puis, de façon itérative, l’algorithme cherche un cycle avec un coût négatif (coût négatif si l’arête est prise en sens inverse du flot) et augmente le flot sur ce cycle. Lorsqu’il n’y a plus de cycle négatif, l’algorithme se termine. Exemple : Construisons le graphe d’écart et cherchons un cycle négatif : Le cycle 4-2-3-4 a un cout de -3 + 1 + 1 = -1, on peut le saturer avec un flot de 2. De même avec le cycle 4-2-1-3-4 avec […]
- [Algorithme Out-of-Kilter](https://complex-systems-ai.com/probleme-de-flot-maximum/algorithme-out-of-kilter/): Problème de flot maximum Page d’accueil Wiki Algorithme out-of-kilter Aussi appelé algorithme de Fulkerson-Ford (à ne pas confondre avec l’algorithme de flot maximum), l’algorithme out-of-kilter permet de calculer un flot maximal à cout minimal avec des bornes min et max sur les arêtes. Nous dirons qu’une arête est In-Kilter si elle satisfait les écarts complémentaires, sinon nous dirons qu’elle est Out-of-Kilter (kilter signifie « en bon état »). La suite des explications ne sera pas traduit pour des soucis de compréhension de la logique sous-jacente au sens de « kilter ». Theorem: A feasible solution x* is an optimal solution of the MCF problem if and […]
- [Programmation logique](https://complex-systems-ai.com/algorithmique/programmation-logique/): Algorithmique Page d’accueil Wiki Programmation logique La programmation logique consiste en la déclaration d’une série de faits et de règles de déduction. L’exécution d’un programme consiste à prouver un théorème. Le programme répond si le théorème peut être prouvé ou non à partir des déclarations faites au préalable. La programmation logique est différente de la programmation procédurale (C, JAVA, etc), les calculs se font sous forme de preuves logiques. On parle de programmation déclarative : le programme décrit une situation correspondant à un problème à résoudre. La programmation déclarative n’est pas incompatible avec la structuration objet. Les formules exprimées en Prolog […]
- [Problème de flot maximum 101](https://complex-systems-ai.com/probleme-de-flot-maximum/): Théories Page d’accueil Wiki I. Flot maximum Network simplex – voir Simplexe Algorithme de Ford-Fulkerson Algorithme d’Edmonds-Karp Algorithme de Dinic MPM Push-relabel algorithm KRT Binary blocking flow algorithm Orlin II. Flot maximum à cout minimum Network simplex – voir Simplexe Cycle-canceling Algorithme de Busacker & Gowen Algorithme Out-of-kilter III. Solveurs Résoudre le problème de flot maximum avec Excel Flot maximum Le flot maximum de modéliser une très large classe de problèmes. Leur interprétation correspond à la circulation de flux physiques sur un réseau : distribution électrique, réseau d’adduction, acheminement de paquets sur Internet, etc. Il s’agit d’acheminer la plus grande quantité […]
- [Algorithmique 101](https://complex-systems-ai.com/algorithmique/): Théories Page d’accueil Wiki I. Écriture et modélisation d’un algorithme Pseudo-langage et logigramme Terminaison et correction Complexité en temps Approximation algorithm Analysis: Adversary model Algorithmic efficiency Amortized analysis Instruction path length Master theorem Output-sensitive algorithm Polynomial delay Potential method Probabilistic analysis of algorithms II. Paradigmes et stratégies de programmation Imperative Programmation orientée objet Procedural programming  Declarative Programmation fonctionnelle Programmation logique Mathematical programming Reactive programming  Programmation structurée Symbolic programming III. Paradigmes algorithmiques Programmation récursive Programmation dynamique Diviser pour régner et dichotomie Méthode naïve – algorithme glouton – force brute Backtracking Branch and bound Prune and search Kernelization Iterative compression Sweep line algorithms […]
- [Colonie de fourmis](https://complex-systems-ai.com/algorithmes-dessaims/colonie-de-fourmis/): Algorithmes d’essaims Page d’accueil Wiki Colonie de fourmis Les algorithmes à base de colonie de fourmis permettent de résoudre des problèmes statiques et offrent un haut degré de flexibilité et de robustesse dans des environnements dynamiques. La colonie s’adapte aux brusques changements d’environnement et continue de fonctionner lorsque certains individus échouent à accomplir leur tâche. La colonie de fourmis décrit des agents ayant un comportements collectifs auto-organisés.Il y a émergence de structures au niveau collectif à partir d’interactions simples basé sur le principe de phéromones laissées par les agents. La principe de colonie de fourmis est simple. Les fourmis sont capables […]
- [Pseudo-langage et logigramme](https://complex-systems-ai.com/algorithmique/pseudo-langage-et-logigramme/): Algorithmique Page d’accueil Wiki Pseudo-langage et logigramme Avant d’écrire un algorithme dans un langage de programmation, il est d’abord décrit dans un langage de plus haut niveau appelé le pseudo-langage. Il s’agit d’un jeu limité d’instructions permettant de décrire le déroulement de l’algorithme de tel manière que toute personne puisse en comprendre le fonctionnement. Le pseudo-langage est usuellement écrit en anglais, mais rien n’empêche de le faire dans une autre langue. Écriture d’un algorithme Tout langage de programmation, pseudo-langage inclut, est composé de variables et d’instructions. Les variables stockent l’information et décrient la manière permettant d’accéder à la mémoire de l’ordinateur. […]
- [Terminaison et Correction](https://complex-systems-ai.com/algorithmique/terminaison-et-correction/): Algorithmique Page d’accueil Wiki Terminaison et correction Lorsque l’on crée un algorithme, il faut tenir compte des trois critères suivant : la terminaison, la correction et la complexité. La terminaison garantit que l’algorithme se termine au bout d’un certain nombre d’opérations élémentaires. La correction garantit que l’algorithme donne le résultat attendu lorsqu’il se termine. Exemple Un être humain et un chien ne vieillissent pas de la même manière. Pour déterminer l’équivalent humain de l’âge d’un chien de moins de 15kg, on utilise le tableau ci-dessous, où x représente l’âge réel de l’animal (en années), et y l’équivalent humain en terme de […]
- [Complexité en temps](https://complex-systems-ai.com/algorithmique/complexite-en-temps/): Algorithmique Page d’accueil Wiki Complexité en temps La complexité en temps représente de façon asymptotique le temps que met un algorithme à trouver une solution. Soit un problème P et M une méthode pour résoudre ce problème. L’algorithme est une description avec des structures de contrôle et de données permettant d’écrire la méthode M dans un langage reconnaissable par tout individu ou machine. Pour rappel, les structures de contrôle sont : une séquence, un embranchement (ou sélection), une boucle (ou itération). Les structures de données sont : des constantes, des variables, des tableaux (ou espace de stockage ordonné), des structures récursives […]
- [GRASP](https://complex-systems-ai.com/algorithmes-stochastiques/grasp/): Algorithmes stochastiques Page d’accueil Wiki Greedy Randomized Adaptive Search Procedure (GRASP) L’algorithme Greedy Randomized Adaptive Search Procedure (GRASP) est une métaheuristique introduite par Feo et Resende en 1989. Son fonctionnement se base sur la répétition de deux phases : une construction gloutonne suivit par une recherche locale. La caractéristique de la méthode GRASP est sa phase de construction d’une solution. Pour ce faire, l’algorithme maintient à jour une liste de fragments de solutions possibles (RCL, restricted candidate list). La solution se construit pas à pas en allant choisir des éléments (dans notre cas, ce sont les gains de combiner de mailles […]
- [Algorithme de Busacker Gowen](https://complex-systems-ai.com/probleme-de-flot-maximum/algorithme-de-busacker-gowen/): Problème de flot maximum Page d’accueil Wiki Algorithme de Busacker Gowen Aussi connu sous le nom d’algorithme de Roy, l’algorithme de Busacker Gowen permet de calculer un flot maximum à coût minimal. Le principe est simple, la recherche du chemin augmentant se fait par un calcul de plus court chemin (chemin de plus petit coût). Les critères d’optimalité sont équivalant au problème de flot. L’algorithme se résume ainsi : Construire un graphe de pcc (plus court chemin) à partir du graphe d’écart du flot arc identique au graphe d’écart prix correspondant à l’arc d’origine si dans le même sens, inverse sinon […]
- [Algorithme de Dinic](https://complex-systems-ai.com/probleme-de-flot-maximum/algorithme-de-dinic/): Problème de flot maximum Page d’accueil Wiki Algorithme de Dinic L’algorithme de Dinic ou Dinitz, s’appuie sur deux notions : un graphe de niveau, et un flot bloquant (level graph & blocking flow). Pour déterminer le graphe de niveau, nous plaçons la source au niveau 1, ses successeurs au niveau 2 et ainsi de suite. Le flot bloquant est le flot maximum pouvant passer dans un chemin donné. L’algorithme de Dinic est le suivant : construire un graphe de niveau trouver un chemin augmentant (le plus petit) de la source vers le puits trouver l’arc limitant le chemin augmentant trouver un […]
- [Algorithme d'Edmonds-Karp](https://complex-systems-ai.com/probleme-de-flot-maximum/algorithme-dedmonds-karp/): Problème de flot maximum Page d’accueil Wiki Algorithme d’Edmonds-Karp L’algorithme d’Edmonds-Karp à un temps d’exécution de O(VE²), il est plus rapide que l’algorithme de Ford-Fulkerson pour les graphes denses, c’est à dire un graphe contenant un grand nombre d’arête (ou arcs) en fonction du nombre de sommets. L’algorithme d’Edmonds-Karp est identique à l’algorithme de Ford-Fulkerson, à l’exception de l’ordre de recherche utilisé pour déterminer un chemin augmentant. Le chemin trouvé doit être le chemin le plus court qui possède une capacité positive. Un tel chemin peut être trouvé par un parcours en largeur, en supposant que les arcs ont tous une […]
- [Problème du sac à dos](https://complex-systems-ai.com/problemes-industriels-et-reduction-polynomiale/probleme-du-sac-a-dos/): Réduction polynomial Page d’accueil Wiki Problème du sac à dos Le problème du sac à dos est l’un des 21 problèmes NP-complets de Richard Karp, exposés dans son article de 1972. Énoncé Le problème du sac à dos modélise une situation analogue au remplissage d’un sac à dos, ne pouvant supporter plus d’un certain poids, avec tout ou partie d’un ensemble donné d’objets ayant chacun un poids et une valeur. Les objets mis dans le sac à dos doivent maximiser la valeur totale, sans dépasser le poids maximum. La forme la plus commune est le problème de sac à dos 0-1 […]
- [Algorithme de Ford-Fulkerson](https://complex-systems-ai.com/probleme-de-flot-maximum/algorithme-de-ford-fulkerson/): Problème de flot maximum Page d’accueil Wiki Algorithme de Ford-Fulkerson L’algorithme de Ford-Fulkerson cherche un chemin augmentant dans le graphe résiduel. Il sature ce chemin s’il existe, sinon il retourne le flot maximum. Plus précisément, l’algorithme établit une coupe minimal pour vérifier le critère d’optimalité. On rappelle que le flot est inférieur ou égale à la coupe. Afin d’initialiser l’algorithme, il est possible d’attribuer un flot quelconque dans le graphe en suivant des chemins simples (de la source vers le puits). Dans le schéma suivant, nous avons pris pour initialisation le chemin s-2-3-t. Après construction du graphe d’écart (residual graph en […]
- [Algorithmes génétiques](https://complex-systems-ai.com/algorithmes-devolution/algorithmes-genetiques/): Algorithmes d’évolution Page d’accueil Wiki Algorithmes génétiques Les algorithmes génétiques sont des algorithmes stochastiques itératifs qui opèrent sur des individus à partir d’une population initiale. Dans les algorithmes génétiques, la population évolue de la génération k à la génération k+1 à l’aide de trois opérateurs : un opérateur de Sélection un opérateur de Croisement un opérateur de Mutation. Le processus provient de l’évolution génétique. On part avec une population de solutions potentielles initiales arbitrairement choisies. On évalue leur performance relative (fitness). Sur la base de ces performances, on crée une nouvelle population de solutions potentielles en utilisant les opérateurs. On recommence […]
- [Evaluation des heuristiques](https://complex-systems-ai.com/optimisation-combinatoire/evaluation-des-heuristiques/): Optimisation combinatoire Page d’accueil Wiki Méthodes d’évaluation des heuristiques Le problème de l’évaluation des heuristiques est crucial. En effet, les heuristiques n’offrent aucune garantie d’optimalité : elles peuvent trouver l’optimum pour certaines données, ou en être très éloignées. Performance relative Supposons qu’on étudie un problème combinatoire pour lequel on dispose déjà d’une méthode exacte (optimale) de référence. Pour une heuristique H et une donnée d, on note H(d) le coût de la solution heuristique et OPT(d) le coût optimal. On appelle performance relative de H sur d le quotient : RH (d) = H(d) / OPT(d). Pour un problème de minimisation, […]
- [Programmation par contraintes](https://complex-systems-ai.com/optimisation-combinatoire/programmation-par-contraintes/): Optimisation combinatoire Page d’accueil Wiki Programmation par contraintes La Programmation par contraintes (PPC) permet de résoudre des problèmes de type Satisfaction de Contraintes (CSP). Un CSP est un problème modélisation sous la forme d’un ensemble de contraintes posées sur des variables, chacune de ces variables prenant ses valeurs dans un domaine défini. Un CSP est défini par un triplet (X,D,C,R) tel que : X={X1,X2,…,Xn} l’ensemble des variables du problème; D une fonction qui associe à chaque variable Xi son domaine (ensemble de valeurs possibles) D(Xi); C=C1,C2,…,Ck} l’ensemble des contraintes. Solution par Programmation par contraintes Résoudre un CSP consiste à affecter des […]
- [Chaines de Markov en temps discret](https://complex-systems-ai.com/processus-de-markov/chaines-de-markov-en-temps-discret/): Processus de Markov Page d’accueil Wiki Difficulté Facile 25% Chaines de Markov en temps discret Lorsqu’on est en présence d’un phénomène aléatoire, on remarque que le futur n’est dépendant que du présent. C’est dans cette condition que l’on peut modélisation les chaines de Markov en temps discret. Soit (Xn) une suite de variables aléatoires à valeurs dans un ensemble fini de J états, Xt=j est l’état du système au temps t. On dit que Xn est une chaîne de Markov de transition si qqsoit n, qqsoit i0, …, in+1 : P(X(n+1)=i(n+1) | Xn =in,…,X0=i0) = P(X(n+1) = i(n+1) | Xn = […]
- [Branch and bound](https://complex-systems-ai.com/optimisation-combinatoire/branch-and-bound/): Optimisation combinatoire Page d’accueil Wiki Branch and bound L’algorithme de Branch and bound (Séparation et évaluation) est une énumération « intelligente » de l’arbre des solutions possibles. Comme son nom l’indique, l’algorithme possède deux temps : la séparation : séparer un ensemble de solutions en sous-ensembles; l’évaluation : évaluer les solutions d’un sous-ensemble en majorant la valeur de la meilleure solution de ce sous-ensemble. L’algorithme de Branch and bound (Séparation et évaluation) propose de parcourir l’arborescence des solutions possibles en évaluant chaque sous-ensemble de solutions. Il garde en mémoire la valeur de la meilleure solution f(s) trouvée jusqu’à présent. Quand l’évaluation d’un sous-ensemble […]
- [Algorithme A étoile](https://complex-systems-ai.com/recherche-de-chemin-theorie-des-graphes/algorithme-a-etoile/): Recherche de chemin Page d’accueil Wiki Algorithme A étoile L’idée de l’algorithme A étoile ou A star ou A*, est d’éviter de développer des chemins estimés trop cher par rapport à ceux connus. Pour cela l’algorithme fera référence à une fonction d’évaluation de son coût total. Le principe est similaire a du branch&bound ou branch&price. Fonction d’évaluation Soient f(n) une fonction d’évaluation pour un sommet n, h(n) une heuristique de coût estimé pour aller vers un état final, et g(n) le coût réel pour atteindre le sommet n. Alors f(n) = h(n)+g(n). La fonction f(n) peut se décrire comme le coût […]
- [Analyse post-optimale de sensibilité](https://complex-systems-ai.com/programmation-lineaire/analyse-post-optimale-de-sensibilite/): Programmation linéaire Page d’accueil Wiki Analyse post-optimale de sensibilité Lorsque la solution de base optimale du problème de PL est analysée pour répondre aux questions relatives aux changements dans sa formulation, l’étude porte le nom d’analyse post-optimale de sensibilité. On appelle post-optimisation l’ensemble des techniques permettant d’obtenir l’optimum du problème de PL lorsque certaines données ont subi des modifications. On considère le problème de programmation linéaire général sous sa forme stand art: Cette étude peut être motivée par plusieurs raisons : Coûts marginaux On appelle coût marginal d’un bien l’augmentation minimale de dépenses, par rapport à la solution optimale, qui résulterait de […]
- [Algorithme d'Edmonds](https://complex-systems-ai.com/probleme-de-planification/algorithme-dedmonds/): Problème de planification Page d’accueil Wiki Algorithme d’Edmonds L’objectif de l’algorithme d’Edmonds est de trouver un couplage parfait (de cardinal maximum) dans un problème d’affectation. Le problème de couplage est le suivant : Construire un graphe biparti (les éléments de gauche ne sont reliés qu’à des éléments de droite par des arcs, les éléments de droites n’ont pas de liaison sortante) tel que les éléments de gauche soient les machines et les éléments de droites soient les tâches à effectuer. Les arcs sont de capacité 1 et de coût en fonction du tableau d’affectation. Si un flot passe par une arête […]
- [Coloration, cliques et stables](https://complex-systems-ai.com/theorie-des-graphes/coloration-cliques-et-stables/): Théorie des graphes Page d’accueil Wiki Coloration de graphe Le problème de coloriage de graphes, pour un graphe G non orienté, consiste à attribuer une couleur à chaque sommet de telle sorte qu’une même couleur ne soit pas attribuée à deux sommets adjacents. Lorsque le graphe est planaire, cela revient au problème de coloriage d’une carte géographique. Le problème de la coloration d’un graphe se pose dans de nombreux domaines pratiques tels que correspondance de motif, la planification sportive, la conception des plans sièges, d’examen horaires, la planification des taxis, et la résolution de Sudoku. Le nombre minimum de couleur nécessaire pour […]
- [Arbres couvrants](https://complex-systems-ai.com/theorie-des-graphes/arbres-couvrants/): Téorie des graphes Page d’accueil Wiki Arbres couvrants Un sous-graphe de G est dit couvrant s’il contient tous les sommets de G.Un sous-graphe couvrant n’est pas forcément connexe. Un arbre couvrant de G est un sous-graphe couvrant de G, et ce sous-graphe est un arbre. Afin de minimiser le coût des réseaux électriques, des connexions de câblage, de la tuyauterie, de la reconnaissance vocale automatique, etc., nous utilisons des algorithmes qui construisent progressivement un arbre couvrant (ou plusieurs de ces arbres) comme étapes intermédiaires du processus de recherche des arbres couvrants minimum. L’Internet et de nombreux autres réseaux de télécommunication ont […]
- [Parcours d'arbres](https://complex-systems-ai.com/theorie-des-graphes/parcours-darbres/): Livre #1 Livre #1 Théorie des Graphes Page d’accueil Wiki Parcours d’arbre Pour parcourir un graphe, nous construisons d’abord un arbre couvrant de ce dernier. On parlera alors de parcours d’arbre. Parcours en largeur Dans le parcours en largeur, on parcourt par profondeur croissante à la racine. ParcoursLargeur(Graphe G, Sommet s): { f = CreerFile(); f.enfiler(s); marquer(s); tant que non f.vide() s = f.defiler(); afficher(s); pour tout voisin t de s dans G si t non marqué FAIRE f.enfiler(t); marquer(t); fin si fin pour fin tant que } Parcours en profondeur : préfixe Les parcours en profondeur sont des parcours récursifs. […]
- [Arbres et arborescences](https://complex-systems-ai.com/theorie-des-graphes/arbres-et-arborescences/): Théorie des graphes Page d’accueil Wiki Arbres et arboresences Les arbres et arborescences sont des graphes particuliers souvent utilisés pour représenter l’aide à la décision, des données, ou pour le calcul de la complexité. Un arbre est un ensemble organisé de nœuds dans lequel chaque nœud a un père et un seul, sauf un nœud que l’on appelle racine. Si un nœud p est le père du nœud f, alors f est un fils de p; si f n’a pas de fils, alors c’est une feuille. Il est possible de stocker tout type d’information dans les nœuds ou les liens. Terminologie […]
- [Théorie des graphes 101](https://complex-systems-ai.com/theorie-des-graphes/): Théories Page d’accueil Wiki I. Théorie des Graphes (Familles) Graphes parfaits Amalgamation de graphes Graphe régulier Cage Graphe biparti Graphe de Cayley Clique Graphe complémentaire Graphe de Bruijin Densité des graphes (Graphes denses et Graphes creux) Graphe d’intervalles Graphe en cercle Graphe line Graphe de Petersen Graphe planaire Graphe aléatoire Graphe à invariance d’échelle Graphe cordal ou splité Treillis II. Arbres et arborescence Arbre et arborescences Arbres couvrants Arbres de Steiner III. Coloration, clique et stable Coloriage, cliques et stables Théorème des Quatre Couleurs Conjecture de Hadwiger (en) Conjecture de Erdös – Faber – Lovász (en) Conjecture de Behzad (en) Graphe […]
- [Programme dual](https://complex-systems-ai.com/programmation-lineaire/programme-dual/): Programmation linéaire Page d’accueil Wiki Programme dual Bien que le programme primal offre une solution par la méthode du simplexe, nous n’avons que la garantie de ne pas pouvoir améliorer la solution. Afin de prouver qu’il s’agit d’une solution optimale, nous devons aussi résoudre son programme dual. Ce programme dual, en plus de garantir ou non l’optimalité, permettra aussi d’analyser la sensibilité des variables au changement. Lorsque le programme primal a plus de variables que de contraintes, alors il n’y a pas de garanti de solution (comme pour un système d’équations). Dans ce cas, il est préférable de passer par le […]
- [LP : Résolution graphique](https://complex-systems-ai.com/programmation-lineaire/resolution-graphique/): Programmation linéaire Page d’accueil Wiki Résolution graphique Il est possible de résoudre les problèmes ayant deux variables (ou deux contraintes pour un problème dual) directement par une résolution graphique. Le processus de résolution se déroule en trois étapes : Domaine réalisable Pour cela, nous représentons chaque contrainte dans le graphe, en hachurant ou coloriant le côté qui ne satisfait pas la contrainte. Ainsi, nous mettons en évidence un domaine de définition ou domaine réalisable, n’importe quel point du domaine de définition satisfait toutes les contraintes du modèle mathématique. Prenons le programme linéaire suivant : Traçons le domaine de définition : Ajout […]
- [Méthodes de descente](https://complex-systems-ai.com/algorithmes-stochastiques/methodes-de-descente/): Algorithmes stochastiques Page d’accueil Wiki Méthodes de descente Comme le nom explicite l’indique, les méthodes de descente, ou recherche locale, consiste à « glisser » le long de la fonction objectif jusqu’à trouver un optimum local, c’est-à-dire où la descente n’est plus possible. Il existe plusieurs sortes de méthode de descente qui nous décrirons ici. Descente simple À partir d’une solution initiale, l’algorithme de descente simple choisit une solution voisine meilleure que la solution courante, jusqu’à ne pas pouvoir effectuer un tel choix. L’algorithme est le suivant : S_O faire S(i+1) = voisin(Si) si f(S(i+1)) < f(Si) accepter S(i+1) fin si tant que […]
- [Recherche Tabou](https://complex-systems-ai.com/optimisation-combinatoire/recherche-tabou/): Algorithmes stochastiques Page d’accueil Wiki Recherche tabou La recherche tabou a été proposée par Fred Glover en 1986 (dont vous trouverez les schémas dans le déroulement de l’algorithme). La méthode utilise une mémoire (ou plusieurs mémoires) qui est mise à jour et exploitée au cours de la recherche. L’idée de base de la liste taboue consiste à mémoriser les configurations ou régions visitées et à introduire des mécanismes permettant d’interdire à la recherche de retourner trop rapidement vers ces configurations. Ces mécanismes sont des interdictions temporaires de certains mouvements (mouvements tabous). À chaque itération, l’algorithme tabou choisit le meilleur voisin non […]
- [Recuit simulé](https://complex-systems-ai.com/algorithmes-bases-sur-la-physique/recuit-simule/): Algorithmes physiques Page d’accueil Wiki Recuit simulé Le recuit est une méthode métallurgique permettant d’obtenir des solides cristallisés en évitant l’état de verre. Une fois le métal fondu, la température est baissée progressivement jusqu’à atteindre un état solide. Pour enlever tous les défauts, le métal est réchauffé puis refroidi, par paliers décroissant de température, jusqu’à atteindre un état stable. Ce système de palier décroissant à donné naissance à l’algorithme de Metropolis de 1953 puis au recuit simulé par IBM en 1983. Présentation de l’algorithme L’algorithme du recuit simulé, ou simulated annealing pour les anglophones, est donc l’adaptation algorithmique du processus du […]
- [Aide à la décision 101](https://complex-systems-ai.com/aide-a-la-decision/): Théories Page d’accueil Wiki I. Décision pure (aide à la décision) La méthode scientifique Modélisation mathématique Modélisation linéaire Gittins index (en) Info-gap decision theory (en) Loss aversion (en) Luce’s choice axiom (en) Mean-preserving spread (en) Menu dependence (en) Pignistic probability (en) Randomised decision rule (en) Recognition primed decision (en) Satisficing (en) Scoring rule (en) Value of information (en) Weighted product model (en) Weighted sum model (en) II. Décision collective Consensus decision-making Condorcet method Instant-runoff voting Contingent vote Single transferable vote Positional voting Borda count Path Voting Implicit utilitarian voting Weighted voting Delphi method Dotmocracy Analytic hierarchy process Hierarchical decision process III. […]
- [Diviser pour régner](https://complex-systems-ai.com/algorithmique/diviser-pour-regner/): Algorithmique Page d’accueil Wiki Diviser pour régner La méthode de diviser pour régner est une méthode qui permet, parfois de trouver des solutions efficaces à des problèmes algorithmiques. L’idée est de découper le problème initial, de taille n, en plusieurs sous-problèmes de taille inférieure, puis de recombiner les solutions partielles jusqu’à obtenir la solution finale. Principe Contrairement à la programmation dynamique, les résultats des sous-problèmes ne sont utiles que pour le résultat du problème parent. L’algorithme de diviser pour régner se décompose en trois étapes : Diviser : le problème est découpé en sous-problèmes de taille n/b. Ces sous-problèmes sont de […]
- [Algorithme naif / glouton / énumération](https://complex-systems-ai.com/algorithmique/algorithme-naif-glouton-enumeration/): Algorithmique Page d’accueil Wiki Algorithme naif Un algorithme naif a pour vocation de fournir un résultat de base à un problème. La méthode naïve ne fait aucun calcul préparatoire et se sert uniquement des données de base du problème. Prenons pour exemple un problème du sac à dos. L’ algorithme naif consisterait à prendre en première les objets de la taille la plus petite jusqu’à ne plus pouvoir mettre de nouvel objet dans le sac. pour i de 1 à n si w[i] + w_conso ≤ W alors x[i] := 1 w_conso := w_conso + w[i] sinon x[i] := 0 fin […]
- [Programmation récursive](https://complex-systems-ai.com/algorithmique/programmation-recursive/): Algorithmique Page d’accueil Wiki Programmation récursive La programmation récursive est une technique de programmation remplaçant les instructions de boucle par des appels de fonctions. Le mécanisme consiste donc, dans la grande majorité des cas, à créer une fonction qui s’appelle elle-même une ou plusieurs fois selon différents critères. La structure d’un algorithme récursif est la suivant : algo () { condition 1 condition 2 ... condition n } Les conditions sont généralement des if, ils incluent les conditions d’arrêts (ne retourne pas la fonction) ou des conditions de continuité (relance la fonction ou retourne la fonction). Les conditions de continuité modifient […]
- [Stepping stone](https://complex-systems-ai.com/probleme-de-planification/stepping-stone/): Problème de planification Page d’accueil Wiki Stepping Stone Le problème résolu par l’algorithme du Stepping stone est le suivant : Soient différentes origines, proposant une certaine offre quantifiable; et des destinations demandant une certaine quantité; un coût de transport est attribué pour chaque combinaison d’origine-destination; comment satisfaire au mieux la demande au moindre coût ? Prenons un exemple pour montrer le déroulement de l’algorithme. Soient quatre origines et cinq demandeurs avec les coûts et quantité suivant le tableau : cij D1 D2 D3 D4 D5 offre O1 7 12 1 5 6 12 O2 15 3 12 6 14 11 O3 […]
- [Algorithme hongrois](https://complex-systems-ai.com/probleme-de-planification/algorithme-hongrois/): Problème de planification Page d’accueil Wiki Algorithme hongrois Aussi appelé algorithme de Kühn, l’algorithme hongrois, ou méthode hongroise résout des problèmes d’affectation de type table de coûts. Considérons un certain nombre de machines et autant de tâches. Chaque machine exécute une tâche à un certain coût. L’objectif est de déterminer la machine sur laquelle s’exécutera chaque tâche, en parallèle. Ce problème étant similaire à un problème de couplage dans un graphe, il répond au critère de König pour la couverture nodale de poids minimum. L’objectif est donc de trouver un élément par ligne et colonne dans la table telle que la […]
- [Méthode MPM](https://complex-systems-ai.com/probleme-de-planification/methode-mpm/): Problème de planification Page d’accueil Wiki Méthode MPM La méthode MPM permet d’évaluer la durée de réalisation d’un projet complexe et de détecter les parties de ce projet ne supportant aucun retard. Les informations sur les tâches sont résumés dans un échéancier. Contrairement à la méthode PERT, les sommets de la méthode MPM sont des tâches à accomplir. Nous pouvons « considérer » que les arêtes de la méthode PERT deviennent des sommets à la méthode MPM (de même pour les sommets deviennent des arêtes). Les principales différences avec la méthode PERT : la représentation des relations d’antériorité d’une tâche partageant avec une […]
- [Méthode PERT](https://complex-systems-ai.com/probleme-de-planification/methode-pert/): Problème de planification Page d’accueil Wiki Méthode PERT Comme le diagramme de Gantt, la méthode PERT permet d’évaluer la durée de réalisation d’un projet complexe et de détecter les parties de ce projet ne supportant aucun retard. Les informations sur les tâches sont résumé dans un échéancier comme l’exemple suivant : tâche précédence durée A – 6 B – 5 C A 4 D B 6 E C 5 F A, D 6 G E, F 4 Étape 1 : construction du graphe à partir de l’échéancier On attribuera le niveau 0 aux tâches qui n’ont pas de tâche antérieure. On […]
- [Diagramme de Gantt](https://complex-systems-ai.com/probleme-de-planification/diagramme-de-gantt/): Problème de planification Page d’accueil Wiki Diagramme de Gantt Le diagramme de Gantt est une vue visuelle des tâches planifiées au fil du temps. Les diagrammes de Gantt sont utilisés pour planifier des projets de toutes tailles et constituent un moyen utile de montrer le travail prévu pour un jour spécifique. Ils vous aident également à afficher les dates de début et de fin d’un projet dans une vue simple. Cet outil répond à deux objectifs : planifier de façon optimale ainsi que communiquer sur le planning établi et les choix qu’il impose. Le diagramme permet : de déterminer les dates de réalisation […]
- [Programmation dynamique](https://complex-systems-ai.com/algorithmique/programmation-dynamique/): Algorithmique Page d’accueil Wiki Programmation dynamique La programmation dynamique est utilisé pour la résolution de nombreux problèmes provenant de la recherche opérationnelle, c’est pourquoi nous ne listerons pas les tutoriels liés à cette méthode. La Programmation Dynamique est une méthode exacte de résolution de problèmesd’optimisation, due essentiellement à R. Bellman (1957). Plus précisément, la programmation dynamique est un paradigme de conception d’algorithmes qu’on peut appliquer pour résoudre un problème s’il répond à l’optimalité de Bellman. Définition. Optimalité de Bellman. Un problème possède la propriété de sous-structure optimale si une solution optimale contient la solution optimale des sous-problèmes. La programmation dynamique ressemble […]
- [Problème de planification 101](https://complex-systems-ai.com/probleme-de-planification/): Théories Page d’accueil Wiki I. Ordonnancement / Planification Gantt PERT MPM II. Affectation Algorithme hongrois Algorithme d’Edmonds III. Transport Stepping stone IV. Solveurs Résolution Affectation avec Excel Résolution Transport avec Excel Problème de planification et d’ordonnancement La planification et l’ordonnancement automatisés concernent la réalisation de stratégies ou de séquences d’actions. La planification moderne, même au sein de l’IA, reflète de plus en plus l’intégration de la théorie et des techniques algorithmiques haute performance de la recherche opérationnelle depuis au moins les années 1950. Introduction aux problèmes de planification La planification est l’organisation de la réalisation d’objectifs dans un domaine précis, avec […]
- [Algorithme de Johnson](https://complex-systems-ai.com/recherche-de-chemin-theorie-des-graphes/algorithme-de-johnson/): Recherche de chemin Page d’accueil Wiki Algorithme de Johnson L’algorithme de Johnson calcule les plus courts chemins pour tout couple de sommets du graphe. Il a une bonne complexité pour les graphes creux (peu d’arêtes en comparaison du nombre de sommets). Il utilise les algorithmes de Dijkstra et de Bellman-Ford, et renvoie soit la matrice des poids des plus courts chemins, soit l’assertion que le graphe possède un circuit de poids négatif. La technique utilisée consiste à se ramener au cas avec uniquement des poids positifs, puis de faire tourner l’algorithme de Dijkstra en partant de chaque sommet. Si les poids […]
- [Algorithme de Floyd Warshall (fermeture transitive)](https://complex-systems-ai.com/recherche-de-chemin-theorie-des-graphes/algoritme-de-floyd-warshall-fermeture-transitive/): Recherche de chemin Page d’accueil Wiki Algorithme de Floyd Warshall Nous voulons déterminer les chemins les plus courts entre toutes les paires de sommets. Nous pourrions utiliser Dijkstra de Bellman-Ford, avec chaque sommet comme source. Pouvons-nous faire mieux? Dans l’algorithme de Floyd Warshall, nous supposons que nous avons accès à un graphe avec n sommets comme matrice d’adjacence n². L’algorithme de Floyd Warshall prend en entrée un graphe orienté et valué, décrit par une matrice d’adjacence donnant le poids d’un arc lorsqu’il existe et la valeur ∞ sinon. Le poids d’un chemin entre deux sommets est la somme des poids sur […]
- [Algorithme de Ford-Bellman](https://complex-systems-ai.com/recherche-de-chemin-theorie-des-graphes/algorithme-de-ford-bellman/): Recherche de chemin Page d’accueil Wiki Algorithme de Ford-Bellman Le problème des plus courts chemins à partir d’une origine n’a de solution que s’il n’existe pas de circuit absorbant atteignable. L’algorithme de Ford-Bellman vérifie qu’il n’existe pas de circuit absorbant atteignable à partir de s. Si c’est le cas, il retourne les plus courts chemins à partir de s. L’algorithme de Ford-Bellman est un algorithme de programmation dynamique gourmand qui calcule les chemins les plus courts de taille croissante. Il convient à n’importe quel graphe. Conditions. Cas général Au départ, la distance est initialisée à 0 pour l’origine et à l’infini […]
- [Algorithme de Bellman](https://complex-systems-ai.com/recherche-de-chemin-theorie-des-graphes/algorithme-de-bellman/): Recherche de chemin Page d’accueil Wiki Algorithme de Bellman L’algorithme de Bellman est basé sur l’observation suivante: si nous connaissons toutes les valeurs des arcs (u, v) avec u dans un sous-graphe et v à l’extérieur de ce sous-graphe. Si nous connaissons tous les chemins les plus courts vers u, donc nous pouvons calculer d(v) = min{d(u) + poids(u,v)}. L’algorithme de Bellmann est un algorithme de programmation dynamique gourmand (similaire à une première recherche de pain), il visite toutes les solutions possibles. Conditions. Pas de cycle Arc uniquement Nombre de sommets fini Une source (et accessoirement une cible) définie L’algorithme de Bellman […]
- [Méthode du Simplexe](https://complex-systems-ai.com/programmation-lineaire/methode-du-simplexe/): Programmation linéaire Page d’accueil Wiki Méthode du simplexe La méthode du simplexe a été introduit par George Dantzig à partir de 1946. Il est un algorithme de résolution des problèmes d’optimisation linéaire. Il consiste à minimiser une fonction linéaire de n variables réelles, où , sur un ensemble défini au moyen de contraintes affines (ou linéaires) d’égalité et d’inégalité. L’ensemble admissible du problème est donc un polyèdre convexe. Méthode La méthode du simplexe est une méthode itérative parcourant les sommets du polyèdre convexe jusqu’à ce que la fonction objectif ne puisse plus être améliorée. Le processus de résolution est le suivant […]
- [Programmation linéaire 101](https://complex-systems-ai.com/programmation-lineaire/): Théories Page d’accueil Wiki I. Méthodes de programmation linéaire La méthode scientifique Modélisation mathématique Modélisation linéaire Solutions et domaine réalisable Forme canonique et forme standard Résolution graphique (2 variables) Simplexe Dual Ecarts complémentaires Analyse de sensibilité Analyse de sensibilité (dual) Origine non réalisable Méthode du grand M II. Solveurs Entrer un LP sous Excel Programmation linéaire En Recherche Opérationnelle (RO) telle que la programmation linéaire, modéliser un problème consiste à identifier: les variables intrinsèques (inconnues) les différentes contraintes auxquelles sont soumises ces variables l’objectif visé (optimisation) appelé fonction Objectif. Dans un problème de programmation linéaire (PL) les contraintes et l’objectif sont […]
- [Algorithme de Dijkstra](https://complex-systems-ai.com/recherche-de-chemin-theorie-des-graphes/algorithme-de-dijkstra/): Recherche de chemin Page d’accueil Wiki Algorithme de Dijkstra E. W. Dijkstra (1930-2002) a proposé en 1959 un algorithme (nommé algorithme de Dijkstra) qui permet de déterminer le plus court chemin entre deux sommets d’un graphe connexe pondéré. L’algorithme de Dijkstra est basé sur l’observation suivante : une fois que nous déterminons le chemin le plus court vers un sommet v, alors les chemins qui vont de v à chacun de ses sommets adjacents pourraient être le plus court chemin vers chacun de ces sommets voisins. L’algorithme de Dijkstra est un algorithme de programmation dynamique glouton, il visite toutes les solutions […]
- [Recherche de chemin 101](https://complex-systems-ai.com/recherche-de-chemin-theorie-des-graphes/): Théories Page d’accueil Wiki I. Plus court chemin, source unique (recherche de chemin) Graphe non-dirigé Algorithme de Dijkstra Dijkstra with binary heap Dijkstra with Fibonacci heap Thorup Graphe dirigé avec poids non négatifs Algorithme de Bellman Algorithme de Ford-Bellman Algorithme de Dantzig Dijkstra with list Dijkstra with binary heap Dijkstra with Fibonacci heap Johnson Gabow Ahuja et al. Thorup Graphe dirigé avec tous types de poids Algorithme de Ford-Bellman Basé sur une heuristique Algorithme A* Anytime Repairing A* (ARA*) Anytime Dynamic A* D* Fringe Fringe Saving A* (FSA*) Generalized Adaptive A* (GAA*) Incremental heuristic search Informational search Iterative deepening A* (IDA*) […]
- [6 Exercices corrigés : automate à pile](https://complex-systems-ai.com/theorie-des-langages/exo-automate-a-pile/): Théorie des langages Page d’accueil Wiki Exercices corrigés : Automate à pile Cette page propose des exercices corrigés sur : automate à pile. Exercice 1 La grammaire (linéaire) S → aSb | ε produit le langage {anbn : n ≥ 0}. En vous inspirant de cet exemple, proposer des grammaires pour chacun des langages suivants : {a2n(bc)3n : n ≥ 0}, {a2nb3c20n : n ≥ 0}, {a2nb3nc20 : n ≥ 0}, {ambn : m ≥ n ≥ 0} Solution 1 – S → aaSbcbcbc | ε 2 – S → aaSc20 | bbb 3 – S → Xc20; X → aaXbbb | ε 4 – S → […]
- [9 Exercices corrigés : optimisation des automates](https://complex-systems-ai.com/theorie-des-langages/optimisation-automates/): Théorie des langages Page d’accueil Wiki Exercices corrigés Optimisation des automates par déterminisation et minimisation Vous trouverez sur cette page des exercices corrigés sur : optimisation des automates, la déterminisation et la minimisation. Déterminisation Exercice 1 Déterminiser les automates suivants : Solution Exercice 2 On considère l’alphabet A constitué des lettres de l’alphabet de la langue française et le langage L = { w ∈ A* / w se termine par man}.  Trouver un automate déterministe qui engendre L. Solution Représentons par x toutes les lettres qui ne sont pas {a,m,n}. L’automate doit reconnaitre les mots [a-z ; A-Z]*man. Construisons un automate indéterministe avec […]
- [9 Exercices corrigés : Langages, automates et grammaires](https://complex-systems-ai.com/theorie-des-langages/exo-langages-automates/): Théorie des langages Page d’accueil Wiki Exercices corrigés sur la théorie des langages, automates et grammaires Exercices corrigés sur la théorie des langages, les automates et les grammaires. Les exercices sont suivis d’une correction. Mots reconnus Exercice 1 Donner tous les mots de tailles 0, 1, 2, 3, et 4 des langages réguliers suivants : (a + ba)* ; a(aa + b(ab) ∗a)∗a. Pour cela, vous pouvez faire un arbre de possibilité pour chacun des langages. Solution Mots de longueurs 0 : epsilon ; Mots de longueurs 1 : a ; Mots de longueurs 2 : aa, ba ; Mots de longueurs 3 […]
- [Projet chaines de Markov : Computer Chess](https://complex-systems-ai.com/processus-de-markov/projet-chaines-de-markov-computer-chess/): Théories Page d’accueil Solution Projet chaines de Markov : Computer Chess Le projet chaines de Markov : Computer Chess, regroupe des notions de théorie des langages et des processus stochastiques discret d’ordre un. ETC: 15 hours (deadline – 5 classes) 2-3 students per team Please take your time on both quality and contents Associate professor and assistant professors will not answer questions about the project. BAREME : 40 points 10 Points 15 Points 15 points “Cameraman: Do you think a human being will ever beat a person at chess? John: Oh… between a human being and a person? My money’s on […]
- [Projet Théorie des langages : Automata](https://complex-systems-ai.com/theorie-des-langages/projet-theorie-des-langages-automata/): Théories Page d’accueil Solutions Projet théorie des langages : Automata Ceci est le premier projet théorie des langages. ETC: 15 hours (deadline – 5 classes) 2-3 students per team Please take your time on both quality and contents Associate professor and assistant professors will not answer questions about the project. Barème: 40 points 15 Points 10 Points 15 points “-Why is it so difficult for you to accept my orders if you’re just a machine? -Just a machine? That’s like saying that you are just an ape.” Partie 1 : Des données lisibles et compréhensibles « Jacq Vaucan: Funny, you were supposed […]
- [ADSA Project: Among Us](https://complex-systems-ai.com/algorithmique/adsa-project-among-us/): Algorithmique Page d’accueil What is Among Us ? ADSA project This page display the Project (Among Us) of the ADSA Course. To do this mi- project:  Make groups of only two students.  Make report on the theoretical study, modification, diagrams or schemas and discussions on the results.   Do not include any code in this theoretical report. Please make attention to the written quality and format of your report.  For each step, please detail the model, the algorithm “no code” and the discussion.  All parts must be coded in a « python or C # » project. One language for all the projects. All […]
- [Introduction à la recherche](https://complex-systems-ai.com/la-recherche-scientifique/introduction-a-la-recherche/): Parcours Recherche Page d’accueil Wiki Introduction à la Recherche Voici les différents cours proposés dans l’Introduction à la Recherche : How to define a problem statement How to conduct a literature survey How to read a scientific paper How to present a research proposal How to present a research work How to expose a scientific poster How to write a scientific paper How to define a problem statement​ How to conduct a literature survey​ How to read a scientific paper​ How to present a research proposal​ How to present a research work​ How to expose a scientific poster​ How to write […]
- [Hamiltonien et Eulerien](https://complex-systems-ai.com/theorie-des-graphes/hamiltonien-et-eulerien/): Théorie des graphes Page d’accueil Wiki Problème : graphe eulérien Pour un graphe orienté, un chemin (ou circuit) eulérien passe une et une seule fois par tous les arcs. De même dans le cas non orienté, une chaîne ou cycle eulérien passe une et une seule fois par toutes les arêtes. Le graphe doit être fortement connexe (ou connexe). En effet, si le graphe ne l’est pas, un ou plusieurs sous-graphes contenant des liaisons ne sont pas atteignables. On constate qu’un cycle ou circuit eulérien contient autant de liaisons arrivant à un sommet qu’il en part (on arrive à un sommet […]
- [Théorème des Quatre Couleurs](https://complex-systems-ai.com/theorie-des-graphes/theoreme-des-quatre-couleurs/): Théorie des graphes Page d’accueil Wiki Théorème des quatre couleurs Le théorème des quatre couleurs énonce la possibilité de colorier (on dit aussi colorer en théorie des graphes) avec quatre couleurs seulement une carte géographique sans que deux pays voisins aient la même couleur. Pour être plus précis, le théorème des quatre couleurs précise qu’en n’utilisant que quatre couleurs différentes, il est possible de colorer n’importe quelle carte découpée en régions connexes (d’un seul morceau), de sorte que deux régions adjacentes (ou limitrophes), c’est-à-dire ayant toute une frontière (et non simplement un point) en commun reçoivent toujours deux couleurs distinctes.Ainsi, chacune […]
- [Qualité sur le nombre de clusters](https://complex-systems-ai.com/partitionnement-de-donnees/qualite-sur-le-nombre-de-clusters/): Partitionnement de données Page d’accueil Wiki Qualité sur le nombre de clusters Un sujet lié à la validation des clusters est de décider si le nombre de clusters obtenu est le bon (Qualité sur le nombre de clusters). Ce point est particulièrement important pour les algorithmes qui ont besoin de cette valeur comme paramètre. La procédure habituelle consiste à comparer les caractéristiques des regroupements de différentes tailles. Généralement, des indices de critères internes sont utilisés dans cette comparaison. Un graphique de ces indices pour différents nombres de clusters peut montrer le nombre de grappes le plus probable. Certains des indices de […]
- [Statistique de Hopkins](https://complex-systems-ai.com/partitionnement-de-donnees/statistique-de-hopkins/): Partitionnement de données Page d’accueil Wiki Statistique de Hopkins Avant de regrouper un ensemble de données, nous pouvons tester s’il existe réellement des clusters. Nous devons tester l’hypothèse de l’existence de modèles dans les données par rapport à un ensemble de données uniformément distribué (distribution homogène). La statistique de Hopkins est calculée comme suit : Si les données sont uniformément réparties, la valeur de H sera d’environ 0,5.
- [Critères de qualité externes](https://complex-systems-ai.com/partitionnement-de-donnees/criteres-de-qualite-externes/): Partitionnement de données Page d’accueil Wiki Critères de qualité externes Les indices de qualité externes sont des indices destinés à mesurer la similitude entre deux partitions. Ils prennent en compte uniquement la répartition des points dans les différents clusters et ne permettent pas de mesurer la qualité de cette répartition. Liste Mesure de rappel de précision Variables indicatrices Mesure fondée sur l’information mutuelle Entropie, pureté et V-mesure Czekanowski-Dice Folkes-Mallows Hubert Γ Jaccard Kulczynski McNemar Phi Rand Rogers-Tanimoto Russel-Rao Sokal-Sneath Notation Tous les indices proposés s’appuient sur une matrice de confusion représentant le décompte des paires de points selon qu’ils sont considérés […]
- [Critères de qualité internes](https://complex-systems-ai.com/partitionnement-de-donnees/criteres-de-qualite-internes/): Partitionnement de données Page d’accueil Wiki Critères de qualité internes Les critères de qualité internes  mesurent généralement la compacité des clusters à l’aide d’une mesure de similitude. Il mesure généralement l’homogénéité intra-cluster, la séparabilité inter-cluster ou une combinaison de ces deux. Il n’utilise pas d’informations externes à côté des données elles-mêmes.  Liste Somme de l’erreur quadratique Critères de dispersion Métrique d’utilité de la catégorie Mesures de coupe Ball-Hall Banfeld-Raftery Critère de Condorcet Critère C Calinski-Harabasz Davies-Bouldin Det_Ratio Dunn GDImn Gamma G+ Ksq_DetW Log_Det_Ratio Log_SS_Ratio McClain-Rao PBM Point biserial Ratkawsky-Lance Ray-Turi Scott-Symons SD_Scat SD_Dis S_Dbw Silhouette Trace W Trace WiB Wemmert-Gançarski Xie-Beni […]
- [Fonction de similarité](https://complex-systems-ai.com/partitionnement-de-donnees/fonction-de-similarite/): Partitionnement de données Page d’accueil Wiki Fonction de similarité Un concept alternatif à celui de la distance est la fonction de similarité (mesure du cosinus, mesure de corrélation de Pearson, Mesure de Jaccard étendue, mesure du coefficient de Dice) s(x_i, x_j) qui compare les deux vecteurs x_i et x_j. Cette fonction doit être symétrique (à savoir s(x_i, x_j) = s(x_j, x_i)) et avoir une grande valeur lorsque x_i et x_j sont en quelque sorte «similaires» et constituent la plus grande valeur pour des vecteurs identiques. Une fonction de similitude où la plage cible est [0,1] est appelée fonction de similitude dichotomique. […]
- [Mesures de distance pour les attributs de type mixte](https://complex-systems-ai.com/partitionnement-de-donnees/mesures-de-distance-pour-les-attributs-de-type-mixte/): Partitionnement de données Page d’accueil Wiki Mesures de distance pour les attributs de type mixte De nombreuses méthodes de partitionnement utilisent des mesures de distance pour déterminer la similitude ou la dissemblance entre n’importe quelle paire d’objets (comme Mesures de distance pour les attributs de type mixte). Il est courant de désigner la distance entre deux instances x_i et x_j comme: d (x_i, x_j). Une mesure de distance valide doit être symétrique et obtient sa valeur minimale (généralement zéro) dans le cas de vecteurs identiques. La mesure de distance est appelée mesure de distance métrique si elle satisfait également aux propriétés […]
- [Mesures de distance pour les attributs ordinaux](https://complex-systems-ai.com/partitionnement-de-donnees/mesures-de-distance-pour-les-attributs-ordinaux/): Partitionnement de données Page d’accueil Wiki Mesures de distance pour les attributs ordinaux De nombreuses méthodes de partitionnement utilisent des mesures de distance pour déterminer la similitude ou la dissemblance entre n’importe quelle paire d’objets (comme Mesures de distance pour les attributs ordinaux). Il est courant de désigner la distance entre deux instances x_i et x_j comme: d (x_i, x_j). Une mesure de distance valide doit être symétrique et obtient sa valeur minimale (généralement zéro) dans le cas de vecteurs identiques. La mesure de distance est appelée mesure de distance métrique si elle satisfait également aux propriétés suivantes : Lorsque les […]
- [Mesures de distance pour les attributs nominaux](https://complex-systems-ai.com/partitionnement-de-donnees/mesures-de-distance-pour-les-attributs-nominaux/): Partitionnement de données Page d’accueil Wiki Mesures de distance pour les attributs nominaux De nombreuses méthodes de partitionnement utilisent des mesures de distance pour déterminer la similitude ou la dissemblance entre n’importe quelle paire d’objets (comme les mesures de distance pour les attributs nominaux). Il est courant de désigner la distance entre deux instances x_i et x_j comme: d (x_i, x_j). Une mesure de distance valide doit être symétrique et obtient sa valeur minimale (généralement zéro) dans le cas de vecteurs identiques. La mesure de distance est appelée mesure de distance métrique si elle satisfait également aux propriétés suivantes : Lorsque […]
- [Mesures de distance pour les attributs binaires](https://complex-systems-ai.com/partitionnement-de-donnees/mesures-de-distance-pour-les-attributs-binaires/): Partitionnement de données Page d’accueil Wiki Mesures de distance pour les attributs binaires De nombreuses méthodes de partitionnement utilisent des mesures de distance pour déterminer la similitude ou la dissemblance entre n’importe quelle paire d’objets (comme des attributs binaires). Il est courant de désigner la distance entre deux instances x_i et x_j comme: d (x_i, x_j). Une mesure de distance valide doit être symétrique et obtient sa valeur minimale (généralement zéro) dans le cas de vecteurs identiques. La mesure de distance est appelée mesure de distance métrique si elle satisfait également aux propriétés suivantes : Dans le cas d’attributs binaires, la […]
- [Minkowski pour les attributs numériques](https://complex-systems-ai.com/partitionnement-de-donnees/minkowski-pour-les-attributs-numeriques/): Partitionnement de données Page d’accueil Wiki Minkowski pour les attributs numériques De nombreuses méthodes de partitionnement utilisent des mesures de distance pour déterminer la similitude ou la dissemblance entre n’importe quelle paire d’objets (comme Minkowski pour les attributs numériques). Il est courant de désigner la distance entre deux instances x_i et x_j comme: d (x_i, x_j). Une mesure de distance valide doit être symétrique et obtient sa valeur minimale (généralement zéro) dans le cas de vecteurs identiques. La mesure de distance est appelée mesure de distance métrique si elle satisfait également aux propriétés suivantes : Étant donné deux instances de dimension […]
- [Partitionnement de données / Clustering 101](https://complex-systems-ai.com/partitionnement-de-donnees/): Théories Page d’accueil Wiki I. Mesure de distance et Fonction de similarité (partitionnement de données) Minkowski pour les attributs numériques Pour les attributs binaires Pour les attributs nominaux Pour les attributs ordinaux Pour les attributs de type mixte Fonction de similarité II. Critères d’évaluation Qualité des données Qualité interne Somme de l’erreur quadratique Critères de dispersion Métrique d’utilité de la catégorie Mesures de coupe Ball-Hall Banfeld-Raftery Critère de Condorcet Critère C Calinski-Harabasz Davies-Bouldin Det_Ratio Dunn GDImn Gamma G+ Ksq_DetW Log_Det_Ratio Log_SS_Ratio McClain-Rao PBM Point biserial Ratkawsky-Lance Ray-Turi Scott-Symons SD_Scat SD_Dis S_Dbw Silhouette Trace W Trace WiB Wemmert-Gançarski Xie-Beni Qualité externe Mesure […]
- [Carte auto-organisée](https://complex-systems-ai.com/algorithmes-neuronaux/carte-auto-organisee/): Algorithmes neuronaux Page d’accueil Wiki Carte auto-organisée La carte auto-organisée est inspirée de cartes de caractéristiques de neurones dans le cerveau constituées de cellules sensibles aux caractéristiques qui fournissent des projections ordonnées entre les couches neuronales, telles que celles qui peuvent exister dans la rétine et la cochlée. Par exemple, il existe des cartes de caractéristiques acoustiques qui répondent aux sons auxquels un animal est le plus souvent exposé, et des cartes tonotopiques qui peuvent être responsables de la préservation de l’ordre des résonances acoustiques. L’objectif de traitement de l’information de l’algorithme de carte auto-organisée est de placer de manière optimale […]
- [Apprentissage de la quantification vectorielle](https://complex-systems-ai.com/algorithmes-neuronaux/apprentissage-de-la-quantification-vectorielle/): Algorithmes neuronaux Page d’accueil Wiki Algorithme d’apprentissage de quantification vectorielle L’apprentissage de quantification vectorielle est lié à la carte auto-organisatrice qui est à son tour inspirée par les capacités d’auto-organisation des neurones dans le cortex visuel. L’objectif de traitement de l’information de l’algorithme d’apprentissage de quantification vectorielle est de préparer un ensemble de vecteurs codebooks (ou prototype) dans le domaine des échantillons de données d’entrée observés et d’utiliser ces vecteurs pour classer des exemples non traités. Un pool de vecteurs initialement aléatoire est préparé qui est ensuite exposé à des échantillons d’apprentissage. Une stratégie le gagnant prend tout est utilisée où […]
- [Réseau de Hopfield](https://complex-systems-ai.com/algorithmes-neuronaux/reseau-de-hopfield/): Algorithmes neuronaux Page d’accueil Wiki Réseau de Hopfield Dans un réseau de Hopfield, au cours du processus de formation, on peut penser que les poids dans le réseau minimisent une fonction énergétique et glissent sur une surface d’énergie. Dans un réseau entrainé, chaque modèle présenté au réseau fournit un attracteur, où des progrès sont réalisés vers le point d’attraction en propageant des informations autour du réseau. L’objectif de traitement de l’information du système est d’associer les composants d’un modèle d’entrée à une représentation holistique du modèle appelé Content Addressable Memory (CAM). Cela signifie qu’une fois formé, le système rappellera des motifs […]
- [Rétropropagation](https://complex-systems-ai.com/algorithmes-neuronaux/retropropagation/): Algorithmes neuronaux Page d’accueil Wiki Rétropropagation Les réseaux de neurones à action directe sont inspirés par le traitement de l’information d’une ou plusieurs cellules neuronales (appelées neurones). Un neurone accepte les signaux d’entrée via son axone, qui transmettent le signal électrique au corps cellulaire. Les dendrites transmettent le signal aux synapses, qui sont les connexions des dendrites d’une cellule aux axones d’autres cellules. Dans une synapse, l’activité électrique est convertie en activité moléculaire (molécules de neurotransmetteurs traversant la fente synaptique et se liant aux récepteurs). La liaison moléculaire développe un signal électrique qui est transmis à l’axone des cellules connectées. L’algorithme […]
- [Perceptron](https://complex-systems-ai.com/algorithmes-neuronaux/perceptron-fr/): Algorithmes neuronaux Page d’accueil Wiki Perceptron Le Perceptron s’inspire du traitement de l’information d’une seule cellule neuronale (appelée neurone). Un neurone accepte les signaux d’entrée via son axone, qui transmettent le signal électrique au corps cellulaire. Les dendrites transmettent le signal aux synapses, qui sont les connexions des dendrites d’une cellule aux axones d’autres cellules. Dans une synapse, l’activité électrique est convertie en activité moléculaire (molécules de neurotransmetteurs traversant la fente synaptique et se liant aux récepteurs). La liaison moléculaire développe un signal électrique qui est transmis à l’axone des cellules connectées. L’objectif de traitement de l’information de la technique est […]
- [Algorithme de cellules dendritiques](https://complex-systems-ai.com/algorithme-immunitaire/algorithme-de-cellules-dendritiques/): Algorithmes immunitaires Page d’accueil Wiki Algorithme de cellules dendritiques L’algorithme de cellules dendritiques est inspiré de la théorie du danger du système immunitaire des mammifères et, plus précisément, du rôle et de la fonction des cellules dendritiques. La théorie du danger a été proposée par Matzinger et suggère que le rôle du système immunitaire acquis est de répondre aux signaux de danger, plutôt que de distinguer le soi du non-soi. La théorie suggère que les cellules présentant l’antigène (telles que les cellules T auxiliaires) activent un signal d’alarme fournissant la co-stimulation nécessairement des cellules spécifiques de l’antigène pour répondre. Les cellules […]
- [Algorithme de réseau immunitaire](https://complex-systems-ai.com/algorithme-immunitaire/algorithme-de-reseau-immunitaire/): Algorithmes immunitaires Page d’accueil Wiki Réseau immunitaire artificiel L’algorithme du réseau immunitaire artificiel est inspiré de la théorie du réseau immunitaire du système immunitaire acquis. La théorie de la sélection clonale de l’immunité acquise tient compte du comportement adaptatif du système immunitaire, y compris la sélection et la prolifération continues de cellules qui sélectionnent le matériel potentiellement nocif (et généralement étranger) dans le corps. Une préoccupation de la théorie de la sélection clonale est qu’elle suppose que le répertoire des cellules réactives reste inactif lorsqu’il n’y a pas d’agent pathogène auquel répondre. Jerne a proposé une théorie du réseau immunitaire (réseaux […]
- [Système de reconnaissance immunitaire artificiel](https://complex-systems-ai.com/algorithme-immunitaire/systeme-de-reconnaissance-immunitaire-artificiel/): Algorithmes immunitaires Page d’accueil Wiki Système de reconnaissance immunitaire artificiel Le système de reconnaissance immunitaire artificiel est inspiré de la théorie de la sélection clonale de l’immunité acquise. La théorie de sélection clonale attribuée à Burnet a été proposée pour tenir compte du comportement et des capacités des anticorps dans le système immunitaire acquis. S’inspirant des principes de la théorie de l’évolution de la sélection naturelle darwinienne, la théorie propose que les antigènes sélectionnent les lymphocytes (à la fois les cellules B et les cellules T). Lorsqu’un lymphocyte est sélectionné et se lie à un déterminant antigénique, la cellule prolifère en […]
- [Algorithme de sélection négative](https://complex-systems-ai.com/algorithme-immunitaire/algorithme-de-selection-negative/): Algorithmes immunitaires Page d’accueil Wiki Algorithme de sélection négative L’algorithme de sélection négative est inspiré du comportement de discrimination de soi-non-soi observé dans le système immunitaire acquis par les mammifères. La théorie de l’immunité acquise tient compte du comportement adaptatif du système immunitaire, y compris la sélection et la prolifération continues de cellules qui sélectionnent le matériel potentiellement nocif (et généralement étranger) dans le corps. Un aspect intéressant de ce processus est qu’il est responsable de la gestion d’une population de cellules immunitaires qui ne sélectionnent pas les tissus du corps, en particulier il ne crée pas de cellules immunitaires autoréactives […]
- [Algorithme de sélection clonale](https://complex-systems-ai.com/algorithme-immunitaire/algorithme-de-selection-clonale/): Algorithmes immunitaires Page d’accueil Wiki Algorithme de sélection clonale L’algorithme de sélection clonale attribuée à Burnet a été proposée pour tenir compte du comportement et des capacités des anticorps dans le système immunitaire acquis. S’inspirant des principes de la théorie de l’évolution de la sélection naturelle darwinienne, la théorie propose que les antigènes sélectionnent les lymphocytes (à la fois les cellules B et les cellules T). Lorsqu’un lymphocyte est sélectionné et se lie à un déterminant antigénique, la cellule prolifère en faisant plusieurs milliers de copies supplémentaires d’elle-même et se différencie en différents types de cellules (plasma et cellules de mémoire). […]
- [Algorithme d'optimisation de l'alimentation bactérienne](https://complex-systems-ai.com/algorithmes-dessaims/algorithme-doptimisation-de-lalimentation-bacterienne/): Algorithmes d’essaims Page d’accueil Wiki Algorithme d’optimisation de l’alimentation bactérienne L’algorithme d’optimisation de l’alimentation bactérienne est inspiré par le comportement de recherche de nourriture de groupe de bactéries telles que E. coli et M. xanthus. Plus précisément, l’algorithme d’optimisation de l’alimentation bactérienne est inspiré par le comportement chimiotactique des bactéries qui percevront les gradients chimiques dans l’environnement (tels que les nutriments) et se déplaceront vers ou loin de signaux spécifiques. Les bactéries perçoivent la direction de la nourriture en fonction des gradients de produits chimiques dans leur environnement. Les bactéries sécrètent des produits chimiques attirants et répulsifs dans l’environnement et peuvent […]
- [Algorithme des abeilles](https://complex-systems-ai.com/algorithmes-dessaims/algorithme-des-abeilles/): Algorithmes d’essaims Page d’accueil Wiki Algorithme des abeilles L’algorithme des abeilles s’inspire du comportement de recherche de nourriture des abeilles mellifères. Les abeilles collectent le nectar de vastes zones autour de leur ruche (plus de 10 kilomètres). Il a été observé que les colonies d’abeilles envoient des abeilles pour recueillir le nectar des parcelles de fleurs par rapport à la quantité de nourriture disponible à chaque parcelle. Les abeilles communiquent entre elles à la ruche via une danse qui informe les autres abeilles de la ruche quant à la direction, la distance et la cote de qualité des sources de nourriture. […]
- [Système de fourmis](https://complex-systems-ai.com/algorithmes-dessaims/systeme-de-fourmis/): Algorithmes d’essaims Page d’accueil Wiki Système de fourmis L’algorithme de système de fourmis est inspiré par le comportement de recherche de nourriture des fourmis, en particulier la communication par des phéromones entre les fourmis concernant un bon chemin entre la colonie et une source de nourriture dans un environnement. Ce mécanisme est appelé stigmergie. Les fourmis errent initialement au hasard dans leur environnement. Une fois la nourriture localisée, une fourmi commencera à déposer des phéromones dans l’environnement. De nombreux voyages entre la nourriture et la colonie sont effectués et si la même route qui mène à la nourriture est suivie, des […]
- [Méthode de cross-entropie](https://complex-systems-ai.com/algorithmes-probabilistes/methode-de-cross-entropie/): Algorithmes probabilistes Page d’accueil Wiki Méthode de cross-entropie Méthode de cross-entropie a été développé comme une technique d’estimation efficace pour les probabilités d’événements rares dans les systèmes de simulation d’événements discrets et a été adapté pour être utilisé dans l’optimisation. Le nom de la technique vient de la méthode de cross-entropie de Kullback-Leibler pour mesurer la quantité d’informations (bits) nécessaires pour identifier un événement à partir d’un ensemble de probabilités. La stratégie de traitement de l’information de l’algorithme consiste à échantillonner l’espace du problème et à approximer la distribution des bonnes solutions. Ceci est réalisé en supposant une distribution de l’espace […]
- [Algorithme d'optimisation bayésienne](https://complex-systems-ai.com/algorithmes-probabilistes/algorithme-doptimisation-bayesienne/): Algorithmes probabilistes Page d’accueil Wiki Algorithme d’optimisation bayésienne Dans un algorithme d’optimisation bayésienne, l’objectif de traitement de l’information est de construire un modèle probabiliste qui décrit les relations entre les composants des solutions d’ajustement dans l’espace du problème. Ceci est réalisé en répétant le processus de création et d’échantillonnage à partir d’un réseau bayésien qui contient les dépendances conditionnelles, les indépendances et les probabilités conditionnelles entre les composants d’une solution. Le réseau est construit à partir des fréquences relatives des composants au sein d’une population de solutions candidates à haut fitness. Une fois le réseau construit, les solutions candidates sont rejetées […]
- [Algorithme génétique compact](https://complex-systems-ai.com/algorithmes-probabilistes/algorithme-genetique-compact/): Algorithmes probabilistes Page d’accueil Wiki Algorithme génétique compact L’objectif de traitement de l’information de l’algorithme génétique compact est de simuler le comportement d’un algorithme génétique avec une empreinte mémoire beaucoup plus petite (sans nécessiter le maintien d’une population). Ceci est réalisé en maintenant un vecteur qui spécifie la probabilité d’inclure chaque composant dans une solution dans de nouvelles solutions candidates. Les solutions candidates sont générées de manière probabiliste à partir du vecteur et les composants de la meilleure solution sont utilisés pour apporter de petites modifications aux probabilités dans le vecteur. L’algorithme génétique compact maintient un vecteur prototype à valeur réelle […]
- [Algorithme de distribution marginale univariée](https://complex-systems-ai.com/algorithmes-probabilistes/algorithme-de-distribution-marginale-univariee/): Algorithmes probabilistes Page d’accueil Wiki Algorithme de distribution marginale univariée La stratégie de traitement de l’information de l’algorithme de distribution marginale univariée consiste à utiliser la fréquence des composants d’une population de solutions candidates dans la construction de nouvelles solutions candidates. Ceci est réalisé en mesurant d’abord la fréquence de chaque composant dans la population (la probabilité marginale univariée) et en utilisant les probabilités pour influencer la sélection probabiliste des composants dans la construction par composants des nouvelles solutions candidates. L’algorithme suivant fournit un pseudocode de l’algorithme de distribution marginale univariée pour minimiser une fonction de coût. L’UMDA a été conçu […]
- [Apprentissage progressif basé sur la population](https://complex-systems-ai.com/algorithmes-probabilistes/apprentissage-progressif-base-sur-la-population/): Algorithmes probabilistes Page d’accueil Wiki Apprentissage progressif basé sur la population L’objectif de traitement de l’information de l’algorithme d’apprentissage progressif basé sur la population (PBIL) est de réduire la mémoire requise par l’algorithme génétique. Cela se fait en réduisant la population d’une solution candidate à un seul prototype vecteur d’attributs à partir duquel des solutions candidates peuvent être générées et évaluées. Des mises à jour et des opérateurs de mutation sont également effectués sur le vecteur prototype, plutôt que sur les solutions candidates générées. L’algorithme d’apprentissage progressif basé sur la population conserve un vecteur prototype à valeur réelle qui représente la […]
- [Algorithme mémétique](https://complex-systems-ai.com/algorithmes-bases-sur-la-physique/algorithme-memetique/): Algorithmes physiques Page d’accueil Wiki Algorithme mémétique L’algorithme mémétique est inspiré par l’interaction de l’évolution génétique et de l’évolution culturelle. Le darwinisme universel est la généralisation des gènes au-delà des systèmes biologiques à tout système où des unités discrètes d’informations peuvent être héritées et soumises à des forces évolutionnaires de sélection et de variation. Le terme « mème » de l’ algorithme mémétique est utilisé pour désigner une information culturelle discrète, suggérant l’interaction entre l’évolution génétique et culturelle. Le génotype évolue en fonction de l’interaction du phénotype avec l’environnement. Cette interaction est mesurée par des phénomènes culturels qui influencent les mécanismes de sélection, […]
- [Algorithme culturel](https://complex-systems-ai.com/algorithmes-bases-sur-la-physique/algorithme-culturel/): Algorithmes physiques Page d’accueil Wiki Algorithme culturel L’algorithme culturel s’inspire du principe de l’évolution culturelle. La culture comprend les habitudes, les connaissances, les croyances, les coutumes et la morale d’un membre de la société. La culture n’existe pas indépendamment de l’environnement et peut interagir avec l’environnement via des cycles de rétroaction positifs ou négatifs. L’étude de l’interaction de la culture dans l’environnement est appelée écologie culturelle. L’algorithme culturel peut être expliqué dans le contexte de l’inspiration. Au fur et à mesure que le processus évolutif se déroule, les individus accumulent des informations sur le monde qui sont communiquées à d’autres individus […]
- [Algorithme de Recherche d'harmonie](https://complex-systems-ai.com/algorithmes-bases-sur-la-physique/algorithme-de-recherche-dharmonie/): Algorithmes physiques Page d’accueil Wiki Recherche d’harmonie L’algorithme de recherche d’harmonie s’est inspiré de l’improvisation des musiciens de jazz. Plus précisément, le processus par lequel les musiciens (qui n’ont peut-être jamais joué ensemble auparavant) affinent rapidement leur improvisation individuelle par le biais de la variation résultant en une harmonie esthétique. Chaque musicien correspond à un attribut dans une solution candidate dans le domaine, et la hauteur et la plage de chaque instrument correspondent aux limites et contraintes de la variable de décision. L’harmonie entre les musiciens est considérée comme une solution candidate complète à un moment donné, et l’appréciation esthétique de […]
- [Optimisation des extremums](https://complex-systems-ai.com/algorithmes-bases-sur-la-physique/optimisation-des-extremums/): Algorithmes physiques Page d’accueil Wiki Optimisation des extremums L’optimisation des extremums est inspirée du modèle de Bak-Sneppen de criticité auto-organisé de la co-évolution du domaine de la physique statistique. Le modèle de criticité auto-organisé suggère que certains systèmes dynamiques ont un point critique en tant qu’attracteur, où les systèmes présentent des périodes de mouvement lent ou d’accumulation suivies de courtes périodes d’avalanche ou d’instabilité. Des exemples de tels systèmes comprennent la formation des terres, les tremblements de terre et la dynamique des tas de sable. Le modèle de Bak-Sneppen prend en compte ces dynamiques dans les systèmes de co-évolution et dans […]
- [Algorithme évolutif de Pareto fort](https://complex-systems-ai.com/algorithmes-devolution/algorithme-evolutif-de-pareto-fort/): Algorithmes d’évolution Page d’acccueil Wiki Difficulté Moyen 50% Algorithme évolutif de Pareto fort SPEA L’objectif de l’algorithme évolutif de Pareto fort SPEA est de localiser et de maintenir un front de solutions non dominées, idéalement un ensemble de solutions optimales de Pareto. Ceci est réalisé en utilisant un processus évolutif (avec des procédures de substitution pour la recombinaison génétique et la mutation) pour explorer l’espace de recherche, et un processus de sélection qui utilise une combinaison du degré de domination d’une solution candidate (forte) et d’une estimation de la densité du front de Pareto comme une fitness assignée. Une archive de […]
- [Algorithme génétique de tri non dominé](https://complex-systems-ai.com/algorithmes-devolution/algorithme-genetique-de-tri-non-domine/): Algorithmes d’évolution Page d’accueil Wiki Algorithme génétique de tri non dominé NSGA L’objectif de l’algorithme génétique de tri non dominé NSGA est d’améliorer l’ajustement adaptatif d’une population de solutions candidates à un front de Pareto contraint par un ensemble de fonctions objectives. L’algorithme génétique de tri non dominé NSGA utilise un processus évolutif avec des substituts pour les opérateurs évolutifs, y compris la sélection, le croisement génétique et la mutation génétique. La population est classée dans une hiérarchie de sous-populations basée sur l’ordre de la domination de Pareto. La similitude entre les membres de chaque sous-groupe est évaluée sur le front […]
- [Système de classeurs](https://complex-systems-ai.com/algorithmes-devolution/systeme-de-classeurs/): Algorithmes d’évolution Page d’accueil Wiki Système de classeurs L’objectif du système de classeurs est d’optimiser le gain en fonction de l’exposition aux stimuli d’un environnement spécifique au problème. Ceci est réalisé en gérant l’attribution de crédit pour les règles qui s’avèrent utiles et en recherchant de nouvelles règles et de nouvelles variations sur les règles existantes à l’aide d’un processus évolutif. Les acteurs du système de classeurs comprennent des détecteurs, des messages, des effecteurs, des commentaires et des classificateurs. Les détecteurs sont utilisés par le système pour percevoir l’état de l’environnement. Les messages sont les paquets d’informations transmis des détecteurs au […]
- [Programmation d'expressions génétiques](https://complex-systems-ai.com/algorithmes-devolution/programmation-dexpressions-genetiques/): Algorithmes d’évolution Page d’accueil Wiki Programmation d’expressions génétiques La programmation d’expressions génétiques s’inspire de la réplication et de l’expression de la molécule d’ADN, en particulier au niveau du gène. L’expression d’un gène implique la transcription de son ADN en ARN qui à son tour forme des acides aminés qui constituent des protéines dans le phénotype d’un organisme. Les éléments constitutifs de l’ADN sont soumis à des mécanismes de variation (mutations telles que des erreurs d’adaptation) ainsi qu’à une recombinaison lors de la reproduction sexuelle. La programmation d’expressions génétiques utilise un génome linéaire comme base pour les opérateurs génétiques tels que la […]
- [Évolution grammaticale pour l'algorithme génétique](https://complex-systems-ai.com/algorithmes-devolution/evolution-grammaticale-pour-lalgorithme-genetique/): Algorithmes d’évolution Page d’accueil Wiki Algorithme évolution grammaticale L’algorithme d’évolution grammaticale s’inspire du processus biologique utilisé pour générer une protéine à partir de matériel génétique ainsi que du processus évolutif génétique plus large. Le génome est composé d’ADN comme une chaîne de blocs de construction qui sont transcrits en ARN. Les codons d’ARN sont à leur tour traduits en séquences d’acides aminés et utilisés dans la protéine. La protéine résultante dans son environnement est le phénotype. Le phénotype est un programme informatique créé à partir d’un génome à base de chaînes binaires. Le génome est décodé en une séquence d’entiers qui […]
- [Programmation de l'évolution pour l'algorithme génétique](https://complex-systems-ai.com/algorithmes-devolution/programmation-de-levolution-pour-lalgorithme-genetique/): Algorithmes d’évolution Page d’accueil Wiki Algorithme de programmation de l’évolution L’objectif de l’algorithme de programmation de l’évolution est de maximiser l’adéquation d’une collection de solutions candidates dans le contexte d’une fonction objective du domaine. Cet objectif est poursuivi en utilisant un modèle adaptatif avec substituts des processus d’évolution, notamment héréditaire (reproduction avec variation) en compétition. La représentation utilisée pour les solutions candidates est directement évaluable par une fonction de coût ou d’objectif du domaine. La représentation des solutions candidates doit être spécifique au domaine, comme les nombres réels pour l’optimisation continue des fonctions. La taille de l’échantillon (BoutSize) pour la sélection […]
- [Evolution différentielle pour l'algorithme génétique](https://complex-systems-ai.com/algorithmes-devolution/evolution-differentielle-pour-lalgorithme-genetique/): Algorithmes d’évolution Page d’accueil Wiki Algorithme d’évolution différentielle L’algorithme d’évolution différentielle consiste à maintenir une population de solutions candidates soumises à des itérations de recombinaison, d’évaluation et de sélection. L’approche de recombinaison implique la création de nouveaux composants de solution candidats basés sur la différence pondérée entre deux membres de la population sélectionnés au hasard ajoutés à un troisième membre de la population. Cela perturbe les membres de la population par rapport à la propagation de l’ensemble de la population. En conjonction avec la sélection, l’effet de perturbation auto-organise l’échantillonnage de l’espace du problème, le liant à des zones d’intérêt connues. […]
- [Stratégies d'évolution pour l'algorithme génétique](https://complex-systems-ai.com/algorithmes-devolution/strategies-devolution-pour-lalgorithme-genetique/): Algorithmes d’évolution Page d’accueil Wiki Difficulté Moyen 50% Stratégies d’évolution Les stratégies d’évolution s’inspirent de la théorie de l’évolution par sélection naturelle. Plus précisément, la technique s’inspire du processus d’évolution au niveau macro ou au niveau de l’espèce (phénotype, héréditaire, variation) et ne s’intéresse pas aux mécanismes génétiques de l’évolution (génome, chromosomes, gènes, allèles). L’objectif de l’algorithme d’évolution stratégique est de maximiser la pertinence de la collecte de solutions candidates dans le contexte d’une fonction objective dans un domaine donné. L’objectif est atteint par l’adoption de la variation dynamique, un substitut de la descente avec modification, où la quantité de variation […]
- [Programmation génétique](https://complex-systems-ai.com/algorithmes-devolution/programmation-genetique/): Algorithmes d’évolution Page d’accueil Wiki Programmation génétique L’algorithme de programmation génétique s’inspire de la génétique des populations (y compris l’hérédité et les fréquences des gènes) et de l’évolution au niveau de la population, ainsi que de la compréhension mendélienne de la structure (comme les chromosomes, les gènes, les allèles) et des mécanismes (comme la recombinaison et la mutation ). Il s’agit de la soi-disant synthèse nouvelle ou moderne de la biologie évolutive. Les individus d’une population apportent leur matériel génétique (appelé le génotype) proportionnel à la pertinence de leur génome exprimé (appelé leur phénotype) à leur environnement. La prochaine génération est […]
- [Recherche à voisinage variable](https://complex-systems-ai.com/algorithmes-stochastiques/recherche-a-voisinage-variable/): Algorithmes stochastiques Page d’accueil Wiki Recherche à voisinage variable La stratégie de recherche à voisinage variable implique l’exploration itérative de voisinages de plus en plus grands pour un optima local donné jusqu’à ce qu’une amélioration soit localisée, après quoi la recherche dans ces voisinages est répétée. La stratégie est motivée par trois principes: 1) un minimum local pour une structure de voisinage peut ne pas être un minimum local pour une structure de voisinage différente, 2) un minimum global est un minimum local pour toutes les structures de voisinages possibles, et 3) les minima locaux sont relativement proche des minima globaux […]
- [Recherche locale guidée](https://complex-systems-ai.com/algorithmes-stochastiques/recherche-locale-guidee/): Algorithmes stochastiques Page d’accueil Wiki Recherche locale guidée La stratégie de l’algorithme de recherche locale guidée consiste à utiliser des pénalités pour encourager une technique de recherche locale à échapper aux optima locaux et à découvrir les optima globaux. Un algorithme de recherche locale est exécuté jusqu’à ce qu’il se coince dans un optima local. Les caractéristiques des optima locaux sont évaluées et pénalisées, dont les résultats sont utilisés dans une fonction de coût augmenté utilisée par la procédure de recherche locale. La recherche locale est répétée plusieurs fois en utilisant les derniers optima locaux découverts et la fonction de coût […]
- [3 Exercices Corrigés de Cas Particuliers en LP](https://complex-systems-ai.com/programmation-lineaire/lp-cas-particuliers/): Programmation linéaire Page d’accueil Wiki Exercices Corrigés de Cas Particuliers (Grand M) en Programmation Linéaire Ce TD propose des exercices corrigés sur des cas particuliers (dégénérescence, grand M, simplexe en deux phases). Tutoriel Un brooker a besoin, pour sa clientèle, de 108 MWh d’électricité pour la ville 1 et de 96 MWh d’électricité pour la ville 2. Cependant, les lois de Kirchhoff ne permettent pas à un distributeur de cibler une ville unique pour le transit énergétique. Deux distributeurs desservent ces villes : le Distributeur A peut envoyer 12 MWh à la ville 1 et 8MWh à la ville 2 par […]
- [5 Exercices Corrigés Dual et écart complémentaire](https://complex-systems-ai.com/programmation-lineaire/ecart-complementaire/): Programmation linéaire Page d’accueil Wiki Exercices corrigés sur le programme dual et écart complémentaire Ce TD propose divers exercices corrigés sur le programme dual et l’algorithme d’écart complémentaire. Les exercices sont suivis des corrections. Tutoriel Prenons le programme linéaire suivant : Résoudre le programme linéaire. Il y a quatre variables de base pour deux contraintes, il est possible que le problème ne soit pas borné et ne possède pas de solution. Puisqu’il y a deux contraintes, le dual aura deux variables, il est facile de trouver une solution graphique à ce nouveau programme linéaire. Le dual est le suivant : Et […]
- [6 exercices corrigés sur Forme Primale de programmation linéaire](https://complex-systems-ai.com/programmation-lineaire/forme-primale-exo/): Programmation linéaire Page d’accueil Wiki Exercices corrigés de programmation linéaire (forme primale) Ce TD propose divers exercices corrigés sur la modélisation en forme primale de programmation linéaire. Tutoriel Un fabriquant d’outillage de fraisage fabrique deux types de fraises : A et B. Les fraises de type A se vendent 300 l’unité, et se fabrique à avec 1 unité d’acier, 2 unités de carbure amovible et 1 unité de diamant synthétique. Les fraises de type B se vendent 200 l’unité, et se fabrique à avec 2 unité d’acier, 1 unités de carbure amovible et 1 unité de diamant synthétique.  Les stocks sont […]
- [6 Exercices Corrigés Modélisation linéaire](https://complex-systems-ai.com/aide-a-la-decision/modelisation-lineaire-ex/): Aide à la décision Page d’accueil Wiki Exercices Corrigés sur la modélisation linéaire à partir d’énoncé Ci-dessus des exercices corrigés de modélisation linéaire. Exercice 1 Une entreprise fabrique deux produits A et B, en utilisant une machine m et deux matières premières p et q. On dispose chaque jour de 8 heures de m, de 10 kg de p et de 36 kg de q. On suppose que : la production d’une unité de A nécessite 2 kg de p et 9 kg de q, et utilise la machine m durant 1 heure ; la production d’une unité de B nécessite […]
- [LP : forme canonique et forme standard](https://complex-systems-ai.com/programmation-lineaire/lp-forme-canonique-et-forme-standard/): Programmation linéaire Page d’accueil Wiki Forme canonique et forme standard Les programmes linéaires suivent certaines règles lors de son écriture. Un programme linéaire qui suit les règles est dit de forme canonique. L’algorithme du simplexe ne peut que s’appliquer sur des programmes linéaires sous la forme canonique. Forme canonique Un programme linéaire sous sa forme canonique est : Si le programme linéaire ne correspond pas à ces critères, il faut transformer les contraintes ou la fonction objectif selon les opérations suivantes : La forme canonique est souvent représenté sous une forme matricielle : Ainsi le programme linéaire suivant : S’écrit sous […]
- [LP : Solutions et domaine réalisables](https://complex-systems-ai.com/programmation-lineaire/lp-solutions-et-domaine-realisables/): Programmation linéaire Page d’accueil Wiki Domaine réalisable Une solution d’un problème linéaire est dit Réalisable si toutes les contraintes sont satisfaites. Le domaine réalisable contient toutes les solutions réalisables du problème. La solution optimal est la/les « meilleure(s) » des solutions réalisables. Pour savoir si une solution est réalisable, il suffit de tester si toutes les contraintes sont satisfaites, cela peut se faire à la main ou sous forme matricielle. A la main : Vérifions si la solution (3, 1) est réalisable. La première équation donne 3*1/3 + 1 = 2, la contrainte est satisfaite.La deuxième inéquation donne -2*3 + 5*1 = -1 […]
- [Modélisation linéaire (exercices)](https://complex-systems-ai.com/aide-a-la-decision/modelisation-lineaire-exercices/): Aide à la décision Page d’accueil Wiki Voici des exercices non corrigés concernant la modélisation linéaire. Tutoriel sur la modélisation linéaire Une entreprise fabrique deux produits A et B, en utilisant une machine m et deux matières premières p et q. On dispose chaque jour de 8 heures de m, de 10 kg de p et de 36 kg de q. On suppose que : la production d’une unité de A nécessite 2 kg de p et 9 kg de q, et utilise la machine m durant 1 heure ; la production d’une unité de B nécessite 2 kg de p […]
- [Modélisation linéaire](https://complex-systems-ai.com/aide-a-la-decision/modelisation-lineaire/): Aide à la décision Page d’accueil Wiki Modélisation linéaire Reprenons les bases de la modélisation linéaire dans le cadre de problème linéaire. Les étapes à suivre sont les suivantes : Exemple 1 Un industriel possède trois usine adapté dans la fabrication de deux produits. Chaque lot de produit lui rapporte une certaine somme, et il connait le nombre d’heure nécessaire pour la fabrication de  chaque type de lot dans ses usines. L’industriel voulant maximiser son profit, il faut donc trouver la meilleure production possible. Posons des variables de décision : Posons les contraintes : Posons la fonction objectif: Ce qui donne […]
- [Algorithme de descente stochastique](https://complex-systems-ai.com/algorithmes-stochastiques/algorithme-de-descente-stochastique/): Algorithmes stochastiques Page d’accueil Wiki Descente stochastique La stratégie de l’algorithme de descente stochastique consiste à itérer le processus de sélection aléatoire d’un voisin pour une solution candidate et à ne l’accepter que si cela entraîne une amélioration. La stratégie proposée visait à remédier aux limites des techniques déterministes d’escalade susceptibles de rester bloquées dans les optima locaux en raison de leur acceptation cupide des déménagements voisins. L’algorithme de descente stochastique a été conçu pour être utilisé dans des domaines discrets à voisins explicites tels que l’optimisation combinatoire (par rapport à l’optimisation continue des fonctions). La stratégie de l’algorithme peut être […]
- [Recherche aléatoire](https://complex-systems-ai.com/algorithmes-stochastiques/recherche-aleatoire/): Algorithmes stochastiques Page d’accueil Wiki Recherche aléatoire La stratégie de recherche aléatoire consiste à échantillonner des solutions sur l’ensemble de l’espace de recherche en utilisant une distribution de probabilité uniforme. Chaque futur échantillon est indépendant des échantillons qui le précèdent. La stratégie a une complexité de temps et de mémoire minimale, car elle ne nécessite qu’une routine de construction de solution candidate et une routine d’évaluation de solution candidate, les deux pouvant être calibrées à l’aide de l’approche. La performance la plus défavorable pour la localisation des optima est pire qu’une énumération du domaine de recherche, étant donné que la recherche […]
- [Algorithmes neuronaux 101](https://complex-systems-ai.com/algorithmes-neuronaux/): Théories Page d’accueil Wiki I. Perceptron et rétropropagation (algorithmes neuronaux) Perceptron ADALINE Règles d’apprentissage de Widrow-Hoff Rétropropagation Méthode de Vogl Delta-bar-delta Quickprop Rprop Règle de Hebb Réseau de Hopfield Mémoire associative bidirectionnelle II. Apprentissage de la quantification vectorielle Apprentissage de la quantification vectorielle LVQ2 LVQ2.1 LVQ3 OLVQ1 GLVQ Robust soft-LVQ Matrix RSLVQ Kernel RSLVQ Generalized relevance LVQ Generalized matrix LVQ Kernel GLVQ Harmonic to minimum LVQ Cauchyy-Schwarz Divergence LVQ Nystrom-approximation generalized LVQ III. Group method of data handling Group method of data handling Combinatorial (COMBI) Multilayered Iterative (MIA) GN Objective System Analysis (OSA) Harmonical Two-level (ARIMAD) Multiplicative–Additive (MAA) Objective Computer Clusterization […]
- [Algorithme immunitaire 101](https://complex-systems-ai.com/algorithme-immunitaire/): Théories Page d’accueil Wiki I. Algorithme de sélection clonale (algorithme immunitaire) Algorithme de sélection clonale Algorithme des cellules B Algorithme du système immunitaire à objectifs multiples Algorithme immunitaire d’optimisation Algorithme immunologique simple CLONALG1 CLONALG2 CLONCLAS Sélection clonale adaptative II. Système immunitaire artificiel Système de reconnaissance immunitaire artificiel Algorithme de réseau immunitaire Réseau immunitaire artificiel Système immunitaire artificiel à ressources limitées opt-aiNet III. Algorithme de sélection négative et cellules dendritiques Algorithme de sélection négative NSA and classification system Algorithme de cellules dendritiques IV. Tutoriels Contenu de va-et-vient Algorithme immunitaire Une description simplifiée du système immunitaire ou d’un algorithme immunitaire est un système […]
- [Algorithmes d'essaims 101](https://complex-systems-ai.com/algorithmes-dessaims/): Théories Page d’accueil Wiki I. Essaims de particules (algorithmes d’essaims) Optimisation des essaims de particules Optimisation des essaims de particules répulsives Essaimage chaotique de particules PSO-Voronoi Quantum-behaved PSO Bare-bones PSO Chaotic PSO Fuzzy PSO PSOT-VAC Opposition-based PSO Simplified PSO II. Système de colonie de fourmis Système de fourmis Système de colonie de fourmis Système de fourmis Max-Min Système de fourmis basé sur le rang Systèmes de fourmis élitistes Optimisation de la colonie de fourmis hyper cube Recherche arborescente non déterministe approximative Système de multiples colonies de fourmis Colonie de fourmis orthogonale continue Optimisation récursive des colonies de fourmis Population-based ACO Beam-ACO […]
- [Algorithmes probabilistes 101](https://complex-systems-ai.com/algorithmes-probabilistes/): Théories Page d’accueil Wiki I. Algorithmes bayésiens (algorithmes probabilistes) Algorithme d’optimisation bayésienne Algorithme d’optimisation bayésienne hiérarchique Algorithme d’optimisation bayésienne incrémentale Algorithme de réseau bayésien Estimation de l’algorithme du réseau bayésien Apprendre l’algorithme de distribution factorisé II. Algorithmes probabilistes à population Apprentissage progressif basé sur la population Algorithme génétique compact Algorithme génétique compact étendu Évolution incrémentielle probabiliste du programme Recombination schemes Blend crossover Simulated binary crossover Fuzzy recombination UNDX Probabilistic model-building genetic algorithms Self-adaptive evolution strategies III. Algorithmes basés sur la distribution et l’entropy Algorithme de distribution marginale univariée Algorithme de distribution marginale bivariée Algorithme de distribution factorisé Incremental UMDA Méthode d’entropie […]
- [Algorithmes basés sur la physique 101](https://complex-systems-ai.com/algorithmes-bases-sur-la-physique/): Théories Home page Wiki I. Recuit simulé (algorithmes basés sur la physique) Recuit simulé Recuit simulé adaptatif Recuit simulé parallèle Recuit simulé rapide Recuit quantique Trempe simulée II. Recherche d’harmonie, algorithme culturel et algorithme mémétique Recherche d’harmonie Algorithme culturel Algorithme mémétique Algorithme évolutif Baldwinien Algorithme évolutif Lamarckien III. Optimisation par physique artificielle et recherche gravitationnelle Central force optimization Extended central force optimization Artificial physics optimization Extended artificial physics optimization Vector model of artificial physicsoptimization Gravitational search algorithm Binary gravitational search algorithm Multiobjective gravitational search algorithm PSO gravitational search algorithm Gravitational interaction optimization Immune gravitation inspired optimization algorithm Electromagnetism-like heuristic Charged system […]
- [Algorithmes d'évolution 101](https://complex-systems-ai.com/algorithmes-devolution/): Théories Page d’accueil Wiki I. Algorithme génétique (algorithmes d’évolution) Algorithme génétique GENITOR II Algorithme génétique CHC Algorithme génétique du haras Programmation génétique Fonctions définies automatiquement Programmation génétique en plusieurs étapes Stratégies d’évolution Stratégies d’évolution de l’adaptation de la matrice de covariance Évolution différentielle Programmation évolutive Évolution grammaticale Programmation d’expression génique II. Système de classeurs Système de classeurs SAMUEL GAssist Memetic Pittsburgh Learning Classifier System GABIL Michigan-style ZCS Michigan-style XCS Memetic Michigan Learning Classifier System III. Algorithme génétique de tri non dominé Algorithme génétique de tri non dominé Algorithme évolutif d’optimisation à objectifs multiples Algorithme génétique évalué par vecteur Stratégie d’évolution paréto-archivée […]
- [Algorithmes stochastiques 101](https://complex-systems-ai.com/algorithmes-stochastiques/): Théories Page d’accueil Wiki I. Recherche aléatoire (algorithmes stochastiques) Recherche aléatoire Recherche aléatoire adaptative Recherche aléatoire adaptative (taille de pas) Recherche aléatoire directionnelle adaptative Recherche aléatoire dirigée Recherche aléatoire localisée Recherche aléatoire rampante II. Descente stochatique Descente stochastique Descente parallèle Descente à plusieurs reprise Redémarrage aléatoire de descente Descente à mutation aléatoire Descente itérative ES(1+1,m,hc) Random bit climber Algorithme génétique (1+1) III. Recherche locale itérée Recherche locale itérée Recherche de voisinage variable Recherche de décomposition de voisinage variable Voisinage variable asymétrique Voisinage variable parallèle GRASP GRASP réactif GRASP parallèle Descente itérée Chaîne de Markov à grand pas Lin-Kernighan itéré Optimisation locale […]
- [Searching in a tree (data structure)](https://complex-systems-ai.com/theorie-des-graphes/searching-in-a-tree-data-structure/): Théorie des Graphes Page d’accueil Wiki To search in a graph, we first build a tree covering the graph. Breadth first search BFS browse by increasing depth to the root. BFS(Graph G, Node s): { f = CreateQueue(); f.stack(s); mark(s); while non f.empty() s = f.pop(); print(s); for each children t of s in G if t unmarked DO f.stack(t); mark(t); end if end for end while } In-depth search : pre-order In-depth algorithms are recursive. In the prefix path, we always browse the left subtree before processing the right subtree. Check if the current node is empty or null. Display […]
- [Résolution LP avec Excel](https://complex-systems-ai.com/programmation-lineaire/resolution-lp-avec-excel/): Programmation linéaire Page d’accueil Wiki Résolution LP avec excel Pour résoudre le programme linéaire avec Excel (résolution LP avec Excel), vous avez besoin du module Solveur. Dans l’onglet Fichier, cliquez sur Options. Sous Compléments, sélectionnez Complément Solveur et cliquez sur le bouton OK. Vérifiez le complément du solveur et cliquez sur OK. Si la manœuvre ne fonctionne pas, vous pouvez cliquer sur Solveur puis Atteindre. Vous trouverez le solveur sur l’onglet Données dans le groupe Analyse, comme indiqué dans l’image suivante. Ecrire un LP avec Excel Pour formuler un problème de programmation linéaire, tenez compte des trois questions suivantes : Quelles […]
- [Résolution Transport avec Excel](https://complex-systems-ai.com/probleme-de-planification/resolution-transport-avec-excel/): Problème de planification Page d’accueil Wiki Comment résoudre un problème de transport avec Excel (unités partant d’usines vers des clients en minimisant le coût de transport). Formuler le problème de transport avec Excel Pour formuler ce problème de transport, il faut répondre aux trois questions suivantes. Quelles sont les décisions à prendre ? Pour résoudre ce problème, Excel doit déterminer le nombre d’unités à expédier de chaque usine à chaque client. (en jaune) Quelles sont les contraintes sur ces décisions ? Chaque usine a une offre fixe et chaque client a une demande fixe. (en bleu clair) Quelle est la mesure […]
- [Résolution Affectation avec Excel](https://complex-systems-ai.com/probleme-de-planification/resolution-affectation-avec-excel/): Problème de planification Page d’accueil Wiki Résolution problème d’affectation avec Excel Voici comment résoudre des problèmes d’affectation avec Excel. Pour formuler un problème d’affectation, il faut répondre à ces trois interrogations. Quelles sont les décisions à prendre ? Pour ce problème, nous avons besoin d’Excel pour savoir quelle personne attribuer à quelle tâche (Oui = 1, Non = 0). Par exemple, si nous affectons la personne 1 à la tâche 1, la cellule C10 est égale à 1. Sinon, la cellule C10 est égale à 0. (en jaune) Quelles sont les contraintes sur ces décisions ? Chaque personne ne peut effectuer […]
- [Résolution Plus court chemin avec Excel](https://complex-systems-ai.com/recherche-de-chemin-theorie-des-graphes/resolution-plus-court-chemin-avec-excel/): Recherche de chemin Page d’accueil WIki   Utilisons le solveur dans Excel pour trouver le chemin le plus court du noeud S au noeud T dans un réseau non dirigé (il y aura moins de contraintes dans un réseau dirigé). Formuler le problème de plus court chemin avec Excel Pour formuler ce problème de plus court chemin avec Excel, répondons aux trois questions interrogations suivantes. Quelles sont les décisions à prendre ? Pour ce problème, nous avons besoin d’Excel pour savoir si un arc est sur le chemin le plus court ou non (Oui = 1, Non = 0). Par exemple, […]
- [Résolution Flot Maximum avec Excel](https://complex-systems-ai.com/probleme-de-flot-maximum/resolution-flot-maximum-avec-excel/): Problème de flot maximum Page d’accueil Wiki Le solver permet de résoudre le problème de flot maximum avec Excel d’un noeud S vers un noeud T dans un graphe orienté. Formuler le problème de flot maximum avec Excel Pour formuler le problème de flot, il faut répondre à ces trois interrogations. Quelles sont les décisions à prendre ? Pour ce problème, nous avons besoin d’Excel pour trouver le flux sur chaque arc. Par exemple, si le débit sur SB est égal à 2, la cellule D5 est égale à 2. (en jaune) Quelles sont les contraintes sur ces décisions ? Le […]
- [Ecarts complémentaires](https://complex-systems-ai.com/programmation-lineaire/ecarts-complementaires/): Programmation linéaire Page d’accueil Wiki Écarts complémentaires Les écarts complémentaires sont utilisable si le primal est réalisable et que la solution est bornée, le dual est réalisable et sa solution est aussi borné. Si les valeurs des solutions primale et duale sont égales, elles sont optimales pour leur programme linéaire, on parle de dualité forte. Parfois il n’est pas possible de trouver de solution, ou pas utile de la calculer. Le programme primal et dual étant lié, il est possible de déduire une solution du programme réciproque à l’aide des écarts complémentaires. Processus L’un des principaux théorèmes de la théorie de […]
- [Analyse post-optimale de sensibilité (dual)](https://complex-systems-ai.com/programmation-lineaire/analyse-post-optimale-de-sensibilite-dual/): Programmation linéaire Page d’accueil Wiki Analyse post-optimale de sensibilité L’analyse post-optimale de sensibilité du programme dual permet de vérifier deux autres mesures de sensibilités : nouvelle variable et nouvelle contrainte. Cas d’étude 1 : introduction d’une nouvelle variable Voici le programme linéaire de base : Nous souhaitons rajouter une nouvelle activité : On souhaite déterminer si la nouvelle activité à un intérêt ou non. En d’autres termes, s’il n’a pas intérêt à le faire, la solution optimale du programme linéaire ci-dessus donne x3 = 0. Ceci est équivalent au fait que la troisième contrainte du dual n’est pas satisfaite : y1 + 3 […]
- [LP : méthode du grand M](https://complex-systems-ai.com/programmation-lineaire/lp-methode-du-grand-m/): Programmation linéaire Page d’accueil Wiki Méthode du grand M Lorsque le simplexe possède des variables artificielles, il est possible de ne pas trouver de solution de départ évident (tester si l’origine est dans le domaine de définition). Dans ce cas il faut trouver une solution de départ avec la méthode du grand M. Cette méthode calcule un problème auxiliaire avant de résoudre le simplexe du programme linéaire, c’est pourquoi on parle d’un simplexe en deux phases. Pourquoi une variable artificielle ? Avant d’expliquer comment obtenir une solution pour commencer le simplexe, il est important de comprendre pourquoi il est nécessaire de […]
- [LP : origine non réalisable](https://complex-systems-ai.com/programmation-lineaire/lp-origine-non-realisable/): Programmation linéaire Page d’accueil Wiki Origine non réalisable Les problèmes dont tous les bi sont positifs sont fait avec Origine Réalisable. Il est facile d’avoir une solution de base et le simplexe est compatible. Pour les problèmes à l’origine non réalisable, on cherche d’abord à résoudre le Problème Auxiliaire. Dans le problème auxiliaire, on ajoute une variable auxiliaire x0. Cette variable rentre dans toutes les contraintes. Nous cherchons à minimiser sa valeur (maximiser son contraire). La première itération est spécifique, on force la variable auxiliaire à rentrer. La ligne pivot est celle dont le bi est le plus petit. La suite […]
- [Modélisation mathématique](https://complex-systems-ai.com/aide-a-la-decision/modelisation-mathematique/): Aide à la décision Page d’accueil Wiki Modélisation mathématique La modélisation mathématique est à la base de tout le travail ingénierie. Une modélisation mathématique se caractérise par trois notions : La présence de choix, à faire parmi un ensemble fini (notion que l’on peut rapprocher de la théorie des probabilités) Un principe de contraintes définissant l’ensemble fini des choix Un principe d’évaluation des choix disponibles Modélisation mathématique d’un problème Les quatre étapes de la modélisation mathématique d’un problème industriel sont les suivantes : Quelles sont les données du problème ? récolter les données du problème, comprendre le problème; Comment modéliser le […]
- [Parcours Recherche : Automate Stochastique (2018-2019)](https://complex-systems-ai.com/processus-de-markov/parcours-recherche-automate-stochastique-2018-2019/): 🔗 Projet Session Lecture Idea/Concept 1 🔗 Lecture 1 Basics      → Probabilité      → Variable aléatoire      → Chaine de Markov temps discret ordre 1      → Théorème ergodique      → Absorption      → Etude d’une chaîne 2 🔗 Lecture 2 Hidden Markov Chain      → Définitions      → Backward-Forward      → Viterbi      → Baum-Welch      → sklearn 3 🔗 Lecture 3 Probabilistic automaton      → Automate probabiliste      → Automate de fréquence      → HMMT      → Merge & Fold      → Mots interdits      → ALERGIA                      REFERENCES Introduction to Algorithms: Cormen, T et Leiserson, C The […]
- [Ope. Res. : Graph theory](https://complex-systems-ai.com/theorie-des-graphes/ope-res-graph-theory-2018-2019/): Théories Page d’accueil Wiki Graph theory course This course presents some graph theory algorithms like spanning trees, shortest path problems and flow problems. 🔗 project 1 🔗 project 2 🔗 SYLLABUS MARKS http://graphonline.ru/en/       Session/Timeline Tutorial/Oral exam Idea/Concept Video none none 🔗 Decision making/motivation           1 🔗 Tutorial 1 Complexity        → 🔗 Big oh notation 🔗      → 🔗 Termination and correctness 🔗     2 🔗 Tutorial 2 Graph theory’s basics        → 🔗 Un/directed graph        → Degree        → Path/cycle        → Complete graph 🔗      […]
- [Smart Grid : Gestion de la demande](https://complex-systems-ai.com/processus-de-markov/smart-grid-gestion-de-la-demande-2018-2019/): Théories Page d’accueil Wiki Gestion de la demande Cours de Gestion de la demande. Introduction à la théorie des langages et aux processus markoviens de type chaîne de Markov de rang 1. 🔗 project 1 🔗 project 2   🔗 NOTES       Session/Timeline Tutorial/Oral exam Idea / Concept Video none none 🔗 Motivation           1 & 2 🔗 TD 1 Automate        → 🔗 Introduction aux langages        → 🔗 Expressions rationnelles 🔗      → 🔗 Automate fini déterministe 🔗      → 🔗Automate fini indéterministe 🔗      → 🔗 Automate fini ε-indéterministe 🔗 […]
- [La file M/M/1](https://complex-systems-ai.com/processus-de-markov/la-file-m-m-1/): Processus de Markov Page d’accueil Wiki Difficulté Facile 25% File M/M/1 Une file M/M/1 suit une loi exponentielle pour l’arrivée et le service des clients. Une file M/M/1 est représentée comme suit : Dans la majorité des cas, le client dans un service est compris dans le nombre de clients dans la file d’attente. Le nombre de clients dans la file se modélise par la chaîne de Markov à temps continu suivante : Les probabilités stationnaires existent car la chaîne est irréductible. Notons p(n) la probabilité que le nombre de clients dans la file N(t)=n quand t tend vers l’infini. Les […]
- [Les files d'attente](https://complex-systems-ai.com/processus-de-markov/les-files-dattente/): Processus de Markov Page d’accueil Wiki Difficulté Facile 25% Files d’attente Une file d’attente (ou des files d’attente) peut être décrit ainsi : des clients (hommes, taches, messages, etc.) arrivent pour un service, attendent dans une file s’ils ne peuvent pas être pris en charge immédiatement, et repartent après avoir eu le service. Le modèle, originalement créé par Erlang pour le système téléphonique de 1909, permet de modéliser la gestion de trafic, la planification et le dimensionnement d’infrastructures et d’usinage. Notation de Kendall Une file d’attente possède 6 critères notées par : T/X/C/K/P/Z T : la distribution de probabilité du temps […]
- [Processus de Poisson](https://complex-systems-ai.com/processus-de-markov/processus-de-poisson/): Processus de Markov Page d’accueil Wiki Difficulté Facile 25% Processus de Poisson Un processus de Poisson de paramètre λ est un processus stochastiques N(t) tel que N(O)=0, N(t) est incrémenté de +1 après un temps T distribué suivant une loi exponentielle de paramètre λ. On parle d’arrivées de Poisson si le temps entre deux arrivées est exponentiel. Prenons pour état la valeur de N(t), alors la chaîne de Markov en temps continu associé au processus de Poisson λ est : Il est possible de connaitre la probabilité pour que N soit au nombre k au temps t par la formule : N(t) est distribué […]
- [Régime permanent](https://complex-systems-ai.com/processus-de-markov/regime-permanent/): Processus de Markov Page d’accueil Wiki Difficulté Moyen 50% Régime permanent Dans une chaîne de Markov en temps continu (et irréductible en temps discret), le vecteur des probabilités stationnaires existe toujours et est indépendant de la distribution initiale (régime permanent). Ce vecteur π est solution de système suivant : Le système est appelé équations de balance. Exemple Deux machines identiques fonctionnent de façon continue à moins d’être brisées. Un réparateur disponible au besoin pour réparer les machines. Le temps de réparation suit une distribution exponentielle avec une moyenne de 0.5 journée. Une fois réparée, le temps d’utilisation d’une machine avant son […]
- [Chaines de Markov en temps continu](https://complex-systems-ai.com/processus-de-markov/chaines-de-markov-en-temps-continu/): Processus de Markov Page d’accueil Wiki Difficulté Moyen 50% Chaines de Markov en temps continu Dans le cas du temps discret, nous observons les états sur des moments instantanés et immuables. Dans le cadre des chaines de Markov en temps continu, les observations se dont de façon continu, c’est à dire sans interruption temporelle. Temps continu Soient M + 1 états mutuellement exclusifs. L’analyse débute au temps 0 et le temps s’écoule de façon continue, on nomme X(t) l’état du système au temps t. Les points de changement d’états ti sont des points aléatoires dans le temps (ils ne sont pas […]
- [Probabilité d'absorption d'un état](https://complex-systems-ai.com/processus-de-markov/probabilite-dabsorption-dun-etat/): Processus de Markov Page d’accueil Wiki Difficulté Moyen 50% Absorption d’un état Une chaîne de Markov est absorbante (absorption d’un état) si et seulement si : il y a au moins un état absorbant, de tout état non absorbant, on peut atteindre un état absorbant. Pour toute chaîne de Markov absorbante et pour tout état de départ, la probabilité de se trouver dans un état absorbant au temps t tend vers 1 lorsque t tend vers l’infini. Lorsque l’on a affaire à une chaîne de Markov absorbante, on est généralement intéressé par les deux questions suivantes : Si une chaîne de […]
- [Critères de récurrence et transience](https://complex-systems-ai.com/processus-de-markov/criteres-de-recurrence-et-transience/): Processus de Markov Page d’accueil Wiki Difficulté Facile 25% Critères de récurrence et transience Nous allons étudier une seconde classification des états dépendant du type de comportement de la chaîne (les critères de récurrence et transience). Soit x un état de la chaîne, nous notons le temps d’atteinte de x, noté Tx, le premier instant où x est visité après le départ. par convention, le temps d’atteinte est infini si nous n’atteignons jamais x. La formule est la suivante (nous utiliserons les notations classiques pour les probabilités) : Si la chaîne part de l’état x, nous employons le terme de temps […]
- [Algorithme de Brzozowski et McCluskey](https://complex-systems-ai.com/theorie-des-langages/algorithme-de-brzozowski-et-mccluskey/): Théorie des langages Page d’accueil Wiki Difficulté DIfficile 80% Algorithme de Brzozowski et McCluskey L’algorithme de Brzozowski et McCluskey utilise de façon intensive la représentation graphique de l’automate. L’automate lui-même est généralisé, en autorisant, comme étiquettes des transitions, non seulement des lettres, mais des expressions régulières. Partant d’une automate fini, on élimine progressivement les états, et à la fin, on se retrouve avec un automate ayant une seule transition. L’étiquette de cette transition est une expression rationnelle pour le langage reconnu par l’automate. Un automate généralisé est défini comme un automate fini non déterministe traditionnel, avec les particularités suivantes : On peut facilement transformer un automate […]
- [Algorithme de McNaughton et Yamada](https://complex-systems-ai.com/theorie-des-langages/algorithme-de-mcnaughton-et-yamada/): Théorie des langages Page d’accueil Wiki DIfficulté Moyen 50% Algorithme de McNaughton et Yamada L’algorithme de McNaughton et Yamada suit les étapes suivantes. Étant donné un automate à n états, et dont les états sont numérotés de 1 à n, on donne une expression pour les langages composés des mots qui étiquettent les chemins de i à j, pour tout couple i, j. Cette expression est construite par récurrence au moyen d’une condition sur les chemins. Cette condition stipule que les chemins ne passent que par certains états autorisés. Notre automate ayant n états, nous nous concentrons donc sur la construction d’une expression régulière pour chacun des n×n langages Ls,s’ = { w∈X* | s.w = s‘ } […]
- [Résolution par le lemme d'Arden](https://complex-systems-ai.com/theorie-des-langages/resolution-par-le-lemme-darden/): Théorie des langages Page d’accueil Wiki Difficulté Difficile 80% Lemme d’Arden Il est important de noter qu’il existe deux version symétriques du lemme d’Arden. Suivant la version qu’on utilise la méthode pour générer les équations est légèrement différente. Version de droite Prenons l’automate suivant : La construction des équations se fait comme suit : le langage reconnu par un état est égale au langage suivi du symbole de transition de ses prédécesseurs. Par exemple, le langage L2 accepté par l’état 2 est égale à : L2 = L1a. Un mot  w ∈ Li si et seulement si ilexiste un calcul de l’automate sur w […]
- [Algorithme de Gloushkov](https://complex-systems-ai.com/theorie-des-langages/algorithme-de-gloushkov/): Théorie des langages Page d’accueil Wiki Difficulté Facile 25% Algorithme de Gloushkov L’algorithme de Gloushkov construit un automate non-déterministe acceptant l’ensemble des mots décrit par une expression rationnelle. Le nombre d’états de l’automate est proportionnelle à la taille de l’expression. Les grandes étapes de l’algorithme de Gloushkov partant d’une expression rationnelle E sont les suivantes : Transformer l’expression E en une nouvelle expression E’ où chaque lettre apparaît au plus une fois dans E’. Construire un automate A’ acceptant l’ensemble des mots décrit par E’ Transformer A’ en un automate A acceptant l’ensemble des mots décrit par E en remplaçant les […]
- [Probabilité d'atteinte d'un état](https://complex-systems-ai.com/processus-de-markov/probabilite-datteinte-dun-etat/): Processus de Markov Page d’accueil Wiki DIfficulté Moyen 50% Probabilité d’atteinte d’un état La probabilité d’atteinte d’un état et par extension le temps d’atteinte d’un état désigne le nombre de temps avant d’atteindre un état de la chaine de Markov. (Xn)n désigne une chaîne de Markov homogène d’espace d’états X fini ou dénombrable de matrice de transition Q : on pourra interpréter Xn comme modélisant l’état d’un système à l’instant n. La loi initiale de la chaîne (Xn) ayant été fixée, seuls interviennent dans l’étude de l’évolution de la chaîne les états susceptibles d’être atteints. On pose Xa = {x ∈ […]
- [Loi invariante et comportement asymptotique](https://complex-systems-ai.com/processus-de-markov/loi-invariante-et-comportement-asymptotique/): Processus de Markov Page d’accueil Wiki Difficulté Moyen 50% Loi invariante et comportement asymptotique Nous cherchons à comprendre la comportement asymptotique d’une chaine de Markov homogène. C’est à dire la limite des probabilités de transition Qn(i,j) quand n devient très grand (la loi invariante). Idée Nous cherchons à répondre à la question suivante : « Quelle est la probabilité qu’après npas, la chaîne de Markov soit dans un état donné ? ». Prenons la matrice de transition P suivante : Supposons qu’aucune des machines n’est en panne le premier jour. Alors nous avons comme vecteur initial (1, 0), pour calculer la répartition […]
- [Automate à pile](https://complex-systems-ai.com/theorie-des-langages/automate-a-pile/): Théorie des langages Page d’accueil Wiki Difficulté Moyen 50% Automate à pile Les langages hors-contexte, décrits par des grammaires hors-contexte, sont reconnus (acceptés) par des automates à pile. De façon informelle, un automate à pile est un automate fini auquel on a ajouté une pile de capacité illimitée initialement vide. L’exécution d’un automate à pile sur un mot donné est semblable à celle d’un automate fini. Toutefois, à chaque étape, l’automate à pile consulte le sommet de sa pile et le remplace éventuellement par une suite de symboles. Un automate à pile est un quintuplet A = (T, P, Q, M, […]
- [Minimisation d'un AFD](https://complex-systems-ai.com/theorie-des-langages/minimisation-dun-afd/): Théorie des langages Page d’accueil Wiki Difficulté Moyen 50% Minimisation d’un AFD Théorème de Myhill-Nérode (minimisation d’un AFD). Soit L un langage rationnel. Parmi tous les AFD reconnaissant L, il en existe un et un seul qui a un nombre minimal d’états. Avant de minimiser un AFD, il faut le compléter, c’est à dire rajouter un état poubelle comme l’état R sur le schéma ci-dessous. L’algorithme de minimisation est le suivant : Exemple Reprenons l’exemple de l’AFD ci-dessus. Il est bien déterministe comme le montre la table de transition. Regardons la table de transition à l’étape 3 :   a b […]
- [Construction de Thompson](https://complex-systems-ai.com/theorie-des-langages/construction-de-thompson/): Théorie des langages Page d’accueil Wiki Difficulté Moyen 50% Construction de Thompson L’algorithme de Thompson ou construction de Thompson permet de construire un automate non-déterministe avec epsilon-transition à partir d’une expression régulière. L’automate se construit récursivement à partir de motifs de base : Les éléments unitaires comme ∅, ε et a sont reconnus par On considère les opérateurs de l’expression régulière R selon l’ordre d’extériorité décroissant. L’opérateur le plus extérieur permet de découper R en R1 | R2 , R1.R2 ou R1*  qui sont reconnus par Voici un exemple de construction avec l’expression (a|b)(a∗|ba∗|b∗)∗ On commence la récursion par la création […]
- [Politique de cookies (UE)](https://complex-systems-ai.com/politique-de-cookies-ue/)
- [Test de Dickey-Fuller](https://complex-systems-ai.com/prediction-forecasting/dickey-fuller/): Forecasting Page d’accueil Wiki Test de Dickey-Fuller Le test de Dickey-Fuller est un moyen de déterminer si le processus (série temporelle) a une racine unitaire. Bases Nous considérons le processus stochastique de forme où |φ| ≤ 1 et εi est un bruit blanc. Si |φ| = 1, on a ce qu’on appelle une racine unitaire. En particulier, si φ = 1, on a une marche aléatoire (sans dérive), qui n’est pas stationnaire. En fait, si |φ| = 1, le processus n’est pas stationnaire, alors que si |φ| < 1, le processus est stationnaire. Nous ne considérerons pas le cas où |φ| […]
- [Test de Pesaran-Timmermann](https://complex-systems-ai.com/prediction-forecasting/pesaran-timmermann/): Forecasting Page d’accueil Wiki Test de Pesaran-Timmermann Le test de Pesaran-Timmermann détermine si une prévision permet de prédire correctement le changement de direction d’une série chronologique. C’est à dire sa précision directionnelle. Description Pour toute série temporelle ti comportant n éléments, nous définissons d’abord Supposons maintenant que nous ayons une série chronologique yi avec n éléments qui est prévue par zi et définissons Sous l’hypothèse nulle selon laquelle z ne prévoit pas la direction du changement de y (c’est-à-dire le signe de yi), nous avons la statistique de test suivante Le test de Pesaran-Timmermann est un test unilatéral dans lequel la […]
- [Test de Diebold-Mariano](https://complex-systems-ai.com/prediction-forecasting/diebold-mariano/): Forecasting Page d’accueil Wiki Test de Diebold-Mariano et HLN Voici en détail le test de Diebold-Mariano et la mesure de Harvey, Leybourne, and Newbold. Bases Supposons que nous ayons deux prévisions f1, …, fn et g1, …, gn pour une série chronologique si y1, …, yn et que nous voulions voir quelle prévision est la meilleure, dans le sens où elle a la meilleure précision prédictive. L’approche évidente consiste à sélectionner la prévision qui présente la mesure d’erreur la plus petite en fonction de l’une des mesures d’erreur décrites dans Erreurs de prévision. Mais nous devons aller plus loin et déterminer […]
- [Méthode multiplicative de Holt-Winters](https://complex-systems-ai.com/prediction-forecasting/holt-winters/): Forecasting Page d’accueil Wiki Méthode multiplicative de Holt-Winters Voici comment fonctionne la méthode multiplicative de Holt-Winters ou triple smoothing. Lissage exponentiel simple / Exponential Smoothing Dans le lissage exponentiel simple (alias simple), la valeur prévue au temps i+1 est basée sur la valeur au temps i et la valeur prévue au temps i (et donc indirectement sur toutes les valeurs temporelles précédentes). En particulier, pour certains α où 0 ≤ α ≤ 1, pour tout i > 1, on définit Notez que nous n’incluons pas le temps i = 1 dans les calculs de MAE et MSE. En algèbre simple, cette […]
- [Erreurs de forecasting](https://complex-systems-ai.com/prediction-forecasting/erreurs-de-forecasting/): Forecasting Page d’accueil Wiki Erreurs de Forecasting Voici les principales mesures pour mesurer les erreurs de forecasting : Mesure dépendant de l’échelle : MAE, MDAE, MSE, RMSE En pourcentage : MAPE, sMAPE, MASE, sMdAPE En relatif : MRAE, MdRAE, RelMAE U-statistic Mesures dépendants de l’échelle Nous utilisons la terminologie suivante : si y1, …, yn représente une série temporelle, alors ŷi représente la ième valeur prévue, où i ≤ n. Pour i ≤ n, la ième erreur ei (alias résiduel) est alors Notre objectif est de trouver une prévision qui minimise les erreurs. Un certain nombre de mesures sont couramment utilisées […]
- [Forecasting avec AutoGluon Amazon](https://complex-systems-ai.com/prediction-forecasting/forecasting-autogluon/): Forecasting Page d’accueil Wiki Forecasting de série temporelle avec AutoGluon Introduction à la bibliothèque Multimodale AutoML d’Amazon AutoGluon avec un problème de prévision de séries chronologiques. Introduction à AutoGluon AutoGluon est une bibliothèque python multimodale open source pour AutoML, lancée par Amazon. Construite sur PyTorch, la bibliothèque utilise des modèles de pointe (SOTA) pour obtenir les modèles les plus performants pour divers problèmes d’apprentissage automatique. Équipé de modèles SOTA Deep Learning, AutoGluon propose des solutions à des problèmes tels que la classification d’images, la détection d’objets, la prédiction de texte, la segmentation d’images, la prévision de séries chronologiques et bien plus […]
- [Validation croisée pour séries temporelles](https://complex-systems-ai.com/prediction-forecasting/validation-croisee/): Forecasting Page d’accueil Wiki Validation croisée (cross-validation) pour les séries temporelles Dans ce tutoriel, nous allons expliquer le principe de validation croisée durant l’apprentissage d’une série temporelle. Principe L’analyse des séries chronologiques représente une approche fondamentale dans le domaine des statistiques et de l’apprentissage automatique, visant à comprendre et à prédire les modèles de données qui évoluent au fil du temps. Compte tenu des caractéristiques uniques des données de séries chronologiques, notamment les tendances, la saisonnalité et l’autocorrélation, les techniques traditionnelles de validation croisée ne parviennent souvent pas à fournir des estimations de performances précises et fiables. Pour relever ces défis, […]
- [PyTimeTK](https://complex-systems-ai.com/prediction-forecasting/pytimetk/): Forecasting Page d’accueil Wiki PyTimeTK la librairie pour l’analyse de séries temporelles Dans ce tutoriel, nous allons montrer comment utiliser la librairie python PyTimeTK pour analyser des données de type série temporelle. PyTimeTK, une librairie optimisée L’analyse des séries chronologiques est fondamentale dans de nombreux domaines, des prévisions commerciales à la recherche scientifique. Bien que l’écosystème Python propose des outils tels que pandas, ils peuvent parfois être verbeux et ne pas être optimisés pour toutes les opérations, en particulier pour les agrégations et visualisations complexes basées sur le temps. PytimeTK offre un mélange de facilité d’utilisation et d’efficacité de calcul et […]
- [AUC et ROC](https://complex-systems-ai.com/apprentissage-supervise/auc-et-roc/): Apprentissage supervisé Page d’accueil Wiki Courbe AUC et ROC, interprétation et multiclasse Ce tutoriel présente la courbe AUC et ROC ainsi que la manière d’interpréter les résultats. Le cas multiclasse est aussi présenté. Mesures de performance En Machine Learning, la mesure des performances est une tâche essentielle. Ainsi lorsqu’il s’agit d’un problème de classification, on peut compter sur une Courbe AUC – ROC. Lorsque nous devons vérifier ou visualiser les performances du problème de classification multi-classe, nous utilisons la courbe AUC (Area Under The Curve) ROC (Receiver Operating Characteristics). Il s’agit de l’une des mesures d’évaluation les plus importantes pour vérifier […]
- [Matrice de confusion](https://complex-systems-ai.com/apprentissage-supervise/matrice-de-confusion/): Apprentissage supervisé Page d’accueil Wiki Matrice de confusion, multiclasse et biais Ce tutoriel présente la matrice de confusion, son utilisation dans le cadre d’une classification multiclasse et les biais qui peuvent être mal perçu lors de la discussion des résultats. Matrice de confusion 2×2 Une matrice de confusion permet de représentation les résultats d’une classification binaire. Les Vrais Positifs, les Faux Positifs, les Vrais Négatifs et les Faux Négatifs. Les éléments en bleu sont ceux correctement prédit (Y chapeau), et ceux en rouge incorrectement. Voyons comment construire une matrice de confusion et comprendre ses terminologies. Considérons que nous devons modéliser un […]
- [CART régression et classification](https://complex-systems-ai.com/apprentissage-supervise/cart-regression/): Apprentissage supervisé Page d’accueil Wiki CART régression et classification : utilisation de l’arbre de décision Voici un tutoriel pour l’implémentation de CART Régression et de CART Classification. Comme cela a été expliqué, les arbres de décision sont l’approche d’apprentissage supervisé non paramétrique. En plus de la classification avec des données continues sur la cible, on retrouve aussi souvent des cas avec des données discrètes sur la cible appelés régression. Dans la régression, le moyen le plus simple peut être d’utiliser la régression linéaire pour résoudre ce cas. Cette fois, la manière de résoudre le cas de régression utilisera un arbre de […]
- [Détection des anomalies des séries temporelles](https://complex-systems-ai.com/prediction-forecasting/detection-des-anomalies/): Forecasting Page d’accueil Wiki Détection des anomalies dans les séries temporelles Ce tutoriel répond à la problématique de la détection des anomalies en préprocessing pour le forecasting des séries temporelles. Contexte Lors de l’analyse des données de séries chronologiques, nous devons nous assurer des valeurs aberrantes, tout comme nous le faisons pour les données statiques. Si vous avez travaillé avec des données à quelque titre que ce soit, vous savez à quel point les valeurs aberrantes sont pénibles pour un analyste. Ces valeurs aberrantes sont appelées « anomalies » dans le jargon des séries chronologiques. Le code de Aayush Bajaj, à […]
- [Pipeline Forecasting](https://complex-systems-ai.com/prediction-forecasting/pipeline-forecasting/): Forecasting Page d’accueil Wiki Pipeline Forecasting avec comparaison de méthodes Dans ce tutoriel, vous apprendrez une pipeline forecasting : comment comparer et sélectionner des modèles de séries temporelles en fonction des performances prédictives. Aperçu Dans la première partie, vous découvrirez de nombreux modèles de séries chronologiques. Cette partie est divisée en trois parties : modèles de séries chronologiques classiques, modèles supervisés, et des modèles basés sur l’apprentissage profond. Dans la deuxième partie, vous verrez une application à un cas d’utilisation dans lequel vous construirez quelques modèles de séries chronologiques pour la prévision boursière et vous apprendrez quelques techniques de modélisation de […]
- [Prédiction Forecasting 101](https://complex-systems-ai.com/prediction-forecasting/): Théories Page d’accueil Wiki I. Forecasting statistique / stochastique Modèle linéaire : ARIMA ARMA ARMAX SARIMA MSARIMA Q-GARCH ST-GARCH ABS-GARCH GARCH-M E-GARCH T-GARCH EWMA ARFIMA MLR Modèle non-linéaire : TAR STAR LSTAR ESTAR SETAR Markov switching  Modèle multivarié: VAR VMA VARMA ARX SSARIMA Exponentional Smoothing : ES Holt-Winters HWT Autres regressifs : DSHW TBATS FASSTER II. Basé sur les Etats Transformation de la série temporelle : HMM Filtre de Kalman Filtre de particules Monte Carlo Bootstraping Importance sampling Modèle univarié : ARIMAx Transfert functions Exponential smoothing Structural unobserved components Hodrick-Prescott filter Spline smoothing Modèle mutlivarié : VARIMAx Structural VAR VECM Dynamic […]
- [Apprentissage Supervisé 101](https://complex-systems-ai.com/apprentissage-supervise/): Théories Page d’accueil Wiki I. Apprentissage Supervisé basés sur la Logique Arbre de décision : ID3 C4.5 PART CART ID2of3 C5.0T AOT SP-Lime k-Lime Tree Merging Decision Tree Extract Soft Decision Tree Règles de décision : Disjonctive normal form Rule induction 1R AntMiner+ cAntMinerPB RIPPER AQ family CN2 Re-RX C5.0R Mesure de qualité des règles : J-measure Generalized Additive Models (GAM) II. Apprentissage statistique Naive Bayesian Networks Bayesian Networks Linear Discriminate Analysis Factorized Asymptotic Bayesian Bayesian Or’s of And’s BOA ORC Two level boolean rules SLIM TILM PILM RiskSLIM Ordered Rules for Classification Bayesian List Machine BLM Bayesian Rule List BRL […]
- [3 Mesures : Impureté de Gini, entropie et erreur de classification](https://complex-systems-ai.com/analyse-des-donnees/gini-entropie-et-erreur/): Analyse des données Page d’accueil Wiki La mesure d’impureté (de Gini) implémente des arbres de décision binaires et les trois mesures d’impuretés ou critères de division couramment utilisés dans les arbres de décision binaires sont l’impureté de Gini (IG), l’entropie (IH) et l’erreur de classification (IE). Impureté de Gini Utilisée par l’algorithme CART (arbre de classification et de régression) pour les arbres de classification, l’impureté Gini est une mesure de la fréquence à laquelle un élément choisi au hasard dans l’ensemble serait incorrectement étiqueté s’il était étiqueté de manière aléatoire en fonction de la distribution des étiquettes dans le sous-ensemble. Mathématiquement, […]
- [Tutoriel Arbre de décision](https://complex-systems-ai.com/analyse-des-donnees/arbre-de-decision/): Analyse des données Page d’accueil Wiki Arbre de décision pour l’analyse des données Un arbre de décision est une approche d’apprentissage supervisé non paramétrique et peuvent être appliqués à la fois aux problèmes de régression et de classification. Conformément à l’analogie avec l’arbre, les arbres de décision mettent en œuvre un processus de décision séquentiel. À partir du nœud racine, une fonctionnalité est évaluée et l’un des deux nœuds (branches) est sélectionné.  Chaque nœud de l’arborescence est essentiellement une règle de décision. Cette procédure est répétée jusqu’à ce qu’une feuille finale soit atteinte, qui représente normalement la cible. Les arbres de […]
- [Exercices Corrigés](https://complex-systems-ai.com/exercices-corriges/): Page d’accueil Cours de Méthodologies Exercices Corrigés – Banque du site Complex-systems-ai Cette page regroupe les exercices corrigés du site. Mathématiques Système logique : Algèbre de Boole et les tableaux de karnaugh Optimisation Combinatoire Programmation logique : Programmation logique par contraintes Optimisation combinatoire : Tutoriel du Branch and Bound sur du LP en nombre entier Tutoriel de Branch and cut (cutting plane, Gomory) Synopsis de Cours – Contrôles – Projets : Projet : Smart City 2030 Projet : The Truman Show Programmation Linéaire Résolution Simplexe : Modélisation Forme primale Dual et écart complémentaire Cas particuliers Synopsis de Cours – Contrôles – […]
- [9 Exercices Corrigés Lego Mindstorms](https://complex-systems-ai.com/algorithmique/exercices-lego-mindstorms/): Algorithmique Page d’accueil Wiki Exercices corrigés sur le logiciel de robotique Lego Mindstorms Cette série d’exercices corrigés sur Lego Mindstorms permet de se familiariser avec des logiciels de programmation et de robotique. Exercice 1 Dans cet exercice, vous allez apprendre à programmer le robot pour effectuer des mouvements simples. Bien comprendre comment faire effectuer ses mouvements à votre robot est primordial car il aura constamment besoin de les effectuer dans les exercices suivants. En vous aidant du guide de programmation qui vous a été fourni, veuillez programmer votre robotpour qu’il effectue les actions suivantes : avancer pendant une durée de 3 […]
- [3 Exercices Corrigés Concurrence](https://complex-systems-ai.com/analyse-logicielle/exercices-concurrence/): Analyse Logicielle Page d’accueil Wiki Exercices corrigés sur les contrôles de concurrence Les problèmes de concurrence sont fréquents dans une base de données. Le verrouillage et l’estampillage sont deux techniques pour les éviter. Voici des exercices corrigés à ce sujet. Préambule Expression des contraintes————————— 0. Préambule PL/SQLSQL: – Déclaratif donc pas de structures de contrôle (boucles, conditions,…)– Données+opérations ensemblistes=> Peu d’applications réalisables par simple suite de requête SQL; besoin d’enrichir SQL avec des capacités procédurales.3 possibilités– Embedded SQL (PRO*C…)– API de communication (SQL-CLI…)– Langage dédié (PL/SQL…) Avantage langages dédiés: Procédures exécutées côté serveur -> Seuls les résultats sont retournés au client […]
- [2 Exercices Corrigés Opérateurs Relationnels](https://complex-systems-ai.com/analyse-logicielle/operateurs-relationnels/): Analyse Logicielle Page d’accueil Wiki Exercices corrigés sur les opérateurs relationnels Cette page présente des cas d’usages pour opérateurs relationnels via des exercices corrigés. Rappel de cours On veut joindre deux relations R et S (non triées). R est plus petite que S |R| = Nbre de page sur disque de R, ||R|| = Nbre de tuples de R, M = Nbre de page mémoire disponibles (on suppose que 3 pages mémoire sont allouées pour les I/O Algorithme de jointure par sort-merge (SMJ) Condition sur la mémoire Coût en I/O M > |R|+|S| Cout = |R|+|S| |R|+|S| > M > sqr(|R|+|S|) […]
- [2 Exercices Corrigés Indexation](https://complex-systems-ai.com/analyse-logicielle/exercices-indexation/): Analyse Logicielle Page d’accueil Wiki Exercices Corrigés – Indexation de clés dans une base de données Les index des bases de données sont traités par indexation afin de trouver au plus vite leur enregistrement dans une base de données. Voici une série d’exercice traitant ce problème. Le cours sur les arbres binaires de recherche traite aussi ce problème en théorie des graphes. Exercice indexation simple Rappelons quelques définitions : Index = table permettant d’associer à une clé d’article (donnée d’application) l’adresse relative de cet article (position dans le fichier) Méthodes d’accès indexé = façon d’aller chercher des articles (données d’application) dans […]
- [3 Exercices Corrigés Hachage](https://complex-systems-ai.com/analyse-logicielle/exercices-hachage/): Analyse Logicielle Page d’accueil Wiki Exercices Corrigés sur le Hachage dans une base de données Le Hachage est particulier au logiciel utilisé, les exercices corrigés suivant explorent les techniques les plus utilisées. Introduction sur le Hachage Les articles d’un fichier aléatoire (on parle également de fichier haché) sont répartis dans des paquets composés d’une ou plusieurs pages disque. Une fonction de hachage h associe à une valeur de clé (discriminante ou non) un entier représentant un numéro de paquet. Tous les articles dont la valeur de clé est telle que la fonction h associe un même numéro de paquet sont stockés […]
- [3 SQL (Vues, intégrité et droits)](https://complex-systems-ai.com/analyse-logicielle/exercices-sql-vues/): Analyse Logicielle Page d’accueil Wiki Exercices Corrigés en SQL – Intégrité, vues et confidentialité SQL sur l’intégrité, les vues et la confidentialité, chaque exercice corrigés explore un de ces concepts. Enoncé L’exemple utilisé est celui d’une base de données « bibliothèque » gérant des lecteurs, des livres identifiés par un numéro et appartenant à une certaine catégorie d’ouvrages (roman policier, roman d’aventures, etc.) et les prêts des livres. LIVRE(Cote,Titre,Auteur,Catégorie) LECTEUR(Numéro,Nom,Adresse,Consommation) PRET(Cote,NumLecteur,DateEmprunt,DateRetour,DateRelance) Exercice 1 Définir en SQL2 les contraintes d’intégrité suivantes :  La consommation d’un lecteur est Forte, Moyenne ou Faible (contrainte de domaine)  Tout prêt doit être fait à un lecteur existant dans la […]
- [11 Exercices corrigés Algèbre Relationnelle](https://complex-systems-ai.com/analyse-logicielle/ex-algebre-relationnelle/): Analyse logicielle Page d’accueil Wiki Exercices corrigés Algèbre Relationnelle Cette page contient des exercices corrigés en Algèbre Relationnelle. Exercice 1 Nous allons étudier l’algèbre relationnelle à travers un exemple de base de données et un ensemble de requêtes exprimées sur cette base de données. La base de données considérée est décrite par le schéma suivant: JOUEUR(Nom,Prénom,Age,Nationalité) RENCONTRE(NomGagnant,NomPerdant,LieuTournoi,Année,Score) GAIN(NomJoueur, LieuTournoi,Année,Rang,Prime,NomSponsor) SPONSOR(Nom,LieuTournoi,Année,Adresse,MtContribution) La relation JOUEUR contient tous les joueurs licenciés. La relation RENCONTRE décrit pour chaque tournoi, l’ensemble π des rencontres opposant deux joueurs (un gagnant et un perdant). La relation décrit aussi le score réalisé à chaque rencontre. Les hypothèses suivantes sont […]
- [Algèbre relationnelle](https://complex-systems-ai.com/analyse-logicielle/algebre-relationnelle/): Analyse logicielle Page d’accueil Wiki Algèbre relationnel Les opérateurs de base de l algèbre relationnelle sont des opérateurs unaires ou binaires appliqués à des relations. L’application de chaque opération produit en résultat une nouvelle relation. On distingue les opérateurs suivants: restriction, projection, jointure, union, différence, intersection, division.  Définitions des opérateurs de base  (1) Restriction d’une relation : La restriction est une opération unaire qui sélectionne un ensemble de lignes (n-uplets) d’une relation, en fonction d’un critère de sélection (prédicat ou expression logique de prédicats). Le résultat d’une restriction est une relation de même schéma que la relation initiale.  (2) Projection d’une […]
- [17 Exercices corrigés SQL requêtes](https://complex-systems-ai.com/analyse-logicielle/exercices-sql-requetes/): Analyse logicielle Page d’accueil Wiki Exercices corrigés SQL requêtes Ces exercices corrigés de requêtes SQL sont pour des débutants à confirmés. Exercice flashback sur modèle entité-association Une agence immobilière veut gérer son parc immobilier. Elle veut stocker dans sa base tout logement voué à la location. Pour cela, elle attribue un identifiant à chaque logement, son adresse, sa superficie et le loyer. Un logement se situe dans un quartier auquel on attribue un numéro et un libellé. A chaque logement correspond un type de logement auquel sont associées des charges forfaitaires. Par ailleurs, l’agence stocke également les locataires de son parc. […]
- [6 Exercices corrigés SQL débutant](https://complex-systems-ai.com/analyse-logicielle/exercices-sql-debutant/): Analyse logicielle Page d’accueil Wiki Exercices corrigés SQL débutant Ces exercices corrigés de SQL débutant s’adressent comme son nom l’indique à des non initiés au langage SQL. D’autres exercices traiteront plus en profondeur des bases de données. Enoncé La base de données utilisée modélise une activité de location de voitures entre particuliers. Les informations conservées dans la base sont les informations concernant les voitures, les propriétaires de ces voitures, les clients et les locations effectuées. Il s’agit de la base de données utilisée comme exemple durant le cours (dans sa version complète… certains attributs ont été ajoutés par rapport à la […]
- [6 Exercices corrigés Modèle Entité Association](https://complex-systems-ai.com/analyse-logicielle/exo-entite-association/): Analyse logicielle Page d’accueil Wiki Exercices corrigés Modèle Entité Association Les exercices corrigés suivants concernent le modèle Entité Association, la construction, la modélisation et la compréhension à partir de cas d’usage. Exercice 1 Ci-dessous le diagramme E/A représentant les visites dans un centre médical. Répondez aux questions suivants (strictement en fonction de ce qui est indiqué dans le schéma). 1. Un patient peut-il effectuer plusieurs consultations ? 2. Un médecin peut-il recevoir plusieurs patients dans la même consultation ? 3. Peut-on prescrire plusieurs médicaments dans la même consultation ? 4. Deux médecins différents peuvent ils prescrire le même médicament ? Solution […]
- [9 Exercices corrigés Algorithme sous LARP](https://complex-systems-ai.com/algorithmique/exercices-corriges-larp/): Algorithmique Page d’accueil Wiki Exercices corrigés sous le logiciel LARP Les exercices corrigés suivants concernent la création d’algorithme selon la structure logigramme du logiciel LARP. Pour bien débuter Rédige le logigramme permettant le fonctionnement suivant : Une barrière s’ouvre à l’aide d’une télécommande à distance. Le système utilise un capteur infrarouge pour savoir si la voiture est passée. La barrière se referme quand la voiture est passée Un gyrophare s’allume lorsque la barrière est ouverte et s’éteint lorsque la barrière est fermée. Utilise uniquement les actions et événements indiqués ci-dessous : Solution Exercice 1 Défi 1: trouver le centre d’un cercle. Rédiger l’organigramme […]
- [12 Exercices corrigés SCRATCH](https://complex-systems-ai.com/algorithmique/exercices-corriges-scratch/): Algorithmique Page d’accueil Wiki Exercices corrigés langage SCRATCH Les exercices corrigés suivants concernent la création d’algorithme selon le langage SCRATCH. Exercice 1 Utiliser le projet chemin_1.sb2 Compléter le script du lutin ‘balle’ pour lui permettre d’atteindre la cible verte. S’il est bloqué, le lutin demande s’il doit se tourner à droite (réponse ‘D’) ou à gauche (réponse ‘G ‘). Le lutin se tourne alors dans la direction indiquée et recommence à avancer si cela est possible. Vous utiliserez les blocs de commande suivants : Solution Exercice 2 Que fait le programme ci-dessous ? Solution Si la valeur est positive, il affiche le nombre, sinon […]
- [Page d'accueil](https://complex-systems-ai.com/): Bienvenue sur la page d’accueil. Les théories et algorithmes de l’intelligence artificielle, de l’apprentissage machine et des bases mathématiques. Cliquez sur une section pour afficher toutes les théories liées. I. Maths Logique mathématique Recherche opérationnelle : Optimisation combinatoire Optimisation linéaire Problème de planification Problème de recherche de chemin Problème de flot II. Analyse systémique Aide à la décision Algorithmique Analyse logicielle Problèmes industriels et réduction polynomiale Théorie des graphes Théorie des jeux Théorie des langages Processus stochastique III. Analyse des données Analyse des données (dimensions et classifications) Analyse descriptive Inférence statistique Corrélation et régressions Data visualization IV. Apprentissage automatique Apprentissage supervisé Partitionnement […]
- [RGPD](https://complex-systems-ai.com/rgpd/): Qui sommes-nous ? L’adresse de notre site est : https://complex-systems-ai.com/. Commentaires Quand vous laissez un commentaire sur notre site, les données inscrites dans le formulaire de commentaire, ainsi que votre adresse IP et l’agent utilisateur de votre navigateur sont collectés pour nous aider à la détection des commentaires indésirables. Une chaîne anonymisée créée à partir de votre adresse e-mail (également appelée hash) peut être envoyée au service Gravatar pour vérifier si vous utilisez ce dernier. Les clauses de confidentialité du service Gravatar sont disponibles ici : https://automattic.com/privacy/. Après validation de votre commentaire, votre photo de profil sera visible publiquement à coté de votre […]
- [Codage de Huffman](https://complex-systems-ai.com/algorithmique/codage-de-huffman/): Algorithmique Page d’accueil Wiki Codage de Huffman Le codage de Huffman est un procédé très utilisé en compression de données. Il sert à encoder un texte en binaire, en utilisant pour chaque lettre un nombre de bits dépendant du nombre de fois où la lettre est présente : plus la lettre apparaît, plus le nombre de bits est petit. Ainsi, le nombre total de bits utilisés pour encoder le texte est réduit par rapport à un codage ASCII standard qui utilise huit bits pour chaque lettre. Quand il s’agit de transmettre de l’information sur un canal non bruité, l’objectif prioritaire est […]
- [22 Exercices corrigés Algorithme Diviser pour régner](https://complex-systems-ai.com/algorithmique/ex-diviser-pour-regner/): Algorithmique Page d’accueil Wiki Exercices corrigés avec algorithme en diviser pour régner Les exercices corrigés suivants concernent la création d’algorithme selon la structure du diviser pour régner (divide&conquer). Les algorithmes de type dichotomie seront aussi étudiés. Exercice 1 On va jouer au jeu du “plus petit, plus grand”. Le but est de deviner un nombre compris entre 1 et n (entier). On considère que l’algorithme prend en entrée la valeur de n et du nombre x à deviner, et qu’il retourne le nombre de coup pour trouver ce nombre. a – Réexprimez le problème de façon plus formel. b – Ecrire […]
- [20 Exercices corrigés algorithme récursif](https://complex-systems-ai.com/algorithmique/exercices-algorithme-recursif/): Algorithmique Page d’accueil Wiki Exercices corrigés : algorithme récursif Les exercices corrigés suivants concernent le principe d’algorithme récursif, par exemple Fibonacci, les tours de Hanoï et bien d’autres cas mathématiques. Les exercices comprennent la récursion simple, la récursion terminale, la récursion croisée ou récursion mutuelle, et le principe de mémoïsation (pour plus de détail sur ce dernier point merci d’aller voir le principe de programmation dynamique). Exercice 1 Réécrire les algorithmes suivants sous forme récursive sous forme terminal quand c’est possible. Un dernier pour la route. Cette fois il faut comprendre ce qu’il fait avant de le rendre récursif terminal ! […]
- [6 Exercices corrigés algorithmes de tri](https://complex-systems-ai.com/algorithmique/exercices-algorithmes-de-tris/): Algorithmique Page d’accueil Wiki Exercices corrigés sur les algorithmes de tri Les exercices corrigés suivants concernent les algorithmes de tri : Tri par sélection, tri par insertion, tri à bulles, tri cocktail, tri rapide et tri fusion. Les tris itératifs : tri par sélection Sur un tableau de n éléments (numérotés de 0 à n-1), le principe du tri par sélection est le suivant : rechercher le plus petit élément du tableau, et l’échanger avec l’élément d’indice 0 ; rechercher le second plus petit élément du tableau, et l’échanger avec l’élément d’indice 1 ; continuer de cette façon jusqu’à ce que […]
- [12 Exercices corrigés sur les structures algorithmiques](https://complex-systems-ai.com/algorithmique/ex-structures-algorithmiques/): Algorithmique Page d’accueil Wiki Exercices corrigés sur les structures algorithmiques Les exercices corrigés suivants concernent les structures algorithmiques, les structures de contrôle et les structures de données. L’objectif est de proposer les structures les plus adaptées à l’énoncé. Exercice 1 Considérons les algorithmes ci-dessous.(a) Quel sera le contenu des variables a, b et éventuellement c après leur exécution ?(b) Dans chacun des cas ci-dessus, y a-t-il des lignes inutiles, et si oui lesquelles ? Solution Dans la plupart des langages de programmation le dernier exemple (1.6) ne générera pas d’erreur mais le résultat ne sera pas souvent ’3’. Selon le langage, […]
- [Newsletter](https://complex-systems-ai.com/newsletter/): [newsletter]
- [Google PageRank et Chaîne de Markov](https://complex-systems-ai.com/processus-de-markov/google-pagerank-et-chaine-de-markov/): Processus de Markov Page d’accueil Wiki L’algorithme de Google PageRank, qui est le centre de la recherche Google, est basé sur les chaînes de Markov, en voici son explication (pour la version basique). La naissance de Google PageRank Avec 1 milliard de sites sur internet, c’est impossible à analyser leurs contenus. Pourtant, l’internet n’est pas une collection de textes indépendants mais un immense hypertexte : les pages se citent mutuellement. En considérant le web comme un graphe et en tenant compte les liens entre les pages, on peut faire des choses intéressantes. Les premières personnes qui ont abordé ce point de […]
- [Les techniques de réduction de dimension](https://complex-systems-ai.com/analyse-des-donnees/les-techniques-de-reduction-de-dimension/): Analyse des données Page d’accueil Wiki Un jeu de données de grande dimension est un jeu de données qui comporte un grand nombre de colonnes (ou de variables). Un tel ensemble de données présente de nombreux défis mathématiques ou informatiques. L’objectif est de réduire les dimensions avec des techniques de réduction de dimension. Techniques de réduction de dimension basés sur le PCA La bonne nouvelle est que les variables (ou appelées caractéristiques) sont souvent corrélées – les données de grande dimension sont dominées « superficiellement » par un petit nombre de variables simples. Nous pouvons trouver un sous-ensemble de variables pour représenter le […]
- [Métriques pour la classification](https://complex-systems-ai.com/analyse-des-donnees/metriques-pour-la-classification/): Analyse des données Page d’accueil Wiki Après avoir effectué l’exploration des données, la sélection et, bien sûr, la mise en œuvre d’un modèle et l’obtention de résultats sous forme de probabilité ou de classe, l’étape suivante consiste à déterminer l’efficacité du modèle basé sur des métriques pour la classification. Quelles métriques pour la classification ? Nous pouvons utiliser des métriques de performance de classification telles que Log-Loss, Accuracy, AUC (Area under Curve), etc. Un autre exemple de métrique pour l’évaluation des algorithmes d’apprentissage automatique est la précision, le rappel, qui peut être utilisé pour trier les algorithmes principalement utilisés par les […]
- [Sélection des colonnes](https://complex-systems-ai.com/analyse-des-donnees/selection-des-colonnes/): Analyse de données Page d’accueil Wiki Les ensembles de données modernes sont très riches en informations avec des données collectées à partir de millions d’appareils et de capteurs IoT. Cela rend les données de grande dimension et il est assez courant de voir des ensembles de données avec des centaines de fonctionnalités et il n’est pas inhabituel de les voir atteindre des dizaines de milliers. La sélection des colonnes / fonctionnalités est un élément très critique dans le flux de travail d’un Data Scientist. Lorsqu’ils présentent des données avec une dimensionnalité très élevée, les modèles s’étouffent généralement parce que Le temps […]
- [Nettoyage des données](https://complex-systems-ai.com/analyse-des-donnees/nettoyage-des-donnees/): Analyse des données Page d’accueil Wiki La sélection des fonctionnalités, le processus de recherche et de sélection des fonctionnalités les plus utiles dans un ensemble de données, est une étape cruciale du pipeline d’apprentissage automatique. Les fonctionnalités inutiles diminuent la vitesse d’apprentissage, diminuent l’interprétabilité du modèle et, surtout, diminuent les performances de généralisation sur l’ensemble de test. L’objectif est donc le nettoyage des données. Pipeline pour le nettoyage des données Le FeatureSelector inclut certaines des méthodes de sélection de fonctionnalités les plus courantes : Fonctionnalités avec un pourcentage élevé de valeurs manquantes Caractéristiques colinéaires (hautement corrélées) Fonctionnalités sans importance dans un modèle […]
- [Apprentissage d'ensembles](https://complex-systems-ai.com/analyse-des-donnees/apprentissage-densembles/): Analyse des données Page d’accueil Wiki Maintenant, supposons que vous ayez choisi le meilleur modèle possible pour un problème particulier et que vous vous efforciez d’améliorer encore sa précision. Dans ce cas, vous devrez appliquer des techniques d’apprentissage automatique plus avancées qui sont collectivement appelées apprentissage d’ensembles. Un ensemble est un ensemble d’éléments qui contribuent collectivement à un tout. Un exemple familier est un ensemble musical, qui mélange les sons de plusieurs instruments de musique pour créer une belle harmonie, ou des ensembles architecturaux, qui sont un ensemble de bâtiments conçus comme une unité. Dans les ensembles, le (tout) résultat harmonieux […]
- [Transformation des données et régression](https://complex-systems-ai.com/correlation-et-regressions/transformation-des-donnees-et-regression/): Corrélation et régressions Page d’accueil Wiki Voici un pipeline expliquant l’exploration des données, leur transformation pour normalisation et la régression (avec analyse de performance). Analyse, transformation et régression Plongeons maintenant dans l’autre catégorie d’apprentissage supervisé – la régression où la variable de sortie est continue et numérique. Il existe quatre types courants de modèles de régression : linéaire, au lasso, de crête (ridge regression), polynomiale. Exploration et préprocessing Ce projet vise à utiliser des modèles de régression pour prédire les scores de bonheur des pays en fonction d’autres facteurs « PIB par habitant », « Soutien social », Espérance de vie en bonne santé », « Liberté […]
- [Pipeline pour la classification](https://complex-systems-ai.com/analyse-des-donnees/pipeline-pour-la-classification/): Analyse des données Page d’accueil Wiki Cette page présente un pipeline pour la classification. C’est à dire le suivi d’un processus de l’exploration des données à la classification en passant par les modèles d’évaluation. Survol de la pipeline pour la classification L’apprentissage supervisé peut être subdivisé en algorithmes de classification et de régression. Le modèle de classification identifie la catégorie à laquelle appartient un objet, tandis que le modèle de régression prédit une sortie continue. Parfois, il existe une ligne ambiguë entre les algorithmes de classification et les algorithmes de régression. De nombreux algorithmes peuvent être utilisés à la fois pour […]
- [Comment gérer les données manquantes](https://complex-systems-ai.com/analyse-des-donnees/comment-gerer-les-donnees-manquantes/): Analyse des données Page d’accueil Wiki L’un des problèmes les plus courants auxquels j’ai été confronté dans le nettoyage des données/l’analyse exploratoire est la gestion des valeurs manquantes: comment gérer les données manquantes. Tout d’abord, comprenez qu’il n’y a AUCUNE bonne façon de traiter les données manquantes.  Comment gérer les données manquantes : la méthodologie Avant de passer aux méthodes d’imputation des données, nous devons comprendre la raison pour laquelle les données manquent. Manquant au hasard (MAR) : Manquant au hasard signifie que la propension d’un point de données à manquer n’est pas liée aux données manquantes, mais elle est liée […]
- [Analyse exploratoire de textes](https://complex-systems-ai.com/analyse-descriptive/analyse-exploratoire-de-textes/): Analyse descriptive Page d’accueil Wiki Représenter visuellement le contenu d’un document texte est l’une des tâches les plus importantes dans le domaine de l’exploration de texte (aussi dit analyse exploratoire de textes). En tant que data scientist ou spécialiste du NLP, non seulement nous explorons le contenu des documents sous différents aspects et à différents niveaux de détails, mais nous résumons également un seul document, montrons les mots et les sujets, détectons les événements et créons des scénarios. Cependant, il existe des écarts entre la visualisation des données non structurées (texte) et des données structurées. Par exemple, de nombreuses visualisations de […]
- [Normaliser Standardiser Redimensionner vos Données](https://complex-systems-ai.com/analyse-des-donnees/normaliser-standardiser-redimensionner-vos-donnees/): Analyse des données Page d’accueil Wiki Afin de pouvoir analyser vos données et de réaliser tout traitement de préprocessing ou de réduction, il est très important de bien normaliser, standardiser et redimensionner vos données. En voici les tutoriels. Tutoriel sur normaliser, standardiser et redimensionner vos données Avant de plonger dans ce sujet, commençons par quelques définitions. « Redimensionner » un vecteur signifie ajouter ou soustraire une constante, puis multiplier ou diviser par une constante, comme vous le feriez pour changer les unités de mesure des données, par exemple, pour convertir une température de Celsius en Fahrenheit. « Normaliser » un vecteur signifie le plus souvent […]
- [Tutoriel sur le t-SNE](https://complex-systems-ai.com/analyse-des-donnees/tutoriel-sur-le-t-sne/): Analyse des données Page d’accueil Wiki Après avoir réalisé une analyse descriptive des données, rempli les vides et sélectionner les premières colonnes. Il est important de continuer de réduire les dimensions, pour cela, ce tutoriel sur le t-SNE présente la réduction de dimensions par analyse non-linéaire. Tutoriel sur le t-SNE et réduction de dimensions non-linéaire La plupart des ensembles de données du monde réel ont de nombreuses fonctionnalités, parfois plusieurs milliers. Chacun d’eux peut être considéré comme une dimension dans l’espace des points de données. Par conséquent, le plus souvent, nous traitons des ensembles de données de grande dimension, où la […]
- [Analyse semi-automatique des données](https://complex-systems-ai.com/analyse-descriptive/analyse-semi-automatique-des-donnees/): Analyse descriptive Page d’accueil Wiki L’analyse exploratoire des données, également connue sous le nom d’EDA, est devenue un sujet de plus en plus brûlant en science des données. Comme son nom l’indique, il s’agit d’un processus d’essais et d’erreurs dans un espace incertain, dans le but de trouver des informations. Cela se produit généralement au début du cycle de vie de la science des données. Dans cette page, je présente un processus EDA semi-automatisé (analyse semi-automatique des données). L’analyse semi-automatique des données : connaître ses données J’utiliserai quatre bibliothèques principales : Numpy — pour travailler avec des tableaux ; Pandas – […]
- [Analyse de données sous Sweetviz](https://complex-systems-ai.com/analyse-descriptive/analyse-de-donnees-sous-sweetviz/): Analyse descriptive Page d’accueil Wiki L’analyse exploratoire des données (EDA) est une première étape essentielle dans la plupart des projets de science des données et consiste souvent à suivre les mêmes étapes pour caractériser un ensemble de données (par exemple, trouver les types de données, les informations manquantes, la distribution des valeurs, les corrélations, etc.). L’une des dernières est une nouvelle bibliothèque Python open-source appelée Sweetviz. Installation et lancement de Sweetviz Après l’installation de Sweetviz (en utilisant pip install sweetviz), chargez simplement les dataframes pandas comme vous le feriez normalement, puis appelez analyze(), compare() ou compare_intra(). import sweetvizimport pandas as pdtrain […]
- [Bonnes pratiques de l'analyse exploratoire des données](https://complex-systems-ai.com/analyse-descriptive/bonnes-pratiques-de-lanalyse-exploratoire-des-donnees/): Analyse descriptive Page d’accueil Wiki Cette page décrit les bonnes pratiques de l’analyse exploratoire des données : que faire avec un jeu de données afin d’en comprendre le contenu. Conseils et bonnes pratiques de l’analyse exploratoire des données (EDA) L’analyse exploratoire des données fait référence au processus critique consistant à effectuer des enquêtes initiales sur les données afin de découvrir des modèles, de repérer des anomalies, de tester des hypothèses et de vérifier des hypothèses à l’aide de statistiques récapitulatives et de représentations graphiques. C’est une bonne pratique de comprendre d’abord les données et d’essayer d’en tirer le maximum d’informations. L’EDA […]
- [Tutoriel sur la moyenne géométrique et harmonique](https://complex-systems-ai.com/analyse-descriptive/tutoriel-sur-la-moyenne-geometrique-et-harmonique/): Analyse descriptive Page d’accueil WIki Cette page montre plusieurs exemples sur les cas d’usage des différentes moyenne, notamment la moyenne géométrique et la moyenne harmonique. Moyenne arithmétique La moyenne arithmétique est nommée de manière appropriée : nous la trouvons en ajoutant tous les nombres de l’ensemble de données, puis en divisant par le nombre de nombres dans l’ensemble de données (afin de ramener la somme à l’échelle des nombres d’origine). 3 + 8 + 10 = 2121 ÷ 3 = 7Arithmetic mean = 7 Remarquez, ce que nous disons essentiellement ici est : si chaque nombre de notre ensemble de données était le même nombre, quel nombre devrait-il être pour avoir […]
- [2 Exercices corrigés analyse exploratoire des données](https://complex-systems-ai.com/analyse-descriptive/ex-analyse-exploratoire/): Analyse descriptive Page d’accueil Wiki Exercices Corrigés sur Analyse exploratoire des données Cette page présente deux exercices corrigés et détaillés avec le code python sur l’analyse exploratoire des données. Exercice 1 Considérons un échantillon aléatoire de finisseurs du marathon de New York en 2002. Cet ensemble de données se trouve dans le package UsingR. Chargez la bibliothèque, puis chargez l’ensemble de données nym.2002. library(dplyr) data(nym.2002, package="UsingR") Utilisez des boîtes à moustaches et des histogrammes pour comparer les temps d’arrivée des hommes et des femmes. Lequel des résumés  décrit le mieux la différence ? data(nym.2002, package="UsingR") male <- nym.2002 %>% filter(gender == […]
- [1 Exercice Corrigé de Branch and cut](https://complex-systems-ai.com/optimisation-combinatoire/exbranch-and-cut/): Optimisation Combinatoire Page d’accueil Wiki Cette page présente un exercice corrigé détaillé résolu par l’algorithme de branch and cut (aussi connu sous le nom de Gomory cutting plane). Branch and cut / Gomory cutting plane Exercice 1 Considérons le programme linéaire suivant : Résoudre par la méthode de Gomory le problème (les deux premières coupes). Solution Résolvons le problème relaxé en nombre réel. La solution est : L’algorithme de Gomory cutting plane prend la variable ayant la partie non entière la plus grande, ici x_1. Nous allons formuler une nouvelle contrainte en considérant seulement les restes fractionnaires de chaque coefficient : […]
- [5 Exercices corrigés de programmation logique par contraintes](https://complex-systems-ai.com/optimisation-combinatoire/exercices-corriges-de-programmation-logique-par-contraintes/): Optimisation Combinatoire Page d’accueil Wiki Programmation logique par contraintes Cette page présente des exercices corrigés détaillés du problème de programmation logique par contraintes, qui est un mélange naturel de la programmation logique et la programmation par contraintes. Exercice 1 On considère le puzzle suivant : Chaque région de la grille doit être remplie par un nombre entre 0 et 9 de sorte que les nombres dans deux régions adjacentes (verticalement ou horizontalement) soient différents à chaque fois qu’il y a quatre régions qui se rencontrent en un point (indiqué par un petit rond), la somme de leurs nombres soient égale à […]
- [1 Exercice corrigé Branch and Bound](https://complex-systems-ai.com/optimisation-combinatoire/exercice-corrige-branch-and-bound/): Optimisation Combinatoire Page d’accueil Wiki Cette page présente un exercice corrigé détaillé du problème de programmation linéaire résolu par l’algorithme de branch and bound. Exercice corrigé pas à pas du branch and bound Le propriétaire d’un atelier d’usinage envisage de s’agrandir en achetant de nouvelles machines, des presses et des tours. Le propriétaire a estimé que chaque presse achetée augmentera les profits de 100 $ par jour et que chaque tour augmentera les profits de 150 $ par jour. Le nombre de machines que le propriétaire peut acheter est limité par le coût des machines et l’espace au sol disponible dans […]
- [Dataviz 101](https://complex-systems-ai.com/dataviz/): Théories Page d’accueil Wiki I. Dataviz données numériques Avec une variable : Histogram Density plot Avec deux variables : Box plot Scatter plot and variants Violin plot 2D density plot Avec trois (ou plus) variables : Bubble plot Stacked area plot Stream graph Ridge line PCA Correlogram Heatmap Dendrogram II. Données catégoriques Une seule variable : Lollipop Word cloud Pie Treemap Circular packing Deux (ou plus) variables : Venn diagram Sunbrust Grouped scatter Stacked barplot Parallel plot Radar plot Sankey diagram Network Chord Arc Edge bundling III. Tutoriels Contenu de va-et-vient Dataviz , la visualisation intelligente des données La visualisation des […]
- [Inférence statistique 101](https://complex-systems-ai.com/inference-statistique/): Théorie Page d’accueil Wiki I. Estimation du point Estimating equations  Maximum likelihood Method of moments M-estimator Minimum distance Unbiased estimators  Mean-unbiased minimum-variance  Rao–Blackwellization Lehmann–Scheffé theorem Median unbiased Plug-in II. Estimation des intervals Confidence interval Pivot Likelihood interval Prediction interval Tolerance interval Resampling  Bootstrap Jackknife III. Test des hypothèses 1- & 2-tails Power  Uniformly most powerful test Permutation test  Randomization test Multiple comparisons IV. Test des paramètres Likelihood-ratio Score/Lagrange multiplier Wald Z-test (normal) Student’s t-test F-test V. Fitting Chi-squared G-test Kolmogorov–Smirnov Anderson–Darling Lilliefors Jarque–Bera Normality (Shapiro–Wilk) Likelihood-ratio test Model selection  Cross validation AIC BIC VI. Rang Sign  Sample median Signed rank (Wilcoxon)  Hodges–Lehmann estimator Rank […]
- [Corrélation et Régressions 101](https://complex-systems-ai.com/correlation-et-regressions/): Théories Page d’accueil Wiki I. Corrélation Pearson product-moment Partial correlation Confounding variable Coefficient of determination II. Analyse des régressions Errors and residuals Regression validation Mixed effects models Simultaneous equations models Multivariate adaptive regression splines (MARS) III. Régression linéaire Simple linear regression Ordinary least squares General linear model Bayesian regression IV. Régression non linéaire Nonlinear regression Nonparametric Semiparametric Isotonic Robust Heteroscedasticity Homoscedasticity Régression généralisé : Exponential families Logistic (Bernoulli) / Binomial / Poisson regressions V. Tutoriels Comment trouver la bonne régression ? De la normalisation des données à la régression Comment gérer les données manquantes Sélection des colonnes Tutoriel sur les bonnes pratiques dans l’analyse exploratoire des […]
- [Analyse descriptive 101](https://complex-systems-ai.com/analyse-descriptive/): Théorie Page d’accueil Wiki I. Analyse descriptive d’une variable distribution  central tendency mean median mode dispersion Variance Standard deviation Average absolute deviation Coefficient of variation Percentile Range Interquartile range shape Central limit theorem Moments Skewness Kurtosis L-moments II. Résumé des données Grouped data Frequency distribution Contingency table III. Dépendance Pearson product-moment correlation Rank correlation  Spearman’s ρ Kendall’s τ Partial correlation Scatter plot IV. Analyse des catégories Cohen’s kappa Contingency table Graphical model Log-linear model McNemar’s test Cochran-Mantel-Haenszel statistics V. Représentation graphique Bar chart Biplot Box plot Control chart Correlogram Fan chart Forest plot Histogram Pie chart Q–Q plot Run chart Scatter […]
- [Analyse des données 101](https://complex-systems-ai.com/analyse-des-donnees/): Théories Page d’accueil Wiki I. Processus de l’analyse des données The process of data analysis Analytical activities of data users Barriers to effective analysis Initial data analysis Data cleansing Data transformation Data modeling II. Réduction des dimensions Analyse en composantes principales Analyse factorielle des correspondances Analyse des correspondances multiples Analyse canonique Positionnement multidimensionnel Analyse Factorielle Multiple Hiérarchique Analyse Procustéenne Généralisée  Analyse Factorielle Multiple Duale Analyse Factorielle de Données Mixtes Iconographie des corrélations ACI  t-SNE  III. Classification Indice de ressemblance : Indice de Jaccard Indice de Dice Indice de concordance Indice de Tanimoto Algorithmes : Arbre de décision Boosting Forêts aléatoires k-NN […]
- [7 Exercices corrigés sur la complexité en temps](https://complex-systems-ai.com/algorithmique/exercices-complexite-en-temps/): Algorithmique Page d’accueil Wiki Exercices corrigés sur la complexité en temps Les exercices corrigés suivants concernent l’analyse d’algorithmes, en particulier l’exactitude, l’exhaustivité et le calcul de la complexité en temps. Exercice 1 Déterminez la complexité temporelle de l’algorithme Check : Solution Avant de calculer la complexité, il faut vérifier si l’algorithme se termine. Les éléments de la matrice sont des entiers, donc peuvent dépasser la valeur de 9, ce qui signifie que tab[value-1] sort de la taille du tableau. L’algorithme n’est donc pas viable et inutile de continuer l’analyse plus loin. Exercice 2 Analyser la complexité de l’algorithme. Écrivez un autre algorithme […]
- [16 Exercices Corrigés Programmation dynamique et Diviser pour régner](https://complex-systems-ai.com/algorithmique/ex-programmation-dynamique/): Algorithmique Page d’accueil Wiki Exercices corrigés sur la programmation dynamique Cette page propose plusieurs exercices corrigés de programmation dynamique et diviser pour régner.  L’objectif est de comprendre la différence entre le paradigme Divide & Conquer (Diviser pour régner) et la programmation dynamique. Les spécificités de la recherche de chemin (plus court chemin), problème de planification, problème de flot maximum et plus généralement la théorie des graphes est traitée à part. Exercice 1 Écrivez un pseudo-code pour un algorithme de type diviser pour régner permettant de trouver la position du plus grand élément dans un tableau de nombres. Écrivez un pseudo-code pour […]
- [6 Exercices corrigés sur les problèmes de transport](https://complex-systems-ai.com/theorie-des-graphes/problemes-de-transport/): Problème de planification Page d’accueil Wiki Exercices corrigés sur les problèmes de transport Cette page présente plusieurs exercices corrigés sur les problèmes de planification et d’ordonnancement automatisés, plus particulièrement sur les problèmes de transport et les algorithmes associés : stepping stone. Exercice 1 Une entreprise doit transporter des fournitures des usines aux chantiers de construction. Les trois usines ont respectivement une capacité d’approvisionnement de 300, 300, 100. Et les trois chantiers en demandent respectivement 200, 200, 300. Les frais de transport sont indiqués dans le graphique suivant : Trouvez comment répartir les fournitures. Solution Résoudre le problème de planification suivant avec […]
- [8 Exercices corrigés sur les problèmes d'affectation](https://complex-systems-ai.com/theorie-des-graphes/problemes-daffectation/): Problème de planification Page d’accueil Wiki Exercices corrigés sur les problèmes d’affectation La page présente plusieurs exercices corrigés sur les problèmes de planification et d’ordonnancement automatisés, en particulier sur les problèmes d’affectation. Exercice 1 Le réseau de la côte atlantique déssert quatre villes. La direction veut attribuer quatre usines aux villes. Le prix pour envoyer de l’énergie d’une usine à chaque ville est décrit ci-dessous :   Raleigh Atlanta Durham Clemson Plant A 210 90 180 160 Plant B 100 70 130 200 Plant C 175 105 140 170 Plant D 80 65 105 120 Une usine ne peut mériter qu’une […]
- [7 Problèmes de plus court chemin](https://complex-systems-ai.com/theorie-des-graphes/de-plus-court-chemin/): Recherche de chemin Page d’accueil Wiki Exercices corrigés de problème de plus court chemin Cette page présente plusieurs exercices corrigés sur le problème de plus court chemin. Les exercices portent principalement sur le chemin le plus court pour une source et le chemin le plus court à partir de plusieurs sources. Exercice 1 La compagnie aérienne Europa dessert plusieurs villes européennes. Le tableau ci-dessous donne en contre les temps de vol entre ces villes. • Comment déterminer l’itinéraire le plus rapide entre deux villes ? • Comment modifier la méthode précédente pour prendre en compte la durée des escales dans les différentes villes ? A B C D E A 1h30 2h00 2h15 B 1h40 3h00 C 2h20 2h55 D 3h20 1h05 […]
- [7 Exercices corrigés sur les problèmes de flot](https://complex-systems-ai.com/theorie-des-graphes/exo-problemes-de-flot/): Problème de flots maximum Page d’accueil Wiki Exercices corrigés sur les problèmes de flot maximum Cette page contient divers exercices corrigés sur les problèmes de flot max. Ces problèmes utilisent principalement l’algorithme Ford-Fulkerson et la solution min-cut. Exercice 1 A l’aide de la méthode de Ford-Fulkerson, calculez un débit maximal dans le réseau suivant : Solution Exercice 2 La figure ci-dessous montre un réseau de flux sur lequel un flux s-t est affiché. La capacité de chaque bord apparaît sous la forme d’une étiquette à côté du bord, et les nombres dans les cases indiquent la quantité de flux envoyée sur chaque […]
- [5 Exercices Corrigés de Problème d'arbre couvrant](https://complex-systems-ai.com/theorie-des-graphes/exo-darbre-couvrant/): Théorie des Graphes Page d’accueil Wiki Exercices corrigés : problème d’arbre couvrant La page présente plusieurs exercices corrigés sur des problèmes de théorie des graphes. Ces exercices portent sur le problème d’arbre couvrant. Exercice 1 Il y a 5 villes. Le coût de construction d’une route directement entre i et j est l’entrée a(i,j) dans la matrice ci-dessous. Une entrée indéfinie indique que la route ne peut pas être construite. Déterminez le moindre coût pour rendre toutes les villes accessibles les unes des autres. Solution Nous ordonnons les arêtes selon les poids : 12, 23, 13, 45, 25, 15, 24, 35, […]
- [4 Exercices Corrigés de Coloration de graphe](https://complex-systems-ai.com/theorie-des-graphes/coloration-de-graphe/): Théorie des Graphes Page d’accueil Wiki Exercices corrigés : modélisation et coloration de graphe Cette page contient divers exercices corrigés sur la modélisation de la théorie des graphes et les problèmes de coloration de graphe. Veuillez consulter la page sur la théorie des graphes pour en savoir plus sur les bases de la théorie des graphes et divers problèmes de théorie des graphes. Exercice 1 Considérant un jeu de dominos utilisant les nombres 0, 1, 2, 3, 4, comme sur chaque domino comprend deux chiffres distincts, comme 1 et 3, le problème suivant est proposé : est-il possible d’aligner tous les […]
- [22 Exercices corrigés : modélisation en graphes et arbres](https://complex-systems-ai.com/theorie-des-graphes/modelisation-en-graphe/): Théorie des graphes Page d’accueil Wiki Exercices corrigés sur les bases de la théorie des graphes (modélisation en graphe et arbres) Cette page montre quelques exercices corrigés sur la modélisation en graphe et arbres. Le but de ces exercices est d’apprendre à modéliser un problème grâce aux concepts et bases de la théorie des graphes. La majorité des problèmes présentés sont des simplexes aussi solvable avec la méthode classique.  Exercice 1 Deux joueurs ont 2 lots d’allumettes ou plus. A chaque tour, le joueur suivant peut retirer un certain nombre d’allumettes d’un lot (selon la règle choisie). Le joueur qui supprime […]
- [Parcours de Graphes](https://complex-systems-ai.com/theorie-des-graphes/parcours-de-graphes/): Théorie des Graphes Page d’accueil Wiki Pour chercher dans un graphe (parcours de Graphes), on construit d’abord un arbre couvrant le graphe. Parcours de Graphes et Parcours d’Arbres Breadth-first search / Recherche en profondeur BFS parcourt l’arbre en augmentant la profondeur jusqu’à la racine. BFS(Graph G, Node s): { f = CreateQueue(); f.stack(s); mark(s); while non f.empty() s = f.pop(); print(s); for each children t of s in G if t unmarked DO f.stack(t); mark(t); end if end for end while } In-depth search : pre-order Les algorithmes en profondeur sont récursifs. Dans le chemin du préfixe, nous parcourons toujours le […]
- [La Recherche Scientifique](https://complex-systems-ai.com/la-recherche-scientifique/): Théories Page d’accueil Wiki Introduction à la recherche scientifique Définir la problématique Définir les questions scientifiques Définir sa méthode et plan scientifique (experimental design) Comment réaliser un état de l’art Comment organiser son état de l’art Etat de l’art avec Zotero Faire un Concept Map / Mind Map Comment lire un papier scientifique Comment résumer un papier scientifique (Feynman) Ecriture d’un papier scientifique Avant tout, il faut connaître l’environnement LaTeX : Ecrire sous LaTeX et Overleaf Après avoir lu le cours sur la problématique et l’état de l’art, vous devez écrire votre Proposition de recherche : Ecrire une proposition de recherche […]
- [Mon compte](https://complex-systems-ai.com/mon-compte/)
- [Bibliothèque](https://complex-systems-ai.com/bibliotheque/): Notre sélection de livres pour la bibliothèque parfaite ! Voici notre sélection pour la bibliothèque sur les sciences de l’informatique et mathématiques Deep learning et réseaux de neurones Mathematics for Machine Learning Linear Algebra and Optimization for Machine LearningArtificial Intelligence for Humans, Volume 1: Fundamental Algorithms Artificial Intelligence for Humans, Volume 2: Nature-Inspired Algorithms Artificial Intelligence for Humans, Volume 3: Deep Learning and Neural Networks Clever Algorithms: Nature-Inspired Programming Recipes Approaching (Almost) Any Machine Learning Problem Quand la machine apprend The Hundred-Page Machine Learning Book Mathematics for Machine Learning Artificial Intelligence: A Modern Approach, Global Edition Langage de programmation : Hands-On […]
- [3 Exercices corrigés sur Algèbre de Boole](https://complex-systems-ai.com/logique-mathematique-27/algebre-de-boole/): Mathématiques Page d’accueil Wiki Exercices corrigés sur Algèbre de Boole et tableau de Karnaugh Ce TD propose des exercices corrigés sur l’algèbre de Boole et les diagrammes ou tableaux de Karnaugh. Exercice 1 La société K-Gaz décide de recruter en interne des collaborateurs pour sa filiale. Pour chaque employé, on définit les variables booléennes suivantes : a=1 s’il a plus de 5 ans d’ancienneté dans l’entreprise b=1 s’il possède un BTS-IG c=1 s’il parle couramment l’anglais La direction des ressources humaines décide que pourront postuler les employés :  qui satisfont aux trois conditions  ou qui ont moins de 5 ans d’ancienneté […]
- [Mathématiques 101](https://complex-systems-ai.com/logique-mathematique-27/): Théories Page d’accueil Wiki I. Système logique Calcul des propositions (connecteurs logiques ET, OU, XOR, etc.) Calcul des prédicats ou Logique d’ordre supérieur(quantificateurs il existe, qqsoit, etc) Algèbre de Boole II. Analyse Equations différentielles ordre 1 Equations différentielles ordre 2 Exercices corrigés : Exercices corrigés équations différentielles ordre 1 Les mathématiques de base A suivre
- [Projet : Smart City sur Netlogo](https://complex-systems-ai.com/algorithmique/netlogo-smart-city-2021/): Cours Page d’Accueil Wiki Projet : Smart City sur Netlogo Ce mini projet s’inscrit dans le cours réalisé à l’ENSTA. Ce mini-projet a pour objectif de produire, par méthode constructive, une simulation d’une Smart City sur le logiciel Netlogo. Le rapport à remettre est un fichier compressé comprenant un PDF détaillant chaque partie ainsi que le code Netlogo de chaque partie. Il est a noté que des paramètres d’observation (graphique, compteur, etc) sont à rajouter afin de valider vos propos. Ces paramètres ne sont pas explicités dans le cahier des charges. Partie 1 : voiture et éclairage intelligent L’observateur définit le […]
- [Projet : Véhicules électriques sur Netlogo](https://complex-systems-ai.com/algorithmique/netlogo-vehicules-electriques-projet-2021/): Cours Page d’Accueil Wiki Projet : Véhicules électriques sur Netlogo Ce mini projet s’inscrit dans le cours réalisé à l’ENSTA. Ce mini-projet a pour objectif de produire, par méthode constructive, une simulation de Vehicules Electriques sur le logiciel Netlogo. Le rapport à remettre est un fichier compressé comprenant un PDF détaillant chaque partie ainsi que le code Netlogo de chaque partie. Il est à noter que des paramètres d’observation (graphique, compteur, etc) sont à rajouter afin de valider vos propos. Ces paramètres ne sont pas explicités dans le cahier des charges. Partie 1 : VE et zones Ce projet consiste à […]
- [Projet : Virtual Power Plants sur Netlogo](https://complex-systems-ai.com/algorithmique/projet-netlogo-vpp-2021/): Cours Page d’Accueil Wiki Projet : Virtual Power Plants sur Netlogo Ce mini projet s’inscrit dans le cours réalisé à l’ENSTA. Ce mini-projet a pour objectif de produire, par méthode constructive, une simulation de Virtual Power Plants sur le logiciel Netlogo. Le rapport à remettre est un fichier compressé comprenant un PDF détaillant chaque partie ainsi que le code Netlogo de chaque partie. Il est à noter que des paramètres d’observation (graphique, compteur, etc) sont à rajouter afin de valider vos propos. Ces paramètres ne sont pas explicités dans le cahier des charges. Partie 1 : Regroupement des petits producteurs Une […]
- [Modélisation de Smart Grids](https://complex-systems-ai.com/algorithmique/modelisation-de-smart-grids/): Le cours de modélisation de Smart Grids à pour objectif d’aborder les thèmes suivant : Les systèmes complexes adaptatifs La modélisation et la simulation La modélisation par multi-agents Les Smart Building et les microgrids Eco-quartiers, agrégateurs et Virtual power plants Le réseau électriques intelligent (Smart Grid) Connexion de réseaux intelligents (P2G, V2G, réseau de distribution d’eau, réseau de chaleur) Les compétences suivantes seront développées : Modélisation systémique Modélisation par multi-agents Logiciel NetLogo Connaissances approfondies des Smart Grids Notation : Les étudiants seront notés via un projet sur 3 séances. Il n’y a pas d’examen final ou de contrôle continu. Le Cours […]
- [Corrected Exercises: Algorithms](https://complex-systems-ai.com/algorithmique/corrected-exercises-algorithms/): Algorithmique Page d’accueil Wiki Corrected exercises about Divide & Conquer and Dynamic programming This page purposes several corrected exercises about algorithms, more particularly on Divide & Conquer paradigm and dynamic programming. Exercise 1 Write a pseudo code for a divide-and-conquer algorithm for finding the position of the largest element in an array of  numbers. Write a pseudo code for a brute-force algorithm, compare with the previous one. Show a tree of the divide-and-conquer algorithm’s process. What is the max level of the tree for  numbers? Solution The brute-force algorithm is trivial: a loop. At each level l, the complete binary tree […]
- [Corrected Exercises: Assignment Problem](https://complex-systems-ai.com/probleme-de-planification/corrected-exercises-assignment-problem/): Problème de planification Page d’accueil Wiki Corrected exercises about assignment problems The page presents several corrected exercises about automated planning and scheduling problems, especially about assignment problems. Exercise 1 The Atlantic Coast Grid deserves four cities. The office wants to assign four plants. The price to send energy from a plant to each city is described below:   Raleigh Atlanta Durham Clemson Plant A 210 90 180 160 Plant B 100 70 130 200 Plant C 175 105 140 170 Plant D 80 65 105 120 A plant can deserve only one city, and a city can take energies only from […]
- [Projet Programmation Linéaire : The Truman Show](https://complex-systems-ai.com/programmation-lineaire/projet-programmation-lineaire-the-truman-show/): Programmation linéaire Page d’accueil Wiki Projet sur la programmation linéaire : The Truman Show Ce projet requiert des notions de programmation linéaire et des algorithmes d’optimisation combinatoire, notamment le Branch & Bound. “We’ve become bored with watching actors give us phony emotions. We are tired of pyrotechnics and special effects. While the world he inhabits is, in some respects, counterfeit, there’s nothing fake about Truman himself. No scripts, no cue cards. It isn’t always Shakespeare, but it’s genuine. It’s a life.” Début du projet La télé-réalité rapporte des milliards d’euros par an. Mais pour faire la différence, il faut oser toujours […]
- [Projet : Terminator](https://complex-systems-ai.com/processus-de-markov/projet-terminator/): Processus stochastique Page d’accueil Wiki Projet sur les Hidden Markov Model : Terminator Ce projet requiert des connaissances sur les chaines de Markov, les automates, et les Hidden Markov Model afin de pouvoir le réaliser. – Est-ce qu’il y a moyen d’apprendre des trucs par programmes chez toi, pour que tu puisses avoir l’air… plus humain… ne plus avoir l’air aussi con.– Mon UPC est un neuro-processeur, un ordinateur à apprendre, plus j’ai de contacts avec les humains et plus j’apprends.– Cool. Début du projet La robotique est un champ d’étude pluridisciplinaire, faisant appel à toutes les compétences et qualités des […]
- [Projet Théorie des Graphes : Sim City 2030](https://complex-systems-ai.com/theorie-des-graphes/projet-theorie-des-graphes-sim-city-2030/): Théorie des graphes Page d’accueil Wiki Projet de théorie des graphes : Sim City 2030 Ce projet sur la théorie des graphes, la programmation linéaire, le branch & bound et les problèmes de flots est une introduction aux problèmes liés au smart grid. Bonjour chers ingénieurs NE, Votre équipe a remporté avec succès le projet Sim City 2030. Notre maire, le vénérable Frédéric Fauberteau (vous pouvez l’appeler dieu) et ses quatre conseillers Guillaume Guérard (le seul, l’unique), Pascal Clain (what else ?), Samir Yahiaoui (vous serez renversé) et Marie-Noémie Thai (notre déesse) vous ont choisi pour construire la plus grande centrale de […]
- [Corrected Exercises: Transportation problems](https://complex-systems-ai.com/probleme-de-planification/corrected-exercises-transportation-problems/): Problème de planification Page d’accueil Wiki Corrected exercises about transportation problems This page presents several corrected exercises about automated planning and scheduling problems, more especially about transportation problems and the related algorithms: the stepping stone. Exercise 1 A company has to transport supplies from plants to the construction sites. The three plants have 300, 300, 100 supply capacity respectively. And the three construction sites demand 200, 200, 300 respectively. The transporting costs are shown in the following graph: Find how to allocate the supplies. Solution Exercise 2 Wheat is harvested in the Midwest and stored in grain elevators in three different […]
- [Corrected Exercises: Flow problems](https://complex-systems-ai.com/probleme-de-flot-maximum/corrected-exercises-flow-problems/): Problème de flot maximum Page d’accueil Wiki Corrected exercises about flow problems This page contains various corrected exercises about max flow problems. Those problems use mainly the Ford-Fulkerson algorithm and the min-cut solution. Exercise 1 Using the Ford-Fulkerson method, compute a maximal flow in the following network: Solution Exercise 2 The figure below shows a flow network on which an s-t flow is shown. The capacity of each edge appears as a label next to the edge, and the numbers in boxes give the amount of flow sent on each edge. (Edges without boxed numbers have no flow being sent on […]
- [Corrected Exercises: Shortest Path](https://complex-systems-ai.com/recherche-de-chemin-theorie-des-graphes/corrected-exercises-shortest-path/): Recherche de chemin Page d’accueil Wiki Corrected exercises about shortest path problems This page presentes several corrected exercises on shortest path problems. The exercises are mainly about shortest path for one source and shortest path from many sources. Exercise 1 The air company Europa serves various European cities. The table below gives against the flight times between these cities.• How to determine the fastest route between two cities?• How to modify the previous method to take into account the duration of stopovers in different cities?   A B C D E A   1h30 2h00   2h15 B 1h40       3h00 C 2h20     2h55   D     3h20   1h05 E 2h25 3h10 1h10 […]
- [Corrected Exercises: Spanning Tree](https://complex-systems-ai.com/theorie-des-graphes/corrected-exercises-spanning-tree/): Théorie des graphes Page d’accueil Wiki Corrected exercises about spanning tree The page presents several corrected exercises about graph theory problems. Those exercises are about spanning tree problems. Exercise 1 There are 5 cities. The cost of building a road directly between i and j is the entry ai,j in the matrix below. An indefinite entry indicates that the road cannot be built. Determine the least cost of making all the cities reachable from each other. Solution We order the edges according to the weights: 12, 23, 13, 45, 25, 15, 24, 35, 14 (raw-column). Kruskal’s Algorithm accepts edges 12, 23, then […]
- [Corrected Exercises: graph theory and coloring](https://complex-systems-ai.com/theorie-des-graphes/corrected-exercises-graph-theory-and-coloring/): Théorie des graphes Page d’accueil Wiki Corrected exercises about graph theory and coloring This page contains various corrected exercises about graph theory modelling and coloring problems. Please see graph theory page to learn about graph theory basics and various graph theory’s problem. Exercise 1 Considering a domino game using the numbers 0, 1, 2, 3, 4, as on each domino include two distinct digits, such as 1 and 3, the following problem is proposed: Is it possible to align all the dominoes so that when two pawns « touch » the numbers « in contact » are identical? Solution Show the problem as a complete graph K5. The problem is to find an Eulerian cycle in the graph. Exercise 2 Consider the sequence 01110100 as being arranged […]
- [Corrected Exercises: Graph theory basics](https://complex-systems-ai.com/theorie-des-graphes/corrected-exercises-graph-theory-basics/): Théorie des graphes Page d’accueil Wiki Corrected exercises on graph theory basics This page shows some corrected exercises about graph theory modeling and trees. The goal of these exercises is to learn how to model a problem through graph theory concepts and basics. Modeling with graph theory Exercise 1 Two players have 2 or more batches of matches. At each turn, the next player may remove a number of matches of a lot (depending on the selected rule). The player who removes the last match loses.Model this game with a graph in the case where one has from two piles each containing three matches, and where a player can remove one or two matches each.What move the first player must play to win the game? Solution Edges are oriented from left to right. If […]
- [Corrected exercises: time complexity](https://complex-systems-ai.com/algorithmique/corrected-exercises-time-complexity/): Algorithmique Page d’accueil Wiki Corrected exercises about Time complexity The following corrected exercises are about algorithm analysis, especially correctness, completeness and time complexity calculus. Exercise 1 Determine the time complexity of the Check algorithm: Solution Check correctness and completeness, especially what happened during the first iteration. Exercise 2 Analyze the complexity of Algorithm. Write another algorithm that does exactly the same thing as Algorithm but with a strictly better asymptotic time complexity. Solution Complexity is O(|A|²). You can improve the algorithm by: first, sort the table in O(n log n) and then check occurrences in O(n), thus complexity becomes O(n log […]
- [Project Graph Theory : Starship Troopers](https://complex-systems-ai.com/probleme-de-flot-maximum/project-graph-theory-starship-troopers/): Problème de flot maximum Page d’accueil Wiki Project Graph Theory : Starship Troopers The Project graph theory : Starship Troopers includes various graph theory problems as pathfinding, max flow problem, assignement. ETC: 15 hours (deadline – 5 classes) 3-4 students per team Please take your time on both quality and contents Associate professor and assistant professors will not answer questions about the project. Scale: 50 points 10 points 15 points 10 points 15 points “Violence, naked force, has settled more issues in history than has any other factor.” Task 1: Relocate the production In the 23rd century, Earth has become a […]
- [Project Graph theory : The Mazerunner](https://complex-systems-ai.com/theorie-des-graphes/project-graph-theory-the-mazerunner/): Théorie des graphes Page d’accueil Wiki Project Graph Theory : The Mazerunner This project is about graph theory problem and pathfinding problem. See the course to find the correct model. 15 hours (during 5 classes) 2 students per team Please take your time on both quality and contents Associate professor and assistant professors will not answer questions about the project. Scale: 50 points 10 points 10 points 15 points 15 points “Just follow me and run like your life depends on it. Because it does.” Task 1: To form the teams The number of Gladers grows up from day to day. […]
- [8 Exercices corrigés : File d'attente](https://complex-systems-ai.com/processus-de-markov/exercices-file-dattente/): Proessus stochastique Page d’accueil Wiki Exercices corrigés : File d’attente Les exercices corrigés ci-dessous concernent la file d’attente, les chaines de Markov en temps continu. Exercice 1 Un système clients-serveur reçoit en moyenne 1000 requêtes par seconde, arrivant selon un processus de Poisson. Il dispose d’un unique serveur pouvant traiter en moyenne 2000 clients par seconde. On suppose que le temps de service d’un client est distribué selon la loi exponentielle. Calculer la probabilité que le temps de service dépasse 2 ms. Quelle est le pourcentage de clients rejetés pour un système ne comportant pas de file d’attente. Même question pour […]
- [9 Exercices corrigés : chaines de Markov en temps discret](https://complex-systems-ai.com/processus-de-markov/exo-chaines-de-markov/): Processus stochastique Page d’accueil Wiki Exercices corrigés : les chaines de Markov en temps discret Cette page regroupe de nombreux exercices corrigés sur les chaines de Markov en temps discret et comportement asymptotique, classe, chaine ergodique, absorption. Exercice 1 Construire la chaîne de Markov correspondant à la matrice stochastique suivante : 0.4 0.6 0 0.2 0.5 0.3 0 0.4 0.6 Combien la chaîne a-t-elle de classe ? Est-elle réductible ? Si oui la réduire. Calculer la probabilité stationnaire, si elle existe, de la chaîne irréductible. Calculer la périodicité des classes. Solution Pour représenter la chaîne, on choisit de numéroter les états de 1 à […]

## Optional

- [Agent (MCP protocol)](websites-agents.hostinger.com/complex-systems-ai.com/mcp)

[comment]: # (Generated by Hostinger Tools Plugin)