Voici la liste des compétences et connaissances à avoir pour votre deuxième colle.

Grammaires :

• Grammaire non-contextuelle (algébrique, hors-contexte).
• Dérivation.
• Langage engendré. Savoir démontrer par récurrence (sur la longueur du mot ou de la dérivation) que le langage engendré par G est bien ce qu'on souhaite.
• Les langages réguliers sont algébriques.
• Arbre de dérivation.
• Grammaire ambigüe. Dérivation gauche. Savoir montrer qu'une grammaire est ambigüe.
• Analyse syntaxique : exemple.

Révisions sur les graphes :

• Définitions : degré, voisins...
• Chemin, cycle, connexité.
• Connexe à $n$ sommets $\Rightarrow$ au moins $n - 1$ arêtes.
• Acyclique à $n$ sommets $\Rightarrow$ au plus $n - 1$ arêtes.
• Composantes connexes, composantes fortement connexes.
• Un graphe est un arbre ssi il est connexe acyclique ssi connexe et $n - 1$ arêtes ssi acyclique et $n - 1$ arêtes.
• Représentations par matrice et liste d'adjacence.
• Parcours en largeur et profondeur.

Exercice à faire en C sur LeetCode, au plus tard pour samedi prochain : https://leetcode.com/problems/maximum-subarray
Il est possible de résoudre cet exercice en O(n).

Exercice à faire en C sur LeetCode, au plus tard pour samedi prochain : https://leetcode.com/problems/minimum-path-sum
Il s'agit d'un cas particulier de recherche de plus court chemin dans un graphe acyclique. Cela peut être résolu par programmation dynamique.

#include <math.h>

// On utilise la récurrence suivante :
// d[i][j] = grid[i][j] + min(d[i - 1][j], d[i][j - 1])

int minPathSum(int** grid, int gridSize, int* gridColSize) {
    int n = gridSize, p = gridColSize[0]; // nombres de lignes et colonnes
    int** d = malloc(n*sizeof(int*)); // d[i][j] = poids min d'un chemin de (0,0) à (i,j)
    for(int i = 0; i < n; i++) {
        d[i] = malloc(p*sizeof(int));
        for(int j = 0; j < p; j++) {
            int a = -1;
            if(i == 0 && j == 0)
                a = 0;
            if(i > 0)
                a = d[i - 1][j];
            if(j > 0 && (a == -1 || d[i][j - 1] < a))
                a = d[i][j - 1];
            d[i][j] = a + grid[i][j];
        }
    }
    return d[n - 1][p - 1];
}

Exercice à faire en C sur LeetCode, au plus tard pour samedi prochain : https://leetcode.com/problems/longest-palindromic-substring/description
Un palindrome est une chaîne qui se lit de la même façon dans les deux sens. Par exemple, "abba" est un palindrome. On cherche à trouver la plus grande sous-chaîne palindrome d'une chaîne donnée.

// Renvoie la sous-chaîne de s de l'indice i à j inclus
char* substring(char* s, int i, int j) {
    char* t = malloc(j - i + 2);
    for(int k = i; k <= j; k++)
        t[k - i] = s[k];
    t[j - i + 1] = '\0';
    return t;
}

#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

char* subword(char* s, int i, int j) {
    char* t = malloc(j - i + 2);
    for(int k = i; k <= j; k++)
        t[k - i] = s[k];
    t[j - i + 1] = '\0';
    return t;
}

char* longestPalindrome(char* s) {
    int n = strlen(s);
    bool** b = malloc(n*sizeof(bool*));
    for(int i = 0; i < n; i++) {
        b[i] = malloc(n*sizeof(bool));
        for(int j = 0; j < n; j++) {
            b[i][j] = true;
        }
    }

    int imax = 0, kmax = 0;
    for(int k = 1; k < n; k++)
        for(int i = 0; i < n - k; i++) {
            b[i][i + k] = s[i] == s[i + k] && b[i + 1][i + k - 1];
            if(b[i][i + k]) {
                kmax = k;
                imax = i;
            }
        }
    return subword(s, imax, imax + kmax);
}

Exercice à faire en C sur LeetCode, au plus tard pour samedi prochain : https://leetcode.com/problems/number-of-islands

// Parcours en profondeur depuis la case (i, j)
void dfs(char** grid, int n, int p, int i, int j) {
    ...
}

int numIslands(char** grid, int gridSize, int* gridColSize) {
    int n = gridSize, p = gridColSize[0]; // n lignes, p colonnes
    int k = 0; // nombre de composantes connexes
    for(int i = 0; i < n; i++)
        for(int j = 0; j < p; j++)
            ...
    return k;
}

// Solution en O(l) avec un parcours en profondeur, où l = np est le nombre de cases de la grille
// Plutôt qu'utiliser une matrice de booléens vus, on peut mettre les cases visitées à 0 pour éviter de les revisiter

void dfs(char** grid, int n, int p, int i, int j) {
    if(grid[i][j] == '0') return;
    grid[i][j] = '0';
    if(i > 0) // chaque sommet a 4 voisins
        dfs(grid, n, p, i - 1, j);
    if(i < n - 1)
        dfs(grid, n, p, i + 1, j);
    if(j > 0)
        dfs(grid, n, p, i, j - 1);
    if(j < p - 1)
        dfs(grid, n, p, i, j + 1);
}

int numIslands(char** grid, int gridSize, int* gridColSize) {
    int n = gridSize, p = gridColSize[0];
    int k = 0;
    for(int i = 0; i < n; i++)
        for(int j = 0; j < p; j++)
            if(grid[i][j] == '1') {
                dfs(grid, n, p, i, j);
                k++;
            }
    return k;
}

