Applications informatiques | Exercices corrigés | Sciences de l'ingénieur 1ère

Concepts & Exercices

\(T(n) = O(f(n))\)

Complexité algorithmique

Base de données

SQL

Stockage structuré

Algorithmes

O(n)

Complexité

Structures

Listes, arbres

Organisation

🎯

Bases de données : Organiser et stocker des informations de manière structurée.

📋

Algorithmes : Séquences d'instructions pour résoudre un problème.

🔍

Structures de données : Façons d'organiser les données en mémoire.

⚙️

Protocoles réseau : Règles de communication entre systèmes.

Exercice 1

Créer une base de données relationnelle simple

Exercice 2

Analyser la complexité d'un algorithme de tri

Exercice 3

Implémenter une structure de données arborescente

Exercice 4

Comprendre les protocoles de communication TCP/IP

Exercice 5

Appliquer des techniques de sécurité informatique

Corrigé : Exercices 1 à 3

1 Base de données relationnelle

Définition :

Base de données relationnelle : Système d'organisation des données en tables liées par des relations.

Méthode de conception d'une base de données :

Identifier les entités et leurs attributs
Déterminer les relations entre entités
Appliquer les règles de normalisation
Créer les tables avec clés primaires et étrangères

Schéma de base de données pour une bibliothèque :

Tables : Livres, Emprunts, Adhérents

Relations : Un adhérent peut emprunter plusieurs livres

Table Livres :

ID_Livre (clé primaire), Titre, Auteur, ISBN, Genre

Table Adhérents :

ID_Adhérent (clé primaire), Nom, Prénom, Email, Date_adhésion

Table Emprunts :

ID_Emprunt (clé primaire), ID_Livre (clé étrangère), ID_Adhérent (clé étrangère), Date_emprunt, Date_retour

Clé étrangère :

Lien vers la clé primaire d'une autre table

Étape 1 : Analyse des besoins

Quelles informations doivent être stockées ?

Étape 2 : Identification des entités

Livres, Adhérents, Emprunts sont les entités principales

Étape 3 : Création des relations

Un adhérent peut emprunter plusieurs livres, un livre peut être emprunté par plusieurs adhérents

CREATE TABLE Livres (
  ID_Livre INT PRIMARY KEY,
  Titre VARCHAR(255),
  Auteur VARCHAR(255),
  ISBN VARCHAR(13)
);

Réponse finale :

Table	Attributs	Clé primaire
Livres	ID_Livre, Titre, Auteur, ISBN	ID_Livre
Adhérents	ID_Adhérent, Nom, Prénom, Email	ID_Adhérent
Emprunts	ID_Emprunt, ID_Livre, ID_Adhérent, Date	ID_Emprunt

Règles appliquées :

• Clé primaire : Identifiant unique dans une table

• Clé étrangère : Crée une liaison entre tables

• Normalisation : Éliminer les redondances

2 Complexité algorithmique

Définition :

Complexité algorithmique : Mesure de l'efficacité d'un algorithme en fonction de la taille des données.

Analyse de l'algorithme de tri à bulles :

Comparaison de chaque paire d'éléments adjacents

Échange si nécessaire

Notation O(n) :

Complexité linéaire - proportionnelle à la taille

Notation O(n²) :

Complexité quadratique - augmentation rapide

Notation O(log n) :

Complexité logarithmique - très efficace

Tri à bulles :

O(n²) dans le pire des cas

Étape 1 : Analyse de la boucle extérieure

Effectuée n fois (taille du tableau)

Étape 2 : Analyse de la boucle intérieure

Effectuée n-1, n-2, ..., 1 fois

Étape 3 : Calcul du nombre total d'opérations

(n-1) + (n-2) + ... + 1 = n(n-1)/2 = O(n²)

Tri à bulles : O(n²)

Réponse finale :

Tri à bulles : O(n²) dans le pire des cas

Tri rapide : O(n log n) en moyenne

Tri fusion : O(n log n) dans tous les cas

Règles appliquées :

• Notation Big O : Bornes supérieures de la complexité

• Meilleur cas : Situation optimale

• Pire cas : Situation la plus défavorable

3 Structure de données arborescente

Définition :

Arbre binaire : Structure de données hiérarchique avec un nœud racine et deux sous-arbres.

Arbre binaire de recherche :

Chaque nœud a au plus deux enfants

Valeur gauche < valeur nœud < valeur droite

Noeud racine :

Point d'entrée de l'arbre

Feuilles :

Noeuds sans enfants

Hauteur :

Longueur du chemin le plus long

Complexité :

O(log n) pour un arbre équilibré

Étape 1 : Définition de la structure

Chaque nœud contient une valeur et des pointeurs vers les enfants

Étape 2 : Insertion d'un élément

