North Rhine-Westphalia Abitur Computer Science - independent foundations cheat sheet

Recursion needs a base case and progress toward that base case.

Overloading uses different signatures; overriding replaces an inherited method.

Unit tests isolate units; integration tests combine them.

Short-circuit evaluation can skip the right operand.

Pass-by-value copies arguments; pass-by-reference can mutate the caller's object.

Decomposition breaks problems down; abstraction removes irrelevant detail.

Binary search requires sorted data and is O(log n).

Merge sort is O(n log n) worst case; bubble sort is O(n^2).

Trace tables prevent guessing about loop output.

Update search bounds to mid + 1 or mid - 1, not mid.

n-bit two's complement range is −2^(n−1) to 2^(n−1) − 1; negation is invert then add 1.

Normalised two's complement mantissa has differing top two bits: 01… for positive, 10… for negative.

Longer mantissa = more precision; longer exponent = more range.

Bitmap size = width × height × colour depth ÷ 8; sound size = rate × resolution × channels × seconds ÷ 8.

Stacks are LIFO, queues FIFO; hash tables give near-constant lookup; linked lists give O(1) insertion once positioned.

Lossless compression preserves all data (RLE, Huffman); lossy discards detail permanently (JPEG, MP3).

Ein totaler DEA hat genau einen Übergang pro Zustand und Zeichen; partielle Konventionen können durch einen Fehlerzustand vervollständigt werden.

Reguläre Sprachen = DEA-erkennbar = durch reguläre Ausdrücke beschreibbar = Typ-3-Grammatik.

Kellerautomaten erkennen genau die kontextfreien Sprachen, etwa a^n b^n.

Das Pumping-Lemma ist notwendig, aber nicht hinreichend für Regularität.

Entscheidbar bedeutet terminierende Ja/Nein-Antwort für jede Eingabe; das Halteproblem ist unentscheidbar.

Die Potenzmengenkonstruktion wandelt jeden NEA in einen äquivalenten DEA um.

Fetch-decode-execute uses the PC, IR, ALU, and registers.

Memory hierarchy: registers, cache, RAM, storage, offline.

RAM is volatile; SSDs retain data without power.

A process has its own address space; threads share one.

Authentication verifies identity; authorization grants permissions.

TCP is reliable and connection-oriented; UDP is connectionless and lower overhead.

IP addresses route between networks; MAC addresses work on the local link.

A /26 subnet has 64 addresses and 62 usable hosts.

DNS resolves names; DHCP assigns addresses.

Security protects data; privacy governs collection and use.

Identification, authentication, authorisation and accounting are four distinct steps.

MFA needs two different factor categories, not two instances of one.

RBAC suits stable job roles; ABAC suits context-dependent, fine-grained rules.

Kerberos uses a KDC with TGT and service tickets for SSO.

Symmetric ciphers handle bulk data; asymmetric ciphers solve key distribution and signatures.

Signing uses a specified signature scheme with the signer’s private key; verification and custody are essential to origin evidence.

ECB leaks patterns; use authenticated modes such as GCM or encrypt-then-MAC.