Génie Informatique - algorithmes, bases de données et réseaux
L'épreuve de Génie Informatique couvre l'algorithmique et la complexité, les structures de données, les bases de données relationnelles (SQL, normalisation), les réseaux (TCP/IP, adressage, routage) et les systèmes d'exploitation. On attend un algorithme correct, sa complexité annoncée, et une justification du choix de structure de données.
Notions clés
- Complexité : O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ) ; un tri par comparaison est en Ω(n log n).
- Structures : tableau, liste chaînée, pile et file, arbre binaire de recherche, table de hachage (gestion des collisions), tas.
- SGBD : clés, intégrité référentielle, 1FN/2FN/3FN, algèbre relationnelle, jointures, GROUP BY et HAVING, logique ternaire des NULL.
- Réseaux : encapsulation, TCP vs UDP, CIDR, masque, adresse de broadcast, NAT, ports.
- OS : processus et threads, ordonnancement, pagination, conditions de Coffman pour l'interblocage.
Exemple travaillé
Découper 192.168.10.0/24 en sous-réseaux d'au moins 50 hôtes.
- Condition : 2^h − 2 ≥ 50 → h = 6 bits d'hôte → préfixe /26, masque 255.255.255.192.
- 2 bits de sous-réseau → 4 blocs : .0, .64, .128, .192.
- Pour 192.168.10.64/26 : adresse réseau .64, hôtes .65 à .126, broadcast .127.
- Vérification : 62 hôtes utiles, la contrainte de 50 est couverte avec une marge de 12 adresses.
Pièges qui coûtent des points
- Oublier de retirer les adresses de réseau et de broadcast du nombre d'hôtes utiles.
- Annoncer O(n) pour deux boucles imbriquées dépendant toutes deux de n.
- Confondre NULL SQL et chaîne vide :
x <> NULLn'est jamais vrai, il fautIS NULL. - Filtrer un agrégat avec WHERE au lieu de HAVING.
- Négliger la division entière et le dépassement de capacité en C ou Java.
- Écrire une fonction récursive sans cas de base, ou sans preuve de décroissance du paramètre.