Progammation - www.el-Kalam.com

L’algorithme A* pour la recherche de chemins

On a déjà au préalable évoqué dans un blog précédant un algorithme de recherche très connu qu’est celui de Dijkstra. On avait évoqué l’importance des algorithmes de recherche, ça permet principalement pour les logiciels de navigation comme titre d’exemple, de trouver d’une façon méthodique le plus court chemin à partir de votre position actuelle dans une carte vers une destination donnée. L’algorithme évoqué dans la vidéo en bas de la chaîne YouTube Computerphile est tout aussi important, C’est l’algorithme A* et représente une réelle amélioration de l’algorithme de Dijkstra.

L’agorithme A*

Lorsque nous avons décrit précédemment l’algorithme de Dijkstra, ça nous a sauté aux yeux combien l’algorithme était si intuitif. En prenant un papier et un crayon, et avec un peu de chance il est possible redécouvrir l’algorithme par soi-même. L’hypothèse de départ est que vous avez une carte de plusieurs villes interconnectées par des routes avec des distances différentes, le but est de trouver le plus court chemin d’une ville de départ vers une ville d’arrivée. Intuitivement, on va commencer par la ville de départ avec une distance de 0, et explorer les voisins directs de cette ville tout en avantageant la ville la plus proche. Algorithmiquement, ça va être une file qui contient la liste ordonnée des villes intermédiaires avec leurs distances à la ville de départ. Ce même processus l’exploration va se répéter pour la tête de file, donc la ville la plus proche. Et continuez au fur et à mesure avec les autres villes jusqu’à y arriver à la ville de destination. Bien sûr dès qu’on termine l’exploration d’une ville en doit la supprimer de la liste, puisque c’était au préalable la ville la plus proche et c’est impossible de trouver dans la liste des villes suivantes un chemin plus cours. Il faut aussi entre-temps mettre à jour les distances des villes anciennement explorées si un nouveau chemin plus court est découvert.

Comparaison de Dijkstra et A*

L’algorithme A* représente une extension de l’algorithme de Dijkstra. Il va utiliser ce qu’on appelle en mathématiques une heuristique pour améliorer l’algorithme de Dijkstra. L’heuristique est une amélioration intelligente de l’algorithme de Dijkstra en le poussant plus rapidement vers la destination, et en lui évitant de faire l’exploration de la totalité des courts chemins. Cette amélioration est aussi si intuitive que l’algorithme de Dijkstra lui-même. Il a suffi de modifier l’algorithme non plus d’ordonner la liste des villes par le plus court chemin, mais par l’addition du plus court chemin avec la distance directe (ou à vol d’oiseau) de la ville vers la destination. Ainsi les villes les plus loin de la destination vont être pénalisées et les villes les plus proches vont être avantagées. On peut voir sur la vidéo en haut de la comparaison entre l’algorithme Dijkstra et l’algorithme A*, et comment l’algorithme de Dijkstra fait l’exploration en largeur et le A* étend son exploration vers la destination. Contrairement à l’algorithme de Dijkstra, l’algorithme A* ne garantit pas le plus court chemin.

L’algorithme A* étoile n’est pas aussi précis que l’algorithme de Dijkstra, mais il a l’avantage d’être beaucoup plus rapide. Ce qui le rend un candidat idéal pour les applications temps réel, où le temps de réponse doit être rapide ou borné. C’est particulièrement vrai pour les jeux vidéo avec une vue de haut, où il faut cliquer sur la souris et laisser le caractère trouver son propre chemin sur le terrain. Ça concerne principalement les jeux de stratégie RTS et les jeux de rôle RPG isométrique. L’algorithme assurant le chemin du caractère vers sa destination est généralement appelé Path-Finder. Vous pouvez voir par exemple sur l’image en haut, l’algorithme A* utilisé comme Path-Finder dans le très célèbre jeu de stratégie StarCraft. D’autres algorithmes plus modernes et plus efficaces sont utilisés comme Path-Finder dans les jeux modernes. L’algorithme A* est aussi utilisé en intelligence artificielle pour la résolution des labyrinthes, du rubik’s cube, ou le puzzle du Taquin, et beaucoup bien d’autres.

