Option Informatique en Spé MP et MP*
Devoir surveillé du 17 mars 1998
Additionneurs, systèmes de numération, parties reconnaissables de N*



Présentation

On construit un circuit additionneur pour des nombres écrits en base 2, et on montre que sa performance ne peut être améliorée, sauf peut-être en changeant de méthode pour représenter les nombres.

On étudie alors une technique de représentation des nombres proposée par Algirdas Avizienis, et permettant l'addition de deux nombres à coût constant; l'idée d'Avizienis consiste à utiliser des chiffres signés.

On s'intéresse ensuite aux langages associés aux parties de N*, lorsqu'un système de numération a été fixé: après avoir défini la reconnaissabilité d'une partie de N*, on donne quelques exemples de parties reconnaissables et de parties qui ne le sont pas.

Enfin, on étudie une autre méthode de représentation des nombres (proposée initialement par Édouard Zeckendorf). Ici, l'idée est de remplacer la suite des puissances d'un même nombre B (la base) par la suite de Fibonacci.

Ce sujet a été soumis à la sagacité des étudiants le mardi 15 mars 1998.