Structures alternatives

a) if x:                       # une condition est deja booleenne
b) if not t:                   # une liste vide est fausse
c) if a < 0:                   # negation d'une inegalite large
d) if a <= 0 and b <= 0:       # De Morgan
e) if a > b:                   # les comparaisons a True sont toujours superflues
f) return cond                 # on renvoie directement l'expression

Le point (f) est le plus penalise en devoir : ecrire if cond: return True else: return False revient a ecrire x = x.

def median3(a, b, c):
    """Mediane de trois nombres deux a deux distincts. Au plus 3 comparaisons."""
    if a < b:
        if b < c:
            return b          # a < b < c
        elif a < c:
            return c          # a < c < b
        else:
            return a          # c < a < b
    else:                     # b < a
        if a < c:
            return a          # b < a < c
        elif b < c:
            return c          # b < c < a
        else:
            return b          # c < b < a

import itertools
for p in itertools.permutations([1, 2, 3]):
    assert median3(*p) == 2

3. Il y a \(3! = 6\) ordres possibles, et une reponse a fournir parmi 3. Un algorithme n'utilisant que des comparaisons est un arbre binaire de decision : avec \(k\) comparaisons il a au plus \(2^k\) feuilles. Il faut distinguer les 6 permutations, donc \(2^k \ge 6\), soit \(k \ge \lceil \log_2 6\rceil = 3\). L'algorithme ci-dessus atteignant 3 comparaisons dans le pire des cas, il est optimal.

def tarif(age, jour):
    """Prix d'une place en dirhams. Renvoie None si l'age est invalide."""
    if not isinstance(age, int) or age < 0:
        return None
    mercredi = (jour.lower() == "mercredi")
    if age >= 65:
        return 7                       # le plus restrictif d'abord
    if age < 12:
        return 5
    if age <= 25:
        return 6 if mercredi else 8
    return 9 if mercredi else 12

assert tarif(8,  "lundi")    == 5
assert tarif(20, "mercredi") == 6
assert tarif(40, "mercredi") == 9
assert tarif(70, "mercredi") == 7
assert tarif(-1, "lundi")    is None

Le test age >= 65 doit venir avant le cas « plus de 25 ans », sinon il ne serait jamais atteint. C'est le meme piege que dans l'exemple des mentions.

1.

Les deux colonnes coincident : les formules sont equivalentes. On retient qu'une implication de premisse fausse est vraie (« le faux implique n'importe quoi »).

def implique(P, Q):
    """P => Q."""
    return (not P) or Q

def equivaut(P, Q):
    """P <=> Q."""
    return P == Q

3. Par De Morgan puis distribution :

\[\neg\bigl(P \wedge (Q \vee \neg R)\bigr) \equiv \neg P \vee \neg(Q \vee \neg R) \equiv \neg P \vee (\neg Q \wedge R).\]

not P or (not Q and R)

4. C'est l'equivalence \(P \Leftrightarrow Q\), qui s'ecrit plus simplement P == Q en Python. Sa negation P != Q est le ou exclusif.

def somme_chiffres(n):
    s = 0
    while n > 0:
        s += n % 10
        n //= 10
    return s

def divisible_par_3(n):
    """Critere de la somme des chiffres. n >= 0."""
    if n == 0:
        return True
    s = somme_chiffres(n)
    while s >= 10:              # on itere jusqu'a obtenir un chiffre
        s = somme_chiffres(s)
    return s in (0, 3, 6, 9)

for n in range(1000):
    assert divisible_par_3(n) == (n % 3 == 0)

2. Demonstration. Ecrivons \(n = \sum_{i=0}^{p} c_i 10^i\). Comme \(10 \equiv 1 \pmod 3\), on a \(10^i \equiv 1^i = 1 \pmod 3\) pour tout \(i\), donc \[ n \equiv \sum_{i=0}^{p} c_i \pmod 3. \] Ainsi \(3 \mid n\) si et seulement si 3 divise la somme des chiffres. Le meme argument vaut pour 9, puisque \(10 \equiv 1 \pmod 9\).

3. Cette fois \(10 \equiv -1 \pmod{11}\), donc \(10^i \equiv (-1)^i \pmod{11}\) et \[ n \equiv \sum_{i=0}^{p} (-1)^i c_i \pmod{11}. \]

def divisible_par_11(n):
    """Critere de la somme alternee des chiffres."""
    s, signe = 0, 1
    while n > 0:
        s += signe * (n % 10)
        signe = -signe
        n //= 10
    return s % 11 == 0

for n in range(2000):
    assert divisible_par_11(n) == (n % 11 == 0)

1. Il est bien plus simple de nier la condition de non-intersection : les segments sont disjoints si et seulement si l'un est entierement a gauche de l'autre, soit \(b_1 < a_2\) ou \(b_2 < a_1\). Par negation (De Morgan) :