Ajout d'exercices pour s'entraîner en autonomie :

• Exercices sur les automates et expressions régulières
• Exercices simples corrigés en OCaml

Exercice à faire en C sur LeetCode, au plus tard pour samedi prochain : https://leetcode.com/problems/merge-two-sorted-lists

Si vous avez terminé l'exercice, vous pouvez faire ce prolongement (plus difficile) : https://leetcode.com/problems/merge-k-sorted-lists

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
 struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {
    if (list1 == NULL) return list2;
    if (list2 == NULL) return list1;
    if (list1->val <= list2->val) {
        list1->next = mergeTwoLists(list1->next, list2);
        return list1;
    }
    if (list1->val > list2->val) {
        list2->next = mergeTwoLists(list1, list2->next);
        return list2;
    }
    return NULL;
}

struct ListNode* merge(struct ListNode** lists, int i, int j) {
    if(i + 1 == j) return lists[i];
    if(i == j) return NULL;
    
    int m = (i + j)/2;
    return mergeTwoLists(merge(lists, i, m), merge(lists, m, j));
}

struct ListNode* mergeKLists(struct ListNode** lists, int listsSize) {
    return merge(lists, 0, listsSize);
}

Voici la liste des compétences et connaissances à avoir pour votre première colle. La colle est constituée d'un ou plusieurs exercices.

Langages :

• Définitions et opérations sur les mots et langages
• Montrer l'égalité de deux langages (double inclusion...)
• Montrer une propriété par récurrence sur des mots
• Connaître la définition de langage régulier
• Montrer qu'un langage est régulier (éventuellement en passant par une expression régulière)
• Connaître la syntaxe des expressions régulières
• Montrer une propriété sur les langages réguliers (ou expressions régulières) par induction structurelle
• Écrire un programme OCaml pour manipuler une expression régulière

Automates :

• Définitions
• Écrire un programme OCaml pour manipuler un automate
• Montrer qu'un langage est reconnaissable
• Trouver le langage reconnu par un automate
• Compléter un automate
• Algorithme de déterminisation et automate des parties
• Stabilité des langages reconnaissables par complémentaire, intersection, union, différence. Automate produit.
• États accessibles et co-accessibles. Automate émondé. Tout automate est équivalent à un automate émondé.
• Lemme de l'étoile, avec démonstration et application pour montrer qu'un langage n'est pas reconnaissable.

Théorème de Kleene :

• Langage local, expression régulière linéaire.
• Algorithme de Berry-Sethi pour construire un automate (de Glushkov) à partir d'une expression régulière.
• ε-transitions. Tout automate avec des ε-transitions est équivalent à un automate sans ε-transition.
• Automate de Thompson (construit récursivement) à partir d'une expression régulière.
• Méthode d'élimination des états pour obtenir une expression régulière à partir d'un automate.
• Théorème de Kleene et conséquences.

Grammaires :

• Grammaire non-contextuelle (algébrique, hors-contexte).
• Dérivation.
• Langage engendré. Savoir démontrer par récurrence (sur la longueur du mot ou de la dérivation) que le langage engendré par G est bien ce qu'on souhaite.
• Les langages réguliers sont algébriques.
• Arbre de dérivation.
• Grammaire ambigüe. Dérivation gauche. Savoir montrer qu'une grammaire est ambigüe.
• Analyse syntaxique : exemple.

Voici le premier exercice à faire en C sur LeetCode, au plus tard pour dimanche prochain (15 septembre) : https://leetcode.com/problems/longest-substring-without-repeating-characters
Une vidéo explicative pour utiliser LeetCode : https://youtu.be/q5dEFWMO8-o
Vous pouvez me demander de l'aide par mail.

// 1ere solution : O(n^3) en regardant, pour chaque sous-chaîne, si elle contient un doublon
int lengthOfLongestSubstring(char* s) {
    int max = 0;
    for(int i = 0; i < strlen(s); i++) {
        int j = i + 1;
        int b = 0;
        while(j < strlen(s)) {
            for(int k = i; k < j; k++) {
                if(s[k] == s[j])
                    b = 1;
            }
            if(b) break;
            j++;
        }
        if(j - i > max)
            max = j - i;
    }
    return max;
}

// 2eme solution : O(n^2) en conservant un tableau count pour savoir si un caractère est déjà présent dans la sous-chaîne
// on utilise un tableau de 256 éléments pour les caractères ASCII
int lengthOfLongestSubstring(char* s) {
    int max = 0;
    int n = strlen(s);
    for(int i = 0; i < n; i++) {
        int j = i;
        int count[256] = {0};
        while(j < n && count[s[j]] == 0) {
            count[s[j]] = 1;
            j++;
        }
        if(j - i > max)
            max = j - i;
    }
    return max;
}

Pour pouvoir utiliser un environnement de développement en ligne avec Visual Code, OCaml, utop, gcc :

• S'incrire sur GitHub (Sign Up).
• Aller sur https://github.com/mpi-lamartin/environnement et cliquer sur le bouton Code puis "Create codespace on main".
• Vous pouvez retrouver votre codespace en cliquant sur le menu en haut à gauche puis "Codespaces".
• Les fichiers sont normalement sauvegardés en ligne... Vous pouvez quand même télécharger (dans "fichier") des fichiers importants pour être sûr de ne pas les perdre.
• Par défaut vous avez le droit à 120h/mois d'utilisation, ce qui devrait être suffisant. Vous pouvez demander un compte étudiant pour avoir 180h/mois : https://github.com/education/students.

Vidéo explicative