L’interview du créateur du C++

Non dans un but de l’embellir, le langage C++ est un des langages proéminent dans le paysage de l’informatique moderne. C’est un langage souvent enseigné dans les instituts et universités, et souvent prédominants dans certains secteurs industriels, comme les systèmes embarqués, les jeux vidéo, la robotique, l’automobile, l’aéronautique, et beaucoup d’autres.

La vidéo en bas est l’interview du créateur du langage C++, c’est le danois Bjarne Stroustrup, par le célèbre académicien Lex Fridman sur sa chaîne Youtube de Podcast. Il a commencé la conception du langage dans le début des années 80 dans les laboratoires Bell Labs aux États-Unis. Il explique sur la vidéo comment il s’est inspiré du langage orienté objet Simula, et comment l’introduction de la Programmation Orientée Objet a fait un bond historique énorme sur la courbe d’évolution des langages de programmation.

La principale innovation derrière le langage C++ et la programmation orientée objet est de donner au programmeur la faculté et la flexibilité de créer ses propres types (appelés Classes), et la personnification de l’interaction entre leurs éléments (appelés Objets), ainsi permettre aux programmeurs de créer leurs propres opérations (appelés Méthodes). Ce qui était au préalable fixe ou limité dans les précédents langages de programmation. Le C++ apporte aussi l’Héritage et le Polymorphisme. Le premier permet de réduire la définition et inter-lier les différents types créés. Et le 2e permet de choisir automatiquement l’opération adéquate et spécifique au type impliqué dans l’opération.

La partie à mon sens, la plus intéressante de l’interview, est lorsque Bjarne Stroustrup explique sa philosophie et sa vision directrice lors de la création du langage, c’est ce qui appelle zero-overhead, c’est mis en-avant sur la vidéo en bas. Son critère était qu’un mécanisme ou une abstraction pour qu’elle soit intégrée au langage, elle ne doit ajouter aucune ou zéro surcharge aux performances du programme. Comme par exemple pour les Classes, Il est toujours possible de recréer un concept similaire dans le langage C, mais d’un point de vue de programmation c’est plus facile de le faire en C++, et c’est surtout équivalent du point de vue de performance. C’est de même pour les Templates ou la programmation Générique. Bjarne Stroustrup a aussi fait l’explication d’un nouveau mécanisme appelé Concept, qui pour faire simple, permet aux programmeurs d’imposer des contraintes sur les opérations possibles sur les nouveaux types créés. Comme par exemple, on ne peut pas faire des opérations arithmétiques sur un type de chaînes de caractères.

Le principe du zero overhead

10 problèmes algorithmiques communs pour les entretiens d’embauche

C’est bien connu que l’algorithmique et les structures de données sont la pierre angulaire lorsqu’il s’agit de la programmation informatique. D’ailleurs il existe beaucoup de cours et tutoriels sur internet et sur le sujet. En sachant que dans beaucoup de cas ça représente un axe principal dans les formations en informatique. Malgré cela, la programmation dans les entreprises informatiques dans le cas réel se situe à un niveau supérieur. Les algorithmes sont plus difficiles, les problèmes sont plus complexes, et l’envergure des programmes est en beaucoup plus grande. Ce qui oblige les étudiants en informatique de s’entraîner et de s’exercer sur une forme d’algorithmes plus complexe et plus poussée pouvoir postuler à des postes de programmation dans des sociétés du high-tech.

10 problèmes communs pour les entretiens d’embauche

Ce qui nous ramènent a présenté la vidéo en haut. C’est une vidéo de la chaîne académique YouTube freeCodeCamp comprenant 10 problèmes algorithmiques qui sont censés être difficiles pour des informaticiens débutants. C’est un bon moyen de préparation et d’entraînement pour les entretiens d’embauche et le passage à la vie professionnelle.

Langages de programmation indispensables à apprendre, selon Geohot ?

