Fiche de révision : Analyse des algorithmes et détection d'alignements dans une matrice binaire

📋 Plan du Cours

1. Analyse manuelle et rôle d'une fonction d'approximation par dichotomie
2. Algorithme récursif de calcul de factorielle et décomposition d'entier en somme de factoriels
3. Construction modulaire d'une matrice binaire à partir d'un fichier texte selon règles de remplissage
4. Recherche d'alignements horizontaux de 1 dans une matrice binaire
5. Recherche d'alignements verticaux par transposition de matrice
6. Décalage des lignes de matrice pour recherche d'alignements diagonaux
7. Assemblage des modules pour affichage des alignements de N éléments dans une matrice binaire

📖 1. Analyse manuelle et rôle d'une fonction d'approximation par dichotomie

🔑 Notions clés & Définitions

• Fonction quoi : Une procédure algorithmique qui calcule une approximation de la racine carrée d'un nombre x en utilisant la méthode de dichotomie, en ajustant itérativement les bornes a et b selon la comparaison entre y au carré et x.
• Soit : Un terme utilisé pour introduire une variable ou une condition dans un contexte mathématique ou algorithmique afin de poser une hypothèse ou définir un élément.

📝 Points essentiels

• Déduire le rôle de la fonction quoi.
• La fonction quoi calcule une approximation de la racine carrée d'un nombre x par dichotomie.

💡 À retenir

Comprendre comment une fonction récursive ou itérative peut approximer une valeur numérique par dichotomie en affinant progressivement un intervalle.

📖 2. Algorithme récursif de calcul de factorielle et décomposition d'entier en somme de factoriels

🔑 Notions clés & Définitions

• Entier naturel : Un nombre entier positif ou nul utilisé pour compter, ordonner, et dans ce contexte, pour calculer des factoriels ou décomposer un entier en somme de factoriels.
• Fonction récursive Fact : Écrire l’algorithme d’un module permettant de retourner la décomposition d’un entier positif en une somme de factoriels.

📝 Points essentiels

• La fonction Fact calcule récursivement la factorielle d'un entier naturel N, définie par N! = 12...*N.
• Tout entier naturel positif N peut s’écrire de façon unique comme somme pondérée de factoriels : N = a11! + a22! + ... + ad*d! avec des coefficients entiers positifs.
• L’algorithme utilise la fonction Fact pour décomposer un entier en somme de factoriels en déterminant les coefficients a1, a2, ..., ad.
• Note : ………/20 2 | 5 Exercice N°2 : (4 points) Tout entier naturel positif N peut s’écrire de façon unique sous la forme : N=a1*1 !

💡 À retenir

Maîtriser la récursivité pour calculer des factoriels et appliquer cette fonction pour décomposer un entier en somme unique de factoriels.

📖 3. Construction modulaire d'une matrice binaire à partir d'un fichier texte selon règles de remplissage

🔑 Notions clés & Définitions

• Matrice binaire : Une structure rectangulaire composée uniquement de 0 et de 1, utilisée pour représenter des données sous forme de grille binaire.
• Fichier Texte : Un fichier contenant des données textuelles structurées, ici utilisé pour stocker les séquences numériques et tirets qui déterminent la matrice.

📝 Points essentiels

• Le nombre de lignes de la matrice correspond au nombre total de lignes du fichier texte.
• Le nombre de colonnes est déterminé par la somme des entiers plus le nombre de tirets (-) dans chaque ligne, le maximum sur toutes les lignes fixant la dimension.
• Chaque entier dans une ligne indique un groupe de 1 consécutifs à insérer dans la matrice, séparés par un 0 entre groupes.
• Les cases restantes dans une ligne sont remplies par des 0 pour compléter la ligne jusqu'au nombre de colonnes.
• Le plus grand résultat obtenu sur l'ensemble des lignes détermine le nombre de colonnes de la matrice.
•  Les cases restantes de la ligne (si la séquence ne remplit pas toute la ligne) sont complétées par des 0.

💡 À retenir

Savoir construire une matrice binaire à partir d'un fichier texte en appliquant des règles précises de calcul de dimensions et de remplissage modulaire.

📖 4. Recherche d'alignements horizontaux de 1 dans une matrice binaire

🔑 Notions clés & Définitions

• Alignement horizontal : Une suite consécutive de 1 de longueur N située dans une même ligne d'une matrice binaire.
• Recherche d’alignements : Le processus consistant à détecter des suites consécutives de 1 de longueur N dans les lignes ou colonnes d'une matrice binaire.

