Cours de NSI

Les structures de base
Affectation des variables
L'essentiel du travail effectué par un programme consiste à manipuler des données organisées comme un ensemble de variables. Une variable apparaît dans un langage de programmation sous un nom explicite qui, pour l'ordinateur, représente une référence désignant une adresse mémoire précise dans la mémoire vive.
Pour stocker une valeur dans une variable, on utilise l'instruction d'affectation, notée par le signe =. Par exemple, l'affectation x = y + 3 est composée d'une variable x et d'une expression y + 3.
Opérations arithmétiques
+ Addition
- Soustraction
* Multiplication
/ Division
// Quotient euclidien
% Reste (modulo)
** Puissance
Opérations booléennes
== Égalité
!= Différence
<= < Infériorité
>= > Supériorité
and Et logique
or Ou logique
Bonnes pratiques de nommage : Un nom de variable commence toujours par une lettre minuscule, utilise uniquement lettres, chiffres et underscore _. Les 33 mots réservés Python (if, for, while, def, return...) ne peuvent pas être utilisés comme noms de variables.
Tests et boucles
Pour écrire des applications véritablement utiles, il faut des techniques permettant d'aiguiller le déroulement du programme dans différentes directions selon les circonstances rencontrées.
L'instruction if/else
La ligne de test commence par if, suivie d'une condition et d'un deux-points. Les instructions à exécuter si la condition est vraie doivent être indentées. La partie else est facultative et s'exécute si la condition est fausse. L'instruction elif permet d'enchaîner plusieurs tests.
La boucle while
Le mot while signifie « tant que ». Cette instruction répète continuellement le bloc d'instructions qui suit, tant que l'expression est vraie. À utiliser quand la décision d'arrêt ne peut s'exprimer que par un test.
La boucle for
La boucle for i in range(m,n) exécute le corps de boucle (n-m) fois. La variable i prend successivement les valeurs m, m+1, ..., n-1. À utiliser quand on connaît à l'avance le nombre de répétitions.
En programmation, une boucle est un système d'instructions qui permet de répéter un certain nombre de fois toute une série d'opérations. Python propose deux instructions : for pour les boucles bornées et while pour les boucles non bornées.
Fonctions et interactions utilisateur
Les fonctions sont des bouts de code exécutés à chaque fois qu'ils sont appelés. Elles permettent de structurer le code, d'éviter les redondances et de le rendre plus lisible pour faciliter la maintenance.
Définition d'une fonction
Une fonction se définit avec l'instruction def suivie du nom et de la liste des arguments. La valeur de retour est indiquée par return.
a = 'Ceci est une chaîne'
>>> a[0]  -> 'C'
>>> a[2:4] -> 'ci'
>>> len(a) -> 19
Entrées/Sorties
print() affiche du texte et/ou le contenu d'une variable.
input() stoppe l'exécution et attend une saisie utilisateur. La valeur renvoyée est une chaîne de caractères.
nom = input('Votre nom ?')
age = int(input('Votre âge ?'))
print('Bonjour', nom)
Notion de variables locales et globales :
Variables locales
Définies à l'intérieur de la fonction, elles sont créées à l'appel et détruites à la sortie. Non visibles par le programme principal.
Variables globales
Créées dans le programme principal, accessibles partout. On recommande de ne pas définir de fonctions dépendant de variables globales modifiables.
Listes
Dans de nombreuses situations, on a besoin de données composites formées de plusieurs nombres ou booléens. Sous Python, on utilise le type liste : une collection d'éléments séparés par des virgules, enfermée dans des crochets.
Déclaration
a = [1, 10, 2, 3, 56, 89] crée une liste de 6 entiers
Accès par indice
a[0] premier élément, a[-1] dernier élément
Tranches (slicing)
a[2:4] éléments d'indice 2 à 3, a[:3] trois premiers
Opérations
+ concaténation, * duplication, append() ajout, del() suppression
Listes par compréhension : 
a = [i*i for i in range(1000)] 
crée une liste des carrés des 1000 premiers entiers. 
On peut ajouter une condition :
[i*i for i in range(30) if i % 4 == 1]
La fonction len() donne la longueur d'une liste. Le test in vérifie la présence d'une valeur. 
Le balayage d’une liste consiste à lire successivement l’ensemble des valeurs contenues dans une liste afin d’éventuellement opérer un traitement. Cette opération peut être réalisé avec une boucle for ayant la liste à balayer comme argument. Dans l’exemple suivant, la variable i prendra successivement les valeurs contenues dans le tableau. La boucle for sera donc exécutées 4 fois puisque la liste a contient 4 éléments.
Il y a deux manières de balayer une liste :
a = [10, 24, 32, 40]
for i in a :
    print(i, end=’’)
est équivalent à :
a = [10, 24, 32, 40]
for i in range(len(a)):
    print(a[i], end=’’)
