Dernière mise à jour: 27 janvier 2005.
Devoir 1
Questions et Réponses
1. Analyse et Complexité:
- Question 1.1a) : Est-ce qu'on peut utiliser les théorèmes vus au cours pour
démontrer la complexité
- Réponse: Oui, mais j'aimerais quand même mieux que l'énoncé
soit démontré par l'utilisation de la définition de grand O seulement (i.e. trouver des constantes c et no
, tels que bla bla...)
2. Piles et Files:
3. Fonctions Récursives:
- Question 3.1a) :Quelle est la valeur de n_0?
- Réponse: Elle peut être ce que l'on veut.
L'algorithme prend en entrée un entier qui sera le n_o de la série.
- Question 3.1a) :Est-ce que n_0 peut être un entier négatif?
- Réponse: Non, seulement un entier positif.
- Question 3.1b) :Est-ce que l'algorithme prend en entrées des nombres entiers ou des
réels?
- Réponse: Des nombres entiers.
- Question 3.1b) :Est-ce que l'algorithme peut prendre en entrées des nombres entiers
négatifs?
- Réponse: Oui
4. Partie Pratique:
- Question: Comment doit-on entrer la matrice de cellules noires et
blanches?
- Réponse: C'est à vous de décider. Votre algorithme
peut prendre en entrée un fichier contenant le tableau n par n, ou vous pouvez demander à
l'utilisateur d'entrer la matrice ligne par ligne ou colonne par colonne ou ...
- Question: Doit-on absolument utiliser un algorithme récursif?
- Réponse: Non, mais comme dans l'énoncé on parle
d'un algo. récursif, je vais donner + de points aux équipes utilisant la récursion
dans leur programme.
- Question: Que voulez-vous dans le fichier trace?
- Réponse: Le fichier trace devrait contenir un exemple d'exécution de votre
programme ainsi qu'une trace des appels de fonctions lors de l'exécution de votre exemple.