Programming, algorithms, relational data and computability
Programming and Software Development
This shared-core programming guide covers language constructs, object-oriented design, development processes, and testing. Practice reading and debugging code: predict output, identify a scope or logic error, and choose tests that expose faults. These are independent exercises rather than a claim about a particular examination’s question distribution.
Constructs and control flow
Variables have type, scope, and lifetime. Local variables exist inside a block or function; parameters receive arguments; global variables are visible more broadly and increase coupling. Value parameters copy the argument; reference parameters can modify the caller's object. Control flow uses sequence, selection, and iteration. Recursion needs a base case and progress toward it; each call adds a stack frame. Short-circuit evaluation means A AND B skips B when A is false; A OR B skips B when A is true.
OOP and process
Encapsulation hides internal state behind methods; inheritance extends a class; polymorphism lets one interface dispatch to different implementations. Overloading is same-name methods with different signatures; overriding replaces an inherited method. The SDLC includes requirements, design, implementation, testing, deployment, and maintenance. Unit tests isolate small units, integration tests combine them, system tests check the whole product, and acceptance tests check user needs. Regression tests confirm changes did not break existing behavior. Version control tracks changes and enables branching and merging.
Worked example
Trace function f(n): if n <= 1 return 1; otherwise return n * f(n-1). f(4) = 4 * f(3) = 4 * 3 * f(2) = 4 * 3 * 2 * f(1) = 24. The base case stops recursion; without it the calls continue until stack overflow. The function computes factorial, and its running time is O(n) calls with O(n) stack depth.
Traps that cost marks
Confusing assignment = with equality ==; integer division following the explicitly specified language’s rounding rule; assuming a loop runs one more or fewer time because of < versus <=; mutating a list while iterating over it; and thinking pass-by-value can swap caller variables in languages that copy primitives.
Computational Thinking and Problem Solving
This shared-core guide develops decomposition, pattern recognition, abstraction, algorithm design and tracing, and evaluation. Use pseudocode and search/sort scenarios to practice predicting output, identifying missing steps, and justifying complexity. The organization is editorial and does not reproduce another credential’s blueprint.
Computational thinking practices
Decomposition splits a large problem into smaller solvable parts. Pattern recognition identifies repeated structures or behaviors. Abstraction removes detail that does not affect the solution and names the essential model. Algorithm design expresses a finite, unambiguous sequence of steps. A flowchart uses an oval for start/end, a parallelogram for input/output, a rectangle for process, a diamond for decision, and arrows for control flow. Pseudocode should show sequence, selection (IF/CASE), and iteration (WHILE/FOR) without language-specific syntax.
Tracing and efficiency
A trace table records variable values after each step; it prevents guessing. Binary search requires sorted data and repeatedly halves the remaining interval, so it is O(log n); linear search is O(n). Comparison sorts such as merge sort are O(n log n) worst case, while bubble and insertion sort are O(n^2). Best, average, and worst cases differ: quicksort is O(n log n) average but O(n^2) worst.
Worked example
Search for 23 in [2, 5, 8, 12, 16, 23, 38, 56, 72, 91] using binary search and zero-based indices. low = 0, high = 9, mid = 4, value 16: 23 is larger, so low = 5. mid = 7, value 56: 23 is smaller, so high = 6. mid = 5, value 23: found after three comparisons. Checking whether the array is sorted comes first; without that precondition, binary search is invalid.
Traps that cost marks
Off-by-one errors at interval boundaries (mid = (low + high) // 2, then low = mid + 1 or high = mid - 1); applying binary search to unsorted data; confusing abstraction with decomposition; ignoring a loop's termination condition; and reporting average-case cost as worst-case.
Data, Databases, and Information Retrieval
What to know
Data questions move from raw facts to organized, queryable information. In the relational model, tables have rows (records) and columns (attributes); keys enforce identity and relationships. A primary key is unique and non-null; a foreign-key constraint references an eligible unique parent key and enforces referential integrity; permitted nulls depend on the declared constraints. Know candidate, composite, and surrogate keys. SQL essentials: SELECT, FROM, WHERE, JOIN, GROUP BY, HAVING, ORDER BY, and aggregate functions. Normalization reduces redundancy and update anomalies: 1 NF atomic values, 2 NF no partial dependency on part of a composite key, 3 NF no transitive dependency. Transactions follow ACID-atomicity, consistency, isolation, durability. Indexes speed reads but cost write time and space. Information retrieval adds inverted indexes, Boolean retrieval, ranking, precision, and recall.
Traps
WHERE filters rows before grouping; HAVING filters groups after aggregation. COUNT(*) counts rows, while COUNT(column) ignores NULLs. NULL comparisons use IS NULL, not = NULL. INNER JOIN drops unmatched rows; LEFT JOIN keeps all left-side rows. Precision is retrieved relevant items divided by retrieved items; recall is retrieved relevant divided by all relevant items. Do not assume more normalization is always better for read-heavy reporting.
Worked example
Students(id, name) and Enrollments(student_id, course). Query: SELECT s.name, COUNT(e.course) FROM Students s LEFT JOIN Enrollments e ON s.id = e.student_id GROUP BY s.id, s.name. A student with no enrollments appears with COUNT(e.course) = 0 because the left join preserves the row and the NULL course is not counted. Rule of thumb: choose the join first, then aggregate, then filter groups with HAVING.
Trace representations and queries separately
A bit pattern acquires meaning from its stated encoding. In unsigned binary, each position contributes a power of two, so 1011 represents eight plus two plus one, or eleven. Signed integers and floating-point values require an explicit representation convention; the same bits do not imply the same numeric value under every convention. Text also requires an encoding, and a byte count is not automatically a character count.
For a database query, construct a tiny example containing two people with the same name, a missing child row and a null field. Group by stable student identity as well as the displayed name, so distinct students are not accidentally merged. A left join preserves an unmatched parent, but a later WHERE condition on a child column can remove that row. Decide which relation and multiplicity are intended before choosing syntax. Test the result against the example rather than relying on the query’s appearance.
Model relationships and trace relational algebra
An entity model describes relevant objects, attributes and relationship cardinalities before physical implementation. A many-to-many relationship usually requires a linking relation with foreign keys to the participating entities; a one-to-many design places the reference on the many side under the chosen representation. State optional participation separately from maximum cardinality. A key constraint must follow the business requirements, not a convenient name.
In classical relational algebra, selection chooses rows satisfying a predicate, while projection retains named attributes and eliminates duplicate tuples under set semantics. SQL SELECT usually retains duplicates unless DISTINCT is requested, so do not silently substitute bag behavior for set behavior. A Cartesian product pairs every tuple of its operands. A join retains pairs satisfying its condition; a natural join additionally matches identically named attributes, which can be surprising after a schema change. For the relation Enroll(student, course), division by a relation of required courses expresses students related to every required course. Do not project away course before division, because the necessary pairing information would already be lost. Check the schemas of both operands, then trace a tiny relation that includes a missing enrollment.
Automata, formal languages and computability
Der Bereich Theoretische Informatik prüft, wie man Sprachen formal beschreibt und welche Maschinen sie erkennen. Erwartet werden das Entwerfen und Minimieren endlicher Automaten, die Umwandlung zwischen regulären Ausdrücken, Grammatiken und Automaten, die Einordnung in die Chomsky-Hierarchie sowie Grundbegriffe der Berechenbarkeit wie Entscheidbarkeit und Halteproblem.
Endliche Automaten
- Ein deterministischer endlicher Automat (DEA) besteht aus Zustandsmenge, Eingabealphabet, Übergangsfunktion, Startzustand und Menge der Endzustände.
- In der hier verwendeten totalen DEA-Definition gibt es für jedes Zustands-Zeichen-Paar genau einen Übergang. Bei einer partiellen Konvention bedeuten fehlende Übergänge Verwerfen; ein zusätzlicher Fehlerzustand liefert einen äquivalenten totalen Automaten.
- Ein NEA darf mehrere Übergänge oder Epsilon-Übergänge haben; jede NEA-Sprache ist auch DEA-erkennbar (Potenzmengenkonstruktion).
- Reguläre Sprachen sind genau die DEA-erkennbaren Sprachen, beschreibbar durch reguläre Ausdrücke und Typ-3-Grammatiken.
Höhere Stufen
- Kontextfreie Sprachen (Typ 2) werden von Kellerautomaten erkannt, etwa a^n b^n; kontextsensitive Sprachen(Typ 1) werden durch linear beschränkte Automaten erkannt. Allgemeine Typ 0-Sprachen sind Turing-erkennbar; ein Erkenner muss bei Wörtern außerhalb der Sprache nicht immer halten.
- Das Pumping-Lemma für reguläre Sprachen ist eine notwendige Bedingung: Zum Nachweis der Nichtregularität muss für jede mögliche Pumping-Länge ein geeignetes Wort gewählt und für jede zulässige Zerlegung ein Pumpfaktor mit einem Wort außerhalb der Sprache gezeigt werden. Eine nicht gefundene Zerlegung ist für sich kein Beweis.
- Entscheidbar heißt: Es gibt ein Verfahren, das für jede Eingabe in endlicher Zeit ja oder nein liefert. Das Halteproblem ist unentscheidbar.
Durchgerechnetes Beispiel
Gesucht ist ein DEA über {a, b} für alle Wörter mit gerader Anzahl von a. Zustand z 0 steht für „gerade Anzahl“ und ist Start- und Endzustand, z 1 für „ungerade“. Übergänge: δ(z 0,a)=z 1, δ(z 0,b)=z 0, δ(z 1,a)=z 0, δ(z 1,b)=z 1. Probe mit „aba“: z 0 →a z 1 →b z 1 →a z 0, Endzustand erreicht, also akzeptiert; das Wort enthält zwei a. Probe mit „ab“: z 0 →a z 1 →b z 1, nicht akzeptiert, da ein a. Der Automat ist total, weil für beide Zeichen in beiden Zuständen ein Übergang definiert ist.
Typische Punktverluste
- Die verwendete Automatenkonvention nicht nennen: totale DEA benötigen alle Übergänge, partielle DEA können fehlende Übergänge als Verwerfen behandeln.
- Startzustand und Endzustand verwechselt oder den Startzustand nicht als akzeptierend markiert, wenn das leere Wort zur Sprache gehört.
- Das Pumping-Lemma als hinreichendes Kriterium missverstanden.
- Reguläre Grammatik mit kontextfreier Grammatik verwechselt: Bei der hier betrachteten rechtslinearen Form sind etwa A → aB und A → a erlaubt; passende Epsilonregeln und Konventionsdetails müssen ausdrücklich berücksichtigt werden.