Collections de données

AP Informatique A · Sujet 4

Leçon vidéo pour ce sujet Ouvrir la page vidéo

4.1

Éthique de la Collecte de Données

Programme

Objectif d'apprentissage 4.1.A : Expliquer les risques pour la vie privée liés à la collecte et au stockage de données personnelles sur des ordinateurs.

4.1.A.1 Lors de l'utilisation d'un ordinateur, la vie privée personnelle est menacée. Lors du développement de nouveaux programmes, les programmeurs devraient essayer de protéger la vie privée personnelle de l'utilisateur.

Objectif d'apprentissage 4.1.B : Expliquer l'importance de reconnaître la qualité des données et les problèmes potentiels lors de l'utilisation d'un ensemble de données.

4.1.B.1 Le biais algorithmique décrit des erreurs systémiques et répétées dans un programme qui créent des résultats injustes pour un groupe spécifique d'utilisateurs.
4.1.B.2 Les programmeurs doivent être conscients de la méthode de collecte de l'ensemble de données et du potentiel de biais lors de l'utilisation de cette méthode avant d'utiliser les données pour extrapoler de nouvelles informations ou tirer des conclusions.
4.1.B.3 Certains ensembles de données sont incomplets ou contiennent des données inexactes. L'utilisation de telles données dans le développement ou l'utilisation d'un programme peut entraîner un fonctionnement incorrect ou inefficace du programme.

Objectif d'apprentissage 4.1.C : Identifier un ensemble de données approprié à utiliser afin de résoudre un problème ou répondre à une question spécifique.

4.1.C.1 Le contenu d'un ensemble de données peut être lié à une question ou un sujet spécifique et pourrait ne pas être approprié pour donner des réponses correctes ou extrapoler des informations pour une autre question ou un autre sujet.

Source : Description du cours et de l'examen AP College Board

Des baies de serveurs dans un centre de données – de grands collectes de données soulèvent des questions éthiques sur la collecte et l'utilisation

Les programmes qui recueillent des données soulèvent des questions de vie privée 隐私 et de consentement 同意. Ne collectez que ce qui est nécessaire, protégez-le, et soyez honnête sur son utilisation. Les données peuvent comporter un biais 偏见 si elles ne représentent pas tout le monde équitablement, menant à des résultats injustes – une responsabilité qui accompagne le stockage d'informations.

Vocabulaire Entrainer

Anglais	Chinois	Pinyin
privacy/ˈprɪvəsi/	隐私	yǐn sī
consent/kənˈsent/	同意	tóng yì
bias/ˈbaɪəs/	偏见	piān jiàn
data structure/ˈdeɪtə ˈstrʌktʃə/	数据结构	shù jù jié gòu

4.2

Pourquoi Nous Avons Besoin de Structures de Données

Programme

Objectif d'apprentissage 4.2.A : Représenter des modèles et des algorithmes impliquant des jeux de données trouvés dans la vie quotidienne à l'aide de langage écrit ou de diagrammes.

4.2.A.1 Un jeu de données est une collection de pièces d'informations ou de données spécifiques.
4.2.A.2 Les jeux de données peuvent être manipulés et analysés pour résoudre un problème ou répondre à une question. Lors de l'analyse des jeux de données, les valeurs du jeu sont accédées et utilisées une par une, puis traitées selon le résultat souhaité.
4.2.A.3 Les données peuvent être représentées dans un diagramme en utilisant un graphique ou un tableau. Cette visualisation peut être utilisée pour planifier l'algorithme qui sera utilisé pour manipuler les données.

Source : Description du cours et de l'examen AP College Board

Un classeur : les collections stockent de nombreuses valeurs sous un seul nom afin que les algorithmes puissent les traiter

Une seule variable ne contient qu'une valeur ; les problèmes réels nécessitent de stocker de nombreuses valeurs liées – une liste d'élèves, des pixels, des lectures de capteurs. Une structure de données 数据结构 organise une collection pour que nous puissions stocker, trouver et traiter des éléments efficacement. Le cours AP utilise trois structures : le tableau, l'ArrayList, et le tableau 2D.

Vocabulaire Entrainer

Anglais	Chinois	Pinyin
array/əˈreɪ/	数组	shù zǔ
Traverse/trəˈvɜːs/	遍历	biàn lì

4.3

Créer et Lire un Tableau

Programme

Objectif d'apprentissage 4.3.A : Développer du code utilisé pour représenter des collections de données apparentées à l'aide d'objets tableaux unidimensionnels (1D).

4.3.A.1 Un tableau stocke plusieurs valeurs du même type. Les valeurs peuvent être soit des valeurs primitives, soit des références d'objets.
4.3.A.2 La longueur d'un tableau est établie au moment de sa création et ne peut pas être modifiée. La longueur d'un tableau peut être accédée via l'attribut length.
4.3.A.3 Lorsqu'un tableau est créé en utilisant le mot-clé new, tous ses éléments sont initialisés avec les valeurs par défaut pour le type de données des éléments. La valeur par défaut pour int est 0, pour double est 0.0, pour boolean est false, et pour un type de référence est null.
4.3.A.4 Les listes d'initialisation peuvent être utilisées pour créer et initialiser des tableaux.
4.3.A.5 Les crochets [ ] sont utilisés pour accéder à et modifier un élément dans un tableau 1D en utilisant un index.
4.3.A.6 Les valeurs d'index valides pour un tableau s'étendent de 0 à une unité inférieure à la longueur du tableau, inclus. L'utilisation d'une valeur d'index hors de cette plage entraînera une ArrayIndexOutOfBoundsException.