Chaînes de caractères
Une chaîne de caractères est une structure de données composites immutable : on ne peut pas la modifier sur place. Pour modifier une chaîne existante, on en extrait les parties appropriées et on reconstitue une nouvelle chaîne par concaténation.
Déclaration avec guillemets simples ou doubles. 
Accès aux caractères par indice comme pour les listes. 
Opérateurs + (concaténation), * (duplication), slicing [m:n]. 
Comparaison avec == et <= pour l'ordre alphabétique.
a = 'Ceci est une chaîne'
>>> a[0]  -> 'C'
>>> a[2:4] -> 'ci'
>>> len(a) -> 19
Dictionnaires
Un dictonnaire (type dict) est un type construit (données composites) mutable de la même manière qu’une liste. La principale différence est que les indices ne sont pas obligatoirement des entiers (0, 1, 2, 3 …) et peuvent être de type str,  float… Ces indices ne sont pas ordonnés et s’appellent des clés. Ces clés doivent être unique et  immutable. A chaque clé correspond une valeur qui peut être quelconque. 
Ce type de données sera privilégié lors de manipulation de tableau de données non homogènes (mélangeant des chaînes de caractères et des entiers par exemple).
Les méthodes items(), keys() et values() permettent d'accéder aux couples clé/valeur, aux clés seules ou aux valeurs seules d'un dictionnaire. L'opérateur & trouve les clés communes à deux dictionnaires.
Type mutable où les clés peuvent être des str ou float. 
Construction avec {} et ajout par d[clé] = valeur. 
Méthode get() évite les erreurs si la clé n'existe pas.
dico = {'yes': 'oui', 'no': 'non'}
dico['and'] = 'et'
>>> dico.get('yes') -> 'oui'
>>> 'yes' in dico -> True
Représentation des nombres
Entiers positifs
Les représentations écrites d'un nombre varient selon les cultures. On distingue l'écriture à base de symboles (numération romaine) et l'écriture à base de rang utilisée actuellement. En informatique, la base 2 (binaire) et la base 16 (hexadécimal) sont privilégiées.
Base 10 (Décimal)
10 symboles : 0-9. Utilisée quotidiennement.
Base 2 (Binaire)
2 symboles : 0 et 1. Utilisée par les ordinateurs.
Base 16 (Hexadécimal)
16 symboles : 0-9 et A-F. Simplifie l'écriture binaire.
Les éléments sont nommés  bit (Binary digIT). 
Un code binaire à n bits possède 2**n états et la valeur la plus grande représentable vaut 2**(n) - 1
Le bit de poids le plus fort est appelé MSB. 
Le bit de poids le plus faible est appelé LSB. 
Un regroupement de k bits s'appelle un mot de k bits. 
Un mot de 8 bits s'appelle un octet. 
 % ou 0b devant le mot binaire indique la base 2 .
Entiers relatifs
Dans cet encodage :
Le bit de poids fort représente le signe des entiers (0 pour un entier positif et 1 pour un entier négatif)
la représentation des nombres positifs ou nul est inchangée
les nombres négatifs sont encodés par la méthode du complément à deux. 
Le complément à deux d’un mot binaire de n bits s’obtient en inversant les n bits et en ajoutant 1. Cette technique permet aussi bien de coder des nombres négatifs en binaire que de retrouver la valeur négative d'un mot binaire codé en complément à deux.
Nombres flottants
 La norme IEEE 754 définit la représentation en virgule flottante sous la forme signe × mantisse × base^exposant. Le format double précision (64 bits) utilise 1 bit de signe, 11 bits d'exposant et 52 bits de mantisse.  Attention : les calculs sur flottants sont inexacts (0.1 + 0.2 == 0.3 renvoie False).
Encodage de texte
La mémoire de l'ordinateur conserve toutes les données sous forme numérique. Il n'existe pas de méthode pour stocker directement les caractères.  Chaque caractère possède un équivalent binaire selon la norme utilisée. Le code ASCII (7 bits, 128 caractères) représente les caractères anglais. L'ASCII étendu (8 bits, 256 caractères) ajoute les caractères accentués. L'Unicode (UTF-8) permet le codage de tous les systèmes d'écriture mondiaux et est devenu le standard pour le Web.
Conversion majuscule/minuscule :  Il suffit de modifier le 6ème bit (poids 32) pour changer la casse. 'A' = 65, 'a' = 97 = 65 + 32.
Unicode 
La généralisation de l’utilisation d’Internet dans le monde et des échanges interculturels a nécessité une prise en compte d’un nombre beaucoup plus importants de caractères d’écriture. La norme Unicode a été créée pour permettre le codage de textes écrits quelque soit le système d’écriture utilisé. On attribue à chaque caractère un nom, une position normative et un bref descriptif qui seront les mêmes quelque soit la plate-forme informatique ou le logiciel utilisés. L’Unicode est une table de correspondance Caractère /  Code (Charset), et l’UTF-8 est l’encodage correspondant le plus répandu. 
Typage
Tous les langages de programmation permettent de manipuler des valeurs. Le typage d'une variable consiste à associer à sa variable symbolique un « type » de donnée, permettant à l'ordinateur de savoir si celle-ci est de type numérique, textuel, etc. et d'allouer en conséquence des zones de mémoire de dimension suffisantes pour stocker cette donnée. Le langage Python effectue un typage dynamique des variables, rendant cette opération automatique lors de l'exécution du code. Avec certains langages (C, C++…), le typage doit être effectué statiquement ce qui demande au programmeur de déclarer expressément le typage de chaque variable.
Déboguer un Programme
La phase de débogage d'un programme, qui consiste à rechercher les erreurs de programmation, est très gourmande en temps. Ceci est particulièrement vrai avec Python dont le typage dynamique repousse la découverte des fautes au moment de l'exécution. Lorsque l'interpréteur Python rencontre un problème, une exception est levée. Si elle n'est pas capturée, cette exception provoque l'arrêt du programme et l'affichage d'un message appelé traceback.
Exceptions Courantes en Python
NameError
Accès à une variable inexistante dans le programme.
IndexError
Accès à un indice invalide d'un tableau ou liste.
KeyError
Accès à une clé inexistante d'un dictionnaire.
TypeError
Opération appliquée à des valeurs incompatibles.
ZeroDivisionError
division par zéro.
ValueError
Argument de valeur incompatible mais de type correct.
Lever et rattraper une exception
Il est possible de déclencher directement une exception avec l'opération raise de Python, en faisant suivre le mot-clé du nom de l'exception à lever. Pour rattraper une exception, on utilise la construction try/except qui permet d'intercepter l'erreur avant que l'exécution ne soit abandonnée. Le bloc try contient le code normal, et le bloc except le comportement alternatif si une exception correspondante est levée.
try :
    x = int(input('Entrer un jour'))
