Algorithmie Flashcards by Clémence D.

Qu’est-ce qu’un ordinateur ?

Il s’agit d’un outil qui effectue des calculs sur de l’information.

How well did you know this?

Not at all

Perfectly

Comment est représentée l’information pour un ordinateur ?

Elle est représentée en binaire, qui utilise des bits (0 ou 1 -> signaux électriques).

How well did you know this?

Not at all

Perfectly

Qu’est-ce qu’un algorithme ?

Une suite finie et ordonnée d’instructions permettant de résoudre un problème ou d’effectuer une tâche.

How well did you know this?

Not at all

Perfectly

Quelle est la différence entre un algorithme et un programme ?

L’algorithme est la logique (conceptuelle), le programme est sa mise en œuvre dans un langage.

How well did you know this?

Not at all

Perfectly

Comment l’ordinateur représente un booléen ?

Pour représenter un booléen, qui est une valeur qui peut être soit vraie soit fausse, on utilise un seul bit.

How well did you know this?

Not at all

Perfectly

Comment l’ordinateur représente un entier ?

Pour représenter un nombre entier, on utilise plusieurs bits que l’on décompose en puissances de deux, ainsi qu’un bit qui indique le signe.

How well did you know this?

Not at all

Perfectly

Quels sont les trois formats qui permettent de représenter les nombres décimaux ?

Double : place la virgule au milieu des bits (précision fixe mais plus de place mémoire).
Flottant : la virgule se déplace en fonction de la valeur (précision pas fixe mais peu de mémoire).
Décimal : représente les nombres comme un texte au format décimal (très grande précision et beaucoup de mémoire)

How well did you know this?

Not at all

Perfectly

Comment l’ordinateur représente les textes ?

Pour représenter les textes on utilise les nombres et une table d’encodage, comme la table ASCII ou la table UTF.

How well did you know this?

Not at all

Perfectly

Comment représente-t-on l’hexadécimal ?

L’hexadécimal représente les nombres en utilisant 16 chiffres, de 0 à F. Ce format décompose les nombres en puissances de 16. Ce format est souvent pour représenter des couleurs.

How well did you know this?

Not at all

Perfectly

Quelles sont les conventions d’écriture pour différencier le binaire, le décimal et l’hexadécimal ?

On utilise les préfixes “0b” devant une valeur décimale, “0x” devant une valeur hexadécimale et rien devant une valeur binaire.

How well did you know this?

Not at all

Perfectly

Quels sont les différentes portes binaires ?

Les portes binaires sont des opérations sur les bits. Pour visualiser les portes, on
utilise les tables de vérités.

La porte NON, notée ‘¬’, retourne la valeur opposée du bit.
La porte ET, notée ‘.’, retourne vraie si et seulement si les deux bits sont vrais.
La porte OU, notée ‘+’, retourne vraie si au moins l’un des deux bits est vrai.
La porte XOU, notée ‘⊕’, retourne vraie si seulement l’un des deux bits
est vrai.

How well did you know this?

Not at all

Perfectly

Quelles sont les priorités de calcule en algèbre de Boole ?

Priorités : () -> ET -> OU -> XOU

How well did you know this?

Not at all

Perfectly

Quelle est la différence entre un langage compilé et un langage interprété ?

Les langages compilés créent un exécutable, tandis que les interprétés utilisent une application.

How well did you know this?

Not at all

Perfectly

Quelle est la différence entre un langage à typage statique et un langage à typage dynamique ?

Le premier impose au programmeur de définir le type de la variable et ne peut le changer. Le deuxième le fait automatiquement et les variables peuvent changer de type.

How well did you know this?

Not at all

Perfectly

Quelle est la différence entre un langage avec gestion de mémoire et un langage avec garbage collector ?

Pour le premier, le programmeur doit allouer et libérer manuellement de la mémoire. Le deuxième utilise un programme secondaire qui met en pause le principal pour nettoyer la mémoire.

How well did you know this?

Not at all

Perfectly

Quelles sont les différentes conventions de nommage ?

Pascale case : coller tous les mots et commencer par une majuscule (ex: MonSuperNom)
Camel case : coller tous les mots et commencer par une minuscule (ex: monSuperNom)
Snake case : tout en minuscule et espacé par des underscores (ex: mon_super_nom)
Screaming case : tout en majuscule et espacé par des underscores (ex: MON_SUPER_NOM)

How well did you know this?

Not at all

Perfectly

Quels sont les différents types de données ?

Study These Flashcards

Les types atomiques :
- BOOL : Booléen
- INT / UINT : Entier
- CHAR : caractère
- STRING : texte
- FLOAT / DOUBLE / DECIMAL : Valeur décimale

Les types composés :
- STRUCTURE : Regroupe plusieurs valeurs sous un même nom.
- ENUM : Liste plusieurs options.
- UNION : Indique qu’une valeur peut être de différents types.

Les collections :
- ARRAY : une séquence de taille fixe de valeurs de même type. Les
éléments sont accessibles via leurs index.

Que signifie “variable” en algorithmie ? Et comment la déclare-t-on ?

Study These Flashcards

C’est une zone mémoire nommée qui permet de stocker une valeur pouvant changer au cours de l’exécution.

INT my_number = 0

Quelles sont les différentes opérations que l’on peut effectuer sur des variables ?

Study These Flashcards

+ : addition ou concaténation
++ : incrémentation de 1
- : soustraction
– : décrémentation de 1
* : multiplication
/ : division
% : modulo (reste de la division)

Quelles sont les différentes opérations de comparaison que l’on peut effectuer sur des variables ?