Comparer avec la racine, aller à gauche ou droite selon la valeur

Étape 3 : Recherche d'un élément

Parcourir l'arbre selon les règles de tri

Arbre BSR : O(log n) en moyenne

Réponse finale :

Structure : Noeud(value, left, right)

Insertion : O(log n) - O(n) selon équilibre

Recherche : O(log n) - O(n) selon équilibre

Suppression : O(log n) - O(n) selon équilibre

Règles appliquées :

• Arbre équilibré : Hauteur minimale pour optimiser les opérations

• Parcours infixé : Gauche, Racine, Droite

• Applications : Indexation, compilation, jeux

Corrigé : Exercices 4 à 5

4 Protocoles TCP/IP

Définition :

Protocole TCP/IP : Ensemble de règles permettant la communication entre ordinateurs sur Internet.

Modèle TCP/IP en couches :

Application, Transport, Internet, Liaison

Chaque couche a des responsabilités spécifiques

Couche Application :

HTTP, FTP, SMTP - interaction utilisateur

Couche Transport :

TCP, UDP - fiabilité et routage

Couche Internet :

IP - adressage et routage

Couche Liaison :

Ethernet, Wi-Fi - transmission physique

Étape 1 : Encapsulation des données

Chaque couche ajoute son en-tête

Étape 2 : Transmission sur le réseau

Paquets routés selon les adresses IP

Étape 3 : Décapsulation à la réception

Chaque couche retire son en-tête

TCP/IP : 4 couches hiérarchiques

Réponse finale :

Couche Application : Services réseau

Couche Transport : TCP/UDP

Couche Internet : IP, ICMP

Couche Liaison : Ethernet, Wi-Fi

Règles appliquées :

• TCP : Connexion orientée, fiable

• UDP : Sans connexion, rapide

• IP : Adresse unique pour chaque appareil

5 Sécurité informatique

Définition :

Sécurité informatique : Ensemble de mesures pour protéger les systèmes d'information.

Cryptographie asymétrique RSA :

Utilisation d'une paire de clés publique/privée

Fondement de la signature numérique

Confidentialité :

Chiffrement des données

Authentification :

Vérification de l'identité

Intégrité :

Protection contre les modifications

Non-répudiation :

Impossible de nier l'envoi

Étape 1 : Génération des clés

Choix de deux grands nombres premiers

Étape 2 : Calcul des clés publique/privée

Basé sur la factorisation difficile

Étape 3 : Chiffrement/déchiffrement

Utilisation des clés pour sécuriser les communications

RSA : basé sur la factorisation

Réponse finale :

Chiffrement symétrique : AES, DES

Chiffrement asymétrique : RSA, ECC

Hachage : SHA-256, MD5

Signature numérique : basée sur RSA

Règles appliquées :

• Clé privée : Gardée secrète

• Clé publique : Partagée librement

• HTTPS : SSL/TLS pour la sécurité web

Cours bien détaillé

\(O(n \log n) < O(n^2)\)

Comparaison de complexité

🎯

Base de données : Système organisé pour le stockage et la récupération.

📋

Algorithmes : Procédures étape par étape pour résoudre des problèmes.

🔍

Structures de données : Façons d'organiser et stocker des données.

⚙️

Protocoles réseau : Règles pour la communication entre systèmes.

💡

Conseil : Normaliser les bases de données pour éviter les redondances

🔍

Attention : Choisir le bon algorithme pour optimiser les performances

⚡

Astuce : Les structures de données influencent la complexité

📋

Méthode : Analyser la complexité avant d'implémenter

✅

Vérification : Tester les performances avec de grandes données

Concepts clés :

Normalisation : Éliminer les redondances dans les bases de données
Complexité : Mesurer l'efficacité des algorithmes
Arbres équilibrés : Optimiser les opérations de recherche
Protocoles : Règles de communication entre systèmes
Sécurité : Protéger les systèmes et données

Règles importantes :

Les bases de données relationnelles organisent les données en tables liées
La complexité algorithmique mesure l'efficacité en fonction de la taille des données
Les structures de données influencent directement la performance
Les protocoles assurent la communication fiable entre systèmes
La sécurité est essentielle dans toutes les applications modernes

Types de structures :

Listes chaînées : Accès séquentiel, insertion facile
Piles : LIFO (Last In First Out)
Files : FIFO (First In First Out)
Arbres : Hiérarchie, recherche rapide
Graphes : Relations complexes entre éléments

Comparaison algorithmique :

Tri par sélection : O(n²) - simple mais lent
Tri rapide : O(n log n) en moyenne - rapide
Tri fusion : O(n log n) dans tous les cas - stable
Recherche linéaire : O(n) - simple
Recherche binaire : O(log n) - rapide mais trié

Applications informatiquesExercices corrigés

Applications informatiques
Exercices corrigés