L3 MIASHS, Algorithme et Programmation 3, année 2023

Les notebooks ne seront pas corrigés (uniquement les fichiers *.py)
Vous pouvez utiliser un ou plusieurs fichiers
N’oubliez pas de commenter votre code
Un bout de code qui ne fonctionne sera corrigé si et seulement s’il est commenté.
Vos documents de TPs, la documentation officielle de Python et le site du cours sont autorisés. Tout le reste est interdit.
Toute communication est interdite et entraine directement un 0 à l’UE et un signalement pour triche

A. itérateurs et itérables

Retournez un objet itérateur qui donne toutes les valeurs impaires par ordre décroissant entre 100 et 50.
Retournez un objet itérable dont les itérateurs sont infinis et retourne les valeurs \(1, 2, 3, 1, 2, 3,\ldots\).
Écrivez une classe BoucleInfinie qui prend en argument une liste d’entiers et qui retourne un objet itérable qui répète cette liste à l’infini.

Par exemple,

B = BoucleInfinie([3, 2, 1, 4])

L’instance B est un itérable dont les itérateurs sont infinis et retournent les valeurs \(3, 2, 1, 4, 3, 2, 1, 4, \ldots\).

B. Sous-facteurs

On peut trouver la première occurrence d’une chaine dans une autre à l’aide de la méthode index des chaines de caractères.

Par exemple:

s = "Un choux à la crème c'est chou."
print(s.index("chou"))

Écrire une fonction génératrice (c’est à dire avec des yield) trouve_positions(u, v) avec u et v deux chaines de caractères qui retourne un itérateur sur les positions de u où v apparait.

Par exemple:

trouve_positions("Un choux à la crème c'est chou", "chou")

doit retourner un itérateur qui donne les valeurs 3 et 26.

C. Une classe simple pour des Matrices

L’objectif est de créer une classe Matrice permettant de manipuler des matrices de manière élémentaire.

Dans cet exercice, il est interdit d’utiliser numpy.

Le stockage des informations de la matrice peut être fait à votre convenance. Le plus simple est probablement d’utiliser des listes de listes ou des dictionnaires de couples d’indices.

Votre classe matrice ne doit hériter d’aucune classe et doit implémenter les méthodes suivantes:

Une initialisation avec un unique argument qui est soit une liste de liste soit une instance de Matrice

M = Matrice([[0, 1], [1, 0]])

donne la matrice

0	1
1	0

Une propriété dimension qui donne ses dimensions (sous forme d’un couple d’entiers)

Par exemple M.dimension retourne (2, 2)

Une méthode c qui prend un indice i et j et retourne le coefficient i,j si ces entiers ne sont pas trop gros et une erreur sinon.

Par exemple, M.c(0, 0) retourne 0, M.c(0, 1) retourne 1 et M.c(0, 2) fait une erreur.

Une méthode __repr__ pour afficher la matrice.
La méthode __eq__ qui teste que deux matrices sont égales.
La méthode __add__ qui permet d’additionner deux matrices, si elles ont la même dimension.
Une méthode transposition qui retourne une nouvelle matrice qui est la transposée sans changer la matrice actuelle.
La méthode __mul__ qui permet de multiplier deux matrices, si elles ont des dimensions compatibles (voir l’article wikipedia pour la formule.

Vérifiez que

Id = Matrice([1, 0], [0, 1]])
M = Matrice([[0, 1], [1, 0]])

Alors Id != M doit retourner True. On a également que M.transposition() == M retourne True.

Calcul du déterminant

Ajoutez une méthode supprime_ligne qui prend en argument un entier (l’indice de la ligne) et retourne une nouvelle matrice où cette ligne a été supprimée
Ajoutez une méthode supprime_colonne qui prend en argument un entier (l’indice de la colonne) et retourne une nouvelle matrice où cette colonne a été supprimée

On rappelle que pour une matrice \(M = (m_{i,j})\) de dimension \(n\times n\), on a la formule suivante: \[\text{det}(M) = \Sigma_{i=0}^{n-1} m_{i,0}(-1)^i \text{det}(M_{i,0})\] où \(M_{i,0}\) est la matrice où la ligne i et la colonne 0 ont été enlevée.

On a également le cas dégénéré où une matrice de taille \(1\times 1\) a pour déterminant son unique valeur.

Ajoutez une propriété déterminant qui retourne le déterminant de la matrice.
Estimez la complexité de ce calcul.

Compiled the: mar. 17 déc. 2024 14:03:32 CET