Source : Description du cours et de l'examen AP College Board

Un tableau 数组 est une collection ordonnée de taille fixe de valeurs de même type. Les indices vont de 0 à length - 1 :

Un tableau à une dimension (une liste) avec ses indices et bornes

int[] nums = new int[5];        // five zeros
int[] vals = {3, 1, 4, 1, 5};   // initialized
int first = vals[0];            // 3
int n = vals.length;            // 5 (a field, not a method)

Accéder à un indice hors 0..length-1 provoque une ArrayIndexOutOfBoundsException.

4.4

Visiter Chaque Élément d'un Tableau

Programme

Objectif d'apprentissage 4.4.A : Développer du code servant à parcourir les éléments d'un tableau 1D et déterminer le résultat de ces parcours.

4.4.A.1 Parcourir un tableau consiste à utiliser des instructions de répétition pour accéder à tous ou à une séquence ordonnée d'éléments dans un tableau.
4.4.A.2 Parcourir un tableau avec une boucle for indexée ou une boucle while nécessite l'accès aux éléments via leurs indices.
4.4.A.3 Une en-tête de boucle élargie for comprend une variable, appelée variable de boucle élargie for. Pour chaque itération de la boucle élargie for, la variable de boucle élargie for est affectée d'une copie d'un élément sans utiliser son index.
4.4.A.4 Affecter une nouvelle valeur à la variable de boucle élargie for ne change pas la valeur stockée dans le tableau.
4.4.A.5 Lorsqu'un tableau stocke des références d'objets, les attributs peuvent être modifiés en appelant des méthodes sur la variable de boucle élargie for. Cela ne change pas les références d'objets stockées dans le tableau.
4.4.A.6 Du code écrit avec une boucle élargie for pour parcourir les éléments d'un tableau peut être réécrit en utilisant une boucle indexée for ou une boucle while.

Source : Description du cours et de l'examen AP College Board

