Modéliser, Résoudre, Programmer comme un pro

Question 1

1 - Python

Quelles sont les méthodes pour ajouter/supprimer un élément d’un set Python ?

Answer 1

add et discard

Question 2

1 - Python

Un ensemble peut-il contenir un objet mutable ? Donner un exemple d’objet mutable.

Answer 2

Non. Une liste par exemple.

Question 3

1 - Python

Quelle propriété est requise pour les clés d’un dictionnaire ?

Answer 3

Elles doivent être immuables.

Question 4

1 - Python

Parmis ces objets, lequels sont immuables ?

• string
• list
• range
• set
• dict
• tuple

Answer 4

Les objets immuables sont :

• string
• range
• tuple

Question 5

1 - Python

Concernant la gestion de la mémoire, quelles sont les caractéristiques de Python ?

Indiquer les conséquences

Answer 5

• Python utilise un ramasse miettes (garbage collector)
• Les variables vivent dans l’espaces des variables
• Les objets vivent dans l’espace de objets
• Lorsqu’une variable contient un objet, elle ne le contient pas vraiment, elle point vers un objet dans l’espace des objets.

Par conséquent, on a besoin ni de déclarer, ni de libérer nos variables.

Question 6

1 - Python - Itérateurs

Quelle fonction permet d’obtenir l’itérateur d’un objet itérable ?

Answer 6

Il s’agit de la fonction iter

Question 7

1 - Python - Itérateurs

Quelle fonction permet d’obtenir l’élément suivant d’un itérateur ?

Answer 7

Il s’agit de la fonction next.

Question 8

1 - Python - Itérateurs

Quelle exception est levée lorsqu’un itérateur est vide ?

Answer 8

C’est l’exception StopIteration;

Question 9

1 - Python - Itérateurs

Que permet le mot clé yield en Python ?

De manière simple.

Answer 9

Il permet de transformer une fonction en itérateur.
C’est une sorte de return qui ne termine pas la fonction.

Question 10

1 - Python - Itérateurs

Comment créer un itérateur récursif à partir d’une fonction en Python ?

Answer 10

Il faut utiliser les mots clés yield from.

Question 11

1 - Python - Itérateurs

Concrètement, comment se comporte une fonction contenant le mot clé yield ?

Avant, Pendant et Après

Answer 11

1. Tant que l’itérateur n’est pas utilisé, rien ne se passe.
2. La fonction est exécutée jusqu’au prochain yield rencontré et retourne alors la valeur associée. La fonction est ensuite “mise en pause” jusqu’au prochain appel à l’itérateur.
3. La fin d’exécution provoque l’exception StopIteration.

Question 12

2 - SAT

Qu’est-ce qu’une variable booléenne ?

Answer 12

C’est une variable qui peut prendre la valeur VRAI ou FAUX.

Question 13

2 - SAT

Qu’est-ce qu’un littéral ?

Answer 13

Un littéral construit à partir de la variable x_i est : soit x_i, soit x_i barre.

Ils ont pour valeur, respectivement, 1 SSI x_i reçoit la valeur 1 et 1 SSI x_i reçoit la valeur 0.

Question 14

2 - SAT

Qu’est-ce qu’une clause ?

Answer 14

Une clause est une disjonction de littéraux.

Question 15

2 - SAT

Comment appelle-t-on une clause qui a pour valeur VRAI ?

Answer 15

On dit que la clause est satisfaite.

Question 16

2 - SAT

Que signifie qu’un ensemble de clause est satisfiable ?

Answer 16

Un ensemble S de clauses est satisfiable SSI il existe une attribution pour chaque variable booléenne satisfaisant toutes les clauses.

Question 17

2 - SAT

Qu’est-ce qu’un attribution ?

Answer 17

C’est le fait de donnr une valeur à chacune de nos variables booléennes;

Question 18

2 - SAT

Quel est le problème posé par le SAT ?

Answer 18

Etant donné un ensemble de clauses (même à 3 littéraux), le problème de décider s’il est satisfiable est un problème difficile.

Actuellement personne ne connait d’algorithme efficace pour le résoudre.

Question 19

2 - SAT

Pourquoi le problème de maximisation est au moins aussi difficile que le problème de décision ?

Answer 19

Puisque si l’on savait résoudre facilement le problème de maximisation alors on saurait résoudre facilement le problème de décision.

Question 20

2 - SAT

Expliquez l’algorithme d’Attribution aléatoire. Pourquoi utilise-t-on cet algorithme ?

Answer 20

L’algorithme attribue de manière aléatoire, équiprobable et indépendante, une valeur booléenne à chaque variable x_i.

On utilise cet algorithme parce que l’on ne sait ni décider, ni maximiser en un temps acceptable.

Question 21

3 - Automates

Comment se caractérise un automate ?

Answer 21

Un automate est caractérisé par :
* un ensemble d’états ;
* un ensemble de symboles : l’alphabet ;
* un ensemble d’états accepteurs, inclus dans l’ensemble des états ;
* un état initial ;

Question 22

3 - Automates

Qu’est-ce que la fonction de transition ?

Answer 22

C’est une fonction qui, d’un état et d’un symbole de l’alphabet donnés, ressort un état.

Exemples : δ(q1, a) = q2 ; δ(q1, b) = q1

Question 23

3 - Automates

Qu’est-ce que l’extension de la fonction de transition ?

Answer 23

C’est un fonction qui, d’un état et d’un mot donnés, ressort un état.

Exemples : δ*(q1, aba) = q2 ; δ*(q2, abba)

Question 24

3 - Automates

Que signifie le fait qu’un mot est accepté ?

Answer 24

Pour un mot w et un état initial q₀, la sortie de δ*(q₀, w) est un état accepteur.

Question 25

3 - Automates

Qu’est-ce qu’un langage ?

Answer 25

C’est l’ensemble des mots acceptés par l’automate.

Question 26

3 - Automates

Qu’est-ce qu’un automate déterministe ?

Answer 26

Un automate d’alphabet A est déterministe si pour tout état q et pour tout caractère c
de l’alphabet l’automate contient exactement une transition δ(q, c)