NUMERIQUE ET SCIENCES INFORMATIQUES

N.B. Niveau : Terminale Générale, enseignement de spécialité NSI (Numérique et Sciences Informatiques)

 
  1. Programmation orientée objet
  2. Récursivité
  3. Base de données et langage SQL
  4. Les listes chainées
  5. Piles et Files
  6. Les dictionnaires
  7. Protocoles de routage
  8. Les arbres
  9. Sécurisation des données
  10. Diviser pour régner
  11. Les processus
  12. Les systèmes sur puce
  13. Recherche textuelle
  14. Les Graphes
  15. L'intelligence artificielle
  16. Epreuves pratiques et écrites du Bac
  17. Le grand oral
 
  1. Algorithmes de référence de première
  2. Mise au point des programmes
  3. Algorithme de recherche dichotomique
  4. Algorithmes de tri par insertion
  5. Fractales récursives
  6. Algorithmes de tri par sélection
  7. Base de données et langage SQL
  8. Modularité
 
  1. Devoir maison n°1
  2. Les 48 sujets de l'épreuve pratique 2024
  3. Les 45 sujets de l'épreuve pratique 2023
 

D
É
C
O
N
N
E
C
T
É

Algorithmes de référence de première

1 - Parcours séquentiel d'un tableau

Programmer en Python les fonctions ci-dessous :

1.1 - La fonction recherche_occurrence :

  • prend en paramètre un tableau d'entiers tab et un entier val,
  • et retourne l'indice de la première occurrence de l'entier val dans le tableau tab, ou -1 si l'entier n'est pas dans le tableau.

Résultats attendus : 

>>>recherche_occurrence([1,5,8,5,-1],5)
>>>1

>>>recherche_occurrence([1,5,8,5,-1],3)
>>>-1

Programme :

       



	

	
				

				
	

	

	
Complexité :

	
	
	
Nous allons déterminer la complexité en nombre de comparaisons dans le pire cas de la fonction
	recherche_occurence, en fonction de la longueur n du tableau.

	
Dans le pire des cas, l'entier n'est pas dans le tableau. On réalise alors :
	
  • n itérations de la boucle ligne 6 comportant deux comparaisons
    • 
		
  • une comparaison (la première de la ligne 6) pour sortir de la boucle,
    • 
		
  • une comparaison ligne 8.
    • 
	

	
La complexité en nombre de comparaisons dans le pire des cas de cette fonction est donc 2n + 2.

	
C'est une complexité linéaire (à savoir).

	

	

	

	




1.2 - La fonction nombre_occurrences :



	
  • prend en paramètre un tableau d'entiers tab et un entier val,
    • 
		
  • et retourne le nombre d'occurrences de val dans tab.
    • 
	

	
Résultats attendus :

		

	
>>>nombre_occurrences([1,5,8,5,-1],5)
>>>2

>>>nombre_occurrences([1,5,8,5,-1],3)
>>>0

	

	

	
Programme :

	

	
	


	  

	

	    
	

	


	

	
				

				


	

	

	
	
Complexité :

	

	
Nous allons déterminer la complexité en nombre de comparaisons dans le pire cas de la fonction
		nombre_occurences, en fonction de la longueur n du tableau.

	
On effectue (dans tous les cas) n itérations de la boucle ligne 6, comportant une comparaison.

	
La complexité en nombre de comparaisons (dans le pire des cas) de cette fonction est donc n.

	
C'est une complexité linéaire (à savoir).
	
	

	


		



1.3 - La fonction moyenne qui :



	
  • prend en paramètre un tableau non vide d'entiers tab,
    • 
		
  • et retourne la moyenne des éléments de tab.
    • 
	

	
Exemple :

		

	
>>>moyenne([10.5,16.5,10,9])
>>>11,5

	

	
Programme :

		

	


	
	


	  

	

	    
	

	


	

	
				

				


	

	

	

	
	
Complexité :

	

	
Nous allons déterminer la complexité en nombre d'additions dans le pire cas de la fonction
		moyenne, en fonction de la longueur n du tableau.
	
On effectue (dans tous les cas) n itérations de la boucle ligne 6, comportant une addition.

	
La complexité en nombre d'additions (dans le pire des cas) de cette fonction est donc n.

	
C'est une complexité linéaire (à savoir).
	
	






1.4 - La fonction maximum :



	
  • prend en paramètre un tableau non vide d'entiers tab,
    • 
		
  • et retourne l'indice et la valeur du plus grand élément de tab.
    • 
	

	
Exemple :

		

	
>>>maximum([8,2,-5,-11,15,0])
>>>(4,15)

	

	
Programme :

		
	
	


	
	


	  

	

	    
	

	


	

	
				

				


	

	

	
	
Complexité :

	

	
Nous allons déterminer la complexité en nombre de comparaisons dans le pire cas de la fonction
		maximum, en fonction de la longueur n du tableau.
	
Dans tous les cas, on parcourt tout le tableau. On effectue donc n itérations de la boucle ligne 6, comportant une comparaison.

	
La complexité en nombre de comparaisons (dans le pire des cas) de cette fonction est donc n.

	
C'est une complexité linéaire (à savoir).
	
	
	
	
	


		



1.5 - La fonction minimum :



	
  • prend en paramètre un tableau non vide d'entiers tab,
    • 
		
  • et retourne l'indice et la valeur du plus petit élément de tab.
    • 
	

	
Exemple :

		

	
>>>minimum([8,2,-5,-11,15,0])
>>>(3,-11)

	

	
	
Programme :

		
		
	
	


	
	


	  

	

	       
	

	


	

	
				

				


	

	

	

	
	


		



	

	











































































Fond :   
Texte :    
Tables :   
Thème Python: