NSI Terminale — Full Programme Overview

NSI (Numérique et Sciences Informatiques) is the French Bac computer-science speciality. The Terminale exam includes a written paper (3h30, coefficient 16) and a practical exam (1h) of Python programming. The syllabus covers five areas: data structures, databases, hardware and networking, programming, and algorithms.

1. Data Structures

Linked lists: each node stores a value and a pointer to the next. Insertion at head is O(1), but access by index is O(n), unlike arrays.

Stacks (LIFO): Last In First Out. Operations: push, pop, top, is_empty. Used for recursion call stacks, undo functionality, and expression evaluation.

Queues (FIFO): First In First Out. Operations: enqueue, dequeue, is_empty. Used for BFS, print queues, and process scheduling.

Binary trees: hierarchical structures where each node has at most two children (left, right). Key metrics: height, size. Three recursive traversals:

• Pre-order (Root-Left-Right)
• In-order (Left-Root-Right) — gives sorted order in a BST
• Post-order (Left-Right-Root)

Binary search trees (BST): for every node, all left-subtree values are smaller and all right-subtree values are larger. Search and insertion are O(log n) when balanced, O(n) in the worst case (degenerate tree).

Graphs: sets of vertices and edges (directed or undirected, weighted or unweighted). Represented as adjacency matrices (O(1) edge lookup, O(n²) memory) or adjacency lists (memory-efficient for sparse graphs).

2. Databases

The relational model (Codd, 1970) organises data into tables. Each table has a schema with typed attributes. A primary key uniquely identifies each record; a foreign key references a primary key in another table, ensuring referential integrity.

SQL essentials:

• SELECT ... FROM ... WHERE ... ORDER BY for queries
• JOIN ... ON for combining tables
• GROUP BY with aggregate functions (COUNT, SUM, AVG)
• INSERT INTO, UPDATE ... SET, DELETE FROM for data manipulation

Normalisation (1NF, 2NF, 3NF) reduces redundancy and ensures consistency.

3. Hardware, OS, and Networking

Von Neumann architecture: CPU (ALU + control unit + registers), RAM, and bus. Memory hierarchy: registers > cache > RAM > secondary storage.

Operating systems manage processes. A process has states (ready, running, waiting, terminated). Scheduling algorithms: Round Robin, priority, FCFS. Deadlock occurs when processes block each other.

TCP/IP model (4 layers): network access, Internet (IP), transport (TCP/UDP), application (HTTP/HTTPS, DNS). Routing uses protocols like RIP (hop count) and OSPF (link cost, Dijkstra).

4. Programming

Recursion: a function that calls itself. Requires a base case and recursive calls converging toward it. Each call adds a frame to the call stack (Python limit: 1000). Memoisation optimises repeated subproblems.

Object-oriented programming (OOP): organises code into classes with attributes (data) and methods (behaviour). Key concepts: encapsulation (bundling data and methods, protecting access), inheritance (a child class inherits from a parent and can specialise). In Python, super().__init__() calls the parent constructor.

Modularity: splitting code into independent, reusable modules (.py files). Import with import or from ... import ....

5. Algorithms

Sorting algorithms:

• Insertion sort: O(n²) average/worst, O(n) best. In-place, stable.
• Merge sort: O(n log n) always. Stable, not in-place (extra memory).
• Quicksort: O(n log n) average, O(n²) worst. In-place, not stable.

Binary search: works on a sorted array. Compare the target with the middle element and halve the search space. O(log n).

Graph traversals:

• BFS (Breadth-First Search): explores by distance levels using a queue. Finds shortest path in unweighted graphs.
• DFS (Depth-First Search): explores as deep as possible using a stack or recursion. Detects cycles, topological sort.

Dijkstra’s algorithm: finds the shortest path from a source in a weighted graph with positive weights. Uses a priority queue. Initialise all distances to infinity except the source (0), repeatedly select the nearest unvisited vertex, and relax its neighbours.

Complexity (Big-O notation): O(1) constant, O(log n) logarithmic, O(n) linear, O(n log n) quasi-linear, O(n²) quadratic, O(2ⁿ) exponential.