On appellera tableau (de dimension deux) toute liste de liste rectangulaire.

1. On dira d'un tableau qu'il a la propriété \(P^{*2+1}_{/3}\) si quel que soit l'entier \(e\) de ce tableau

   • soit \(2e+1\) est encore dans ce tableau;
   • soit \(e\) est un multiple de \(3\) et \(e/3\) est encore dans ce tableau.

   Écrire une fonction a_prop_mul2plusone_or_div3 qui accepte un tableau en argument et retourne True s'il a la propriété \(P^{*2+1}_{/3}\) si quel et False sinon. Ainsi [[1, 9], [4, 3]] a cette propriété mais pas [[1, 3], [7, 11]] ce qui est plus facile à voir quand les tableaux sont bien saisis comme ci-dessous

   tab_a_la_prop = [[1, 9],
                    [4, 3]]
   
   tab_n_a_pas_la_prop = [[1,  3],
                          [7, 11]]
   

   def a_prop_mul2plusone_or_div3(tab):
       for line in tab:
           for e in line:
               e_satis_cond = False
               for line2 in tab:
                   if 2*e+1 in line2:
                       e_satis_cond = True
                       break
                   if e % 3 == 0 and e // 3 in line2:
                       e_satis_cond = True
                       break
               if not e_satis_cond:
                   return False
       return True
   
   A = [[0, 0], [0, 0]]
   assert a_prop_mul2plusone_or_div3(A)
   
   A = [[1, 3], [0, 0]]
   assert a_prop_mul2plusone_or_div3(A)
   
   A = [[1, 3], [7, 11]]
   assert not a_prop_mul2plusone_or_div3(A)
   

2. On dira d'un élément A[i][j] d'un tableau à deux dimensions A que c'est un point selle si c'est à la fois un plus petit élément de sa ligne et un plus grand élément de sa colonne.

   1. Compléter la fonction has_saddle_point_v0 ci-dessous afin qu'elle retourne True si le tableau admet un point selle et False sinon.

      def has_saddle_point_v0(tab):
          n, p = len(A), len(A[0])
          for i in range(n):
              for j in range(p):
                  elmt = A[i][j]
                  for i2 in range(??):
                      if A[i2][j] ?? elmt:
                          return ??
                  for j2 in range(??):
                      if A[i][j2] ?? elmt:
                          return ??
          return ??
      

      def has_saddle_point_v0(tab):
          n, p = len(A), len(A[0])
          for i in range(n):
              for j in range(p):
                  elmt = A[i][j]
                  for i2 in range(n):
                      if A[i2][j] > elmt:
                          return False
                  for j2 in range(p):
                      if A[i][j2] < elmt:
                          return False
          return True
      

   2. 1. Si on suppose le tableau A carré de taille \(n\times{}n\), le temps d'execution (sur une machine fixée et dans le pire des cas) de l'appel has_saddle_point_v0(A) est-il plutôt proportionnel à \(n\) (càd linéaire en \(n\))? Proportionnel à \(n^2\) (càd quadratique en \(n\))? Proportionnel à \(n^3\) (càd cubique en \(n\))?
      2. Outre le tableau passé en argument, la quantité de mémoire de cet appel est-il constant, linéaire, quadratique ou cubique en \(n\)?