Parcourir 遍历 un tableau avec une boucle for (donne l'indice) ou une boucle enhanced for / for-each (donne chaque valeur, lecture seule) :

for (int i = 0; i < a.length; i++) { a[i] *= 2; }   // can modify
for (int v : a) { System.out.println(v); }          // read each value

4.5

Algorithmes Standard de Tableau

Programme

Objectif d'apprentissage 4.5.A : Développer du code pour des algorithmes standards et originaux dans un contexte ou une spécification donnée impliquant des tableaux et déterminer le résultat de ces algorithmes.

4.5.A.1 Il existe des algorithmes standards qui utilisent des parcours de tableaux pour :
- déterminer une valeur minimale ou maximale
- calculer une somme ou une moyenne
- déterminer si au moins un élément possède une propriété particulière
- déterminer si tous les éléments possèdent une propriété particulière
- déterminer le nombre d'éléments ayant une propriété particulière
- accéder à toutes les paires consécutives d'éléments
- déterminer la présence ou l'absence d'éléments dupliqués
- décaler ou faire pivoter des éléments vers la gauche ou la droite
- inverser l'ordre des éléments

Source : Description du cours et de l'examen AP College Board

Maîtrisez ces modèles : calculer une somme ou une moyenne, trouver le max/min, compter les éléments répondant à une condition, vérifier s'il y a un double, et inverser ou décaler des éléments. Chacun est un parcours avec un résultat accumulé :

int sum = 0;
for (int v : a) sum += v;
double avg = (double) sum / a.length;

4.6

Lire des Données depuis un Fichier Texte

Programme

Objectif d'apprentissage 4.6.A : Développer du code pour lire des données à partir d'un fichier texte.

4.6.A.1 Un fichier est un stockage de données persistant lorsque le programme n'est pas en cours d'exécution. Les données dans un fichier peuvent être récupérées lors de l'exécution du programme.
4.6.A.2 Un fichier peut être connecté au programme en utilisant les classes File et Scanner.
4.6.A.3 Un fichier peut être ouvert en créant un objet File, en utilisant le nom du fichier comme argument du constructeur.
- File(String str) est le constructeur File qui accepte un nom de fichier String à ouvrir en lecture, où str est le chemin d'accès du fichier.
4.6.A.4 En utilisant la classe File, il est requis d'indiquer quoi faire si le fichier avec le nom fourni ne peut pas être ouvert. Une façon de réaliser cela est d'ajouter throws IOException à l'en-tête de la méthode qui utilise le fichier. Si le nom de fichier est invalide, le programme se terminera.
4.6.A.5 Les classes File et IOException font partie du package java.io. Une instruction import doit être utilisée pour rendre ces classes disponibles pour l'utilisation dans le programme.
4.6.A.6 Les méthodes et constructeurs Scanner suivants — y compris ce qu'ils font et quand ils sont utilisés — font partie de la référence rapide Java :
- Scanner(File f) est le constructeur Scanner qui accepte un File pour la lecture.
- int nextInt() retourne le prochain int lu depuis le fichier ou la source d'entrée s'il est disponible. Si le prochain int n'existe pas ou est hors plage, cela entraînera une InputMismatchException.
- double nextDouble() retourne le prochain double lu depuis le fichier ou la source d'entrée. Si le prochain double n'existe pas, cela entraînera une InputMismatchException.
- boolean nextBoolean() retourne le prochain boolean lu depuis le fichier ou la source d'entrée. Si le prochain boolean n'existe pas, cela entraînera une InputMismatchException.
- String nextLine() retourne la prochaine ligne de texte sous forme de String lu depuis le fichier ou la source d'entrée ; peut retourner la chaîne vide si appelée immédiatement après une autre méthode Scanner qui lit depuis le fichier ou la source d'entrée.
- String next() retourne le prochain String lu dans le fichier ou la source d'entrée.
- boolean hasNext() retourne true s'il y a un prochain élément à lire dans le fichier ou la source d'entrée ; retourne false sinon.
- void close() ferme ce scanner.
- Instruction d'exclusion : Accepter l'entrée clavier est hors du programme du cours et de l'examen AP Computer Science A.
4.6.A.7 L'utilisation de nextLine et des autres méthodes Scanner ensemble sur la même source d'entrée nécessite parfois du code pour ajuster les différentes façons dont les méthodes gèrent les espaces blancs.
- Instruction d'exclusion : Écrire ou analyser du code utilisant à la fois nextLine et d'autres méthodes Scanner sur la même source d'entrée est hors du programme du cours et de l'examen AP Computer Science A.
4.6.A.8 La méthode additionnelle suivante String — y compris ce qu'elle fait et quand elle est utilisée — fait partie de la référence rapide Java :
- String[] split(String del) retourne un tableau String où chaque élément est un sous-chaîne de this String, qui a été découpé autour des correspondances de l'expression donnée del.
- Instruction d'exclusion : Le paramètre del utilise un format appelé expression régulière. Écrire ou analyser du code utilisant l'une des propriétés spéciales des expressions régulières (par exemple, \\*, \\.) est hors du programme du cours et de l'examen AP Computer Science A.
4.6.A.9 Une boucle élargie while peut être utilisée pour détecter si le fichier contient encore des éléments à lire en utilisant la méthode hasNext comme condition de la boucle.
4.6.A.10 Un fichier doit être fermé lorsque le programme a fini de l'utiliser. La méthode close de Scanner est appelée pour fermer le fichier.

Source : Description du cours et de l'examen AP College Board

File et IOException vivent dans java.io, donc un programme qui lit un fichier a besoin de import java.io.*;. Ouvrir un fichier peut échouer (il pourrait ne pas exister), et Java vous oblige à gérer cela – la façon la plus simple est d'ajouter throws IOException à l'en-tête de la méthode. Un Scanner lit ensuite le fichier ligne par ligne, utilisant hasNext... pour tester avant de lire :

import java.io.*;
...
public static void readFile() throws IOException {
    Scanner f = new Scanner(new File("data.txt"));
    while (f.hasNextLine()) {
        String line = f.nextLine();
    }
}

Lire des jetons typés avec nextInt(), nextDouble(), ou nextBoolean() provoque une InputMismatchException si le prochain jeton est du mauvais type – par exemple appeler nextInt() lorsque la prochaine chose dans le fichier est le mot cat.

4.7

Envelopper un Nombre dans un Objet

Programme

Objectif d'apprentissage 4.7.A : Développer du code pour utiliser des objets Integer et Double à partir de leurs homologues primitifs et déterminer le résultat de l'utilisation de ces objets.

4.7.A.1 La classe Integer et la classe Double font partie du package java.lang. Un objet Integer est immuable, ce qui signifie qu'une fois un objet Integer créé, ses attributs ne peuvent pas être changés. Un objet Double est immuable, ce qui signifie qu'une fois un objet Double créé, ses attributs ne peuvent pas être changés.
4.7.A.2 L'autoboxing est la conversion automatique que le compilateur Java effectue entre les types primitifs et leurs classes enveloppes d'objet correspondantes. Cela inclut la conversion d'un int en un Integer et d'un double en un Double. Le compilateur Java applique l'autoboxing lorsqu'une valeur primitive est :
- passée comme paramètre à une méthode attendant un objet de la classe enveloppe correspondante
- affectée à une variable de la classe enveloppe correspondante
4.7.A.3 L'unboxing est la conversion automatique que le compilateur Java effectue de la classe enveloppe vers le type primitif. Cela inclut la conversion d'un Integer en un int et d'un Double en un double. Le compilateur Java applique l'unboxing lorsqu'un objet de classe enveloppe est :
- passé comme paramètre à une méthode attendant une valeur du type primitif correspondant
- affectée à une variable du type primitif correspondant
4.7.A.4 La méthode de classe Integer suivante — y compris ce qu'elle fait et quand elle est utilisée — fait partie de la référence rapide Java :
- static int parseInt(String s) retourne l'argument String sous forme de int.
4.7.A.5 La méthode de classe Double suivante — y compris ce qu'elle fait et quand elle est utilisée — fait partie de la référence rapide Java :
- static double parseDouble(String s) retourne l'argument String sous forme de double.

Source : Description du cours et de l'examen AP College Board

Un ArrayList stocke des objets, pas des primitifs, donc un primitif est enveloppé dans un objet : Integer enveloppe int, Double enveloppe double. Java fait cela avec l'autoboxing (int vers Integer) et le unboxing (inversement) automatiquement, donc vous pouvez écrire list.add(5) et int x = list.get(0).

Vocabulaire Entrainer

Anglais	Chinois	Pinyin
autoboxing/ˌɔːtəʊˈbɒksɪŋ/	自动装箱	zì dòng zhuāng xiāng

4.8

Boîte à Outils ArrayList

Programme

Objectif d'apprentissage 4.8.A : Développer du code pour des collections d'objets liés utilisant des objets ArrayList et déterminer le résultat de l'appel de méthodes sur ces objets.

4.8.A.1 Un objet ArrayList est mutable en taille et contient des références d'objets.
4.8.A.2 Le constructeur ArrayList ArrayList() construit une liste vide.
4.8.A.3 Java permet le type générique ArrayList<E>, où le paramètre de type E spécifie le type des éléments. Lorsque ArrayList<E> est spécifié, les types des paramètres de référence et du type de retour lors de l'utilisation des méthodes ArrayList sont le type E. ArrayList<E> est préféré à ArrayList. Par exemple, ArrayList<String> names = new ArrayList<String>(); permet au compilateur de trouver des erreurs qui seraient autrement trouvées à l'exécution.
4.8.A.4 La classe ArrayList fait partie du package java.util. Une instruction import doit être utilisée pour rendre cette classe disponible pour l'utilisation dans le programme.
4.8.A.5 Les méthodes ArrayList suivantes — y compris ce qu'elles font et quand elles sont utilisées — font partie de la référence rapide Java :
- int size() retourne le nombre d'éléments dans la liste.
- boolean add(E obj) ajoute obj à la fin de la liste ; retourne true.
- void add(int index, E obj) insère obj à la position index (0 <= index <= size), déplaçant les éléments aux positions index et supérieures vers la droite (ajoute 1 à leurs indices) et ajoute 1 à la taille.
- E get(int index) retourne l'élément à la position index dans la liste.
- E set(int index, E obj) remplace l'élément à la position index par obj ; retourne l'élément auparavant situé à la position index.
- E remove(int index) retire l'élément à la position index, déplaçant les éléments aux positions index + 1 et supérieures vers la gauche (soustrait 1 à leurs indices) et soustrait 1 à la taille ; retourne l'élément auparavant situé à la position index.
4.8.A.6 Les indices d'un ArrayList commencent à 0 et se terminent au nombre d'éléments - 1.

Source : Description du cours et de l'examen AP College Board

Qu'est-ce qu'un ArrayList est vraiment

Un ArrayList 动态数组 (tableau dynamique) grandit et se réduit lorsque vous ajoutez ou supprimez des éléments. Déclarez-le avec le type d'élément dans <> :

ArrayList<String> names = new ArrayList<String>();
names.add("Amy");           // append
names.add(0, "Bob");        // insert at index
names.get(0);               // read
names.set(1, "Cara");       // replace
names.remove(0);            // delete, shifts the rest left
names.size();               // count (a method, unlike array.length)

Vocabulaire Entrainer

Anglais	Chinois	Pinyin
ArrayList/əˈreɪ lɪst/	动态数组	dòng tài shù zǔ
2D array/ˌtuː ˈdiː əˈreɪ/	二维数组	èr wéi shù zǔ
row-major order/rəʊ ˈmeɪdʒə ˈɔːdə/	行主序	xíng zhǔ xù

4.9

Parcourir chaque élément d'un ArrayList

Programme

Objectif d'apprentissage 4.9.A : Développer du code servant à parcourir les éléments d'un ArrayList et déterminer les résultats de ces parcours.

4.9.A.1 Parcourir un ArrayList consiste à utiliser des instructions d'itération ou récursives pour accéder à tous ou à une séquence ordonnée des éléments dans un ArrayList.
4.9.A.2 Supprimer des éléments pendant un parcours d'un ArrayList nécessite l'utilisation de techniques spéciales pour éviter de sauter des éléments.
4.9.A.3 Tenter d'accéder à une valeur d'index hors de sa plage entraînera une IndexOutOfBoundsException.
4.9.A.4 Changer la taille d'un ArrayList tout en le parcourant avec une boucle élargie for peut entraîner une ConcurrentModificationException. Par conséquent, lorsqu'on utilise une boucle élargie for pour parcourir un ArrayList, vous ne devez pas ajouter ou supprimer d'éléments.

Source : Description du cours et de l'examen AP College Board

Parcourez avec une boucle à index ou une boucle for-each, comme pour les tableaux (utilisez size() et get(i)) :

for (int i = 0; i < list.size(); i++) { ... list.get(i) ... }
for (String s : list) { ... }

Compétence d'examen : lors de la suppression d'éléments dans une boucle à index, parcourrez soit à l'envers, soit ne n'incrémentez pas i après une suppression – sinon la suppression décale les éléments vers la gauche et vous sautez un élément. Et n'ajoutez ni ne supprimez jamais d'éléments pendant que vous parcourez un ArrayList avec une boucle for-each : modifier sa taille en cours de boucle provoque une ConcurrentModificationException, utilisez donc une boucle à index (à l'envers, comme ci-dessus) chaque fois que vous devez supprimer.

4.10

Algorithmes standards pour ArrayList

Programme

Objectif d'apprentissage 4.10.A : Écrire du code pour des algorithmes standards et originaux pour un contexte ou une spécification particulière impliquant des objets ArrayList et déterminer le résultat de ces algorithmes.

4.10.A.1 Il existe des algorithmes ArrayList standards qui utilisent des traversées pour :
- déterminer une valeur minimale ou maximale
- calculer une somme ou une moyenne
- déterminer si au moins un élément possède une propriété particulière
- déterminer si tous les éléments possèdent une propriété particulière
- déterminer le nombre d'éléments ayant une propriété particulière
- accéder à toutes les paires consécutives d'éléments
- déterminer la présence ou l'absence d'éléments dupliqués
- décaler ou faire pivoter des éléments vers la gauche ou la droite
- inverser l'ordre des éléments
- insérer des éléments
- supprimer des éléments
4.10.A.2 Certains algorithmes nécessitent la traversée simultanée de plusieurs String, tableaux bidimensionnels (array) ou objets ArrayList.

Source : Description du cours et de l'examen AP College Board

Les mêmes algorithmes que pour les tableaux – max/min, comptage, somme – plus l'insertion et la suppression que les tableaux ne peuvent pas faire facilement. Une tâche courante consiste à supprimer tous les éléments correspondant à une condition, en gérant soigneusement le décalage des indices.

4.11

Grilles : Tableaux bidimensionnels

Programme

Objectif d'apprentissage 4.11.A : Développer du code utilisé pour représenter des collections de données apparentées à l'aide d'objets tableaux bidimensionnels (2D).

4.11.A.1 Un tableau 2D est stocké sous forme de tableau de tableaux. Par conséquent, la façon dont les tableaux 2D sont créés et indexés est similaire à celle des objets tableaux unidimensionnels (1D). La taille d'un tableau 2D est établie au moment de sa création et ne peut pas être modifiée. Les tableaux 2D peuvent stocker soit des données primitives, soit des références d'objets.
- Énoncé d'exclusion : Les objets tableaux 2D non rectangulaires sont hors programme du cours et de l'examen AP Computer Science A.
4.11.A.2 Lorsqu'un tableau 2D est créé en utilisant le mot-clé new, tous ses éléments sont initialisés avec les valeurs par défaut pour le type de données des éléments. La valeur par défaut pour int est 0, pour double est 0.0, pour boolean est false, et pour un type de référence est null.
4.11.A.3 La liste d'initialisation utilisée pour créer et initialiser un tableau 2D consiste en des listes d'initialisation représentant des tableaux 1D ; par exemple, int[][] arr2D = { {1, 2, 3}, {4, 5, 6} };.
4.11.A.4 Les crochets [row][col] sont utilisés pour accéder et modifier un élément dans un tableau 2D. Aux fins de l'examen, lors de l'accès à l'élément à arr[first][second], le premier indice est utilisé pour les lignes, le second indice est utilisé pour les colonnes.
4.11.A.5 Un tableau unique qui constitue une ligne d'un tableau 2D peut être accédé en utilisant le nom du tableau 2D suivi d'une seule paire de crochets contenant l'indice de ligne.
4.11.A.6 Le nombre de lignes contenues dans un tableau 2D peut être accédé via l'attribut length. Les valeurs d'indice de ligne valides pour un tableau 2D s'étendent de 0 jusqu'à une unité inférieure au nombre de lignes ou à la longueur du tableau, inclus. Le nombre de colonnes contenues dans un tableau 2D peut être accédé via l'attribut length de l'une des lignes. Les valeurs d'indice de colonne valides pour un tableau 2D s'étendent de 0 jusqu'à une unité inférieure au nombre de colonnes ou à la longueur de toute ligne donnée du tableau, inclus. Par exemple, étant donné un tableau 2D nommé values, le nombre de lignes est values.length et le nombre de colonnes est values[0].length. L'utilisation d'une valeur d'indice en dehors de ces plages entraînera une ArrayIndexOutOfBoundsException.

Source : Description du cours et de l'examen AP College Board

Un tableau 2D 二维数组 est une grille (lignes et colonnes) – un tableau de tableaux :

Un tableau bidimensionnel (un tableau) avec des indices de ligne et de colonne

int[][] grid = new int[3][4];   // 3 rows, 4 columns
grid[r][c] = 7;                 // row r, column c
int rows = grid.length;         // 3
int cols = grid[0].length;      // 4

Explorer

Indexer un tableau 2D par ligne et colonne

Un tableau 2D est une grille adressée par [row][col]. Déplacez les indices et regardez quelle cellule ils sélectionnent — ligne d'abord, puis colonne, tous deux comptant à partir de 0.

4.12

Parcourir une grille

Programme

Objectif d'apprentissage 4.12.A : Développer du code utilisé pour parcourir les éléments d'un tableau 2D et déterminer le résultat de ces traversées.

4.12.A.1 Les instructions d'itération imbriquées sont utilisées pour parcourir et accéder à tous ou à une séquence ordonnée d'éléments dans un tableau 2D. Puisque les tableaux 2D sont stockés comme des tableaux de tableaux, la façon dont les tableaux 2D sont parcourus en utilisant des boucles for et des boucles améliorées for est similaire aux objets de tableau 1D. Les instructions d'itération imbriquées peuvent être écrites pour parcourir le tableau 2D en ordre ligne-major, colonne-major, ou un ordre défini de manière unique. L'ordre ligne-major fait référence à un ordre des éléments de tableau 2D où la traversal se fait à travers chaque ligne, tandis que la traversal colonne-major se fait vers le bas chaque colonne.
4.12.A.2 La boucle externe d'une boucle imbriquée for améliorée utilisée pour parcourir un tableau 2D parcourt les lignes. Par conséquent, la variable de boucle for améliorée doit être du type de chaque ligne, c'est-à-dire un tableau 1D. La boucle interne parcourt une ligne unique. Par conséquent, la variable de boucle for améliorée interne doit être du même type que les éléments stockés dans le tableau 1D. L'attribution d'une nouvelle valeur à la variable de boucle for améliorée ne modifie pas la valeur stockée dans le tableau.

Source : Description du cours et de l'examen AP College Board

Parcourir un tableau 2-D

Visitez chaque cellule avec des boucles imbriquées – l'extérieure sur les lignes, l'intérieure sur les colonnes (ordre row-major 行主序) :

for (int r = 0; r < grid.length; r++)
    for (int c = 0; c < grid[0].length; c++)
        System.out.print(grid[r][c]);

4.13

Algorithmes standards pour tableaux 2D

Programme

Objectif d'apprentissage 4.13.A : Développer du code pour des algorithmes standards et originaux dans un contexte ou une spécification particulière impliquant des tableaux 2D et déterminer le résultat de ces algorithmes.

4.13.A.1 Il existe des algorithmes standards qui utilisent des traversées de tableaux 2D pour :
- déterminer une valeur minimale ou maximale de tous les éléments ou pour une ligne, colonne ou autre sous-section désignée
- calculer une somme ou une moyenne de tous les éléments ou pour une ligne, colonne ou autre sous-section désignée
- déterminer si au moins un élément possède une propriété particulière dans tout le tableau 2D ou pour une ligne, colonne ou autre sous-section désignée
- déterminer si tous les éléments du tableau 2D ou d'une ligne, colonne ou autre sous-section désignée possèdent une propriété particulière
- déterminer le nombre d'éléments dans le tableau 2D ou dans une ligne, colonne ou autre sous-section désignée ayant une propriété particulière
- accéder à toutes les paires consécutives d'éléments
- déterminer la présence ou l'absence d'éléments dupliqués dans le tableau 2D ou dans une ligne, colonne ou autre sous-section désignée
- décaler ou faire pivoter des éléments dans une ligne vers la gauche ou la droite ou dans une colonne vers le haut ou le bas
- inverser l'ordre des éléments dans une ligne ou une colonne

Source : Description du cours et de l'examen AP College Board

Tâches typiques de grille : sommer une ligne ou une colonne, trouver le max dans la grille, compter les cellules correspondantes, ou sommer une diagonale (où r == c). Chacune est une traversal imbriquée avec un résultat accumulé.

4.14

Trouver une valeur : Recherche linéaire et binaire

Programme

Objectif d'apprentissage 4.14.A : Développer du code utilisé pour des algorithmes de recherche linéaire afin de rechercher des informations spécifiques dans une collection et déterminer les résultats de l'exécution d'une recherche.

4.14.A.1 Les algorithmes de recherche linéaire sont des algorithmes standards qui vérifient chaque élément dans l'ordre jusqu'à ce que la valeur souhaitée soit trouvée ou que tous les éléments du tableau ou de ArrayList aient été vérifiés. Les algorithmes de recherche linéaire peuvent commencer le processus de recherche depuis n'importe quelle extrémité du tableau ou de ArrayList.
4.14.A.2 Lors de l'application d'algorithmes de recherche linéaire aux tableaux 2D, chaque ligne doit être accédée puis la recherche linéaire appliquée à chaque ligne du tableau 2D.

Source : Description du cours et de l'examen AP College Board

Recherche binaire : diviser par deux et vaincre

Recherche linéaire 线性搜索 vérifie chaque élément à tour de rôle – fonctionne sur n'importe quelle liste, prenant jusqu'à $n$ étapes.
Recherche binaire 二分搜索 ne fonctionne que sur une liste triée : vérifiez le milieu, puis éliminez la moitié qui ne peut pas contenir la cible, en répétant. Elle prend environ $\log_2 n$ étapes – bien plus rapide sur de grandes données.

La recherche binaire divise la plage en deux à chaque étape

La recherche linéaire vérifie chaque élément à tour de rôle jusqu'à ce que la cible soit trouvée

int lo = 0, hi = a.length - 1;
while (lo <= hi) {
    int mid = (lo + hi) / 2;
    if (a[mid] == target) return mid;
    else if (a[mid] < target) lo = mid + 1;
    else hi = mid - 1;
}

Compétence d'examen : la recherche binaire nécessite des données triées ; sachez combien de comparaisons elle effectue et comment lo, hi, mid sont mis à jour.

Exemple résolu. Cherchez target = 40 dans le tableau trié {3, 9, 14, 23, 31, 42, 55} (indices 0–6). Commencez avec lo=0, hi=6 :

mid = (0+6)/2 = 3, a[3]=23 < 40, donc lo = 4;
mid = (4+6)/2 = 5, a[5]=42 > 40, donc hi = 4;
mid = (4+4)/2 = 4, a[4]=31 < 40, donc lo = 5;
maintenant lo (5) > hi (4), donc la boucle se termine – 40 est absent.

Chaque étape a divisé la plage en deux, donc même cet échec n'a pris que trois comparaisons.

Explorer

Comparer recherche linéaire et recherche binaire

La recherche linéaire vérifie chaque élément à tour de rôle ; la recherche binaire divise par deux une liste triée à chaque étape. Observez la recherche binaire atteindre la cible en bien moins de comparaisons.

Vocabulaire Entrainer

Anglais	Chinois	Pinyin
Linear search/ˈlɪnɪə sɜːtʃ/	线性搜索	xiàn xìng sōu suǒ
Binary search/ˈbaɪnəri sɜːtʃ/	二分搜索	èr fēn sōu suǒ
Selection sort/sɪˈlekʃn sɔːt/	选择排序	xuǎn zé pái xù

4.15

Mettre des données en ordre : Tri par sélection et par insertion

Programme

Objectif d'apprentissage 4.15.A : Déterminer le résultat de l'exécution de chaque étape des algorithmes de tri pour trier les éléments d'une collection.

4.15.A.1 Le tri par sélection et le tri par insertion sont des algorithmes de tri itératifs qui peuvent être utilisés pour trier des éléments dans un tableau ou un ArrayList.
4.15.A.2 Le tri par sélection sélectionne répétés le plus petit (ou le plus grand) élément de la partie non triée de la liste et l'échange contre sa position correcte (et finale) dans la partie triée de la liste.
4.15.A.3 Le tri par insertion insère un élément de la partie non triée d'une liste dans sa position correcte (mais pas nécessairement finale) dans la partie triée de la liste en décalant les éléments de la partie triée pour faire de la place au nouvel élément.

Source : Description du cours et de l'examen AP College Board

Tri par insertion

Tri à bulles, passe par passe

Tri par sélection 选择排序 trouve répétitivement le plus petit élément restant et l'échange pour le placer correctement.
Tri par insertion 插入排序 fait croître un front trié, insérant chaque nouvel élément à l'endroit où il appartient.

Un tri par insertion, déplaçant chaque clé à sa place itération après itération

Les deux sont simples et prennent environ $n^2$ étapes en moyenne – parfaits pour de petits tableaux. Soyez capable de tracer le tableau après chaque passe.

Explorer

Observer un algorithme de tri ordonner une liste

Un tri réorganise les éléments dans l'ordre. Parcourez le tri par sélection/insertion pour voir la zone triée grandir d'un élément à la fois.

Vocabulaire Entrainer

Anglais	Chinois	Pinyin
Insertion sort/ɪnˈsɜːʃn sɔːt/	插入排序	chā rù pái xù

4.16

Méthodes qui s'appellent elles-mêmes : Récursivité

Programme

Objectif d'apprentissage 4.16.A : Déterminer le résultat de l'appel de méthodes récursives.

4.16.A.1 Une méthode récursive est une méthode qui s'appelle elle-même. Les méthodes récursives contiennent au moins un cas de base, qui arrête la récursion, et au moins un appel récursif. La récursivité est une autre forme de répétition.
4.16.A.2 Chaque appel récursif possède son propre ensemble de variables locales, y compris les paramètres. Les valeurs des paramètres capturent les progrès d'un processus récursif, tout comme les valeurs des variables de contrôle de boucle capturent les progrès d'une boucle.
4.16.A.3 Toute solution récursive peut être reproduite par l'utilisation d'une approche itérative et vice versa.
- Énoncé d'exclusion : L'écriture de code récursif est hors programme du cours et de l'examen AP Computer Science A.

Source : Description du cours et de l'examen AP College Board

Récursivité & pile d'appels

La récursivité 递归 est une méthode qui s'appelle elle-même sur une entrée plus petite. Elle nécessite un cas de base 基本情况 qui arrête les appels, et un cas récursif qui approche du cas de base :

public static int factorial(int n) {
    if (n <= 1) return 1;          // base case
    return n * factorial(n - 1);   // recursive case
}

Sans cas de base atteignable, la récursivité ne s'arrête jamais (débordement de pile).

La récursivité et l'itération sont interchangeables. Toute solution récursive peut être réécrite avec une boucle (approche itérative), et toute boucle peut être réécrite avec la récursivité - ils résolvent les mêmes problèmes. La factorial ci-dessus a le même effet qu'une version itérative :

public static int factorial(int n) {
    int result = 1;
    for (int i = 2; i <= n; i++) result *= i;   // same answer, no self-call
    return result;
}

Ainsi le choix porte sur la clarté, pas sur la capacité : la récursivité se lit naturellement pour les problèmes ayant une structure auto-similaire (arbres, tri fusion), tandis que l'itération évite le coût mémoire d'une trame d'appel empilée à chaque étape. L'examen peut vous demander de convertir l'un en l'autre.

Explorer

Déplier un appel récursif

Une méthode récursive s'appelle elle-même sur une entrée plus petite jusqu'à ce qu'elle atteigne un cas de base, puis les résultats remontent. Parcourez pour voir les appels empiler et se dérouler.

Vocabulaire Entrainer

Anglais	Chinois	Pinyin
Recursion/rɪˈkɜːʃn/	递归	dì guī
base case/beɪs keɪs/	基本情况	jī běn qíng kuàng

4.17

Recherche récursive et tri fusion

Programme

Objectif d'apprentissage 4.17.A : Déterminer le résultat de l'exécution d'algorithmes récursifs utilisant des chaînes de caractères ou des collections.

4.17.A.1 La récursivité peut être utilisée pour parcourir des objets String, des tableaux et des objets ArrayList.

Objectif d'apprentissage 4.17.B : Déterminer le résultat de chaque itération d'un algorithme de recherche binaire utilisé pour rechercher des informations dans une collection.

4.17.B.1 Les données doivent être dans un ordre trié pour utiliser l'algorithme de recherche binaire. La recherche binaire commence au milieu d'un tableau trié ou d'un ArrayList et élimine la moitié du tableau ou de ArrayList à chaque appel récursif jusqu'à ce que la valeur souhaitée soit trouvée ou que tous les éléments aient été éliminés.
4.17.B.2 La recherche binaire est généralement plus efficace que la recherche linéaire.
- Énoncé d'exclusion : Les algorithmes de recherche autres que la recherche linéaire et binaire sont hors programme du cours et de l'examen AP Computer Science A.
4.17.B.3 L'algorithme de recherche binaire peut être écrit de manière itérative ou récursive.

Objectif d'apprentissage 4.17.C : Déterminer le résultat de chaque itération de l'algorithme de tri fusion (merge sort) lorsqu'il est utilisé pour trier une collection.

4.17.C.1 Le tri fusion est un algorithme de tri récursif qui peut être utilisé pour trier des éléments dans un tableau ou un ArrayList.
- Énoncé d'exclusion : Les algorithmes de tri autres que le tri par sélection, le tri par insertion et le tri fusion sont hors programme du cours et de l'examen AP Computer Science A.
4.17.C.2 Le tri fusion divise répétés un tableau en sous-tableaux plus petits jusqu'à ce que chaque sous-tableau ne contienne qu'un seul élément, puis fusionne récursivement les sous-tableaux triés ensemble dans l'ordre trié pour former le tableau final trié.

Source : Description du cours et de l'examen AP College Board

Tri par fusion : découpage, puis fusion

La récursivité alimente des algorithmes efficaces. La recherche binaire peut être écrite récursivement (chercher dans la bonne moitié). Le tri fusion 归并排序 divise le tableau en deux, trie chaque moitié récursivement, puis fusionne les deux moitiés triées – prenant environ $n\log_2 n$ étapes, beaucoup plus rapide que le tri par sélection ou insertion sur de grandes données.

Le tri fusion divise le tableau en éléments individuels, puis fusionne les moitiés triées vers le haut

Exemple résolu. Tracez factorial(4). Chaque appel renvoie à un plus petit : factorial(4) = 4 * factorial(3) = 4 * 3 * factorial(2) = 4 * 3 * 2 * factorial(1). factorial(1) atteint le cas de base et retourne 1, donc les appels se déroulent vers l'intérieur : 2 * 1 = 2, puis 3 * 2 = 6, puis 4 * 6 = 24. Écrire chaque appel au-dessus de sa valeur retournée est la manière fiable de tracer la récursivité.

Compétence d'examen : tracez une méthode récursive en écrivant chaque appel et sa valeur de retour, et sachez que l'efficacité du tri fusion ($n\log n$) bat les triers simples $n^2$.

Vocabulaire Entrainer

Anglais	Chinois	Pinyin
Merge sort/mɜːdʒ sɔːt/	归并排序	guī bìng pái xù

4.17

Conseils d'examen

Pesez les avantages et inconvénients de la collecte de données – cette unité est testée par une justification écrite courte, pas par du code.
Protégez les informations d'identification personnelle (PII) et expliquez les risques de confidentialité et de sécurité dans leur contexte.
Nommez des préjudices réels : fuites de données, surveillance et biais algorithmique dus à des données non représentatives.
Respectez la propriété intellectuelle et les licences lorsque vous réutilisez du code ou des données.
Donnez une réponse spécifique et argumentée – un « cela pourrait être mauvais » vague ne rapporte aucun point.

Leçons interactives sur ce sujet

Traversez-le étape par étape, avec des exercices à vérification instantanée.

Épreuves Passées

Plus de sujets dans AP Informatique A