Articles sur Blog | 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.

Cours sur les systèmes d’exploitation

Tout informaticien sait que les systèmes d’exploitation forment une couche logicielle importante pour le bon fonctionnement d’un ordinateur. Pour bien comprendre le bon fonctionnement des ordinateurs, Il faut bien comprendre la distinction entre logiciel et matériel. Un système d’exploitation est du logiciel, mais différent des logiciels normaux. Les systèmes d’exploitation sont différents des applications normales, Par exemple, un système d’exploitation ne peut pas être un jeu vidéo, ou un lecteur audio, ou, un éditeur de texte. Les systèmes d’exploitation, comme Microsoft Windows, Linux, ou MacOS, forment une couche logicielle intermédiaire entre le hardware et entre les applications. Ça simplifie d’une manière significative aux applications l’utilisation du matériel. Ça permet aussi aux différentes applications de cohabiter en symbiose sur le même système. Ça donne aussi aux utilisateurs les mécanismes et les outils pour contrôler leurs propres machines.

Cours sur les Systèmes d’exploitation

On peut encore continuer à énumérer les différents rôles d’un système d’exploitation. Mais il faut savoir que le rôle des systèmes d’exploitation est primordial en informatique. Sur la vidéo en haut de la chaîne Youtube Lectures for sleep & study, un excellent cours sur les systèmes d’exploitation est présenté. L’aspect abordé sur cette vidéo est l’aspect académique, ça veut dire que ça parle du côté technique interne des systèmes d’exploitation. Ça permet principalement aux étudiants en informatique de comprendre comment réellement un système d’exploitation fonctionne de l’intérieur.

Analyse de l’ordinateur de la fusée qui s’est posée sur la Lune

Ça a été dit que le moment où l’humain a foulé le premier pied sur la lune, était un grand pas pour l’humanité. Et c’était vrai, c’était une révolution sans précédent. Dans la vidéo qui suit, on va voir une analyse croustillante sur l’ordinateur de bord qui a beaucoup aidé à la réalisation de cette mission. L’ordinateur en question s’appelle Apollo Guidance Computer (AGC), un ordinateur très faible techniquement en comparaison aux normes des ordinateurs des temps modernes. Historiquement, c’était un ordinateur qui a été développé par l’université du Massachusetts dans le début des années 60 avec des techniques, disons-le, ingénieuses et peu présentes dans les architectures modernes. On peut aussi mentionner des procédés obsolètes comme par exemple ; L’utilisation du complément-à-1 un pour représenter les entiers, alors que toutes les architectures modernes utilisent le complément-à-2. Ou l’utilisation de la technologie obsolète de mémoire dite mémoires à tores de ferrite. Ou l’utilisation des banques de mémoire lorsque l’architecture possède peu de bites pour adresser la mémoire dans sa totalité. Néanmoins, l’AGC utilise des techniques, à mon avis, qui sont révolutionnaires pour l’époque. Comme l’encodage de l’adressage indirect utilisant une technique pour hacker une instruction et la fusionner avec la suivante. Ou l’utilisation de l’adressage mémoire pour accéder aux différents registres, ce qui simplifie significativement la programmation. Ou l’instruction bizarre, jamais vu de ma part, appelée CCS “Count, Compare, and Skip”. Ce qui m’a aussi marqué c’est l’utilisation des portes discrètes universelles NAND pour construire toutes l’architecture.

Présentation sur Apollo Guidance Computer

Moi personnellement, ces voyages dans le passé sur les architectures de l’époque, j’en raffole. J’ai même développé une passion dans l’exploration et la compréhension des architectures des machines et des consoles du passé. Vous allez voir sur la vidéo beaucoup d’explication technique concernant l’architecture des ordinateurs et la conception hardware, du passé. À mon avis, c’est l’un des meilleurs endroits aux étudiants pour apprendre et se familiariser avec ce domaine du hardware. La vidéo a été conjointement présentée par Michael Steil (voici son blog) and Christian Hessmann, le premier est un nom bien connu dans ce spécifique domaine. Comme de coutume, ça a été présenté à la plus grande convention de hacker en Europe, le Chaos Computer Club, qui se déroule tous les ans en Allemagne (leur site web et chaine Youtube), dans laquelle Michael Steil est souvent invité.

La séquence de démarrage de Linux

