Форум DL

Мой профиль

Требования Syllabus к знаниям

Included, unlimited
Included, to be clarified
Included, not for task description

4 Mathematics

4.1 Arithmetics and Geometry

~ Integers, operations (incl. exponentiation), comparison
~ Basic properties of integers (sign, parity, divisibility)
~ Basic modular arithmetic: addition, subtraction,multiplication
~ Prime numbers
~ Fractions, percentages
~ Line, line segment, angle, triangle, rectangle, square, circle
~ Point, vector, coordinates in the plane
~ Polygon (vertex, side/edge, simple, convex, inside, area)
~ Euclidean distances
~ Pythagorean theorem

4.2 Discrete Structures (DS)

DS1. Functions, relations, and sets
- Functions (surjections, injections, inverses, composition)
- Relations (reexivity, symmetry, transitivity, equivalence relations, total/linear order relations, lexicographic order)
- Sets (inclusion/exclusion, complements, Cartesian products, power sets)

DS2. Basic logic
~ First-order logic
~ Logical connectives (incl. their basic properties)
~ Truth tables
~ Universal and existential quantiffication
~ Modus ponens and modus tollens

DS3. Proof techniques
- Notions of implication, converse, inverse, contrapositive, negation, and contradiction
- Direct proofs, proofs by: counterexample, contraposition, contra-diction
- Mathematical induction
- Strong induction (also known as complete induction)
~ Recursive mathematical definitions (incl. mutually recursive definitions)

DS4. Basics of counting
~ Counting arguments (sum and product rule, arithmetic and geometric progressions, Fibonacci numbers)
- Permutations and combinations (basic denitions)
- Factorial function, binomial coefficients
- Inclusion-exclusion principle
- Pigeonhole principle
- Pascal's identity, Binomial theorem

DS5. Graphs and trees
- Trees and their basic properties, rooted trees
- Undirected graphs (degree, path, cycle, connectedness, Euler/Hamilton path/cycle, handshaking lemma)
- Directed graphs (in-degree, out-degree, directed path/cycle, Euler/Hamilton path/cycle)
- Spanning trees
- Traversal strategies
- `Decorated' graphs with edge/node labels, weights, colors
- Multigraphs, graphs with self-loops
- Bipartite graphs
- Planar graphs

5 Computing Science

5.1 Programming Fundamentals (PF)

PF1. Fundamental programming constructs (for abstract machines)

~ Basic syntax and semantics of a higher-level language (at leastone of the specific languages available at an IOI, as announced in the Competition Rules for that IOI)
~ Variables, types, expressions, and assignment
~ Simple I/O
~ Conditional and iterative control structures
~ Functions and parameter passing
~ Structured decomposition

PF2. Algorithms and problem-solving

- Problem-solving strategies (understand{plan{do{check, separation of concerns, generalization, specialization, case distinction, working backwards, etc.)
- The role of algorithms in the problem-solving process
- Implementation strategies for algorithms (also see x6 SE1)
- Debugging strategies (also see x6 SE3)
- The concept and properties of algorithms (correctness, efficiency)

PF3. Fundamental data structures

~ Primitive types (boolean, signed/unsigned integer, character)
~ Arrays (incl. multicolumn dimensional arrays)
~ Strings and string processing
~ Static and stack allocation (elementary automatic memory management)
~ Linked structures
~ Implementation strategies for graphs and trees
~ Strategies for choosing the right data structure
~ Elementary use of real numbers in numerically stable tasks
~ The floating-point representation of real numbers, the existence of precision issues.
~ Pointers and references

PF4. Recursion

~ The concept of recursion
~ Recursive mathematical functions
~ Simple recursive procedures (incl. mutual recursion)
~ Divide-and-conquer strategies
~ Implementation of recursion
~ Recursive backtracking

5.2 Algorithms and Complexity (AL)

AL1. Basic algorithmic analysis

- Algorithm specification, precondition, postcondition, correctness,invariants
- Asymptotic analysis of upper complexity bounds (informally if possible)
- Big O notation
- Standard complexity classes (constant, logarithmic, linear, O(n log n ), quadratic, cubic, exponential)
- Time and space tradeoffs in algorithms
- Empirical performance measurements.

AL2. Algorithmic strategies

- Simple loop design strategies
- Brute-force algorithms (exhaustive search)
- Greedy algorithms
- Divide-and-conquer
- Backtracking (recursive and non-recursive), Branch-and-bound
- Dynamic programming

AL3a. Algorithms

- Simple algorithms involving integers: radix conversion, Euclid's algorithm, primality test by O(pn) trial division, Sieve of Eratosthenes, factorization (by trial division or a sieve), efficient exponentiation
- Simple operations on arbitrary precision integers (addition, subtraction, simple multiplication)
- Simple array manipulation (filling, shifting, rotating, reversal, re-sizing, minimum/maximum, prefix sums, histogram, bucket sort)
- sequential processing/search and binary search
- Quicksort and Quickselect to find the k-th smallest element.
- O(n log n ) worst-case sorting algorithms (heap sort, merge sort)
- Traversals of ordered trees (pre-, in-, and post-order)
- Depth- and breadth-first traversals
- Applications of the depth-first traversal tree, such as:
... Topological sort
... Algorithms to determine the (existence of an) Euler path/cycle
- Finding connected components and transitive closures.
- Shortest-path algorithms (Dijkstra, Bellman-Ford, Floyd-Warshall)
- Minimum spanning tree (Jarnik-Prim and Kruskal algorithms)
- O (V E ) time algorithm for computing maximum bipartite matching.

AL3b. Data structures

- Stacks and queues
- Representations of graphs (adjacency lists, adjacency matrix)
- Binary heap data structures
- Representation of disjoint sets: the Union-Find data structure.
- Statically balanced binary search trees. Instances of this include
binary index trees (also known as Fenwick trees) and segment
trees (also known as interval trees and tournament trees).
- Balanced binary search trees
- Augmented binary search trees
- O (log n ) time algorithms for answering lowest common ancestor
queries in a static rooted tree.
- Creating persistent data structures by path copying or using fat nodes.
- Composition of data structures, e.g. 2-D statically balanced binary trees

Excluded, but considering inclusion
- String algorithms: there is evidence that the inter-reducibility between KMP, Rabin-Karp hashing, suffix arrays/tree, suffix automaton, and Aho-Corasick makes them difficult to separate.
- Heavy-light decomposition and separator structures for static trees.
- Data structures for dynamically changing trees and their use in graph algorithms.

AL7. Automata and grammars

- Understanding a simple grammar in Backus-Naur form

AL8. Advanced algorithmic analysis

- Basics of combinatorial game theory, winning and losing positions, minimax algorithm for optimal game playing
- Amortized analysis

AL10. Geometric algorithms

- Representing points, vectors, lines,line segments.
- Checking for colinear points, parallel/orthogonal vectors, clock-wise turns.
- Intersection of two lines.
- Computing area of a polygon.
- Checking whether a (general/convex) polygon contains a point.
- Coordinate compression.
- O(n log n ) time algorithms for convex hull
- Sweeping line method