2022-2023/1NSI/09_Recherche_par_dichotomie.../index.rst

38 lines
1.2 KiB
ReStructuredText
Raw Permalink Blame History

This file contains ambiguous Unicode characters

This file contains Unicode characters that might be confused with other characters. If you think that this is intentional, you can safely ignore this warning. Use the Escape button to reveal them.

Recherche par dichotomie et complexité
######################################
:date: 2023-03-13
:modified: 2023-03-17
:authors: Benjamin Bertrand
:tags: Python, Compexité
:category: 1NSI
:summary: Mesurer le temps d'execution, calculer une complexité et recherche par dichotomie.
Éléments du programme
=====================
.. list-table:: Interaction Homme machine sur le web
:header-rows: 1
* - Contenus
- Capacités attendues
- Commentaires
* - Recherche dichotomique dans un tableau trié
- Montrer la terminaison de la recherche dichotomique à laide dun variant de boucle.
- Des assertions peuvent être utilisées. La preuve de la correction peut être présentée par le professeur.
Quelques algorithmes classiques sont étudiés. Létude de leurs coûts respectifs prend tout son sens dans le cas de données nombreuses, qui peuvent être préférentiellement des données ouvertes.
Progression
===========
`Plan de travail sous forme de notebook <./Temps d'exécution.ipynb>`_: analyse de la performance d'un programme puis découverte de la recherche par dichotomie.
Cours sur la complexité
.. image:: ./1B_complexite.pdf
:height: 200px
:alt: Bilan sur la complexité