N’importe quel informaticien de nos jours sait ce que c’est Linux. C’est le système d’exploitation Open-source et gratuit, adoré par les informaticiens puisqu’il offre beaucoup plus de commanditées aux informaticiens par rapport aux autres systèmes d’exploitation. Néanmoins, dans le marché grand public des PC de bureau, il se place à la 3e place après Windows et Mac OS. L’un des points forts qui rend Linux attrayant pour les informaticiens, est son ouverture et la possibilité de facilement le modifier. Comme vous allez voir sur la vidéo en bas, le processus de démarrage, appelé aussi le processus de boot, de Linux est bien connu et bien documenté, et bien flexible aussi. Contrairement aux autres systèmes d’exploitation. Cet aspect est très intéressant pour les informaticiens d’un point de vue pédagogique, puisque ça permet de comprendre comment un système d’exploitation se comporte. Et aussi d’un point de vue de flexibilité, puisque ça devient plus facile de modifier et de customiser le système d’exploitation aux besoins de l’application.

Linux booting process

La vidéo en haut et celle de la chaîne Youtube ByteByteGo. Une très bonne chaîne technique qui explique généralement des concepts informatiques. Vous allez voir dans la vidéo la succession tout le processus de démarrage du système d’exploitation Linux.

Histoire des FPGAs

De nos jours, Les FPGAs forment le fer de lance éducatif de la conception hardware, et c’est pratiquement le meilleur moyen de créer du hardware par des étudiants. Malgré cela, je l’ai toujours évité. Pour faire apprendre le hardware, j’ai toujours préféré des logiciels de simulation simplistes comme Logisim, ou l’utilisation directe des portes logiques en utilisant des composantes électroniques de la série 74. La raison est que l’apprentissage par FPGA pose plusieurs barrières académiques.

La première barrière, et la plus conséquente à mon avis et sans doute l’argent. Le prix d’une FPGA disons standard, est autour de 10 millions (100000 DA), ce qui est énorme et totalement exorbitant pour un simple étudiant. Pourtant, il existe d’autres moyens pour acquérir des FPGAs avec un prix moins cher. Comme les kits de FPGA vendues dans les sites électroniques chinois. Le compromis avec ces FPGAs c’est que ce sont des FPGAs des générations antérieures. C’est comme de nos jours acheter un PC Pentium 3 pour l’utiliser comme un ordinateur de travail. Il y a aussi une firme chinoise de construction d’FPGAs nommée Tong, qui fournit des produits low-spec (peu performant) mais avec des prix vraiment très bas. J’ai réussi par exemple à trouver en Algérie un modèle de 1 K-portes avec un prix de 3000 DA.

La deuxième barrière est la complexité d’utilisation. En comparaison avec un logiciel de simulation comme Logisim ou l’utilisation directe des portes logiques avec la série 74, les FPGAs sont beaucoup plus complexes. Pour utiliser une FPGA vous devrez tout d’abord, Avoir un bon PC pour installer le logiciel lourd du développement d’FPGA. Avoir une licence du constructeur pour utiliser ce logiciel. Dans certains cas, avoir un câble spécial pour flasher ou supplanter le nouveau circuit dans l’FPGA. La puce FPGA se trouvant sur une carte électronique (PCB) avec des entrées/sorties et plusieurs composantes, vous devrez vous documenter sur cette carte pour pouvoir l’utiliser…etc.

La troisième barrière, aussi en liaison avec la deuxième barrière, c’est le temps d’apprentissage additionnel nécessaire pour pouvoir utiliser les FPGAs. En sachant que l’FPGA est par nature complexe, son utilisation demande un certain temps d’apprentissage. Comme par exemple les logiciels de développement, appelés généralement EDA, en dehors du développement du circuit, une dizaine d’autres étapes sont nécessaires pour pouvoir implanter le circuit développé sur l’FPGA.

Histoire des FPGAs

La vidéo en haut est hébergé sur la chaîne Youtube d’Asianometry. Une bonne chaîne consacrée au développement hardware et aux puces électroniques. La vidéo ne traite pas à proprement dit les FPGAs, mais plutôt une vue historique sur l’évolution de ces derniers. Intéressant de comprendre comment s’est fait l’évolution de ce hardware particulier, qu’on peut désigner comme du hardware volatile.

Adresse réseau MAC