except ValueError :
    print('Entrer un entier valide')
Signaler un problème
Il est possible de déclencher directement toutes ces exceptions (on dit « lever une exception ») avec l'opération raise de Python.
>>> raise IndexError('indice trop grand')

Taceback (most recent call last) :
File "<stdins>", line 1, in <module>
IndexError : indice trop grand
Vérifier une condition
Les assertions permettent de vérifier qu’une condition est vraie pendant l’exécution du programme. Si la condition est fausse, une AssertionError est levée. Elles sont principalement utilisées pendant le développement pour détecter des erreurs de logique.
def calculer_factorielle(n):
   assert n >= 0, "Le nombre doit être positif ou nul."
   if n == 0:
       return 1
   else:
       return n * calculer_factorielle(n - 1)
Programmation Orientée Objet (POO)
La POO résulte de la prise de conscience des problèmes posés par l'industrie du logiciel en termes de complexité accrue et de stabilité dégradée. Elle s'inspire du monde réel en faisant interagir des objets à l'aide de messages, laissant de côté la notion de variable au profit d'objets ayant chacun ses propres caractéristiques.
Programmation impérative
Programmation objet
Concepts fondamentaux
Encapsulation
Regrouper données et méthodes dans un objet, masquer la complexité et proposer une interface simple d'utilisation.
Classe
Description générale d'une famille d'objets avec ses attributs (données) et méthodes (actions).
Objet
Instance particulière d'une classe, créée en invoquant le constructeur __init__.
Classes
Dans la programmation objet, une classe est la description générale d'une famille d'objet. La classe est comme un moule à objets, elle définit les données communes (attributs) et les actions (méthodes) que les objets de la classe pourront réaliser. 
Un objet est donc un paramétrage particulier d’une classe, ainsi tous les objets d’une même classe possèdent les mêmes méthodes et attributs. Par contre les valeurs des attributs changeront d’un objet à un autre. 
La représentation d’une classe peut s’effectuer en suivant le modèle de la figure ci-contre. Ce diagramme est appelé diagramme de classe.
                                           Diagramme de classe
Accès Public et Privé
Les attributs privés (précédés de __) ne sont pas accessibles directement mais par des accesseurs (getters) et mutateurs (setters). 
Le constructeur __init__ initialise l'objet lors de sa création.  La variable self désigne l'objet lui-même.
Fonctions Récursives
Un programme est récursif s'il se réemploie lui-même pour parvenir au résultat. La récursivité fournit des algorithmes concis et élégants, permettant de définir des concepts et résoudre certains problèmes difficiles à traiter avec des boucles uniquement.
La récursivité fournit des algorithmes concis et élégants. Il s’agit à la fois d’un style de programmation mais également d’une technique pour définir des concepts et résoudre certains problèmes qu’il n’est parfois pas facile de traiter en programmant uniquement avec des boucles. Il faut cependant se méfier de la complexité, de plus il faut bien s’assurer de définir un cas d’arrêt pour interdire une récursivité infinie.
Structure d'une Fonction Récursive
1
Déterminer le type de retour
2
Écrire la condition d'arrêt
3
Écrire l'appel récursif
Exemple de code récursif →
def fonctionRecursive(args):
    if condition_arret:
        return valeur
    fonctionRecursive(arg)
En Python, la taille de la pile est limitée à 1000 par défaut. Si dépassement → RuntimeError: maximum recursion depth exceeded
Structures de données linéaires
Une structure de données est une manière d'organiser les données pour faciliter leur traitement. On parle de type abstrait de données (TAD). Utiliser une structure appropriée peut significativement réduire la complexité d'une application.
Piles (LIFO - Last In First Out)
Une pile LIFO est une structure linéaire de données basée sur le principe suivant : le dernier élément entré sera le premier sorti. 
Les insertions et suppressions se font donc à une seule extrémité (sommet). 
Utilisations : fonction annuler, historique de navigation, pile d'appels du microprocesseur.
Files (FIFO - First In First Out)
Une file FIFO dite aussi file d'attente est une structure de données basée sur le principe suivant : premier entré, premier sorti. 
Les insertions et suppressions se font donc aux extrémités opposées. 
Utilisations : file d'impression, mémoire tampon réseau (buffer).
Listes
Une liste est une structure de données permettant de regrouper des données et dont l’accès est séquentiel. Elle correspond à une suite finie d’éléments repérés par leur rang (index). Les éléments sont ordonnés et leur place a une grande importance. Une liste est évolutive, on peut ajouter ou supprimer un élément à n’importe quel endroit. Pour une liste aussi on peut parler de tête (1er élément) et de queue (le reste).  Contrairement au tableau, la taille d’une liste peut varier au cours du temps. En effet, une liste n'est pas allouée en une seule fois, mais chaque élément est alloué indépendamment, sous la forme d'un maillon.
Graphes
Un graphe permet de représenter la structure et les connexions d'un ensemble complexe : réseaux routiers, circuits électriques, interactions biologiques. La théorie des graphes débute avec Euler au XVIIIe siècle.
Graphes Orientés
Relations orientées appelées arcs, représentées par des flèches.
Graphes Non Orientés
Relations appelées arêtes. 
Deux arêtes d’un graphe sont dites adjacentes si elles possèdent au moins un sommet en commun. 
Deux sommets d’un graphe non orienté sont dits adjacents (ou voisins) s’il existe une arête les joignant. 
Une chaîne ou un chemin est une suite consécutive d’arêtes sur un graphe non orienté. 
Lorsqu’un graphe non orienté est en une partie, il est dit connexe.
Représentation des Graphes
Matrice d'Adjacence
Tableau N x N de booléens.
 Simple mais coûteux en mémoire (N² espace). 