3. 1. Écrire une fonction col_index_all_min_row acceptant un tableau et un indice de ligne de ce tableau et qui retourne la liste des indices colonne des plus petits éléments de cette ligne puis se servir de cette fonction (dûment testée évidemment) pour écrire une fonction has_saddle_point_v1 qui utilise (un peu) plus de mémoire que has_saddle_point_v0 mais va (nettement) plus vite (au moins dans le pire des cas et avec de gros tableaux). On précisera si la classe de complexité (dans le pire des cas) de has_saddle_point_v0 c'est à dire si elle est constant, linéaire, quadratique ou cubique en \(n\).

   2. Écrire une fonction saddle_point acceptant un tableau en entrée et qui retourne la liste des points selles (chacun représenté par le couple (i,j)) de ce tableau. Par exemple avec

      A = [[ 0,-1, 1],
           [ 0, 0, 2],
           [-1,-2, 3]]
      

      l'appel saddle_point(A) doit retourner [(1,0), (1,1)].

      def col_index_all_min_row(A, i):
          row = A[i]
          cur_min = row[0] + 1
          min_ind_list = []
          for j in range(len(row)):
              elmt = row[j]
              if elmt < cur_min:
                  cur_min, min_ind_list = elmt, [j]
              elif elmt == cur_min:
                  min_ind_list.append(j)
          return min_ind_list
      
      A = [[0, -1, 1], [0, 0, 2], [-1, -2, 3]]
      assert col_index_all_min_row(A, 0) == [1]
      assert col_index_all_min_row(A, 1) == [0, 1]
      assert col_index_all_min_row(A, 2) == [1]
      
      def is_col_max(A, i, j):
          elmt = A[i][j]
          for k in range(len(A)):
              if A[k][j] > elmt:
                  return False
          return True
      
      A = [[ 0, -1, 1],
           [ 0,  0, 2],
           [-1, -2, 3]]
      assert is_col_max(A, 0, 0)
      assert is_col_max(A, 1, 1)
      assert is_col_max(A, 2, 2)
      assert not is_col_max(A, 2, 1)
      
      
      def saddle_point(tab):
          for i in range(len(A)):
              L = col_index_all_min_row(A, i)
              for j in L:
                  if is_col_max(A, i, j):
                      return True
          return False
      
      A = [[0, -1, 1], [0, 0, 2], [-1, -2, 3]]
      assert saddle_point(A)
      
      A = [[3, 2], [1, 4]]
      assert not saddle_point(A)
      
      def saddle_point_list(tab):
          res = []
          for i in range(len(A)):
              L = col_index_all_min_row(A, i)
              for j in L:
                  if is_col_max(A, i, j):
                      res.append((i, j))
          return res
      
      A = [[ 0, - 1, 1], [ 0,   0, 2], [-1, -2, 3]]
      assert saddle_point_list(A) == [(1,0), (1,1)]
      
      A = [[3, 2], [1, 4]]
      assert saddle_point_list(A) == []
      

4. Écrire la définition d'une fonction saddle_point_list qui accepte un tableau en argument et retourne la liste de ses points selles. par exemple avec

   A = [[0,-1,1],[0,0,2],[-1,-2,3]]

   l'appel saddle_point_list(A) doit retourner [(1,0), (1,1)].

On appellera tableau (de dimension deux) toute liste de liste rectangulaire. On appelle sous-tableau une partie rectangulaire d'un tableau (c'est à dire constituée de lignes et de colonnes successives).

1. 1. Écrire une fonction a_une_ligne_strict_pos qui accepte un tableau en entrée et renvoie True s'il a une ligne dont tous les éléments sont strictement positifs et False sinon.

      def a_une_ligne_strict_pos(tab):
          n, p = len(tab), len(tab[0])
          for line in tab:
              line_strict_ops = True
              for elmt in line:
                  if elmt <= 0:
                      line_strict_ops = False
              if line_strict_ops:
                  return True
          return False
      
      A = [[-1, 1], [1, 1]]
      assert a_une_ligne_strict_pos(A)
      
      A = [[0, 1], [1, 0]]
      assert not a_une_ligne_strict_pos(A)
      
      A = [[-1, 1], [1, -2]]
      assert not a_une_ligne_strict_pos(A)
      

   2. Idem avec les colonnes: écrire une fonction a_une_colonne_strict_pos qui accepte un tableau en entrée et renvoie True s'il a une colonne dont tous les éléments sont strictement positifs et False sinon.

      def a_une_colonne_strict_pos(tab):
          n, p = len(tab), len(tab[0])
          for j in range(p):
              col_strict_ops = True
              for i in range(n):
                  if tab[i][j] <= 0:
                      col_strict_ops = False
              if col_strict_ops:
                  return True
          return False
      
      A = [[-1, 1], [1, 1]]
      assert a_une_colonne_strict_pos(A)
      
      A = [[0, 1], [1, 0]]
      assert not a_une_colonne_strict_pos(A)
      
      A = [[-1, 1], [1, -2]]
      assert not a_une_colonne_strict_pos(A)
      

