Aller au contenu principal

Informatique aux concours

Quentin Fortier
Quentin Fortier
Professeur d'informatique

Écrit​

  • CCINP : une épreuve de 4h
    Rapport 2024
  • Mines-Pont (et Mines-Telecom) : une épreuve de 3h et une épreuve de 4h Rapport 2024

Oral​

Colle 3 : Graphes

Quentin Fortier
Quentin Fortier
Professeur d'informatique

Voici la liste des compétences et connaissances à avoir en colle ainsi que le DS 3.

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. Application à la connexité et à la recherche de cycle.

Arbres couvrants :

  • Définition.
  • Algorithme de Kruskal. Correction.
  • Union-Find avec compression de chemin et union par rang.

Composantes fortement connexes et Kosaraju : tout.

Couplages et graphes bipartis : Tout le cours sur les couplages.

Colle 2 : Grammaires et graphes

Quentin Fortier
Quentin Fortier
Professeur d'informatique

Voici la liste des compétences et connaissances à avoir pour votre deuxième colle ainsi que le DS 2.

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. Application à la connexité et à la recherche de cycle.

Arbres couvrants :

  • Définition.
  • Algorithme de Kruskal. Correction.
  • Union-Find avec compression de chemin et union par rang.

LeetCode 6

Quentin Fortier
Quentin Fortier
Professeur d'informatique

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).

Indice

Parcourir nums[i] en conservant deux variables : la somme maximum finissant en nums[i] et la somme maximum trouvée jusqu'à présent.

Voir algorithme de Kadane.

Solution
int maxSubArray(int* nums, int numsSize) {
    int maxi = nums[0], max_cur = nums[0];
    for(int i = 1; i < numsSize; i++) {
        // invariant : max_cur est la somme consécutive max qui se termine en i
        max_cur = max_cur + nums[i];
        if(max_cur < nums[i])
            max_cur = nums[i];
        if(max_cur > maxi)
            maxi = max_cur;
    }
    return maxi;
}

LeetCode 5

Quentin Fortier
Quentin Fortier
Professeur d'informatique

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.

Indice

Calculer d[i][j] = la longueur minimum d'un chemin de (0, 0) à (i, j) en utilisant uniquement des déplacements vers le bas et vers la droite.

  1. Trouver une équation de récurrence pour b[i][j].
  2. Remplir le tableau b en utilisant cette équation de récurrence.
  3. Renvoyer la solution.
Solution
#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];
}

LeetCode 4

Quentin Fortier
Quentin Fortier
Professeur d'informatique

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.

Indice

Un algorithme naïf qui regarde, pour tout i, j, si la sous-chaîne de s de i à j est un palindrome (= qui se lit de la même façon dans les deux sens), a une complexité O(n^3).

Pour que le programme soit accepté, on peut trouver une solution en O(n^2) par programmation dynamique. Pour cela :

  1. Définir un tableau b tel que b[i][j] vaut vrai si la sous-chaîne de s de i à j est un palindrome.
  2. Trouver une équation de récurrence pour b[i][j].
  3. Remplir le tableau b en utilisant cette équation de récurrence.
  4. Trouver la plus grande sous-chaîne palindrome en parcourant le tableau b.

On pourra utiliser la fonction suivante :

// 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;
}
Solution
#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);
}

LeetCode 3

Quentin Fortier
Quentin Fortier
Professeur d'informatique

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

Indice

Cela revient à calculer les composantes connexes du graphe dont les sommets sont les cases de la grille et où chaque case a 4 arêtes possibles avec les cases voisines.
Pour calculer le nombre de composantes connexes, on peut utiliser un parcours en profondeur (ou en largeur). On peut directement utiliser grid comme tableau des vus (en mettant une case à '0' après l'avoir visitée).

// 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;
}

Si besoin, vous pouvez revoir le cours de 1ère année.

Solution
// 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;
}

LeetCode 2

Quentin Fortier
Quentin Fortier
Professeur d'informatique

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

Indice

On pourra écrire une fonction récursive.

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

Indice

Réutiliser la fonction précédente pour fusionner deux listes.
L'idéal est de résoudre ce problème en O(n log (k)) où n est la somme des tailles des listes et k le nombre de listes.

Solution

Solution en O(nlog(k)) avec une approche diviser pour régner (où n = somme des tailles des listes et k = nombre de listes) :

  • l1 = fusionner récursivement les k/2 premières listes
  • l2 = fusionner récursivement les k/2 dernières listes
  • retourner la fusion (avec mergeTwoLists) de l1 et l2

Chaque fusion s'effectue en O(n) et il y a log(k) fusions, d'où la complexité en O(nlog(k))

/**
 * 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);
}