Parcours des voisins en O(N).
Liste d'Adjacence
Dictionnaire associant à chaque sommet sa liste de voisins. 
Ajout d'arc et test de présence en O(1). 
Optimal pour des graphes peu denses.
Arbres
Un arbre est un graphe connexe sans cycle avec une racine. Dans un arbre, chaque nœud a un seul nœud père (excepté la racine). Chaque nœud peut avoir un nombre arbitraire de fils, dont il est le père.
La taille d’un arbre est son nombre de nœuds.
Les nœuds qui n’ont pas de fils sont appelés les feuilles.
L’arité d’un nœud est son nombre de fils. 
Deux nœuds ayant le même père sont dits nœuds frères.
La profondeur d’un nœud est la longueur du chemin le plus court vers la racine (la racine a donc pour profondeur 0).
La hauteur d’un arbre est la profondeur du nœud le plus profond (0 s’il est réduit à la racine et -1 si l’arbre est vide).
Les arbres binaires
Un arbre binaire est un arbre dont chaque nœud a au plus deux fils généralement ordonnés : le fils gauche et le fils droit. Il est équilibré si, pour chaque nœud interne, les sous-arbres gauche et droit ont une hauteur qui diffère de un au plus.
Un arbre binaire est complet si tous ses niveaux sont remplis, sauf éventuellement le dernier et que dans ce cas les feuilles du dernier niveau sont tassées à gauche. Un arbre binaire complet est forcément équilibré.
Les parcours d'arbres sont : 
Largeur ou BFS
niveau par niveau
Le parcours en largeur d'abord est un parcours étage par étage (de haut en bas) et de gauche à droite.
 Préfixe ou Préordre
