Qu'est-ce qu'un algorithme en intelligence artificielle ?
Un algorithme classique spécifie explicitement le traitement des données, sa conception passe par le contrôle explicite de comment passer des paramètres au but.
Les algorithmes d'IA sont “méta”, c'est à dire que l'algorithme spécifie comment apprendre, et ce sont les données d'apprentissage qui le “formatent”.Quel est le lien entre l'intelligence artificielle et le concept des algorithmes ?
Les algorithmes utilisés dans l'intelligence artificielle sont des algorithmes spécifiques dont les modèles produits évoluent en fonction des données qui leurs sont fournies et dont ils se « nourrissent ».
Comment Appelle-t-on les algorithmes d'intelligence artificielle ?
« apprentissage machine »), apprentissage artificiel ou apprentissage statistique est un champ d'étude de l'intelligence artificielle qui se fonde sur des approches mathématiques et statistiques pour donner aux ordinateurs la capacité d'« apprendre » à partir de données, c'est-à-dire d'améliorer leurs performances à
- Un algorithme classique spécifie explicitement le traitement des données, sa conception passe par le contrôle explicite de comment passer des paramètres au but.
Les algorithmes d'IA sont “méta”, c'est à dire que l'algorithme spécifie comment apprendre, et ce sont les données d'apprentissage qui le “formatent”.
Première partie : Algorithmique avancée pour les graphes
Algorithmique avancée Corrigé du TP2
Algorithmique I
Algorithmique Avancée exercices: “Divide and Conquer”
Chapitre 8 Structures de données avancées
Algorithmique et Structures de Données
Algorithmique et structures des données avancées
Chapitre 1 : Notions dalgorithme et de programme
Cours de lalgorithmique et programmation: Licence SMI
Algorithmique Avancée pour l"IntelligenceArtificielle et les graphes (AAIA)Pierre-Edouard Portier et Christine SolnonINSA de Lyon - 3IF2018/20191/108IntroductionOrganisation et objectifs pédagogiques1IntroductionOrganisation et objectifs pédagogiquesModélisation de problèmes avec des graphes2Définitions3Structures de données pour représenter un graphe4Parcours de graphes5Plus courts chemins6Problèmes de planification7Quelques problèmes NP-difficiles sur les graphes2/108IntroductionOrganisation et objectifs pédagogiquesPositionnement de l"EC AAIA au sein des UE d"IFUnités d"enseignement du département IF :Système d"InformationArchitectures matérielles, Réseaux et SystèmesFormation généraleDéveloppement logiciel (DL)Méthodes et Outils Mathématiques (MOM)EC de l"UE DL en 3IF :Introduction à l"algoBases de la POOPOO avancéeGénie logicielEC de l"UE MOM en 3IF :Calcul matriciel et synthèse d"imagesTraitement du signal et imageProbabilitésAlgo pour l"IA et les graphes3/108IntroductionOrganisation et objectifs pédagogiquesRéférentiel des compétencesApprofondissement de compétences abordées au semestre 1 :Choisir les structures de données adaptées à la situationDéterminer la complexité d"un algorithmeProuver la correction d"un algorithme;Implémenter de bons logicielsNouvelles compétences :Modéliser et résoudre des problèmes à l"aide de graphes et/ou detechniques d"IAReformuler un nouveau problème à résoudre en un problèmeconnu en théorie des graphes ou en IAChoisir le bon algorithme pour résoudre le problèmeSavoir adapter un algorithme connu à un contexte particulierIdentifier la classe de complexité d"un problème4/108IntroductionOrganisation et objectifs pédagogiquesOrganisation9 cours en amphi5 cours : C.
Solnon (du 5 février au 5 mars);Algorithmique avancée pour les graphes4 cours : P.-E.Portier;Algorithmique avancée pour l"IA6 TD et 3 TPdu 11 février au 7 juinEvaluation1 DS + questionnaires Moodle (sur les cours et sur les TP)5/108IntroductionOrganisation et objectifs pédagogiquesPour en savoir plus Sur l"algorithmique en général :AlgorithmiqueT.
Cormen, C. Leiserson, R. Rivest, C.SteinEditions Dunod - 2010Sur les graphes :La théorie des graphesAimé SacheCollection "Le sel et le fer", n22Editions Cassini - 20036/108IntroductionModélisation de problèmes avec des graphes1IntroductionOrganisation et objectifs pédagogiquesModélisation de problèmes avec des graphes2Définitions3Structures de données pour représenter un graphe4Parcours de graphes5Plus courts chemins6Problèmes de planification7Quelques problèmes NP-difficiles sur les graphes7/108IntroductionModélisation de problèmes avec des graphesEuler 1741 :Solutio problematis at geometriam situs pertinentisoù comment résoudre un problème grâce à la " géométrie de situation "" Outre cette partie de la géométrie qui s"occupe de la grandeur et de la mesure ( ),Leibniz a fait mention, pour la première fois, d"une autre partie encore très inconnueactuellement, qu"il a appeléeGeometria Situs( ).
Cette branche s"occupeuniquement de l"ordre et de la situation, indépendamment des rapports de grandeur. "Problème :" Peut-on arranger son parcours de telle sorte que l"onpasse sur chaque pont, et que l"on ne puisse y passerqu"une seule fois? Cela semble possible, disent lesuns; impossible, disent les autres; cependantpersonne n"a la certitude de son sentiment. "Proposition d"Euler pour résoudre ce problème :" Former avec les lettres A, B, C, D une série de 8 lettres dans laquelle ces voisinages(A-C, A-B, A-D, D-C et B-D) apparaissent autant de fois qu"il a été indiqué (2, 2, 1, 1 et1 fois); mais avant de chercher à effectuer une telle disposition, il est bon de sedemander si celle-ci est réalisable. ( ) Aussi ai-je trouvé une règle qui donne, pourtous les cas, la condition indispensable pour que le problème ne soit pas impossible. "8/108IntroductionModélisation de problèmes avec des graphesEuler 1741 :Solutio problematis at geometriam situs pertinentisoù comment résoudre un problème grâce à la " géométrie de situation "" Outre cette partie de la géométrie qui s"occupe de la grandeur et de la mesure ( ),Leibniz a fait mention, pour la première fois, d"une autre partie encore très inconnueactuellement, qu"il a appeléeGeometria Situs( ).
Cette branche s"occupeuniquement de l"ordre et de la situation, indépendamment des rapports de grandeur. "Problème :" Peut-on arranger son parcours de telle sorte que l"onpasse sur chaque pont, et que l"on ne puisse y passerqu"une seule fois? Cela semble possible, disent lesuns; impossible, disent les autres; cependantpersonne n"a la certitude de son sentiment. "Proposition d"Euler pour résoudre ce problème :" Former avec les lettres A, B, C, D une série de 8 lettres dans laquelle ces voisinages(A-C, A-B, A-D, D-C et B-D) apparaissent autant de fois qu"il a été indiqué (2, 2, 1, 1 et1 fois); mais avant de chercher à effectuer une telle disposition, il est bon de sedemander si celle-ci est réalisable. ( ) Aussi ai-je trouvé une règle qui donne, pourtous les cas, la condition indispensable pour que le problème ne soit pas impossible. "8/108IntroductionModélisation de problèmes avec des graphesExemples de modélisation par des graphesRéseau de transport13CuireHôtel de VilleLouis Pradel51331814Fourvière12Hôpital Feyzin VénissieuxVaulx-en-VelinLa GrappinièreRillieux SemaillesGare de Vénissieux14Gare St-PaulCharpennesCharles Hernu21617Gare Part-Dieu Vivier Merle9132567Vaulx-en-VelinLa Soie815Vieux LyonCathédrale St-Jean20E20Saint-Just2021Perrache192122EurexpoParc du ChêneGrange Blanche22261681325St-Priest Bel AirCité InternationaleCentre de Congrès45Bellecour122091020EAéroport Lyon Saint ExupéryIUT - FeyssineJet d'eauMendès FranceGare d'OullinsGare de Vaise614Gare Part-DieuVillette471214Jean Macé22Debourg107La DouaGaston BergerMeyzieu Les Panettes1713491294111214491472516121271631592631115178125221622161525151712122525251726172622227102515725791449132515Musée d'Art ContemporainCentre de CongrèsInterpolParc Tête d'Or Pt Churchill MuséumParc Tête d'OrDuquesneVitton - BelgesGrandclémentPoizatBernaixCyprian Léon BlumLéon BlumPont des PlanchesLefèvreCuzin - StalingradHôtel de Ville - CampusGrand VireLesireMas du TaureauVaulx les GrôlièresAlsaceInstitut d'ArtContemporainVerlaineL.
BrailleMontalandBlanquiCentre Mémoires et SociétéLes HallesPaul BocusePart-DieuJules FavreGaribaldiLafayetteSaxeLafayetteSt-Clair - Square BrossetMontée des SoldatsCaluire Place FochMontessuy FlemingMontessuy CalmetteImpasse MathieuSquare Elie VignalTonkinRosselliniParc Tête d'Or StalingradLycée CuzinCaluire Chemin PetitLeclercDrevetRillieuxLes AlagniersGeorgeSandMicheletCompanetPiscine duLoup PenduLesVerchèresEspace BaudelaireTerreauxLa FeuilléeBon CoinCité InternationaleTransbordeurLeclercThimonnierPERICAMercières6HenonAmpère Victor HugoMonplaisirLumière Place GuichardBourse du TravailMassénaFochCroix - PaquetRépubliqueVilleurbanne FlachetAlain Gilles Cusset6Brotteaux26Gratte - CielCroix - Rousse145133CordeliersPlace Jean Jaurès24E2124Gorge de LoupL.
BonnevayAstroballe25ParillySans SouciLaennecGuillotièreGabriel PériGaribaldiSaxe Gambetta614ValmyStade de GerlandCentreBerthelotGaribaldiBerthelotSaint-AndréRue del'UniversitéQuaiClaude BernardCollège BellecombeRebuferHôtel de Ville - Bron826Ambroise ParéVinatierEssarts - IrisBoutasse - Camille Rousset Les AlizésPorte des AlpesParilly - UniversitéHippodromeEurope - UniversitéParc TechnologiqueHauts de FeuillySalvador AllendeAlfred de VignySt-Priest - Hôtel de VilleEsplanade des ArtsJules FerryCordièreSainte-BlandineSuchetPart-DieuServientProfesseur BeauvisageCISLÉtats-UnisVivianiJoliot CurieMarcel SembatLycée Jacques BrelLa BorelleCroizat - Paul BertMarcel HouëlHôtel de VilleHerriot - CagneVénissyDivision LeclercDarnaiseMaurice ThorezLénine - CorsièreRoutede VienneLycée LumièreÉtats-UnisMusée Tony GarnierLe TonkinUniversitéLyon 1Croix-LuizetDécinesGrand Large1613DauphinéLacassagneSaxePréfectureCondorcetINSA - EinsteinPalais de JusticeMairie du 3e9ReconnaissanceBalzac17Bel AirLes Brosses26Gare deVilleurbanneThiersLafayetteLibertéDe TassignyCurialLycéeJean-Paul SartreBachut - Mairie du 8eVillonJean XXIII - Maryse BastiéMinimesThéâtres RomainsLes jours de salonEn semaineManufactureMontlucLycée ColbertHalleTony GarnierMuséedes ConfluencesENS LyonHôtel de RégionMontrochet11ArchivesDéparte-mentalesDécines CentreMeyzieu GareMeyzieu Z.i.15Mermoz - PinelLe RhôneLe RhôneLa SaôneLe RhôneCanal de JonagePlan lignes fortesMétroTramwayFuniculaireLigne majeure de Bus(en correspondance avec métro / tramway)septembre 2017Appli mobile TCLsitemobilewww.tcl.fr m.tcl.fr(prix d'un appel local)ALLÔ TCL 04 26 10 12 12SERVICESParc relais TCLPour les autres lignes de bus se référer aux plans détaillésJean MacéLes Sources14Bachut - Mairie du 8eLaurent Bonnevay - Astroballe15Charpennes - Charles HernuSurville Route de Vienne16Charpennes - Charles HernuLaurent Bonnevay - Porte des Alpes17Hôtel de Ville - Louis PradelCroix-Rousse Nord18PerracheFrancheville Taffignon19BellecourFrancheville Taffignon / Fort du Bruissin2020EPerracheGorge de Loup21PerracheGrange Blanche222424EGare Part-Dieu - Vivier MerleSaint-Priest Plaine de Saythe / Sogaris Promotrans25Cité Internationale - TransbordeurGrange Blanche26Gare Part-Dieu - Vivier MerleCuire1Gare Part-Dieu - Vivier MerleRillieux Semailles2Gare Saint-PaulVaulx- en-Velin La Grappinière3Jean MacéCité Internationale4CordeliersRillieux Semailles - Vancia Château Bérard5Gare Part-Dieu - Vivier MerleÉcully Le Pérollier6Gare Part-Dieu - Vivier MerleHôpital Lyon Sud7Grange BlancheVaulx- en-Velin Résistance8Bellecour - Antonin PoncetHôpitaux Est9Bellecour - CharitéSaint-Genis Barolles10Saxe - GambettaLaurent Bonnevay - Astroballe11Bellecour - Antonin PoncetHôpital Feyzin Vénissieux12Grange BlancheMontessuy Gutenberg13LIGNES MAJEURES BUSMÉTROPerracheVaulx- en-Velin La SoieCharpennes - Charles HernuGare d'OullinsHôtel de Ville - Louis PradelCuireGare de VaiseGare de VénissieuxFUNICULAIREVieux Lyon - Cathédrale St-JeanSaint-JustVieux Lyon - Cathédrale St-JeanFourvièreTRAMWAYDebourgHôtel de Région - MontrochetIUT - FeyssinePerracheSaint-Priest Bel-AirGare Part-Dieu - VilletteMeyzieu Z.i.Meyzieu Les Panettes (en semaine)Hôpital Feyzin VénissieuxLa Doua - Gaston BergerGrange BlancheParc du ChêneEurexpo (les jours de salon)Toutes les stations de métro,tramway et trolleybus C1 C2 C3sont accessibles à l'exceptionde la station Croix-Paquet.Pour connaître la disponibilitédes ascenseurs, appelerle 04 26 10 12 12 outcl.fr rubrique accessibilité.Gare ferroviaireDesserte aéroport(tarification spéciale)AéroportParc relais véloGorge de LoupCraponne Val d'Yzeron / Grézieu Gym.
E.Catalon0600LF0600LF9/108IntroductionModélisation de problèmes avec des graphesExemples de modélisation par des graphesRéseaux de régulation génétiqueSommets = gènesArêtes = influence entre gènes10/108IntroductionModélisation de problèmes avec des graphesExemples de modélisation par des graphesRéseaux sociauxSommets = URL de blogs[Image empruntée àArcs = Hyper-liens7bis.wordpress.com/tag/reseaux-sociaux/]11/108Définitions1Introduction2Définitions3Structures de données pour représenter un graphe4Parcours de graphes5Plus courts chemins6Problèmes de planification7Quelques problèmes NP-difficiles sur les graphes12/108DéfinitionsGraphes non orientésDéfinitionUn graphe non orienté est défini par un couple(S;A)tel queSest un ensemble desommetsASSest un ensemble d"arêtesLa relation binaire définie parAestsymétrique;8(si;sj)2SS;(si;sj)2A,(sj;si)2A(notéfsi;sjg)Exemple :S=f1;2;3;4;5;6gA=ff1;2g;f1;5g;f5;2g;f3;6gg123456Terminologie :siestadjacentàsjsi(si;sj)2A:adj(si) =fsjjfsi;sjg 2Agdegréd"un sommet = nombre de sommets adjacents :d(si) = #adj(si)Graphecompletsi8fsi;sjg S;fsi;sjg 2A13/108DéfinitionsGraphes orientésDéfinitionUn graphe orienté est défini par un couple(S;A)tel queSest un ensemble de sommetsASSest un ensemble d"arcs;Relation binairenon symétrique:(si;sj)2A6)(sj;si)2AExemple :S=f1;2;3;4;5;6gA=f(2;1);(1;5);(2;5);(5;2);(4;5);(3;6);(6;3);(6;6)g123456Terminologie :sjestsuccesseurdesisi(si;sj)2A:succ(si) =fsjj(si;sj)2Agsjestprédécesseurdesisi(sj;si)2A:pred(si) =fsjj(sj;si)2Agdemi-degré extérieur= nb de successeurs :d+(si) = #succ(si)demi-degré intérieur= nb de prédécesseurs :d(si) = #pred(si)14/108DéfinitionsGraphes partielsDéfinitionG0= (S;A0)est un graphe partiel deG= (S;A)siA0AExemple :123456GrapheG= (S;A)123456Graphe partiel deG15/108DéfinitionsSous-graphesDéfinitionG0= (S0;A0)est un sous-graphe deG= (S;A)siS0SetA0=A\S0S0;G0est le sous-graphe deGinduitparS0Exemple :123456GrapheG= (S;A)125Sous-graphe deGinduit parf1;2;5g16/108DéfinitionsCheminements et connexitésDéfinitions dans le cas d"ungraphe non orienté G= (S;A)Chaîne= Séquence de sommets