====== Diviser pour régner ======

[[nsi:terminales:diviser_pour_regner|Fiche de cours]]

  * [[nsi:tds:quickhull|Algorithme Quickhull]]\\ Consiste à chercher l'enveloppe convexe d'un nuage de points
  * [[nsi:tds:quart_de_tour|Quart de tour d'une image]]\\ Méthode rapide pour effectuer le quart de tour d'une image
  * [[nsi:tds:maths:karatsuba|Algorithme de Karatsuba]]\\ Méthode rapide pour multiplier deux entiers. Peut être adapté pour multiplier deux polynômes.
  * [[nsi:tds:maths:fft|FFT]]\\ Transformée de Fourier rapide. Impossible de surestimer l'importance de cet algorithme, mais un peu délicat à expliquer en deux lignes...
  * [[nsi:tds:deux_points_les_plus_proches|Deux points les plus proches]]\\ Recherche les deux points les plus proches dans un nuage de points.

<WRAP center info>
L'alogorithme de [[https://fr.wikipedia.org/wiki/Algorithme_de_Shamos_et_Hoey|Shamos est Huey]] est un exemple d'algorithme //diviser pour régner//. Il sert à déterminer des [[https://fr.wikipedia.org/wiki/Diagramme_de_Vorono%C3%AF|diagrammes de Voronoi]]. Mais c'est un algorithme théorique, pensable sur papier mais difficile à réaliser en pratique. D'ailleurs, pour déterminer des diagrammes de Voronoi, on préfère l'algorithme de Fortune comme décrit dans ce [[nsi:tds:carte:fortune_algorithme|TD]].
</WRAP>