Fiche de révision : Introduction à l’algorithmique

📋 Plan du Cours

1. Machines de Turing et calcul universel
2. Automates cellulaires et parallélisme
3. Domaines et métiers de l’informatique
4. Définition et rôle des algorithmes
5. Mariages stables et affectation
6. Du problème au programme
7. JavaScript et pages web interactives

📖 1. Machines de Turing et calcul universel

🔑 Notions clés & Définitions

• Machine de Turing : Une machine de Turing est un modèle de calcul équipé d’un ruban et capable d’exécuter des instructions.

★ À maîtriser

• Les machines de Turing sont à l’origine du premier problème d’indécidabilité connu, le problème de l’arrêt.

Compléments

• L’exécution présentée d’une machine de Turing réalise une division entière par 2.

💡 Astuce mémo

Règles d’exécution → calcul ; limites du calcul → problème de l’arrêt

📖 2. Automates cellulaires et parallélisme

🔑 Notions clés & Définitions

• Automate cellulaire : Un automate cellulaire est une grille de cellules dont chaque cellule possède un état qui évolue au cours du temps selon des règles.

★ À maîtriser

• Dans un automate cellulaire, l’état d’une cellule au temps suivant dépend de son état au temps présent et de celui de ses cellules voisines.

Compléments

• Le Jeu de la vie de Conway, créé en 1970, peut simuler la résolution de n’importe quel calcul.

📌 Un automate cellulaire peut être vu comme un ordinateur exécutant plusieurs tâches en parallèle, chaque cellule constituant une tâche.

💡 Astuce mémo

Une grille de cellules dont chaque case évolue avec ses voisines

📖 3. Domaines et métiers de l’informatique

★ À maîtriser

• L’informatique couvre une diversité de domaines, de métiers, d’enseignements et de recherches.

• Les applications informatiques citées comprennent:

  • le traitement de données
  • les systèmes interactifs
  • la synthèse de parole
  • la reconnaissance de formes
  • l’apprentissage automatique
  • la simulation
  • la traduction
  • la commande de machines-outils

Compléments

• L’informatique est présente dans des objets comme les voitures, les montres, les réfrigérateurs, les ascenseurs et la robotique.

• Les métiers cités comprennent:

  • développeur
  • administrateur réseau
  • administrateur de bases de données
  • auditeur
  • consultant
  • ingénieur
  • chercheur

📖 4. Définition et rôle des algorithmes

🔑 Notions clés & Définitions

• Algorithme : Suite ordonnée d’instructions non ambiguës permettant de résoudre un problème donné.
• Algorithmique : Science des algorithmes qui s’intéresse à la manière de les construire.

📝 Points essentiels

• L’algorithmique s’intéresse notamment à:
  • la terminaison
  • la validité
  • la complexité
  • la réutilisabilité

💡 Astuce mémo

Algorithme = suite d’instructions ; algorithmique = science qui les construit et les analyse

📖 5. Mariages stables et affectation

🔑 Notions clés & Définitions

• Mariages stables : Le problème des mariages stables consiste à former des couples entre deux communautés selon les préférences de chaque membre pour les membres de l’autre communauté.

★ À maîtriser

• Pour chaque membre célibataire de la première communauté, l’algorithme de Gale et Shapley essaie le membre préféré qui ne l’a pas encore rejeté, puis le couple est formé ou la proposition est rejetée selon la préférence du membre déjà engagé.

• L’algorithme de Gale et Shapley, publié en 1962, produit une solution stable optimale pour la communauté qui propose.

📌 L’affectation post-bac adapte les mariages stables à des formations pouvant accueillir plusieurs candidats, à des vœux limités des candidats et à des classements limités aux candidatures reçues.

Compléments

• En 2019, 66 % des candidatures ont été traitées avec l’outil d’aide à la décision de Parcoursup, d’après la Cour des Comptes.

💡 Astuce mémo

Préférer → proposer → rejeter ou former un couple

📖 6. Du problème au programme

🔑 Notions clés & Définitions

• Langage algorithmique : Représentation textuelle d’un algorithme destinée à un lecteur humain.

★ À maîtriser

📌 Un algorithme décrit la suite d’actions pour résoudre un problème, tandis que la programmation traduit cet algorithme dans un langage de programmation pour produire un programme.

• La programmation ou implémentation traduit un algorithme dans un langage de programmation, puis le code source est transformé par compilation ou interprétation en binaire compréhensible par la machine.

Compléments

• Le langage algorithmique recherche un compromis entre la simplicité et la lisibilité de la langue naturelle et l’absence d’ambiguïté nécessaire à l’implémentation.

• Le cours choisit JavaScript comme langage de programmation et indique qu’il existe plus de 700 langages de programmation.

💡 Astuce mémo

Problème → algorithme → programme

📖 7. JavaScript et pages web interactives

🔑 Notions clés & Définitions

• JavaScript : Langage de programmation informatique créé pour rendre les pages web vivantes et dynamiques.

★ À maîtriser

• JavaScript s’écrit sous forme de scripts dans des fichiers d’extension .js liés au code HTML et est interprété par les navigateurs côté client.

• Pour lier un fichier JavaScript à une page HTML, il faut indiquer dans la balise head le chemin relatif du fichier avec la balise <script src="chemin/script.js"></script>.

Compléments

• 🔄 Depuis JavaScript, un programme peut:
  1. récupérer des balises HTML
  2. modifier des balises HTML
  3. créer des balises HTML
  4. lire une donnée dans une balise input
  5. afficher un résultat calculé

📊 Tableaux de synthèse

Algorithme, pseudo-code et programme