racine - gauche - droit
Chaque nœud est visité avant que ses fils le soient.
On part de la racine, puis on visite son fils gauche (et éventuellement le fils gauche de celui-ci, etc.) avant de remonter et de redescendre vers le fils droit.
Postfixe ou Suffixe
gauche - droit - racine
Chaque nœud est visité après ses fils le soient.
On part donc de la feuille la plus à gauche, et on ne remonte à un nœud père que si ses fils ont tous été visités.
Infixe ou En ordre
gauche - racine - droit
Chaque nœud est visité après son fils gauche mais avant son fils droit.
On part donc de la feuille la plus à gauche et on remonte par vagues successives. Un nœud ne peut pas être visité si son fils gauche ne l'a pas été.
Les arbres binaires de recherches (ABR)
Un arbre binaire de recherche (ABR) est un arbre binaire tel que :
Les clefs des nœuds doivent être ordonnables (il doit exister une relation d’ordre) pour chacun de ses nœuds.
Chaque nœud du sous-arbre gauche a une clé inférieure ou égale à celle du nœud considéré.
Chaque nœud du sous-arbre droit possède une clé supérieure à celle-ci
Un ABR permet de rechercher rapidement (faible coût) des enregistrements dont les clés sont données par les nœuds de l’arbre.
Algorithmique et Optimisation
L'optimisation consiste à déterminer les paramètres maximisant ou minimisant une fonction. Plusieurs approches algorithmiques existent selon le type de problème rencontré.
Méthodes d'Optimisation
Diviser pour Régner
Le principe de diviser pour régner consiste à ramener la résolution d’un problème sur N données à la résolution d’un problème sur la moitié des données et poursuivre ce découpage jusqu’à ce que le problème devienne évident(par exemple trier un tableau d’une donnée). Une fois que les solutions des sous problèmes ont été trouvées, on les combine pour obtenir la solution du problème complet.
Le paradigme "diviser pour régner" repose donc sur 3 étapes :
DIVISER
Le problème d'origine est divisé en un certain nombre de sous-problèmes
RÉGNER
On résout les sous-problèmes (les sous-problèmes sont plus faciles à résoudre que le problème d'origine)
COMBINER 
Les solutions des sous-problèmes sont combinées afin d'obtenir la solution du problème d'origine.
Méthode Gloutonne
Un algorithme glouton (greedy algorithm) est un algorithme qui suit le principe de faire, étape par étape, un choix optimum local. Au cours de la construction de la solution, l’algorithme résout une partie du problème puis se focalise ensuite sur le sous-problème restant à résoudre.
Simple et intuitif mais cet algorithme n'assure pas la solution optimale globale.  Exemples : rendu de monnaie, sac à dos, Dijkstra.
Un algorithme glouton est un algorithme qui suit le principe suivant :
Résout le problème étape par étape, en faisant un choix optimal local dans l'espoir d'obtenir un résultat optimal global.
Ce choix d'étape n'est jamais remis en cause lors des étapes suivantes.
Algorithme des k plus proches voisins (KNN)
L'algorithme K-NN (K plus proches voisins) est une méthode d'apprentissage supervisé. Pour prédire, il cherche les K instances les plus proches dans le jeu de données et se base sur leurs variables de sortie. Principe : "Dis-moi qui sont tes voisins, je te dirai qui tu es."
Pour effectuer une prédiction, l’algorithme K-NN va chercher les K instances du jeu de données les plus proches de notre observation. Ensuite pour ces K voisins, l’algorithme se basera sur leurs variables de sortie (output variable), pour calculer la valeur de la variable de l’observation qu’on souhaite prédire.
Complexité des algorithmes
Le calcul de la complexité d’un algorithme permet de mesurer sa performance. Il existe deux types de complexité :
Complexité spatiale
Permet de quantifier l’utilisation de la mémoire
Complexité temporelle
Permet de quantifier la vitesse d’exécution
La complexité temporelle est liée à la notion de coût (en temps) d'un algorithme. C'est l'ordre de grandeur du nombre d'opérations arithmétiques ou logiques que doit effectuer l'algorithme pour résoudre le problème auquel il est destiné. Cet ordre de grandeur dépend évidemment de la taille N des données en entrée.
Bases de données relationnelles
Il est possible de gérer des données représentées de manière tabulaire (avec des fichiers CSV par exemple) et d'utiliser un langage de programmation pour effectuer les traitements. Cette approche convient pour des requêtes simples et des volumes de données limités, mais devient rapidement insuffisante face aux besoins actuels.
Les défis modernes de la gestion des données :
Le volume des données est souvent gigantesque (Big Data)
Les requêtes peuvent être complexes et nécessiter des optimisations
Les données sont utilisées simultanément par différents programmes ou utilisateurs (sites marchands, réservations en ligne, etc.)
C'est pourquoi l'utilisation de bases de données relationnelles est aujourd'hui la solution la plus répandue et la plus performante.
Les bases de données relationnelles reposent sur un modèle mathématique logique, défini en 1970 par l'informaticien britannique Edgar F. Codd (1923-2003) lors de ses travaux chez IBM. Il a reçu le prestigieux prix Turing en 1981 pour cette contribution majeure.
Ce modèle permet de modéliser les relations existantes entre plusieurs informations et de les organiser entre elles. Il est implémenté par des logiciels appelés Systèmes de Gestion de Bases de Données (SGBD).
Une base de données est donc un ensemble structuré d'informations organisées de manière à être facilement manipulées. Le modèle relationnel est aujourd'hui le plus utilisé car il permet l'indépendance entre structure physique et organisation logique des données.
Du tableau à la base relationnelle
Les composants d'un système relationnel avec ses trois niveaux : physique (fichiers et index), logique (interface SQL et tables), et applicatif (serveur SGBD).
Contraintes d'Intégrité
Contraintes de Domaine
Limitent les valeurs illégales ou mal formées selon le type d'attribut
Contraintes d'Entité
Clés primaires assurant l'unicité de chaque enregistrement
Contraintes Référentielles
Clés étrangères protégeant les relations entre tables
Structure des tables et concept de clés
Les structures du niveau logique définissent une modélisation des données sous forme de tables. Comprendre cette organisation est fondamental pour maîtriser les bases de données relationnelles.
Table
Composée de lignes et de colonnes, comme un tableau classique
Enregistrement
Chaque ligne correspond à un enregistrement, un ensemble de données liées
Attribut
Chaque colonne représente un attribut permettant de classifier les champs
Champ
Chaque donnée dans une cellule correspond à un champ spécifique
Les clés : le ciment des relations
Les relations d'une base sont connectées par certaines valeurs qu'elles contiennent. Ces liens sont stockés sous forme de clés.
Clé primaire
Elle permet d'identifier de manière unique chaque enregistrement d'une table. Elle facilite la mise en relation entre tables et garantit qu'aucun doublon n'existe.
Clé étrangère
Elle permet de mettre en relation deux tables au sein d'une BDD relationnelle et d'assurer l'intégrité référentielle des données.
Exemple : La table Produits (clé primaire : Référence) est liée à la table Ventes (clé étrangère : Référence produit). Le SGBD vérifie que toutes les valeurs de la clé étrangère correspondent à des valeurs existantes dans la clé primaire.
Langage SQL
Le SQL (Structured Query Language) permet d'envoyer des ordres appelés requêtes au SGBD. Le premier rôle du programmeur est de traduire des questions du langage naturel vers le langage SQL.
SELECT
Sélectionne les colonnes
SELECT * FROM table
SELECT col1, col2 FROM table
WHERE
Filtre les lignes
SELECT * FROM table
WHERE condition
DISTINCT
Supprime les doublons
SELECT DISTINCT col
FROM table
ORDER BY
Trie les résultats (ASC/DESC)
SELECT * FROM table
ORDER BY col ASC
Fonctions d'agrégation et jointures
📊 Fonctions d'agrégation (ou de groupes)
Les fonctions d'agrégation permettent de calculer des valeurs récapitulatives à partir d'un ensemble de lignes dans une table. Ces fonctions travaillent donc sur les colonnes :
AVG(col) : calcule la moyenne
SUM(col) : calcule la somme
MIN(col), MAX(col) : minimum et maximum
COUNT(col) : compte le nombre de lignes
🔗 Jointures avec JOIN
Une jointure permet d'associer plusieurs tables en les liant à partir d'un attribut commun :
SELECT t1.col, t2.col
FROM Table1 t1
JOIN Table2 t2
ON t1.attr = t2.attr
La clause ON spécifie les conditions de correspondance entre les enregistrements.
Modification des données et types SQL
Les requêtes de mise à jour permettent de modifier le contenu de la base de données. Le SGBD est garant du respect des contraintes d'intégrité.
INSERT INTO
Ajoute un nouvel enregistrement
INSERT INTO table (attr1, attr2)
VALUES (val1, val2)
UPDATE
Modifie des valeurs existantes
UPDATE table
SET attr = val
WHERE condition
DELETE
Supprime des enregistrements
DELETE FROM table
WHERE condition
Contraintes d'intégrité : Le SGBD interdit l'insertion de clés primaires dupliquées et la suppression d'enregistrements référencés par des clés étrangères dans d'autres tables.
Types de données SQL
Le web et ses langages
Le web est géré au niveau mondial par le W3C - World Wide Web Consortium. Cet organisme international indépendant définit les standards permettant aux ordinateurs connectés de pouvoir communiquer ensemble. Ces standards concernent les règles de communication, ainsi que les formats et langages à utiliser. Plusieurs langages ont été standardisés par le W3C pour décrire le contenu des pages (HTML), leur forme (CSS) et pour programmer les interactions (JavaScript).
Le principe d’échange de pages Web sur Internet fonctionnement sur le modèle client-serveur :
Client :
Application qui demande un service.
Ce sont par exemple les ordinateurs qui demandent une page Web au serveur. En pratique, c'est le navigateur Web (Firefox, Chrome, Safari, Edge, …) qui est le client car c’est lui qui effectue les requêtes.
Serveur 
Machine capable de délivrer des services (mail, web, DHCP…)
Ce sont par exemple les ordinateurs qui délivrent les sites Web aux internautes, c’est-à-dire aux clients. 
Le client fait une requête au serveur, qui lui répond en lui envoyant le code HTML de la page Web avec le protocole HTTP ou HTTPS.
Protocole HTTP ou HTTPS
Pour garantir le chiffrement des données entre le client et le serveur, il existe une version sécurisée du protocole HTTP, c'est le protocole HTTPS. 
1
le client (le navigateur Web) contacte un serveur et demande une connexion sécurisée en proposant une liste de méthodes de chiffrement.
2
Le serveur répond en choisissant dans cette liste une méthode de chiffrement et produit un certificat garantissant qu'il est bien le serveur en question. 
3
Les données échangées entre le client et le serveur sont ensuite chiffrées grâce à un algorithme de cryptographie.
Méthode GET et POST
Ces méthodes font partie des requêtes HTTP telles que HEAD, OPTIONS, CONNECT, TRACE, PUT, PATCH ou DELETE 
GET 
Méthode permettant de demander une ressource.
C'est la méthode employée lorsque le navigateur charge des élèments d'une page web.
POST 
Méthode utilisée pour soumettre des données en vue d'un traitement côté serveur. C'est la méthode employée lorsque l'on envoie au serveur les données issues d'un formulaire.
Langage HTML
Le langage HTML (Hypertext Markup Language ) a été conçu pour standardiser le format des pages envoyées par un serveur à un navigateur web. HTML est un langage de description des pages web permettant de structurer un texte en lui ajoutant des balises pour préciser comment le navigateur doit interpréter et mettre en forme le contenu.
Le document HTML peut être représenté par une arborescence notée DOM
Langage CSS
Le style graphique d'une page (polices utilisées, tailles, couleurs...) peut être précisé par un fichier de style au format CSS. Un fichier CSS (de anglais Cascading Stylesheet) contient des règles de mise en forme. Par exemple, tous les titres de niveau 1 (marqués par les balise H1) sont de telle couleur et de telle police. L’usage de fichiers CSS contribue a homogénéiser la présentation d'une page web et à séparer le fond, c’est-a-dire le contenu, de la forme.
Architecture des réseaux et protocoles
Un réseau informatique met en relation des ordinateurs via une technologie qui leur permet de communiquer. Le réseau Internet est un WAN (Wide Area Network) maillé interconnectant de nombreux réseaux locaux (LAN) de natures très différentes.
Switch (Commutateur)
Mémorise les adresses MAC et dirige les trames vers le port concerné. 
Routeur
Interconnecte des réseaux différents. Décide de la route selon les adresses IP. 
Carte réseau (NIC)
Interface entre matériel et réseau. Possède une adresse MAC unique.
Modèle TCP/IP
L’approche utilisée au sein des réseaux consiste à diviser les données en parties de taille moins importante et plus facilement gérables pour les envoyer sur le réseau. Cette division du flux de données en parties plus petites est appelée segmentation. La segmentation des messages permet, par l’envoi de parties individuelles de plus petite taille depuis une source vers une destination, à de nombreuses conversations différentes de s’entremêler sur le réseau. Le processus qui sert à entremêler les parties des différentes conversations entre elles sur le réseau est appelé multiplexage. Afin d’assurer une synchronisation des messages, il faut aussi fixer des règles concernant la méthode d'accès, le contrôle de flux et le délai d'attente de la réponse. Enfin, Il est aussi nécessaire de procéder à une encapsulation des parties du message avant de les envoyer sur le réseau (et de procéder à une désencapsulations lors de la réception).
Le modèle TCP/IP décrit la fonctionnalité des protocoles qui sont implémentés sur les hôtes émetteurs et récepteurs, interagissent pour fournir une livraison de bout en bout d’applications sur un réseau.
Adressage IPv4 
Au niveau de la couche réseau, les ordinateurs communiquent entre eux grâce au protocole IP (Internet Protocol), qui utilise les adresses organisées en 4 octets et représentés en décimal pointé (entre 0 et 255). Ces adresses servent aux ordinateurs du réseau pour communiquer entre eux, ainsi chaque ordinateur d'un réseau possède une adresse IP unique sur ce réseau. 
On distingue en fait deux parties dans l'adresse IP : une partie des nombres à gauche est appelée identificateur de réseau (Net-id ). L’autre partie, les nombres de droite désignent les ordinateurs de ce réseau et est appelée identificateur d'hôte (Host-id ). Pour définir les parties réseau et hôte d'une adresse, les périphériques utilisent un mot de 32 bits distinct appelé masque de sous-réseau. Il suffit d’appliquer un et logique entre l’adresse IPv4 et le masque de sous réseau pour trouver l’adresse réseau. Le protocole DHCP distribue automatiquement les adresses IP aux hôtes du réseau
Des adresses particulières…
Lorsque l'on annule la partie Host-id, c'est-à-dire lorsque l'on remplace les bits réservés aux machines du réseau par des zéros (par exemple 194.28.12.0 ), on obtient l'adresse réseau. Cette adresse ne peut être attribuée à aucun des ordinateurs du réseau.
Lorsque la partie Net-id est annulée, c'est-à-dire lorsque les bits réservés au réseau sont remplacés par des zéros, on obtient l'adresse machine. Cette adresse représente la machine spécifiée par le Host-id qui se trouve sur le réseau courant.
Lorsque tous les bits de la partie Host-id sont à 1, l'adresse obtenue est appelée adresse de diffusion (broadcast). Il s'agit d'une adresse spécifique, permettant d'envoyer un message à toutes les machines situées sur le réseau spécifié par le Net-id .
Enfin, l'adresse 127.0.0.1 est appelée adresse de rebouclage (ou loopback), car elle désigne la machine locale (ou localhost).
Des outils pour l'administrateur réseau →
Protocoles de Routage
Envisager de configurer les tables de routage à la main dans un réseau maillé est quasiment impossible. En effet, chaque fois qu’un élément du réseau tombe en panne ou qu'une modification est apportée à sa topologie (ajout d’une nouvelle liaison ou d’un nouveau routeur), il est nécessaire de recalculer toutes les routes et de mettre à jour les tables de routage de chaque routeur. On a donc cherché à automatiser ce processus en laissant les routeurs se charger eux-mêmes de mettre à jour leur table de routage, sans aucune intervention humaine. Ainsi, en plus de la transmission des paquets, les routeurs s’échangent les informations dont ils disposent sur les routes du réseau, en fonction de l'état de leurs voisins et de leurs liens de communication. Les règles à suivre pour réaliser ces échanges sont définies par un protocole de routage.
Protocole RIP
Distance en nombre de sauts. 
Vision locale (routing by rumor).
Maximum 15 sauts, 25 entrées. Mise à jour toutes les 30s.
Protocole OSPF
Vision globale du réseau. 
Distance tenant compte des débits. 
Utilise l'algorithme de Dijkstra pour les routes optimales.
Opérations booléennes 
Les fonctions booléennes sont utilisées partout : langages de programmation, architecture des ordinateurs, algorithmes cryptographiques. Les opérations NON, ET et OU permettent d'exprimer toutes les autres. 
En combinant plusieurs transistors, on reproduit le comportement des fonctions booléennes. les composants électroniques ainsi créés sont appelés portes logiques. C'est en associant ces portes logiques que l'on peut faire des circuits plus complexes tels que les mémoires ou les microprocesseurs qui constituent un ordinateur.
NON (not)
Inverse la valeur : not True = False
ET (and)
Vrai si les deux sont vrais
OU (or)
Vrai si au moins un est vrai
Architecture matérielle et langage assembleur
Un ordinateur (computer) se définit comme une machine de traitant de l’information à partir d’instructions organisées en programme. Il est capable : ✗ d’acquérir et de conserver des informations ✗ d’effectuer des traitements ✗ de restituer les informations stockées.
Composants d'un ordinateur
Les grands principes de fonctionnement des ordinateurs tels que nous les connaissons aujourd’hui reposent sur des travaux réalisés au milieu des années 40 par une équipe de chercheurs de l’université de Pennsylvanie. Ces travaux concernaient la conception d'un ordinateur dans lequel les programmes à exécuter étaient stockés au même endroit que les données qu’ils devaient manipuler, à savoir dans la mémoire de l'ordinateur. Cette idée d'utiliser une zone de stockage unique pour les programmes et les données est toujours utilisée aujourd’hui. Cette architecture est appelée modèle de Von Neumann, en l'honneur du mathématicien et physicien John Von Neumann qui participa à ces travaux.
Le schéma ci-contre décrit l'organisation des principaux composants d'un ordinateur selon l'architecture de Von Neumann. Ce modèle comporte quatre types de composants : 
une unité arithmétique et logique (UAL)
une unité de contrôle
la mémoire de l'ordinateur
les périphériques d'entrée sortie. 
Les deux premiers composants sont habituellement rassemblés dans un circuits électroniques qu'on appelle Unité Centrale de Traitement ou processeur (CPU en anglais, pour Control Processing Unit).
Langage machine
Les programmes stockés dans la mémoire centrale d'un ordinateurs sont constituées d'instructions de bas niveau, directement compréhensibles par le CPU. Il s'agit des instructions du langage machine. Lorsqu’elles sont stockées dans la mémoire, ces instructions ne sont ni plus ni moins que de simples nombres binaires, comme les données manipulées par les programmes.
Pour progresser dans l'exécution d'un programme, l'unité de contrôle de l'ordinateur réalise de manière continue, à un rythme imposé par l’horloge globale, la boucle suivante, appelée cycle d'exécution d'une instruction : 
Chargement de l'instruction (FETCH)
Décodage de l'instruction : opérations et opérandes (DECODE) 
Exécution des opérations (EXECUTE)
Ecriture du résultat (WRITEBACK)
Langage machine
Le langage machine, ou code machine, est la suite de bits qui est interprétée par le processeur d'un ordinateur exécutant un programme informatique. C'est le langage natif d'un processeur, c'est-à-dire le seul qu'il puisse traiter. Il est composé d'instructions et de données à traiter codées en binaire. Chaque processeur possède son propre langage machine donc un code machine ne peut s'exécuter que sur la machine pour laquelle il a été préparé. Le code machine est aujourd'hui généré automatiquement, généralement par la compilation d'un langage de programmation.
langage assembleur
Le langage assembleur (ou simplement assembleur ou ASM) est un langage de bas niveau qui représente le langage machine sous une forme lisible par un humain. Les combinaisons de bits du langage machine sont représentées par des symboles dits « mnémoniques ». Le programme assembleur convertit ces mnémoniques en langage machine exécutable.
Systèmes d'exploitation
En informatique, un système d'exploitation (souvent appelé OS — de l'anglais operating system — ou parfois SE — en français) est un ensemble de programmes qui dirige l'utilisation des ressources d'un ordinateur par des logiciels applicatifs. 
Le système d'exploitation (OS) assure la liaison entre ressources matérielles, utilisateur et logiciels. Il gère le processeur, la mémoire, les entrées/sorties, les applications, les droits et les fichiers.
Processus
Un processus est un programme en cours d'exécution avec ses ressources propres : instructions, mémoire (pile, tas, data), ressources (fichiers, sockets), environnement (PID, utilisateur, priorité).
États d'un processus 
1
Prêt 
En attente de pouvoir accéder au processeur
2
Bloqué
En attente des ressources nécessaires
3
Elu
Exécute toutes ses instructions
4
Terminé
Libère la mémoire et la totalité des ressources
Attention à l'interblocage (deadlock) présent lorsque deux processus s'attendent mutuellement.
Interblocage 
Le fonctionnement multitâche apporte malheureusement de nouveaux problèmes comme celui de l'interblocage. Imaginez deux processus, le premier s'est accaparé une ressource A et le second une ressource B ; chacun convoite ensuite la ressource de l'autre et n'est prêt à libérer sa propre ressource que si, celle de l'autre devient accessible. On est là face à une situation de blocage mutuel, un interblocage (deadlock). Celle-ci se traduit par la mise en sommeil définitif des deux processus, dans l'attente d'une libération de ressource qui ne surviendra jamais. La figure 1 illustre une situation simple d’interblocage. Dans un article de 1971, Jr Coffman a établi les conditions d'un interblocage : ✗ Au moins une ressource doit être conservée dans un mode non partageable. ✗ Un processus doit maintenir une ressource et en demander une autre. ✗ Une ressource ne peut être libérée que par le processus qui la détient. ✗ Chaque processus doit attendre la libération d'une ressource détenue par un autre qui fait de même.
Sécurisation des Communications
Le principe de base de la sécurisation d’une communication consiste à modifier la données qui doit être transmise (le chiffrement), de façon à ce que toute personne qui l’intercepterait ne pourrait pas en comprendre le sens. Seul le destinataire va pouvoir retrouver la donnée initiale (le déchiffrement) et la lire. Les méthodes de chiffrement sont basées sur l’utilisation de clés (chaîne de caractères) qui vont, par l’application d’un algorithme, chiffrer ou déchiffrer le message. Il existe deux principaux types de chiffrement de données qui permettent de rendre un message lisible uniquement par son destinataire: ✗ le chiffrement symétrique à clé partagée, ✗ le chiffrement asymétrique avec une paire clé publique / clé privée.
1
Chiffrement Symétrique
Une seule clé partagée pour chiffrer et déchiffrer
2
Chiffrement Asymétrique
Clé publique pour chiffrer, clé privée pour déchiffrer
3
HTTPS (TLS)
Combine les deux : asymétrique pour échanger une clé symétrique de session

©JPGardette
 Gamma, Napkin & NotebookLM
Made with