Décidabilité : Tout le cours.
Classes de complexité : Tout le cours.
Merci de poser obligatoirement au moins une question de décidabilité ou classe de complexité : montrer qu'un problème est indécidable (réduction depuis ARRET) ou NP-complet (NP + réduction polynomiale depuis SAT).
Algorithmes d'approximation et Branch and Bound : Tout le cours.
Algorithmes probabilistes : Tout le cours.
Exercice à faire en C sur LeetCode pendant les vacances de Noël : https://leetcode.com/problems/find-champion-ii (facile)
Et pour ceux qui veulent plus difficile : https://leetcode.com/problems/shortest-cycle-in-a-graph
Pour le premier exercice, il s'agit de trouver s'il existe un unique sommet de degré entrant nul.
Pour le deuxième exercice, on peut utiliser un parcours en largeur : si on est en train de visiter un sommet u et qu'on trouve un voisin v de u qui est déjà visité, alors on a trouvé un cycle de longueur d[u] + d[v] + 1.
int findChampion(int n, int** edges, int edgesSize, int* edgesColSize) {
int** g = (int**)malloc(sizeof(int*) * n);
for (int i = 0; i < n; i++) {
g[i] = (int*)malloc(sizeof(int) * n);
for (int j = 0; j < n; j++)
g[i][j] = 0;
}
for (int i = 0; i < edgesSize; i++) {
int u = edges[i][0], v = edges[i][1];
g[u][v] = 1;
}
int c = -1;
for(int j = 0; j < n; j++) {
int deg = 0;
for (int i = 0; i < n; i++)
deg += g[i][j];
if(deg == 0) {
if(c != -1) {
return -1;
}
c = j;
}
}
return c;
}
Voici la liste des compétences et connaissances à avoir en colle ainsi que le DS 3.
Révisions sur les graphes : Tout le cours.
Arbres couvrants : Tout le cours.
Composantes fortement connexes et Kosaraju : Tout le cours.
Couplages et graphes bipartis : Tout le cours.
Plus courts chemins et A* : Tout le cours.
Décidabilité : Tout le cours.
Classes de complexité : Tout le cours.
Merci de poser obligatoirement au moins une question de décidabilité ou classe de complexité : montrer qu'un problème est indécidable (réduction depuis ARRET) ou NP-complet (NP + réduction polynomiale depuis SAT).
Algorithmes d'approximation et Branch and Bound : Tout le cours.
Algorithmes probabilistes : Tout le cours.
Exercice à faire en C sur LeetCode, au plus tard pour samedi prochain : https://leetcode.com/problems/min-cost-to-connect-all-points
Utiliser l'algorithme de Kruskal sur le graphe dont les sommets sont les points et les arêtes sont les distances entre les points.
Voici la liste des compétences et connaissances à avoir pour votre deuxième colle ainsi que le DS 2.
Grammaires :
Révisions sur les graphes :
Arbres couvrants :
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).
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.
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;
}
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.
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.
#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.
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 :
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;
}
#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
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 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 :