Bavarian Abitur Informatics, increased requirement level - 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).

State whether addresses refer to bytes or words before calculating capacity.

Distinguish PC, instruction register, address register and data register.

For n-bit two’s complement the range is−2^(n−1) through 2^(n−1)−1.

Cache locality and pipeline hazards matter more than a clock-rate label alone.

Draw a scheduling timeline before averaging waits.

Distinguish a TLB miss from a nonresident page fault.

LRU is a stack algorithm; FIFO can exhibit Belady’s anomaly.

Protect the shared invariant and analyze actual wait dependencies.

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.

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.

Define states, actions, objective and goal test before choosing a search.

Breadth-first minimum-edge guarantees need equal edge costs.

A-star guarantees depend on heuristic and repeated-state handling assumptions.

Separate training, validation and final evaluation roles.

Precision and recall use different denominators; accuracy can conceal class imbalance.

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.