Study These Flashcards

< : inférieur
<= : inférieur ou égale
> : supérieur
>= : supérieur ou égale
== : vérifie l’égalité
!= : vérifie la différence

Quels sont les opérateurs logiques ?

Study These Flashcards

! : porte binaire NON
& : porte binaire ET
&& : porte binaire « raccourcie » ET
| : porte binaire OU
|| : porte binaire « raccourcie » OU
^ : porte binaire XOU
«_space; : décalage de bits à gauche (= *2)
» : décalage de bits à droite (= /2)

Comment déclare-t-on un tableau ? Quelle est la méthode pour accéder au premier et dernier élément du tableau ?

Study These Flashcards

INT [] my_array = INT [100]

premier élément : my_array[0]
dernier élément : my_array[my_array.lenght - 1]

ATTENTION : la taille d’un tableau est fixe !

Qu’est-ce qu’une structure de données ?

Study These Flashcards

Une structure de données permet d’organiser des informations, de
représenter des relations, des priorités, etc…

Citer des types de structures de données.

Study These Flashcards

List (liste chaînée ou doublement chaînée)
Stack (pile)
Queue (file)
Map (dictionnaire)
Graph
Tree (arbre)

Qu'est-ce qu'une liste ?

Une liste peut être chaînée ou doublement chaînée. Elle fonctionne comme un tableau mais la taille n’est pas fixe.

Qu'est ce qu'une pile ?

Fonctionne comme une liste mais les éléments ne sont pas accessibles via leurs index. Le premier élément ajouté dans la pile est le dernier à sortir (FILO : First In Last Out).

Qu'est ce qu'une file ?

Fonctionne comme une liste mais les éléments ne sont pas accessibles via leurs index. Le premier élément ajouté dans la file est le premier à sortir (FIFO : First In First Out).

Qu'est ce qu'un dictionnaire ?

Associe des clés à des valeurs. Il ne peut pas y avoir plusieurs fois la même clé, mais il peut y avoir plusieurs fois la même valeur.

Qu'est ce qu'un graph ?

Représente des relations entre des objets (GPS, réseaux social, …).

Qu'est ce qu'un arbre ?

Il s’agit d’une structure hiérarchique de parent à enfants qui représente des relations entre des objets.

Comment exprime-t-on une condition en pseudo code ?

IF (condition) THEN Actions … ELIF (condition 2) THEN Actions … ELSE Actions … ENDIF ou SWITCH (valeur) THEN CASE (valeur 1) THEN Actions … BREAK CASE (valeur 2) THEN Actions … BREAK DEFAULT THEN Actions … BREAK ENDSWITCH ATTENTION : une seule branche de la condition s'exécute.

Comment réalise-t-on une boucle en pseudo-code ?

Répétitions infinies jusqu'à break : LOOP THEN Actions … ENDLOOP Boucle avec condition en entrée : WHILE (condition) THEN Actions … ENDWHILE Boucle qui s'exécutera au moins une fois : DO Actions … WHILE (condition) Boucle avec compteur : FOR (INT i = 0; i < 10; i++) THEN Actions … ENDFOR Itération sur les valeurs d'un tableau : INT [] values = {1, 2, 3, 4} FOREACH val IN values THEN Actions … ENDFOREACH

Quel est la différence entre BREAK et CONTINUE ?

Break permet de sortir d'une boucle sans considérer la fin de celle-ci. Continue permet de passer à l'itération suivante sans finir la boucle.

Quelle est la différence entre une fonction et une procédure ?

La fonction renvoie une valeur, la procédure non. FONCTION (TYPE1 paramètre1, TYPE2 paramètre2, …) TYPE THEN Actions … RETURN valeur ENDFONCTION

Qu'est-ce qu'une structure ?

Une structure est un type de données qui permet de regrouper plusieurs attributs, appelées champs, sous un même nom. Ces champs peuvent être de types différents. On accède aux champs d’une structure avec le point (.). STRUCTURE nom TYPE1 attribut1 TYPE2 attribut2 … ENDSTRUCTURE

Qu'est-ce qu'une énumération ?

Une énumération permet de définir un ensemble de constantes entières nommées, utilisées pour représenter des états ou des catégories de manière plus lisible. ENUM nom Option1 Option 2 … ENDENUM

Qu'est ce qu'une union ?

Une union est un type spécial qui permet de stocker plusieurs types différents dans le même espace mémoire, mais un seul à la fois. UNION nom TYPE1 variante1 TYPE2 variante2 … ENDUNION

Quels sont les différents types de mémoire ?

- Stack (la pile) : c'est une mémoire rapide utilisée pour stocker les variables locales et les appels de fonctions. Elle est gérée automatiquement, mais limitée en taille. - Heap (le tas) : c'est une mémoire plus grande utilisée pour allouer dynamiquement de la mémoire avec malloc. C’est plus lent et il faut penser à libérer cette mémoire avec free pour éviter les fuites.

Qu'est ce qu'un pointeur ?

Contrairement aux variables qui permettent de stocker une valeur, un pointeur stocke un emplacement mémoire.

Que permet d'évaluer la complexité ?

La complexité permet d’évaluer le temps d’exécution et l’empreinte mémoire d’un algorithme. On utilise la notation « Big O » qui évalue par ordre de grandeur la complexité d’un algorithme. La notation « Big O » utilise principalement ces valeurs remarquables : - O(1) - O(log𝑛) "bon" - O(𝑛) - O(𝑛log𝑛) - O(𝑛^2) "mauvais" - O(2^n) - O(𝑛!)

Algorithmie Flashcards

(40 cards)