📝 Points essentiels

• La recherche d'alignements horizontaux consiste à détecter des suites consécutives de 1 de longueur N dans chaque ligne de la matrice.
• La procédure trouve_align_H utilise trouve_suite pour remplir un tableau d'enregistrements TH contenant le numéro de ligne et l'indice de début de chaque alignement horizontal.

💡 À retenir

Appréhender la détection systématique d'alignements horizontaux dans une matrice binaire via des procédures modulaires et structurées.

📖 5. Recherche d'alignements verticaux par transposition de matrice

🔑 Notions clés & Définitions

• Matrice transposée M1 : Une matrice obtenue en échangeant les lignes et les colonnes d'une matrice M, de sorte que l'élément en position (i, j) dans M devienne l'élément en position (j, i) dans M1.

📝 Points essentiels

• M= Matrice transposée M1= Question : 1.
• Ecrire une procédure transpose (M, NL, NC, M1) permettant de construire la matrice transposé M1 de la matrice M.

💡 À retenir

Exploiter la transposition de matrice permet de transformer la recherche verticale d'alignements en un problème horizontal déjà résolu.

📖 6. Décalage des lignes de matrice pour recherche d'alignements diagonaux

🔑 Notions clés & Définitions

• Décalage gauche : Décalage qui consiste à décaler chaque ligne d'une matrice vers la gauche d'un nombre de colonnes égal à son rang, en complétant par des zéros aux extrémités.

📝 Points essentiels

• La recherche d'alignements diagonaux s'effectue en décalant chaque ligne de la matrice vers la gauche ou la droite selon son rang.
• La procédure decale_gauche décale chaque ligne vers la gauche d'autant de colonnes que son numéro de ligne, complétant par des zéros aux extrémités.
• La procédure decale_droite réalise un décalage similaire vers la droite avec compléments en zéros.
• Ces décalages permettent de transformer la recherche diagonale en une recherche verticale ou horizontale dans la matrice décalée.

💡 À retenir

Comprendre comment le décalage des lignes de matrice facilite la détection d'alignements diagonaux en transformant la structure des données.

📖 7. Assemblage des modules pour affichage des alignements de N éléments dans une matrice binaire

🔑 Notions clés & Définitions

• Alignements de N éléments dans : Suites consécutives de N éléments identiques (1 dans ce contexte) détectées dans la matrice M selon les directions horizontale, verticale ou diagonale.

📝 Points essentiels

• La matrice M est supposée déjà remplie par des 0 et 1 avec dimensions NL lignes et NC colonnes.
• Dans la suite, nous décidons de rechercher les alignements de 1 dans une matrice M de dimension NL lignes*NC colonnes déjà remplie par des 0 et des 1.

💡 À retenir

Savoir combiner plusieurs modules algorithmiques permet de produire un affichage complet et structuré des alignements dans une matrice binaire.

📊 Tableaux de Synthèse

Comparaison des méthodes de recherche d'alignements

⚠️ Pièges & Confusions Fréquentes

1. Confusion entre alignements horizontaux, verticaux et diagonaux.
2. Oublier de transposer la matrice pour la recherche verticale.
3. Ne pas ajuster la taille de la matrice lors du décalage pour recherche diagonale.
4. Erreur dans le calcul du nombre de colonnes lors de la construction de la matrice à partir du fichier texte.
5. Confusion entre décalage vers la gauche et vers la droite pour la recherche diagonale.
6. Oublier de compléter par des zéros après décalage.
7. Mauvaise gestion des limites lors de la recherche d'alignements.

✅ Checklist Examen

1. Comprendre la fonction d'approximation par dichotomie.
2. Maîtriser la récursivité pour le calcul de factorielle.
3. Savoir construire une matrice binaire à partir d'un fichier texte.
4. Savoir détecter des alignements horizontaux dans une matrice.
5. Utiliser la transposition pour la recherche verticale.
6. Appliquer le décalage pour la recherche diagonale.
7. Assembler les modules pour afficher tous les alignements.
8. Vérifier la cohérence des dimensions de la matrice.
9. Gérer les cas limites lors de la recherche d'alignements.
10. Tester chaque étape séparément pour éviter les erreurs.
11. Documenter chaque procédure pour clarifier leur rôle.
12. Utiliser des exemples concrets pour valider chaque étape.