Agrégation informatique externe 2025, épreuve 1Sujet et rapport du jury

AGREGATION CONCOURS EXTERNE

INFORMATION AUX CANDIDATS

Ces codes doivent être reportés sur chacune des copies que vous remettrez.

Gestion de fichiers dans un éditeur de texte

Préliminaires

Partie I. Lecture d'un fichier

#include <fcntl.h>
#include <unistd.h>
#include <stdio.h>
int editer_document(void* contenu) {
    /* Code non détaillé */
}
int charger_document(int fd) {
    /* Code non détaillé */
}
int main (int argc, char *argv[]) {
    int fd = open(argv[0], O_RDONLY);
    char* contenu;
    if (charger_document(fd, &contenu) != EXIT_FAILURE) {
        editer_document(contenu);
    }
    close(fd);

    return 0;
}

Partie II. Manipulation du contenu

Partie III. Gestion des modifications

A OPEN

A. 1 NOM

A. 2 SYNOPSIS

#include <sys/types.h>
#include <sys/stat.h>
#include <fcntl.h>
int open(const char *pathname, int flags);

A. 3 DESCRIPTION

A. 4 VALEUR RENVOYÉE

B FSTAT

B. 1 NOM

fstat - Obtenir l'état d'un fichier (file status)

B. 2 SYNOPSIS

#include <sys/types.h>
#include <sys/stat.h>
#include <unistd.h>
int fstat(int fd, struct stat* buf);

B. 3 DESCRIPTION

struct stat {
    dev_t st_dev; /* ID du périphérique contenant le fichier */
    ino_t st_ino; /* Numéro inæud */
    mode_t st_mode; /* Protection */
    nlink_t st_nlink; /* Nb liens matériels */
    uid_t st_uid; /* UID propriétaire */

    gid_t st_gid; /* GID propriétaire */
    dev_t st_rdev; /* ID périphérique (si fichier spécial) */
    off_t st_size; /* Taille totale en octets */
    blksize_t st_blksize; /* Taille de bloc pour E/S */
    blkcnt_t st_blocks; /* Nombre de blocs alloués */
};

B. 4 VALEUR RENVOYÉE

C MMAP

C. 1 NOM

C. 2 SYNOPSIS

#include <sys/mman.h>
void *mmap(void *addr, size_t length, int prot, int flags, int fd, off_t offset);
int munmap(void *addr, size_t length);

C. 3 DESCRIPTION

C.3.1 munmap()

C. 4 VALEUR RENVOYÉE

Structure de corde

Figure 1: Une corde représentant la chaîne de caractères "Je passe un concours de recrutement d'enseignants."

type rope =
    | Leaf of int * string
    | Concat of int * int * rope * rope

Concat (51, 3,
    Concat (21, 2,
        Concat (6, 1, Leaf (3, "Je "), Leaf (3, "pas")),
        Concat (15, 1, Leaf (4, "se u"), Leaf (11, "n concours "))
        ),
    Concat (29, 2,
        Leaf (10, "de recrute"),
        Concat (19, 1, Leaf (5, "ment "),
            Leaf (14, "d’enseignants.")))
    )

• -la concaténation, à gauche ou à droite, de la corde vide avec une corde r vaudra r;
• -la concaténation de deux feuilles sera remplacée par une unique feuille si la longueur de la chaîne obtenue ne dépasse pas max_string_length;
• -par extension, la concaténation d'une feuille et d'un nœud Concat dont l'un des sousarbres est une feuille sera simplifiée si la concaténation se fait du côté de cette feuille et si la longueur maximale des feuilles n'est pas dépassée.

type 'a undo_redo = 'a list ref * 'a list ref

• -la pile undo est constituée des versions antérieures à la version courante, de la plus récente à la plus ancienne dans l'ordre de dépilement;
• -la pile redo est constituée des versions ultérieures à la version courante, de la plus récente à la plus ancienne dans l'ordre de dépilement.

(ref [], ref [Leaf (0, "")])

Recherche de motif

• -[0, 2, 8] pour X=aba et T=abababbaabaa
• -[] pour X=abc et T=abababbaabaa

• -Comme c'est l'objectif de cette partie, vous n'êtes pas autorisé à utiliser l'un des différents tests de présence d'une sous-chaîne fourni par le langage Python, comme "ab" in "bababa", "bababa".find("ab"), …. On pourra cependant se servir de in pour tester si un élément est dans une liste, un dictionnaire, ou un ensemble. On pourra également utiliser in pour parcourir une structure itérable: for i in range(10), for 1 in "abababb", for x in [1,4,3,7] sont autorisés.
• -Sauf si c'est explicitement précisé différemment dans l'énoncé, toutes les complexités sont des complexités en temps et dans le pire cas.

• -Quand on vous demande d'écrire une fonction Python avec des contraintes de complexité en temps ou en espace additionnel, on ne vous demande pas de justifier que votre fonction a les bonnes complexités.
• -On considère que les arguments passés à une fonction vérifient toujours les pré-conditions de l'énoncé, il n'est pas nécessaire de les tester.

def fenetre(X, T):
    solution = []
    for i in range(len(T)-len(X)+1):
        if occurrence_position(X, T, i):
            solution.append(i)
    return solution

• -la fonction fenetre ;
• -la fonction fenetre_saut qui utilise difference_position_debut(X, T, i);
• -la fonction fenetre_saut qui utilise difference_position_fin(X, T, i).

• -si u = ε est le mot vide, alors Q_ε = {0} et on a δ_ε(0, a) = 0 pour tout a ∈ Σ;
• -sinon, on écrit u = vα, où v ∈ Σ^∗ est un mot et α ∈ Σ est une lettre, on note p = δ_v(|v|, α) et on définit pour tout état q ∈ Q_u et toute lettre σ ∈ Σ :
  δ_u(q, σ) = {|u|, si q = |u| − 1 et σ = α,; |u|, si q = |u| et (p, σ) = (|u| − 1, α); δ_v(p, σ), si q = |u| et (p, σ) ≠ (|u| − 1, α); δ_v(q, σ), sinon.

Question 3.10. En utilisant l'automate A_u sur un alphabet bien choisi, écrire une fonction Python appelée recherche_automate(X, T) qui résout le problème Recherche en temps O(n + m).