Le fonctionnement des réseaux informatiques à un bas niveau, ça veut dire à un niveau proche de la transmission électrique, là où les protocoles essentiels et élémentaires formant l’infrastructure basique qui va construire cet immense réseau d’Internet. On trouve principalement 2 formes d’adresses pour distinguer une entité dans le réseau. La plus connue est sans doute l’adresse IP, c’est principalement l’adresse qui va distinguer votre ordinateur parmi des millions d’ordinateurs sur l’ensemble d’internet. C’est une adresse dite logique, parce qu’elle n’est pas fixe à la machine, et change souvent car elle est en général affectée par le fournisseur d’accès à Internet ISP. La 2e forme d’adresse est l’adresse MAC, et contrairement à l’adresse IP cette adresse est fixe à la machine et ne théoriquement pas être changée. Cette adresse est généralement appelée l’adresse physique, et plus précisément elle se trouve gravée sur la carte réseau (le NIC) de la machine. Contrairement à l’adresse IP, L’adresse MAC est normalement utilisée pour reconnaître les machines locales dans le même réseau, les machines qui ont une connexion physique directe, comme par exemple les ordinateurs, les téléphones, les tablettes connectés au même routeur dans la maison. Dans le réseau local, une machine doit avoir les 2 adresses en même temps, et c’est le protocole ARP qui permet de faire la liaison entre ces 2 adresses en détenant une base de données des adresses de toutes les machines sur le réseau. Sur la vidéo en bas de la chaîne PowerCert Animated Videos plus de détails sont donnés et la manière exacte d’utiliser ces adresses est bien expliquée.

L’adresse MAC

Le jeu de la vie de Conway

John Conway est un brillant mathématicien qui a travaillé sur un concept qui s’appelle le jeu de la vie. C’est un concept avec un raisonnement un peu particulier, consistant à créer des entités complexes évoluant à partir d’entités simples, cultivées dans un environnement régi par un nombre restreint de règles très simples. Ce jeu a permis après en mathématique, la création ce qu’on appelle les Automates Cellulaires. Mais très récemment, ça a beaucoup évolué et ça a abouti à un nouveau domaine scientifique nommé Artificial Life (ou ALife), consistant à créer de la vie artificielle, et potentiellement intelligente, dans un environnement virtuel contrôlé par des lois et des règles artificielles et des stimulus. La plus récente percée est sans doute le projet Lenia.

Le jeu de la vie par John Conway

Sur les 2 vidéos de l’excellente chaîne Youtube Numberphile, on peut voir l’explication du jeu de la vie, par Conway. Il explique entre autres, comment le jeu s’exécute, l’historique de son évolution, et les différentes études mathématiques effectuées sur ce jeu. Dans ce genre de système, Il est fascinant de voir comment avec des automatismes et des règles si simples, on peut créer des entités relativement évoluées et indépendantes. Et surtout, ça ouvre la porte sur un nombre de créations infini. Mais le principal problème pour ces systèmes, c’est qu’il est très difficile de contrôler ce processus de création. L’évolution dans ce genre de système est tellement complexe qu’il est très difficile de prédire le résultat après un nombre élevé d’itérations. Le plus important c’est d’arriver à créer des systèmes stable dans le temps.

L’invention du jeu de la vie par Conway

La question naturelle qui se pose pour un informaticien est de savoir s’il est possible de recréer un système informatique en utilisant ces automates. Et s’il est possible de les recréer physiquement, en électronique ou sur une autre technologie d’information. John Conway a déjà évoqué dans les vidéos qu’il est possible de créer des configurations pour le calcul. Ça reste à savoir s’il serait possible de recréer n’importe quel système informatique complet. Peut-être en réussissant à recréer l’une des Portes Universelles (ou même les Transistors), avec la possibilité de faire transmettre l’information, il serait possible de construire des processeurs et des composants hardwares avec des caractéristiques nouvelles et différentes.

Introduction au jeu de Go

Le jeu de Go est un jeu de table comme les jeux d’échecs ou le jeu de dames. Peu connu mondialement mais très populaire en Asie de l’Est, notamment au Japon, en Corée du Sud, et en Chine. À l’instar des jeux d’échecs, c’est un jeu très technique qui demande beaucoup de réflexion. Comme vous allez voir sur la vidéo, ses règles sont très simples mais la quantité de stratégies qui peuvent en découler de ces règles est sans limite. Comme les jeux d’échecs, le jeu de Go baigne dans une culture propre à lui. Il possède une communauté et un nombre énorme d’adeptes, avec des associations, des clubs, des centres de formation, des livres, des cours… etc. Les joueurs haut niveau qui participent aux compétitions mondiales, sont généralement intensément entraînés dès leur plus jeune âge.

How to play Go

Beaucoup de personnes pensent que le jeu de Go est plus technique que le jeu d’échecs, mais réellement, il est difficile de présenter des arguments suffisamment solides dans une activité purement intellectuelle. En tout cas, deux événements historiques à retenir pour ces deux jeux. C’est la défaite de Garry Kasparov, le top mondial des échecs, en 1997 face à l’IA de IBM Deep Blue. Depuis, l’intelligence artificielle est jugée plus forte dans ce jeu que l’être humain. Et aussi plus récemment, en 2016, le champion du monde du jeu de Go Lee Sedol, a perdu face à l’intelligence artificielle de Google AlphaGo. Ce qui démontre la supériorité de l’intelligence artificielle face à l’humain dans ce genre d’exercice intellectuel.