2. 1. Écrire une fonction chaque_ligne_au_moins_un_strict_pos qui accepte un tableau en entrée et renvoie True si toutes les lignes ont au moins un élément strictement positif et False sinon

      def chaque_ligne_au_moins_un_strict_pos(tab):
          for line in tab:
              un_elmt_strict_pos = False
              for elmt in line:
                  if elmt > 0:
                      un_elmt_strict_pos = True
                      break
              if not un_elmt_strict_pos:
                  return False
          return True
      
      A = [[-1, 1], [1, 1]]
      assert chaque_colonne_au_moins_un_strict_pos(A)
      
      A = [[0, 1], [1, 0]]
      assert chaque_colonne_au_moins_un_strict_pos(A)
      
      A = [[-1, -1], [1, -2]]
      assert not chaque_colonne_au_moins_un_strict_pos(A)
      

   2. Écrire une fonction chaque_colonne_au_moins_un_strict_pos qui accepte un tableau en entrée et renvoie True si toutes les colonnes ont au moins un élément strictement positif et False sinon

      def chaque_colonne_au_moins_un_strict_pos(tab):
          n, p = len(tab), len(tab[0])
          for j in range(p):
              un_elmt_strict_pos = False
              for i in range(n):
                  if tab[i][j] > 0:
                      un_elmt_strict_pos = True
                      break
              if not un_elmt_strict_pos:
                  return False
          return True
      
      A = [[-1, 1], [1, 1]]
      assert chaque_colonne_au_moins_un_strict_pos(A)
      
      A = [[0, 1], [1, 0]]
      assert chaque_colonne_au_moins_un_strict_pos(A)
      
      A = [[-1, -1], [1, -2]]
      assert not chaque_colonne_au_moins_un_strict_pos(A)
      