Geohot est le pseudonyme du célèbre hacker du nom de George Hotz. C’était un hacker bien connu dans le début des années 2000 pour ses jailbreak des téléphones iPhone, et surtout célèbre pour être le premier à pouvoir contourner la sécurité de la console de jeux Playstation 3, réputée à être très sécurisée à son époque. Après avoir eu des problèmes avec la justice, notamment avec la société Sony pour le hack de leur console, Il s’est converti à l’intelligence artificielle et a créé sa propre boîte informatique nommée comma.ai, spécialisée dans la vision des véhicules autonomes. Et après cela, juste récemment il a lancé son propre framework en deep learning appelé tinygrad.

Geohotz chez Lex Fridman

La vidéo est un extrait d’une interview avec le célèbre académicien journaliste Lex Fridman (voici le lien de sa chaîne Youtube). Dans la vidéo, on peut remarquer que Geohot prend plus ou moins le point de vue d’un hacker. Il va souligner l’importance d’apprendre des langages bas niveau, comme le langage C et l’assembleur, avec ce qui est rare pour un informaticien, les langages de description hardware comme Verilog et VHDL. En plus de quelques langages fonctionnels comme de Haskell et des langages ML (Machine Learning) comme le TensorFlow et le PyTorch. Geohot dispose d’une chaîne Youtube très intéressante (voici le lien de la chaîne), dans laquelle vous pouvez trouver des vidéos globalement de programmation et des projets qu’il fait. Il dispose aussi d’une chaîne Twitch, sur laquelle il stream de temps en temps, sur laquelle vous pouvez le contacter directement (voici le lien de la chaîne).

L’algorithme de la recherche dichotomique

La recherche dichotomique, ou encore bien connu en anglais sous le nom de “Binary search”, est un algorithme de recherche bien connu en académie et surtout bien implanté dans le domaine pratique. Ça s’apparente aux arbres binaires dont j’ai récemment écrit un article les concernant. Ils sont apparentés dans le sens où les arbres binaires peuvent implémenter efficacement l’algorithme de la recherche dichotomique.

La vidéo en bas de la chaîne YouTube Computerphile expose très bien le concept de l’algorithme, et même que l’idée derrière cet algorithme est assez simple et intuitive. Supposons un ensemble où vous avez des valeurs ou des entrées ordonnées, comme par exemple un dictionnaire, où les entrées sont ordonnées par ordre alphabétique. La méthode la moins efficace pour chercher un mot est de parcourir les entrées une à une du début à la fin du dictionnaire. Mais en réalité, il est plus optimal de commencer la recherche au milieu. En sachant que les entrées sont ordonnées, vous pouvez deviner si la valeur recherchée se trouve dans la moitié inférieure ou dans la moitié supérieure. Vous venez ainsi d’éliminer le temps de recherche sur la moitié de l’ensemble. Et le processus ensuite va se répéter récursivement pour la moitié restante jusqu’à arriver précisément à trouver la position de votre valeur. C’est ainsi le principe de fonctionnement de la recherche dichotomique.

Algorithme de recherche dichotomique

Théoriquement, cette méthode peut à première vue sembler peu efficace, mais en réalité elle est très très puissante. Si par exemple vous avez un dictionnaire d’un million d’entrées, dans le pire des cas, vous aurez à faire 20 opérations pour trouver votre valeur. Alors que dans une recherche avec la méthode basique de parcourir toutes les entrées, dans le pire des cas, vous aurez à faire un million d’opérations. Entre 20 opérations et un million d’opérations il n’y a pas photo, clairement l’algorithme est très efficace. Et ça l’est encore plus avec des ensembles plus grands, puisque la complexité de cet algorithme est logarithmique. C’est vrai que ça semble vertigineux, si vous ne me croyez pas, vous pouvez tester ça vous-même, en utilisant une calculatrice et en divisant la valeur un million par 2, 20 fois.

Guru99, L’immense portail de tutoriels en informatique

Je viens de découvrir ce site web Guru99 presque par hasard. Par la magie de l’internet, j’ai fait la connaissance de l’un des administrateurs de ce site web, en raison que nous proposons presque le même continu sur le Net. Après avoir fait un bref détour sur le site, j’ai pu constater que c’était un site énorme, et pour lui rendre justice, je dois clairement le qualifier de portail au lieu de sites web. Il contient énormément de tutoriel, fait par différents enseignants, Incluant différents thèmes. D’ailleurs, je n’arrive même pas à inclure tout le contenu dans cet article, ainsi je vais lister ici-bas les partis qui me semblent les plus intéressantes :