def se_croisent(a1, b1, a2, b2):
    """Les segments [a1,b1] et [a2,b2] ont-ils un point commun ?"""
    return a1 <= b2 and a2 <= b1

assert se_croisent(0, 5, 3, 8)
assert se_croisent(0, 5, 5, 9)      # contact en un point
assert not se_croisent(0, 5, 6, 9)

def intersection(a1, b1, a2, b2):
    """Segment intersection, ou None s'il est vide."""
    a, b = max(a1, a2), min(b1, b2)
    return (a, b) if a <= b else None

assert intersection(0, 5, 3, 8) == (3, 5)
assert intersection(0, 2, 7, 9) is None

3. Deux rectangles s'intersectent si et seulement si leurs projections sur \(Ox\) et sur \(Oy\) s'intersectent : le probleme se decouple en deux problemes 1D independants.

def rect_croisent(r1, r2):
    """r = (x_min, y_min, x_max, y_max)."""
    x1, y1, X1, Y1 = r1
    x2, y2, X2, Y2 = r2
    return (x1 <= X2 and x2 <= X1) and (y1 <= Y2 and y2 <= Y1)

def bissextile(a):
    return a % 4 == 0 and (a % 100 != 0 or a % 400 == 0)

DUREES = [31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31]

def jours_dans_mois(m, a):
    """Nombre de jours du mois m (1..12) de l'annee a."""
    if m == 2 and bissextile(a):
        return 29
    return DUREES[m - 1]

def date_valide(j, m, a):
    """La date j/m/a est-elle une date reelle ?"""
    if not (1 <= m <= 12):
        return False
    return 1 <= j <= jours_dans_mois(m, a)

def jour_julien(j, m, a):
    """Numero du jour dans l'annee. Precondition : date valide."""
    n = j
    for k in range(1, m):
        n += jours_dans_mois(k, a)
    return n

assert jour_julien(31, 12, 2024) == 366
assert jour_julien(31, 12, 2023) == 365
assert jour_julien(1, 3, 1900) == 60      # 1900 n'est PAS bissextile
assert jour_julien(1, 3, 2000) == 61      # 2000 l'est
assert not date_valide(29, 2, 1900)
assert date_valide(29, 2, 2000)

Le test date_valide(29, 2, 1900) est le plus discriminant : il verifie a la fois la regle des multiples de 100 et le chainage entre les trois fonctions.

1. Une telle fonction est determinee par la donnee de son image sur chacun des \(2^n\) elements de \(\{0,1\}^n\), et chaque image vaut 0 ou 1 : il y a donc \(\boxed{2^{2^n}}\) fonctions. Pour \(n=2\) cela fait \(2^4 = 16\) fonctions (dont \(\wedge\), \(\vee\), \(\oplus\), \(\Rightarrow\), les deux constantes...), et pour \(n=3\), \(2^8 = 256\).

2. Soit \(f\) une fonction booleenne a \(n\) variables. On note \(A = f^{-1}(\{1\})\) l'ensemble des \(n\)-uplets ou \(f\) vaut 1. Pour \(a = (a_1,\dots,a_n) \in A\), posons \[ m_a(x_1,\dots,x_n) = \bigwedge_{i=1}^{n} \ell_i, \qquad \ell_i = \begin{cases} x_i & \text{si } a_i = 1\\ \neg x_i & \text{si } a_i = 0.\end{cases} \] Le monome \(m_a\) vaut 1 exactement en \(x = a\). Donc \(f = \bigvee_{a \in A} m_a\) : c'est la forme normale disjonctive. Elle n'utilise que \(\neg\), \(\wedge\) et \(\vee\). Or par De Morgan \(P \vee Q = \neg(\neg P \wedge \neg Q)\) : on elimine \(\vee\). Le systeme \(\{\neg, \wedge\}\) est donc complet. (Si \(A = \emptyset\), \(f\) est la constante 0, egale a \(x_1 \wedge \neg x_1\).)

3.

• \(\neg P = P \barwedge P\), car \(\neg(P \wedge P) = \neg P\) ;
• \(P \wedge Q = \neg(P \barwedge Q) = (P \barwedge Q)\barwedge(P \barwedge Q)\) ;
• \(P \vee Q = \neg(\neg P \wedge \neg Q) = (P \barwedge P)\barwedge(Q \barwedge Q)\).

Comme \(\{\neg, \wedge\}\) est complet et que ces deux connecteurs s'expriment par NAND, le connecteur NAND est a lui seul complet.

def nand(P, Q):
    return not (P and Q)

def non(P):        return nand(P, P)
def et(P, Q):      return nand(nand(P, Q), nand(P, Q))
def ou(P, Q):      return nand(nand(P, P), nand(Q, Q))

for P in (False, True):
    assert non(P) == (not P)
    for Q in (False, True):
        assert et(P, Q) == (P and Q)
        assert ou(P, Q) == (P or Q)
print("systeme complet verifie")