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]]
   

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 ??
      

   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)].

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.
   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.
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
   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
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 ??
   

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.
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)!