Форум 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

Мой профиль

From: Michal Forisek
Sent: Saturday, March 16, 2024 2:46 AM
To: ioi-announce@lists.ioinformatics.org
Subject: [IOI-announce] IOI Syllabus for 2025

Hello, friends!

One of the outcomes of the IOI 2024 Winter Meeting is that your ISC has made another revision of the IOI Syllabus. This update *does not* apply to IOI 2024 -- the updated Syllabus will only become official at its end.

The only real change is that the simplest implementation of maxflow / mincut is now included, to go along with the already included and very similar basic algorithm for maximum bipartite matching.

In addition to the change, there has been a bunch of clarifications:
some more precise specifications, some additional explicitly excluded topics, and some other cosmetic changes.

For those interested in seeing all updates, a version of the Syllabus with the current batch of updates highlighted is available here:
https://algo.sk/ioi-syllabus/ioi-syllabus-2025-draft.pdf

The official IOI 2024 version of the Syllabus is available here:
https://ioinformatics.org/page/syllabus/12
and more materials on the Syllabus, including its older versions, here:
https://algo.sk/ioi-syllabus/

If you have any questions or comments related to the Syllabus, we would love to hear from you. Feel free to reach out either directly to me, or to the whole ISC at ioi-sc@lists.ioinformatics.org

--
misof
~
[name] Miso Forisek [web] http://algo.sk
[gmail] michal.forisek [fb] http://facebook.com/misof