3. Écrire une fonction taille_max_sous_tab_strmt_pos qui accepte un tableau en argument et retourne la taille (sous la forme d'un tuple (nb_lignes,nb_colonnes)) d'un des sous-tableaux de taille maximal (ici comprendre: qui a le plus d'éléments) parmi ceux constitués uniquement de réels strictement positifs. Ainsi
   • avec A=[[-1,1,3],[-2,5,-1],[-3,2,4]] l'appel taille_max_sous_tab_strmt_pos(A) doit renvoyer (3,1).
   • avec A=[[-1,1,3],[-2,5,1],[-3,2,-4]] l'appel taille_max_sous_tab_strmt_pos(A) doit renvoyer (2,2).

1. Écrire une fonction nbr_max_car_succ_egaux qui accepte une chaîne de caractères en argument et retourne un tuple donc le premier élément est un entier (la longueur de la plus grande sous-liste constante) et le second un caractère (le caract_re constituant cette sous-chaîne).

2. Compléter et déboguer les fonctions itératives est_sous_chaine_iter_sans_tranches et est_sous_chaine_iter_avec_tranches ci-dessous pour qu(elles acceptent deux arguments de type str et retournent True si le second est une sous-chaîne du premier et False sinon. Ainsi les appels est_sous_chaine_iter_sans_tranches("abcd", "bc") et est_sous_chaine_iter_avec_tranches("abcd", "bc") doivent renvoyer True alors que les appels est_sous_chaine_iter_sans_tranches("abcd", "bd") et est_sous_chaine_iter_avec_tranches("abcd", "bd") doivent renvoyer False. Rappelons que si s (resp. L) est une chaîne de caractères (resp. une liste) alors s[i:j] renvoie la sous-chaîne (resp. la suos-liste) constituée des caractères (resp. des valeurs de la liste) d'indice k vérifiant i<=k<j.

   def est_sous_chaine_iter_sans_tranches(??):
       for ind_str1 ni range(??):
           est_sous_chaine_ici = ??
           for ind_str2 in range(??):
               if str1[??] != str2[??):
                   est_sous_chaine_ici = ??
           if est_sous_chaine_ici:
               retur ??
       return ??
   

   def est_sous_chaine_iter_avec_tranches(??):
       n1, n2 = len(str1), len(str2)
       for ind_str1 in range(??):
           if str1[??:??] == ??
               return ??
       return ??
   

   def est_sous_chaine_iter_sans_tranches(str1, str2):
       for ind_str1 in range(len(str1)-len(str2)+1):
           est_sous_chaine_ici = True
           for ind_str2 in range(len(str2)):
               if str1[ind_str1+ind_str2] != str2[ind_str2]:
                   est_sous_chaine_ici = False
           if est_sous_chaine_ici:
               return True
       return False
   
   def est_sous_chaine_iter_avec_tranches(str1, str2):
       n1, n2 = len(str1), len(str2)
       for ind_str1 in range(n1-n2+1):
           if str1[ind_str1:ind_str1+n2] == str2:
               return True
       return False
   
   
   str1, str2 = "acbabad", "cba"
   assert est_sous_chaine_iter_sans_tranches(str1, str2)
   assert est_sous_chaine_iter_avec_tranches(str1, str2)
   
   str1, str2 = "acbabad", "abd"
   assert not est_sous_chaine_iter_sans_tranches(str1, str2)
   assert not est_sous_chaine_iter_avec_tranches(str1, str2)
   

   def est_sous_chaine_iter(str1, str2):
       for ind_str1 in range(len(str1)-len(str2)+1):
           est_sous_chaine_ici = True
           for ind_str2 in range(len(str2)):
               if str1[ind_str1+ind_str2] != str2[ind_str2]:
                   est_sous_chaine_ici = False
           if est_sous_chaine_ici:
               return True
       return False
   
   str1, str2 = "acbabad", "cba"
   assert est_sous_chaine_iter(str1, str2)
   
   str1, str2 = "acbabad", "abd"
   assert not est_sous_chaine_iter(str1, str2)
   

3. On dira ici qu'une chaîne str2 est une sous-chaîne extraite de la chaîne str1 si on peut obtenir str2 en supprimant des caractères à str1. Écrire une fonction itérative est_sous_chaine_extraite_iter qui renvoie True si si son second argument est une sous-chaîne extraite du premier et False sinon. Ainsi

   • l'appel est_sous_chaine_extraite_iter("acbabad", "acbbd") doit renvoyer True;
   • et l'appel est_sous_chaine_extraite_iter("acbabad", "acbbb") doit renvoyer False.

   def est_sous_chaine_extraite_iter(str1, str2):
       ind_str2 = 0
       for ind_str1 in range(len(str1)):
           if ind_str2 == len(str2):
               return True
           if str1[ind_str1] == str2[ind_str2]:
               ind_str2 += 1
       return ind_str2 == len(str2)
   
   str1, str2 = ("acbabad", "acbbd"
   assert est_sous_chaine_extraite_iter(str1, str2)
   
   str1, str2 = "acbabad", "acbbb"
   assert not est_sous_chaine_extraite_iter(str1, str2)
   

4. On dit d'un tableau B que c'est un sous-tableau de A s'il forme un bloc rectangulaire de A c'est à dire s'il s'obtient en ne gardant que des éléments situées dans certaines lignes et certaines colonnes successives de A. Écrire une fonction est_sous_tableau qui fait vous savez quoi. Ici, mieux vaut utiliser les tranches (slices)!

   def est_sous_tableau_ici(A, B, i, j):
       nA, pA = len(A), len(A[0])
       nB, pB = len(B), len(B[0])
       assert 0<=i<nA and 0<=j<pA
       if i > nA-nB or j > pA-pB:
           return False
       for k in range(nB):
           if A[i+k][j:j+nB] != B[k]:
               return False
       return True
   
   A = [[1, 2 ,3, 4],
        [5, 6, 7, 8],
        [9,10,11,12]]
   B = [[ 6, 7],
        [10,11]]
   print(est_sous_tableau_ici(A, B, 1, 1))