France Terminale Computer Science (specialty)

Chapters: 6

1. History of computing

Key events

History of Computing: From Gears to the Web – Computing grew from tools for counting to machines that follow programs. Pascal built a gear calculator in 1642. Babbage designed a programmable engine and Ada Lovelace wrote the first program idea in 1843. In 1936 Alan Turing described a universal machine. The first large electronic computers, such as ENIAC (1945), filled rooms; programming languages (Fortran 1957, C 1972) made them easier to use. Chips made computers small: personal computers arrived in the late 1970s and 1980s. ARPANET (1969) grew into the Internet, and the World Wide Web opened in 1991. Codd's relational model (1970) gave databases a firm base. Open-source software, such as Linux (1991), let people share code. Many scientists shaped this story.

Lists, stacks, queues, dictionaries · Trees, BSTs, graphs · Object-oriented programming

Data Structures: Arrays, Lists, Stacks, Queues and Trees – A data structure is a way of organising data in memory so a program can use it well. Arrays keep items in numbered boxes for instant access by index. Linked lists chain nodes with pointers, so inserting is easy. Stacks work last-in-first-out, queues first-in-first-out. Dictionaries find values by key, and trees store data in levels so searching is fast. Choosing the right structure makes programs faster and simpler.
Graph Theory: Dots, Lines and Networks – A graph is a set of vertices (dots) joined by edges (lines). The degree of a vertex is how many edges touch it, and the sum of all degrees is twice the number of edges. An Euler trail uses every edge once and exists only when 0 or 2 vertices have odd degree. A tree is a connected graph with no cycles and n − 1 edges. Weighted graphs model roads and networks; Kruskal’s and Prim’s algorithms find a minimum spanning tree.
Object-Oriented Programming (OOP) – Object-oriented programming builds a program out of objects. A class is a blueprint that lists the data (attributes) and actions (methods) its objects will have. Each object is made from a class and keeps its own data. The four big ideas are encapsulation (hide data behind methods), inheritance (a new class reuses an old one), polymorphism (the same method call behaves in the right way for each object) and abstraction (show only what is needed).

Relational model, SQL, DBMS

Relational Databases: Tables, Rows, Columns and Keys – Keeping data in many separate files leads to repeated data, mismatched copies and hard searching, so we use a database managed by a DBMS. In the relational model data sits in tables called relations. A column is an attribute, a row is a tuple, and the set of allowed values for a column is its domain. The number of columns is the degree; the number of rows is the cardinality. A candidate key is any column (or set) that can identify every row uniquely; the one chosen is the primary key and the others are alternate keys. A foreign key is a column in one table that refers to the primary key of another table, linking them.

SoC, processes, routing, secure communication

Operating System – An operating system (OS) is the main system software that sits between the user and the hardware and manages all resources. Its functions: process management (sharing the CPU between programs), memory management (giving and taking back RAM), file management, device management (through drivers) and security (passwords, permissions). Users talk to the OS through a user interface: command line (CLI), graphical (GUI), touch, voice or gesture. Examples: Windows, Linux, macOS, Android, iOS.

Recursion, modularity, paradigms, computability

Recursion: Functions That Call Themselves – Recursion is when a function solves a problem by calling itself on a smaller version of the same problem. Every recursive function needs a base case, where it stops and returns an answer directly, and a recursive case that moves closer to the base case. Each call gets its own stack frame on the call stack; frames are removed as calls return.

Tree/graph algorithms, divide and conquer, dynamic programming, text search

Introduction to Problem Solving – Problem solving on a computer has stages: analyse the problem (inputs, outputs, rules), develop an algorithm (a finite, clear, ordered set of steps), code it in a programming language, test it with different inputs, and debug (find and remove errors). An algorithm can be shown as a flowchart (oval = start/stop, parallelogram = input/output, rectangle = process, diamond = decision, arrows = flow) or as pseudocode (structured plain English). Decomposition breaks a big problem into smaller sub-problems that are solved separately and then joined.