Qu'est-ce qu'un algorithme d'intelligence artificielle ?
Des algorithmes à l'intelligence artificielle
Pour planter le décor, voici la définition d'un algorithme, telle que donnée par la CNIL en 2018 : « la description d'une suite finie et non ambigüe d'étapes (ou d'instructions) permettant d'obtenir un résultat à partir d'éléments fournis en entrée ».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 ».
Quelle est la différence entre algorithme et intelligence artificielle ?
Quand on parle d'intelligence artificielle, on fait souvent référence au fait d'imiter un cerveau, c'est à dire avec un réseau de neurones qui est capable d'apprendre, contrairement à un algorithme classique qui ne fait que du calcul de façon bête et méchante comme une calculatrice.
- Il utilise une évaluation heuristique sur chaque nœud pour estimer le meilleur chemin y passant, et visite ensuite les nœuds par ordre de cette évaluation heuristique.
C'est un algorithme simple, ne nécessitant pas de prétraitement, et ne consommant que peu de mémoire.
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 & Programmation II -:: UMI E-Learning ::
INSA de Lyon3IFAnnée scolaire 2018-2019TD d"Algorithmique Avancée pourl"Intelligence Artificielle et les GraphesExercice 1 :Considérons un réseau social dans lequel les membres peuvent choisir d"être amis(siaest ami deb, alorsbest nécessairement ami dea).
Nous souhaitons montrer qu"il existe aumoins deux membres du réseau qui ont le même nombre d"amis, et qu"il existe un nombre pairde membres ayant un nombre impair d"amis.1.Définiss ezun graphe et r eformulezces deux pr opriétéspar rapport à ce graphe. 2.Démontr ezles deux pr opriétés.Exercice 2 :Un groupe de neuf scouts partent camper dans la montagne.
Ils communiquent enmorse, avec leurs lampes de poche, mais les configurations du terrain font que :- Arthur ne peut communiquer qu"avec Babar et Donald;- Babar ne peut communiquer qu"avec Arthur et Fernand;- Céleste ne peut communiquer qu"avec Fernand;- Donald ne peut communiquer qu"avec Arthur et Gontran;- Ernestine ne peut communiquer qu"avec Fernand, Gontran et Isidore;- Fernand ne peut communiquer qu"avec Babar, Céleste, Ernestine et Isidore;- Gontran ne peut communiquer qu"avec Donald, Ernestine et Hugo;- Hugo ne peut communiquer qu"avec Gontran et Isidore;- Isidore ne peut communiquer qu"avec Ernestine, Fernand et Hugo.Afin d"être certains que tout le monde soit bien informé, ils ont convenu que tout scout recevantun message pour la première fois le retransmet instantanément à son tour.
Arthur veut envoyer lemessage "Toujours prêt" à ses camarades.En supposant que l"envoi du message en morse prendune minute à chaque fois, Arthur souhaite savoir combien de temps il faudra pour que tout lemonde ait reçu son message, et qui seront les derniers informés.1.Définisse zun graphe, et r eformulezle pr oblèmeen le ramenant à un pr oblèmevu en cours. 2.Quel algorithm epermet de résoudr ece pr oblème?Résolvez-le en détaillant les étapes de la résolution.Exercice 3 :Le savant Cosinus souhaite ordonner ses vêtements de telle sorte qu"il puisse lesenfiler du premier au dernier, sachant que- le caleçon (k) doit être enfilé avant le pantalon (p) et les chaussures (c),- les chaussettes (t) doivent être enfilées avant les chaussures (c),- le pantalon (p) doit être enfilé avant de mettre la ceinture (u) et les chaussures (c),- la chemise (h) doit être enfilée avant de mettre la cravate (r) et la ceinture (u),- la cravate (r) et la ceinture (u) doivent être mises avant d"enfiler la veste (v),- la montre (m) peut être mise à tout moment.1.Définisse zun graphe, et r eformulezle pr oblèmeen le ramenant à un pr oblèmevu en cours. 2.Quel alg orithmepermet de résoudr ece pr oblème?3.Résolv ezle pr oblèmeen détaillant les étapes de la résolution.
Christine Solnon et Christian Wolf 1 1/4Année scolaire 2018-2019 INSA de Lyon3IFExercice 4 :L"algorithme de Kosaraju décrit ci-dessous permet de rechercher les composantesfortement connexes (CFC) d"un graphe orienté.
1) FonctionKosaraju(g)Entrée :Un graphe orientég= (S;A)Postcondition :Retourne l"ensemble des composantes fortement connexes deg2CFC ;3num DFSnum(g)4Construire le graphegt= (S;At)tel queAt=f(si;sj)j(sj;si)2Ag5Colorier tous les sommets degten blanc6pourchaque sommetsipris par ordre denumdécroissantfaire7sisiest blancalors8B fsj2Sjsjest blancg9DFSrec(gt;si)10Ajouter àCFCl"ensemblefsj2Bjsjest noirg11retourneCFCExécutez cet algorithme sur le graphe ci-dessous en détaillant les étapes de la résolution.abcdghfiePour nous convaincre de la correction de cet algorithme, nous introduisons le graphe des com-posantes fortement connexesgcfc= (Scfc;Acfc)tel que-Scfcest une partition deStelle que chaque sommet deScfccontient tous les sommets deSappartenant à une CFC différente;-les ar csde gcfctraduisent l"existence de chemins entre les sommets des CFC :Acfc=f(cfci;cfcj)2ScfcScfcj 9un cheminhs1;:::;skitel ques12cfci;sk2cfcjgCe graphe peut-il avoir des circuits?Dessinezgcfcpour le graphe précédent.Montrez qu"après l"exécution de la ligne 3 de l"algorithme, pour tout arc(cfci;cfcj)2Acfc, la plusgrande valeur denumde l"ensemble des sommets decfciest supérieure à la plus grande valeur denumde l"ensemble des sommets decfcj.
Autrement dit,maxfnum[si]jsi2cfcig> maxfnum[sj]jsj2cfcjgEn déduire des propriétés sur les couleurs des sommets au moment de l"appel à DFSrec(gt;si)(ligne 9 de l"algorithme) :-Peut-il y avoir des sommets gris ?-Que peut -ondir edes sommets noirs ?-Que peut -ondir edes sommets blancs ?En déduire que l"algorithme est correct.2/4 2 Christine Solnon et Christian WolfINSA de Lyon3IFAnnée scolaire 2018-2019Exercice 5 :Partant de Moscou, Michel Strogoff, courrier du Tsar, devait rejoindre Irkoutsk.Avant de partir, il avait consulté une voyante qui lui avait dit entre autres choses :"Après Kazan, méfiez-vous du ciel, à Omsk, attention aux tartares, dans Ekaterinbourg, atten-tion aux yeux, après Astana, méfiez-vous de l"eau, et surtout prenez garde partout à un grandbrun avec des bottes noires "A partir de ces informations, Michel Strogoff avait estimé, pour chaque liaison entre deux villes,sa probabilité de réussite ainsi que le temps nécessaire, en jours (chiffre entre parenthèses) :0.5 (2)0.8 (3)0.1 (2)1 (2)0.9 (2)1 (3)0.7 (2)0.5 (3)0.5 (1)0.9 (4)0.3 (1)0.8 (2)0.9 (6)AstanaIrkouskEkaterinbourgOmskMoscouNovosibirkKazan1.Quel algorithme peut-il utiliser pour tr ouverle chemin le plus sûr allant de M oscouà Irkoutsk? Quelles adaptations faut-il apporter à cet algorithme? Déterminez un itinéraireoptimal en détaillant les étapes de la résolution.2.Michel Str ogoffse r enditalors compte qu"il pouvait y avoir plusieurs chemins, allant de Moscou à Irkoutsk, qui maximisent sa probabilité de réussite.
Il décida alors de choisir,parmi les différents chemins les plus sûrs, le plus rapide.Quel algorithme peut-il utiliserpour cela? Quelles adaptations faut-il apporter à cet algorithme? Déterminez un itinéraireoptimal en détaillant les étapes de la résolution.Exercice 6 :Arthur a 6 camarades (Babar, Céleste, Donald, Ernest, Ferdinand et Gontran) avecquiilvajouerautennis.Quandilvajouerautennisavecundeces6camarades,ilpasseleprendrechez lui, et fait ensuite la route jusqu"au terrain de tennis avec lui.
Il souhaiterait optimiser sestemps de parcours et a établi pour cela un plan du quartier, avec pour chaque tronçon de routele temps estimé (en minutes) pour parcourir le tronçon, en tenant compte des attentes aux feux etautres aléas de la circulation.CelesteFerdinandBabarGontranDonald1 1113Arthur2Ernest1626214TennisChristine Solnon et Christian Wolf 3 3/4Année scolaire 2018-2019 INSA de Lyon3IFPour chacun de ses 6 camarades, il vous demande quel est l"itinéraire le plus rapide pour aller dechez lui jusqu"au terrain de tennis, en passant par chez son camarade.1.Définissez un graphe, et r eformulezle pr oblèmeen le ramenant à un pr oblèmevu en cours. 2.Quel algorithme vu en cours permet de résoudr ece pr oblème?Comment l"adap terpour minimiser le nombre de calculs à faire?3.Résolvez le pr oblèmeen détaillant le dér oulementde l"algorithme.
Exercice 7 :Aujourd"hui Jon a décid