BUT Informatique cheat sheet

Complexité temporelle courante : accès tableau O(1), recherche linéaire O(n), recherche dichotomique sur tableau trié O(log n), tri par comparaison O(n log n) au mieux, tri naïf O(n²).

Récursivité : toute fonction récursive doit posséder un cas de base atteignable ; sinon débordement de pile (StackOverflowError en Java). La profondeur d'appel est bornée par la taille de la pile du thread.

Encapsulation POO : attributs privés, accès par getters/setters ; une classe abstraite ne s'instancie pas, une interface déclare un contrat sans état (hors constantes).

Surcharge (overload) = même nom, signature différente, résolue à la compilation. Redéfinition (override) = même signature dans une sous-classe, résolue à l'exécution (polymorphisme dynamique).

En Java, == compare les références pour les objets et la valeur pour les primitives ; equals() doit être cohérent avec hashCode() si l'objet est utilisé dans un HashSet ou une HashMap.

Gestion des exceptions : checked exceptions (héritant d'Exception hors RuntimeException) doivent être déclarées ou capturées ; finally s'exécute même en cas de return ou d'exception.

Git de base : commit enregistre l'instantané local, push envoie vers le dépôt distant, pull = fetch + merge, branche = pointeur mobile sur un commit ; un conflit survient quand deux branches modifient les mêmes lignes.

Tests unitaires : structure Arrange-Act-Assert ; un test doit être isolé, déterministe et rapide. La couverture de code mesure les lignes/branches exécutées, pas la qualité des assertions.

Notation asymptotique : O(f) borne supérieure, Ω(f) borne inférieure, Θ(f) borne serrée. On ignore constantes et termes d'ordre inférieur : 3n² + 5n + 7 = Θ(n²).

Règle de la somme : O(f) + O(g) = O(max(f,g)). Règle du produit : O(f) × O(g) = O(f·g). Une boucle imbriquée de taille n sur n donne O(n²).

Structures de données : tableau O(1) en accès indexé mais O(n) en insertion au milieu ; liste chaînée O(1) en insertion en tête mais O(n) en accès ; table de hachage O(1) en moyenne, O(n) au pire (collisions).

Mémoïsation : stocker les résultats de sous-problèmes pour transformer une récursion exponentielle en temps polynomial (ex. Fibonacci naïf O(2^n) devient O(n) avec cache).

Tri : comparatif en Ω(n log n) dans le cas général (borne informationnelle) ; tri par comptage/radix en O(n+k) mais seulement pour clés entières bornées.

Optimisation prématurée : mesurer avant d'optimiser (profiling). Le goulot d'étranglement réel est souvent les entrées/sorties ou les accès mémoire, pas le CPU.

Localité mémoire : parcourir un tableau ligne par ligne (row-major) améliore le cache ; un accès colonne par colonne provoque des défauts de cache et peut multiplier le temps par 10.

Parallélisme : la loi d'Amdahl borne le gain : speedup ≤ 1 / (s + (1−s)/p) où s est la fraction séquentielle et p le nombre de processeurs.

Modèle TCP/IP : couche application (HTTP, DNS, SSH), transport (TCP, UDP), internet (IP, ICMP), accès réseau (Ethernet, Wi-Fi). TCP est orienté connexion et fiable ; UDP sans connexion et non fiable.

Adressage IPv4 : adresse 32 bits, masque de sous-réseau. Nombre d'hôtes utilisables = 2^(32−préfixe) − 2 (on retire adresse réseau et broadcast). Ex. /24 → 254 hôtes.

Ports : 0–1023 réservés (well-known), 1024–49151 enregistrés, 49152–65535 dynamiques. Un port ne peut être écouté que par un seul processus à la fois sur une même IP.

DNS : résolution hiérarchique racine → TLD → domaine. Enregistrements A (IPv4), AAAA (IPv6), CNAME (alias), MX (mail), NS (serveur de noms). Cache soumis à TTL.

SSH : authentification par clé publique/privée, port par défaut 22. La clé privée ne quitte jamais le client ; la clé publique est déposée dans ~/.ssh/authorized_keys du serveur.

Permissions Unix : rwx pour propriétaire/groupe/autres, notation octale (r=4, w=2, x=1). chmod 755 = rwxr-xr-x ; chown change le propriétaire ; umask soustrait les droits par défaut.

Diagnostic réseau : ping teste la joignabilité ICMP, traceroute affiche le chemin des routeurs, netstat/ss liste les connexions, dig interroge le DNS, curl teste une requête HTTP.

Pare-feu et NAT : iptables filtre par chaîne (INPUT, OUTPUT, FORWARD) et règle (ACCEPT, DROP, REJECT). Le NAT traduit les adresses privées en adresse publique pour la sortie.

Modèle relationnel : une relation (table) a des attributs (colonnes) et des tuples (lignes). Une clé primaire identifie un tuple de façon unique ; une clé étrangère référence la clé primaire d'une autre table.

Formes normales : 1FN (valeurs atomiques), 2FN (pas de dépendance partielle à la clé), 3FN (pas de dépendance transitive). La 3FN élimine la plupart des redondances.

SQL : SELECT … FROM … WHERE … GROUP BY … HAVING … ORDER BY. WHERE filtre avant agrégation, HAVING filtre après. COUNT(*) compte les lignes, COUNT(colonne) ignore les NULL.

Jointures : INNER JOIN ne garde que les correspondances ; LEFT JOIN garde toutes les lignes de gauche (NULL à droite si absent) ; CROSS JOIN produit le produit cartésien.

Transactions ACID : Atomicité, Cohérence, Isolation, Durabilité. COMMIT valide, ROLLBACK annule. Les niveaux d'isolation (READ COMMITTED, SERIALIZABLE…) gèrent les lectures fantômes et sales.

Index : accélère les recherches (souvent en B-arbre, O(log n)) mais ralentit les INSERT/UPDATE et consomme de l'espace. Un index est utile sur les colonnes filtrées ou jointes.

NULL en SQL n'est pas égal à zéro ni à la chaîne vide : toute comparaison avec NULL renvoie UNKNOWN. Utiliser IS NULL / IS NOT NULL ; les agrégats ignorent les NULL sauf COUNT(*).

Modélisation : diagramme entité-association (entités, associations, cardinalités 1:1, 1:N, N:M). Une association N:M se traduit en table de jointure avec deux clés étrangères.

Cycle en V : phases séquentielles descendantes (spécification, conception, réalisation) puis remontantes de test (unitaire, intégration, validation). Adapté aux exigences stables.

Méthodes agiles (Scrum) : itérations courtes (sprints de 1 à 4 semaines), rôles Product Owner, Scrum Master, équipe ; artefacts backlog, sprint backlog, incrément.

Diagramme de Gantt : barres horizontales représentant la durée des tâches sur un axe temporel ; permet d'identifier le chemin critique (séquence de tâches déterminant la durée totale).

Estimation : le point de fonction ou le story point mesure l'effort relatif, pas le temps absolu. La vélocité = points livrés par itération, utilisée pour planifier.

Analyse des risques : identifier, qualifier (probabilité × impact), planifier une réponse (éviter, réduire, transférer, accepter). Un risque non suivi est un risque subi.

Triangle de contraintes : périmètre, coût (ressources) et délai sont liés ; modifier l'un impacte les autres. La qualité est la variable d'ajustement si le triangle est figé.

Traçabilité des exigences : chaque exigence doit être reliée à une conception, un test et une livraison. Un cahier des charges distingue exigences fonctionnelles et non fonctionnelles.

Revue de projet : jalons (milestones) et livrables vérifiables. Un jalon marque une décision (go/no-go), pas nécessairement une durée.

Git collaboratif : une branche par fonctionnalité, pull request pour revue, merge ou rebase pour intégrer. Ne jamais réécrire l'historique d'une branche partagée (pas de force-push sur main).

Convention de commit : format type(scope): description (ex. feat(auth): ajout du login). Types courants : feat, fix, docs, refactor, test, chore.

Revue de code : objectifs = détecter les défauts, partager la connaissance, uniformiser le style. Une revue efficace porte sur de petits diffs (< 400 lignes).

Documentation : README (installation, usage), CHANGELOG (versions), commentaires expliquant le pourquoi plutôt que le quoi. Le code doit être lisible sans commentaire superflu.

Communication asynchrone : ticket/issue avec critères d'acceptation, statut visible, responsable assigné. Réunion courte (daily) pour synchroniser, pas pour résoudre un problème technique.

Intégration continue (CI) : à chaque push, compilation + tests automatisés + analyse statique. Un pipeline rouge bloque le merge ; le build doit rester vert sur la branche principale.

Conflit d'équipe : distinguer désaccord technique (arbitrer par des données/mesures) et conflit relationnel (médiation). Le consensus n'est pas l'unanimité.

Licences et propriété : connaître la licence du code réutilisé (MIT, GPL, Apache). La GPL impose la redistribution du code dérivé sous GPL ; MIT et Apache sont permissives.