Exercices sur les algorithmes et les ordinateurs #

Entrée :
Tableau d’entiers monTableau de taille N

Variables :
Entier somme = 0 // La somme du tableau
Entier index = 0 // Index de l’élément du tableau

Sortie :
Entier somme

Algorithme sommeTableau :

TANT QUE index < taille de monTableau FAIRE
    somme = somme + monTableau[index] // Addition des nombres
    index = index + 1 // Incrémentation de l’index
FIN TANT QUE

retourne somme

Entrée :
Tableau d’entiers monTableau de taille N
Entier nombreATrouver

Variables :
Entier index = 0 // Index de l’élément du tableau

Sortie :
Index de l’entier ou -1 si non trouvé

Algorithme trouverEntier :

TANT QUE index < taille de monTableau FAIRE
    SI nombreATrouver est égal à monTableau[index] ALORS
        retourner index // Fin de l’algorithme
    FIN SI
    index = index + 1 // Incrémentation de l’index
FIN TANT QUE

retourner -1 // Nombre non trouvé

Voici un algorithme inefficace. Vous pouvez faire mieux :

Variable entière i = 0
Variable entière somme = 0
TANT QUE i < 1000
    SI le reste de la division par 3 de i est zéro OU le reste de la division par 5 de i est zéro ALORS
        somme = somme + i
    i = i + 1
FIN TANT QUE
Retourne somme

Voici un algorithme inefficace (effectuant plus d’opérations que nécessaire). Vous pouvez faire mieux :

Variable entière i = 1
Variable entière solution = 1
TANT QUE i < 317584931803
    SI le reste de la division de 317584931803 par i est zéro ALORS
        Variable entière j = 3
        Variable booléenne premier = vrai
        TANT QUE j < i
            SI le reste de la division de i par j est zéro ALORS
                premier = faux
            j = j + 1
        FIN TANT QUE
        SI premier ALORS
            solution = i
    i = i + 1
FIN TANT QUE
Retourne solution

Pour les curieux, voici une solution exécutable en Python (voir ici) :

i = 1
solution = 1
while i < 317584931803:
    if 317584931803 % i == 0:
        j = 3
        premier = True
        while j < i:
            if i % j == 0:
                premier = False
            j = j + 1
        if premier:
            print(i, " est premier")
            solution = i
    i = i + 1
print(solution)

Vous pouvez supprimer la ligne print(i, " est premier") pour n’obtenir que la réponse finale. Notez que j commence à 3, car tout diviseur premier (sauf 2) est impair d’après le théorème fondamental de l’arithmétique.

Variable entière x

Divise x par 10, stocke le quotient dans la variable y

Divise y par 10, retourne le reste de la division

Exemple : si x est 531, le quotient de 531 divisé par 10 est 53, reste 1. Le quotient de 53 divisé par 10 est 5, reste 3.

L’itérateur i prend les valeurs de 0 à N, accédant ainsi à N+1 éléments du tableau R, ce qui provoque une erreur d’accès hors limites.

Algo pol

Entrée :
Nombres réels a, b, c // Coefficients du polynôme

Variables :
Nombres réels X1, X2, A // Racines et discriminant

Début
    A = b² - 4ac
    Si A < 0 Alors
        Afficher «&nbsp;ce polynôme n’a pas de racine dans R&nbsp;»
    Sinon
        Si A égale 0
            X1 = X2 = -b/(2a)
        Sinon // A > 0
            X1 = (-b - √A)/(2a)
            X2 = (-b + √A)/(2a)
        Fin Si
    Fin Si
Fin

Algo base

Entrée :
Nombre entier positif B // Base
Nombre entier positif M // Nombre à convertir

Variables :
Nombre entier q, r
Suite de caractères alphanumériques S

Début
    S = chaîne vide
    Si B < 2 Alors
        Afficher «&nbsp;entrez un entier supérieur ou égal à 2&nbsp;»
    Sinon
        q = M
        Tant que q > 0
            r = q - (q ÷ B) × B
            au cas où r
                égal à 10 : ajouter A au début de S
                égal à 11 : ajouter B au début de S
                égal à 12 : ajouter C au début de S
                égal à 13 : ajouter D au début de S
                égal à 14 : ajouter E au début de S
                égal à 15 : ajouter F au début de S
                dans tous les autres cas : ajouter r au début de S
            q = q ÷ B
        Fin Tant que
    Fin Si
Fin

Voici l’équivalent en Python (voir ici) :