Langages de programmation :

Diverses ressources :

Bases de données :

Projet du weekend : Angry Birds-like en Python

Il n’y a pas plus fun et amusant dans la programmation que la programmation des jeux vidéo, le but étant de créer un univers vidéoludique dans lequel les joueurs peuvent s’amuser, et même parfois apprendre, ou être projeté dans un univers imaginaire et suivre une histoire, ou faire la connaissance et socialiser avec d’autres joueurs. Malgré son aspect jovial, la programmation des jeux vidéo n’est pas une tâche si facile. Contrairement à d’autres types d’application, la programmation des jeux vidéo nécessite la maitrise de nombreux aspects très différents les des autres. Comme par exemple, la programmation procédurale, la programmation objet, la programmation événementielle, la programmation concurrentielle, la simulation physique comme sur le tutoriel en bas, la programmation réseaux, la maitrise de quelques notions en algèbre et en géométrie, l’intelligence artificielle, systèmes d’exploitation pour le portage et la distribution sur différentes plateformes, une bonne base d’algorithmes et de structures de données, et surtout l’infographie (ou en Anglais computer graphics)…etc.

Simulation physique sur Python

Sur la vidéo en haut, de l’excellente chaîne Youtube Tech With Tim, il est possible de suivre un petit tutoriel sur comment on peut développer avec Python une simulation physique similaire à la simulation utilisée dans le jeu Angry Birds. La vidéo ne se focalise pas réellement sur l’aspect jeu vidéo, mais plutôt sur l’aspect simulation physique. Il y a beaucoup de jeux dont leur gameplay se base sur la physique, mais dans la plupart du temps, ce n’est pas si facile pour un étudiant ou un débutant avec des connaissances basiques de la programmation de passer à la programmation des jeux vidéo utilisant la physique. En réalité, ce que vous allez voir sur la vidéo est une petite introduction au framework graphique PyGame, qui est utilisée le plus souvent pour le développement de petits jeux vidéo (dit jeux indé). Il est utilisé conjointement avec une autre bibliothèque appelée PyMunk dédiée à assurer la simulation physique du jeu. Normalement pour maîtriser le tout, le développeur doit investir beaucoup de son temps, mais la vidéo ici représente juste une petite introduction pour ce type de programmation pour avoir un pas de départ.

Les arbres binaires comme structure de données

Il est évident que les structures de données en informatique font partie des mécanismes de programmation les plus importantes à maîtriser pour la programmation. Une structure de données est la manière d’organiser la donnée à l’intérieur d’un programme pour que celle-ci soit le plus efficacement possible facile à accéder et à utiliser. Les structures de données, il y en a de tous genre, du plus simple au plus compliqué, comme les tableaux, les vecteurs, les listes chaînées, les piles, les files, les anneaux, les arbres, les graphes…etc.

Cours sur les Arbres Binaires

Sans surprise, les arbres binaires (appelées en Anglais Binary Tree, Bi-Tree ou B-Tree) s’inspirent d’une schématisation arborescente, qui est considérée comme une structure de données relativement plus ou moins complexe. On peut l’imaginer simplement comme une arborescence généalogique d’une famille avec plusieurs générations. Il y a le nœud qui représente l’individu, chaque individu peut posséder plusieurs enfants, les enfants ont leurs propres enfants, et ainsi de suite. Et l’arrière-grand-père le plus haut dans la hiérarchie est appelé la racine de l’arbre, c’est celui qui représente l’arbre. Pour les arbres dits binaires, un individu ne peut posséder plus de 2 enfants. Les arbres binaires sont très utilisés, peut-être le cas le plus probable est celui de la recherche dichotomique. C’est un algorithme très efficace pour la recherche de données dans une grande base de données.

La vidéo en haut de la chaîne YouTube du site web éducatif www.freecodecamp.org illustre cette structure de donnée sous format d’un tutoriel de courte durée pour espérant apprendre à l’intégrer dans ses propres programmes.

Le premier code de Wozniak pour Apple-1

