Prêt à booster tes révisions ?
Essayer maintenantSans carte bancaire - Rejoins +40 000 étudiants
Fiches de révision informatique L1 : algorithmique, Python, structures de données, complexité, systèmes et réseaux. Programme universitaire complet.
Première année universitaire d'informatique, sans pré-requis : on part du principe que tu débutes. Le S1 et le S2 t'amènent à maîtriser cinq blocs : algorithmique et programmation (Python le plus souvent), mathématiques discrètes, architecture machine, systèmes d'exploitation et réseaux. Voilà ce qu'il faut retenir pour les partiels.
L'algorithmique est le cœur du semestre. Un algorithme est une suite finie d'instructions qui résout un problème en un nombre fini d'étapes. Les exigences universitaires : démontrer la terminaison, la correction et estimer la complexité.
Le tableau offre un accès en O(1) par index mais une insertion en O(n). La liste chaînée inverse ces complexités. Les listes Python combinent l'accès tableau et le redimensionnement amorti.
Une fonction est récursive lorsqu'elle s'appelle elle-même. Toujours : un cas de base et un appel sur un sous-problème strictement plus petit. Exemples canoniques : factorielle, Fibonacci, parcours d'arbre, tri fusion. La preuve de terminaison passe par une fonction de variant (entier qui décroît strictement).
La complexité estime le nombre d'opérations en fonction de la taille n de l'entrée.
| Notation | Sens | Exemple |
|---|---|---|
| O(1) | Constant | Accès tableau |
| O(log n) | Logarithmique | Recherche dichotomique |
| O(n) | Linéaire | Parcours simple |
| O(n log n) | Quasi-linéaire | Tri fusion, tri rapide moyen |
| O(n²) | Quadratique | Tri à bulles, sélection |
| O(2ⁿ) | Exponentielle | Sous-ensembles |
À retenir : on majore le terme dominant et on ignore les constantes. La complexité dans le pire cas prime aux partiels.
Recherche dichotomique : O(log n) sur un tableau trié. Pseudo-code à savoir réécrire de mémoire.
Le S1 ou S2 comporte un module de mathématiques pour l'informatique. Notions à maîtriser :
Modèle OSI en 7 couches, modèle TCP/IP en 4 couches. Protocoles à savoir : HTTP, HTTPS, DNS, TCP vs UDP, IP, Ethernet. Adressage IP : classes A, B, C ; masque de sous-réseau ; différence IPv4 / IPv6.
Si tu utilises EduFiche, balance ton poly d'algo + tes TP Python : tu récupères une fiche par notion avec les complexités, les pseudo-codes et quelques exercices types. Le gain réel est sur les chapitres denses qu'on n'a pas le temps de digérer en TD (récursivité, complexité, structures de données chaînées).