def f(M, B):
    s = ""
    if B < 2:
        print("entrez un entier supérieur ou égal à 2")
        return
    q = M
    while q > 0:
        r = q - (q // B) * B
        if r == 10: s = "A" + s
        elif r == 11: s = "B" + s
        elif r == 12: s = "C" + s
        elif r == 13: s = "D" + s
        elif r == 14: s = "E" + s
        elif r == 15: s = "F" + s
        else: s = str(r) + s
        q = q // B
    return s

Algo parité

Entrée :
Nombre entier positif M // Nombre à tester

Variables :
Suite de caractères alphanumériques S

Début
    S = Algo_base(2, M)
    Si dernier caractère de S est égal au chiffre 0 Alors
        Afficher « pair »
    Sinon
        Afficher « impair »
    Fin Si
Fin

Entrée :
Entier positif n

Variable :
Entier fact = 1
Entier i = 1

TANT QUE i <= n FAIRE
    fact = fact × i
    i = i + 1
FIN TANT QUE

Retourner fact

Entrée :
Tableau d’entiers T de taille N

Variables :
Entier i = 0
Entier j = N - 1

TANT QUE i < j FAIRE
    échanger T[i] et T[j]
    i = i + 1
    j = j - 1
FIN TANT QUE

Retourner T

Entrée :
Chaîne de caractères S

Variable :
Entier compteur = 0
Entier i = 0

TANT QUE i < longueur de S FAIRE
    SI S[i] est une voyelle ALORS
        compteur = compteur + 1
    FIN SI
    i = i + 1
FIN TANT QUE

Retourner compteur

Entrée :
Entier positif n

Variables :
Entier original = n
Entier renverse = 0

TANT QUE n > 0 FAIRE
    renverse = renverse × 10 + (reste de la division de n avec 10)
    n = n ÷ 10
FIN TANT QUE

SI original = renverse ALORS
    Retourner Vrai
SINON
    Retourner Faux
FIN SI

Entrée :
Tableau d’entiers T de taille N

Variables :
Entier min = T[0]
Entier max = T[0]
Entier i = 1

TANT QUE i < N FAIRE
    SI T[i] < min ALORS
        min = T[i]
    FIN SI
    SI T[i] > max ALORS
        max = T[i]
    FIN SI
    i = i + 1
FIN TANT QUE

Retourner min, max

Dans un tableau non trié de taille \( n \), il faut au pire comparer l’élément recherché à chaque élément du tableau, soit \( n \) comparaisons. Cela correspond à une recherche linéaire, de complexité \( O(n) \).

La recherche binaire n’est applicable qu’aux tableaux triés, car elle repose sur le fait que l’on peut éliminer la moitié des éléments à chaque étape en comparant la valeur recherchée à l’élément du milieu. Si le tableau n’est pas trié, on ne peut pas savoir dans quelle moitié chercher. Sa complexité en temps est \( O(\log n) \).

Un exemple classique est le tri à bulles (bubble sort). Pour chaque élément, on compare avec tous les autres, ce qui fait environ \( n^2 \) comparaisons pour un tableau de taille \( n \). C’est pourquoi sa complexité est \( O(n^2) \).

Une complexité en \( O(n \log n) \) signifie que le nombre d’opérations croît plus vite que linéairement, mais beaucoup moins vite que quadratiquement. Par exemple, le tri fusion (merge sort) divise le tableau en deux à chaque étape (logarithmique) et traite chaque élément à chaque niveau de division (linéaire), d’où le \( n \log n \). Pour de grands tableaux, c’est beaucoup plus rapide qu’un tri naïf en \( O(n^2) \).

Alan Kay a conçu la programmation orientée objet pour faciliter la création de systèmes logiciels modulaires, flexibles et évolutifs, inspirés par la biologie et la communication entre objets autonomes. Son objectif principal était de permettre à chaque « objet » d’être responsable de son propre état et de communiquer avec d’autres objets uniquement via des messages, favorisant ainsi l’encapsulation et l’indépendance des composants.

Pour Kay, la programmation orientée objet devait avant tout encourager l’émergence de systèmes dynamiques, adaptatifs et faciles à modifier, plutôt que de se limiter à la simple hiérarchie de classes et à l’héritage. Il insistait sur l’importance de la communication par messages et sur la capacité à faire évoluer les programmes sans tout réécrire.

De nos jours, la programmation orientée objet est souvent réduite à l’organisation du code et des données, alors que la vision originale de Kay mettait l’accent sur la modularité, la flexibilité et l’autonomie des objets. Sa conception visait à rendre la programmation plus naturelle, intuitive et proche du fonctionnement des systèmes vivants.

Dahl et Nygaard ont conçu Simula pour faciliter la modélisation et la simulation de systèmes complexes, comme des réseaux, des usines ou des processus sociaux. Leur motivation était de représenter chaque entité du système par un « objet » autonome, regroupant données et comportements, afin de refléter la réalité de manière plus naturelle et modulaire.

Ils voulaient permettre l’encapsulation, la réutilisation du code grâce à l’héritage, et la création de structures hiérarchiques. Cette approche a posé les bases de la programmation orientée objet moderne, en rendant la conception de logiciels plus flexible, évolutive et adaptée à la complexité des systèmes réels.

James Gosling est un informaticien canadien considéré comme le principal créateur du langage Java, développé chez Sun Microsystems dans les années 1990. Son objectif était de concevoir un langage portable, sécurisé, simple et adapté aux systèmes embarqués et aux réseaux. Java devait permettre d’écrire un programme une seule fois et de l’exécuter partout (« Write Once, Run Anywhere »), grâce à la machine virtuelle Java (JVM).

Java est largement utilisé dans :

• Le développement d’applications d’entreprise (banques, assurances, télécommunications), grâce à sa robustesse, sa sécurité et la richesse de ses bibliothèques.
• Le développement d’applications mobiles (notamment Android), car Java est le langage principal pour Android et bénéficie d’un vaste écosystème.
• Les systèmes embarqués et l’Internet des objets (IoT), où la portabilité et la fiabilité de Java sont des atouts majeurs.

La notation de Backus-Naur (BNF) est une méthode formelle pour décrire la syntaxe des langages de programmation et des langages formels. Elle permet de spécifier les règles de formation des expressions valides dans un langage, en utilisant des symboles non terminaux, des symboles terminaux et des règles de production.

La BNF est largement utilisée pour définir la grammaire des langages de programmation, des protocoles ou des formats de données.

Exemple de BNF pour une expression arithmétique simple :

<expression> ::= <chiffre> | <expression> "+" <chiffre>
<chiffre> ::= "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9"

Cela décrit une expression composée d’un ou plusieurs chiffres séparés par des +.

À 3 GHz, un cycle d’horloge dure :

1 / 3 000 000 000 = 0,333... nanoseconde (ns) par cycle.

La lumière parcourt environ 30 cm (0,3 mètre) en 1 ns. Donc, en 0,333 ns, elle parcourt :

30 cm × 0,333... ≈ 10 cm.

Réponse : Pendant un cycle d’horloge à 3 GHz, la lumière parcourt environ 10 centimètres dans le vide.

Un kilo-octet (ko) correspond à 1 000 octets (selon le système décimal, préfixe SI), tandis qu’un kibioctet (Kio) correspond à 1 024 octets (selon le système binaire, préfixe IEC). Le préfixe « kilo » (k) est utilisé pour les puissances de 10, alors que « kibi » (Ki) est utilisé pour les puissances de 2. Ainsi, 1 Kio = 1 024 octets, 1 ko = 1 000 octets.

Entrée :
Tableau d’entiers trié T de taille N

Variables :
Entier nouvelle_taille = 1
Entier i = 1

Tant que i < N faire
    Si T[i] ≠ T[nouvelle_taille - 1] alors
        T[nouvelle_taille] = T[i]
        nouvelle_taille = nouvelle_taille + 1
    Fin si
    i = i + 1
Fin tant que

Retourner nouvelle_taille

Entrée :
Entier a
Entier positif ou nul n

Variable :
Entier résultat = 1
Entier i = 0

Tant que i < n faire
    résultat = résultat × a
    i = i + 1
Fin tant que

Retourner résultat

Entrée :
Chaîne de caractères S
Caractère c

Variable :
Entier compteur = 0
Entier i = 0

Tant que i < longueur de S faire
    Si S[i] = c alors
        compteur = compteur + 1
    Fin si
    i = i + 1
Fin tant que

Retourner compteur

Un temps moyen de \( O(1) \).

Un système d’exploitation est un logiciel qui agit comme interface entre l’utilisateur, les applications et le matériel. Ses rôles incluent la gestion des ressources, l’interface utilisateur, l’exécution des programmes, la sécurité et la gestion des erreurs.

Faux : Le système d’exploitation gère aussi les ressources matérielles.

Windows (ordinateurs personnels), macOS (Mac), Linux (serveurs et personnalisation), Android/iOS (mobiles).

Le noyau gère directement le matériel et les ressources de base.

Le multitâche permet l’exécution simultanée de plusieurs programmes via l’ordonnancement. Le multithreading gère les threads légers au sein d’un processus pour la concurrence.

Le CPU exécute les instructions des programmes, effectuant calculs et transferts.

Un processeur avec plusieurs cœurs indépendants, permettant le traitement parallèle (ex. : multitâche plus efficace).

Un processus est une instance isolée d’un programme ; un thread est une unité d’exécution légère partageant la mémoire du processus.

Via l’ordonnancement, en alternant entre processus pour maximiser l’utilisation du CPU.

Vrai.

Hiérarchie : RAM, cache, etc., pour équilibrer vitesse et coût.

RAM : rapide mais volatile ; cache : très rapide, non volatile pour les données fréquentes.

DRAM : recharge périodique, bon compromis ; SRAM : accès rapide, coûteuse.

Une faute de page charge la page depuis le disque en RAM.

Localité temporelle : réutilisation des mêmes données ; spatiale : données proches. Le cache stocke les données récentes/proches pour accélérer.

Interactions avec le monde extérieur via périphériques.

Interruptions (alerte CPU) et DMA (transfert direct vers RAM).

Direct Memory Access : transfert sans monopoliser le CPU, utile pour la performance.

Entrée : Clavier, Microphone ; Sortie : Écran ; Stockage/Réseau : Disque dur, Réseau Wi-Fi.

Pour lisser les échanges lents et éviter les blocages du CPU.