Exercices sur les algorithmes et problèmes #

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 « ce polynôme n’a pas de racine dans R »
    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 « entrez un entier supérieur ou égal à 2 »
    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

La complexité en temps mesure la quantité d’opérations ou le temps d’exécution d’un algorithme en fonction de la taille des données d’entrée. La complexité en espace mesure la quantité de mémoire supplémentaire nécessaire à l’algorithme pour fonctionner. Un algorithme peut être rapide (faible complexité en temps) mais utiliser beaucoup de mémoire (complexité en espace élevée), ou l’inverse.

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