Pour ceux qui ne le savent pas encore, Steve Wozniak avec Steve Jobs sont les cofondateurs de la célèbre firme technologique Apple. Avant la création de cette firme, Steve Wozniak à l’aide de son ami Steve Jobs, ont conçu dans un garage leur première machine Apple-1. Et on soupçonne que le premier code que Wozniak a développé pour cette machine soit son Monitor System. Au tout début, Apple-1 n’avait pas de système d’exploitation (même que Apple-1 officiellement n’a jamais reçu de Système d’Exploitation), ainsi Wozniak a imaginé le développement d’un petit moniteur pour cette machine, appelé Woz Monitor. Par principe, le moniteur est un outil de débogage et de configuration matérielle, en sachant que son principal rôle est de donner la capacité à l’utilisateur d’accéder et de modifier directement la mémoire et les périphériques de la machine. Le moniteur que Wozniak a développé est très simple, il se comporte que de 256 octets, écrit en assembleur 6502, et son code est entièrement disponible et bien expliqué sur Internet (sur cette page) et sur GitHub. Le code du moniteur est très populaire pour les machines faite maison.

Woz Monitor source code

La vidéo en haut et celle de Ben Eater. Personnellement, moi j’en raffole des vidéos de Ben Eater, parce qu’ils sont très académiques, bien clairs, et très bien expliquées. Sur la vidéo, il explique l’utilisation du moniteur pour sa propre machine faite maison.

La programmation d’un émulateur

Étant actuellement un enseignant en architecture des ordinateurs, et un enseignant de programmation et structures de données dans le passé. Je peux sereinement suggérer aux étudiants en informatique, que le meilleur exercice pour maitriser les 2 disciplines est de développer soi-même un émulateur. Alors c’est quoi un émulateur ? L’émulateur par définition est un logiciel qui va reproduire ou répliquer exactement le même comportement d’une machine donnée sur une machine hôte différente. Vous pouvez par exemple émuler une console du type Nintendo sur un PC de bureau. L’émulateur va se comporter exactement comme une console Nintendo le ferait réellement. Vous aurez ainsi l’équivalent d’une console installé sur un PC et vous pourrez jouer à cette console.

Le fait de programmer un émulateur est très enrichissant pour un étudiant. Ça va premièrement, le faire investir en programmation sur un projet relativement de grande envergure, à la différence des petits exercices et travaux pratiques qu’il a l’habitude de faire dans lequel il doit planifier au préalable et construire une architecture logicielle qu’il doit suivre et soutenir tout au long du projet. Et deuxièmement, il doit bien maîtriser l’architecture de la machine à émuler. Il doit effectivement reproduire en logiciel les composantes hardwares de la machine. Ainsi, il va reconstruire le processeur avec toutes ses instructions et ses caractéristiques, il doit aussi reproduire les mémoires de la machine, le système vidéo, le système de son, les entrées/sorties… etc. Sur la vidéo en bas de la chaîne YouTube Computerphile, un émulateur pour la célèbre machine Atari 2600 est grossièrement décrit par le docteur Steve Bagley.

L’émulateur de machines

Il faut savoir que les consoles de jeux sont principalement les émulateurs les plus connus parmi les émulateurs de toutes les machines. Pour la simple raison que ça va permettre aux utilisateurs de jouer à ces machines sur leurs propres ordinateurs. Malheureusement, ces consoles de jeux sont parmi les machines les plus dures à émuler, en raison de la complexité de leur système graphique. Cependant, pour un étudiant avec un bon niveau en programmation et en architecture des ordinateurs, Il lui est possible de développer des émulateurs jusqu’à la 4e génération des consoles de jeux, même si que pour faire tourner de simple démo ou homebrew, incluant ainsi des consoles comme la Nintendo NES, SNES, Sega Mega Drive, Master System…etc. Ce qu’on appelle les consoles à 16 bits. À partir de la 5e génération, ou les consoles dites 32 bits, ça devient difficile pour un simple étudiant de développer tout seul un émulateur pour une machine de ce type, en raison que ces machines sont devenues beaucoup plus puissantes que les précédentes, principalement à cause de l’intégration de la technologie 3D. On peut compter parmi ces consoles, la Sony Playstation 1, La Sega Saturn, La Nintendo 64. Jusqu’aux dernières générations de consoles.