Germany Jahrgangsstufe 11 Computer Science

Chapters: 5

1. Graphs

Graphs and graph algorithms

Graph Algorithms – A graph is a set of vertices joined by edges, which can carry weights. Breadth-first search (BFS) explores in layers using a queue and finds the fewest-edge path. Depth-first search (DFS) goes deep using a stack or recursion and backtracks. Trees can be traversed pre-order, in-order and post-order. Dijkstra's algorithm finds shortest paths from one vertex when weights are non-negative. Kruskal's and Prim's algorithms build a minimum spanning tree. Route inspection finds the shortest closed route using every edge; the travelling salesperson problem asks for the shortest tour of every vertex. In a flow network, the maximum flow equals the capacity of the minimum cut.

Encoding and encryption

Cybersecurity: Threats and How We Stop Them – Cybersecurity protects computers, networks and data. It aims for confidentiality, integrity and availability (the CIA triad). Common threats are malware, phishing and social engineering, brute-force password attacks and denial of service. Defences include strong authentication, encryption, firewalls, anti-malware software, updates, access control and backups.

How networks and the Internet communicate

Network Types, Topologies and Protocols: Size, Shape and Rules – Networks are grouped by size: PAN (a few metres around one person), LAN (a room, building or campus), MAN (a city) and WAN (a country or the world). A topology is the layout of how nodes are wired: bus (all on one backbone cable), star (all to a central hub or switch) and tree (stars joined in levels). A protocol is a set of rules: TCP/IP breaks and routes data on the Internet, HTTP and HTTPS carry web pages, FTP moves files, SMTP sends email, POP3 downloads email, PPP links two devices directly, TELNET logs into a remote computer, and VoIP carries voice calls over the Internet.

Artificial intelligence and machine learning

Machine Learning – Machine learning (ML) is a way for computers to learn a rule from examples instead of being told the rule. We give data made of features (inputs) and, in supervised learning, labels (answers). The machine fits a model: regression predicts a number, a decision tree asks yes/no questions to pick a class, and k-means clustering groups unlabelled data. We train on most of the data, test on data it never saw, and measure accuracy or error. A model that only memorises (overfits) fails on new data.

Computer science extension projects

Coming soon