Exercices — Algorithmique et logique

On considère la liste L = [3, 7, 1, 9, 4, 6, 2, 8, 5].

1. Quelle est la longueur de L ? Quelle est la valeur de L[0], L[4], L[-1] ?
2. Quelle est la valeur de L[2:5] ?
3. Écrire l’instruction Python pour ajouter 10 à la fin de la liste.
4. Écrire l’instruction pour supprimer la valeur 9 de la liste.
5. Sans utiliser max(), écrire un algorithme en Python qui calcule le maximum de la liste.

Écrire chaque liste en compréhension Python.

1. La liste des entiers de 1 à 20.
2. La liste des carrés des entiers de 1 à 10.
3. La liste des entiers de 1 à 50 divisibles par 3.
4. La liste des cubes des entiers impairs de 1 à 15.
5. La liste [0, 2, 4, 6, 8, 10] (sans écrire chaque valeur).

Écrire en Python chaque algorithme.

1. Une fonction moyenne(L) qui calcule la moyenne des éléments d’une liste de nombres.
2. Une fonction compter(L, x) qui compte le nombre d’occurrences de x dans L (sans utiliser count()).
3. Une fonction inverser(L) qui retourne la liste dans l’ordre inverse (sans utiliser reverse() ni le slicing [::-1]).
4. Une fonction fusionner(L1, L2) qui retourne une liste contenant tous les éléments de L1 et L2 triés dans l’ordre croissant.

Soit \(E = \{1, 2, 3, 4, 5, 6, 7, 8, 9, 10\}\), \(A = \{2, 4, 6, 8, 10\}\) (pairs), \(B = \{3, 6, 9\}\) (multiples de 3).

1. Calculer \(A \cap B\), \(A \cup B\) et \(\overline{A}\) (complémentaire dans \(E\)).
2. Est-ce que \(B \subset A\) ? Justifier.
3. Calculer \(A \times \{0, 1\}\) (donner les 4 premiers éléments).
4. Écrire en Python les ensembles \(A\) et \(B\) comme listes, puis calculer leur intersection et réunion.

Pour chaque proposition, indiquer si elle est vraie ou fausse (avec justification).

1. « \(2 + 2 = 4\) et \(\sqrt{4} = 2\) »
2. « \(3 > 5\) ou \(7 < 10\) »
3. « Il existe un entier \(n\) tel que \(n^2 = 2\) »
4. « Pour tout réel \(x\), \(x^2 \geq 0\) »
5. Écrire la négation de : « Pour tout entier \(n\), \(n^2 + 1 \geq 2\) »
6. Écrire la négation de : « Il existe un réel \(x\) tel que \(x^2 < 0\) »

Pour chaque implication, écrire la réciproque et la contraposée, puis dire si chacune est vraie ou fausse.

1. « Si \(n\) est divisible par 6, alors \(n\) est divisible par 2. »
2. « Si \(x = 3\), alors \(x^2 = 9\). »
3. « Si \(n^2\) est impair, alors \(n\) est impair. » (démontrer par contraposée)
4. Identifier : quelle est la condition nécessaire et quelle est la condition suffisante dans l’implication « être un carré parfait ⟹ être positif ou nul » ?

Une année est bissextile si elle est divisible par 4, sauf si elle est divisible par 100, à moins qu’elle ne soit aussi divisible par 400.

1. Écrire la proposition logique complète définissant une année bissextile à l’aide des connecteurs « et », « ou », « non ».
2. Écrire en Python une fonction est_bissextile(n) qui retourne True si l’année \(n\) est bissextile.
3. Tester avec 2000, 1900, 2024, 2100.
4. Utiliser une liste en compréhension pour lister toutes les années bissextiles entre 1900 et 2100.
5. Combien y a-t-il d’années bissextiles entre 1900 et 2100 inclus ?

On compare deux algorithmes qui parcourent une liste de \(n\) éléments :

1. Donner le nombre d'opérations effectuées par algo_lineaire et algo_quadratique en fonction de \(n\). Exprimer leur coût (= ordre de grandeur) sous la forme \(O(n^k)\).
2. Compléter le tableau ci-dessous (durée approximative pour 1 million d'opérations par seconde) :

3. Tracer les deux courbes \(t \mapsto n\) et \(t \mapsto n^2\) sur le même repère (échelle linéaire), pour \(n \in [0, 100]\). Que remarque-t-on ?
4. Pourquoi le coût quadratique devient-il rapidement « impraticable » pour de grands \(n\) ?