Term NSI
Exercice 1 : La conjecture de syracuse (lien wiki).
Soit un la suite d'entiers définie par :
un+1 = un / 2 si un est pair,
= 3 x un + 1 sinon
avec u0 un entier quelconque plus grand que 1.
Ecrire une fonction récursive syracuse(u_n) qui affiche les valeurs successives de la suite un tant que un est plus grand que 1.
Exercice 2 : Inversion d'une chaîne de caractère
Vous allez écrire une fonction qui prend une chaîne en entrée et renvoie l’inverse de cette chaîne.
Exercice 3 : longueur de chaine
Soit une chaine de caractères, écrire un algorithme récursif permettant de déterminer sa longueur
Exercice 4 : Palindrome
Un mot est un palindrome si on peut le lire dans les deux sens de gauche à droite et de droite à gauche. Exemple KAYAK est un palindrome. Ecrire une fonction récursive permettant de vérifier si un mot est un palindrome.
Exercice 5 : Sujet 0 exo 2
Exercice 6 : Sujet 1 de l'épreuve pratique
L'interface d'une structure de données abstraite est l'ensemble des opérateurs nécessaires à la manipulation de cette structure.
Exemple : Une pile est définie par l'interface comprenant les opérations suivantes:
-
Consulter le dernier élément de la pile: sommet()
-
Savoir si la pile est vide: est_vide()
-
Empiler un élément pour le mettre au sommet de la pile: empiler(élément)
-
Dépiler un élément pour le retirer du sommet de la pile: dépiler()
Sujet 0 : Exo 1
Sujet 3 : Exo 5
Sujet 6 : Exo 2
10. Calculabilité et décidabilité*
D'après Wikipedia :
Un problème de décision est dit décidable s'il existe un algorithme, une procédure mécanique qui se termine en un nombre fini d'étapes, qui le décide, c'est-à-dire qui réponde par oui ou par non à la question posée par le problème. S'il n'existe pas de tels algorithmes, le problème est dit indécidable. Par exemple, le problème de l'arrêt est indécidable.
Une petite mise au point est peut-être nécessaire : Dire qu'un problème est indécidable ne veut pas dire que la question posée n'a pas et n'aura jamais de solution, mais seulement qu'il n'existe pas de méthode unique et bien définie, applicable d'une façon mécanique, pour répondre à la question.
Démonstration de l'indécidabilité du problème de l'arrêt (raisonnement par l'absurde) :
Supposons qu'il existe un algorithme arret renvoyant soit True soit False (en un temps fini).
On peut définir grâce à arret un nouvel algorithme qu'on appelle paradoxe qui agit comme suit :
def paradoxe():
if arret(paradoxe):
while True:
pass
else:
return 0
Supposons que paradoxe() renvoie un résultat. Dans ce cas arret(paradoxe) va renvoyer True. L'algorithme paradoxe va déclancher une boucle infinie et ne jamais s'arrêter, ce qui est une contradiction. Supposons à l'inverse que paradoxe() ne renvoie pas de résultat, car ne s'arrête jamais. Alors arret(paradoxe) va répondre False et l'algorithme paradoxe renverra ainsi 0, ce qui est à nouveau une contradiction.
L'algorithme paradoxe ne peut donc pas exister. Et donc arret non plus.
Source : Numérique et sciences informatiques Tle. Ellipses.
15. Algorithmes sur les arbres binaires
Activité : Implémentation des algorithmes sur les arbres binaires et POO.
19. Méthode diviser pour régner
Sujet 7 exo 1 - 2023
Sujet 24 exo 2 - 2023
Ecrire la fonction tri(tab) à l'aide de la fonction fusion
Exercices :
Sujet 19 exo 1 - 2023 (recherche dichotomique non récursive)
Sujet 9 exo 2 - 2023 (recherche dichotomique récursive)
Exercice 1 : Epreuve pratique sujet 7 exo 1 2021
Exercice 2 : écrire une version non récursive du problème de "rendu de monnaie" en utilisant la programmation dynamique.
Exercice bonus : modifier votre précédent programme pour qu'il renvoie la liste des pièces constituant la solution optimale, plutôt que le nombre minimal de pièces.
22. Composants intégrés d'un système sur puce*
24. Modularité, exceptions et assertion
