Russia 11 класс Informatics (advanced)
Chapters: 3
1. Theoretical foundations
Measuring information · Data compression · Error-correcting codes · Systems and models · Graphs and trees · Artificial intelligence
- Information Theory – Information is something that removes uncertainty. We measure it in bits: one bit is the answer to one fair yes/no question. If N outcomes are equally likely, the information is I = log2 N bits (Hartley). If outcomes have different probabilities, the average information is H = −Σ p log2 p bits (Shannon). Information is created, stored, processed and transferred through a channel that may add noise.
- Data Compression – Compression makes a file smaller so it uses less storage and travels faster. Lossless compression (RLE, Huffman, dictionary methods, ZIP, PNG) gives back exactly the original data. Lossy compression (JPEG, MP3, MP4) removes detail people hardly notice, so files get much smaller but the lost detail cannot return. Compression ratio = original size ÷ compressed size.
- Computer Simulation – A model is a simplified description of a real system that keeps only what matters. A computer simulation runs that model step by step in time to see what would happen. It has variables (the state), rules (how the state changes), parameters (numbers we can set) and often randomness, so we repeat runs and average. We check a simulation against real data (validation). Simulations are used for weather, traffic, disease spread, flight training and design, because they are cheaper, safer and faster than real tests, but they are only as good as their model and data.
- Graph Theory: Dots, Lines and Networks – A graph is a set of vertices (dots) joined by edges (lines). The degree of a vertex is how many edges touch it, and the sum of all degrees is twice the number of edges. An Euler trail uses every edge once and exists only when 0 or 2 vertices have odd degree. A tree is a connected graph with no cycles and n − 1 edges. Weighted graphs model roads and networks; Kruskal’s and Prim’s algorithms find a minimum spanning tree.
- Emerging Trends: AI, IoT, Cloud and Blockchain – Emerging technologies are new tools that are changing how we live and work. AI lets machines do smart tasks; machine learning lets them learn from data; NLP lets them use human language. AR adds virtual things to the real world, VR replaces it. Robots sense, think and act. IoT devices with sensors create big data, which smart cities use. Cloud computing rents out IaaS, PaaS or SaaS over the internet; grid computing joins many computers for one big job. Blockchain keeps a shared record that is very hard to change secretly.
2. Algorithms and programming
Theory of algorithms · Algorithms on numbers · Data structures · Graph algorithms · Dynamic programming · Object-oriented programming
- Stack in Python: Last In, First Out – A stack is a data structure where items are added and removed from one end only, called the top. It follows LIFO: last in, first out. Adding is push; removing is pop; looking at the top without removing is peek. Popping an empty stack is underflow; pushing into a full fixed-size stack is overflow. In Python a list works as a stack: append() pushes onto the end (the top) and pop() removes from the end.
- Dynamic Programming – Dynamic programming (DP) solves a big problem by solving each smaller subproblem only once and saving the answer. It works when subproblems overlap and the best answer is built from best answers of smaller parts (optimal substructure). Top-down DP is memoization; bottom-up DP fills a table. DP often turns exponential time into polynomial time.
3. Information technologies
Computer modelling · Databases · Web applications
- Computer Simulation – A model is a simplified description of a real system that keeps only what matters. A computer simulation runs that model step by step in time to see what would happen. It has variables (the state), rules (how the state changes), parameters (numbers we can set) and often randomness, so we repeat runs and average. We check a simulation against real data (validation). Simulations are used for weather, traffic, disease spread, flight training and design, because they are cheaper, safer and faster than real tests, but they are only as good as their model and data.
- Relational Databases: Tables, Rows, Columns and Keys – Keeping data in many separate files leads to repeated data, mismatched copies and hard searching, so we use a database managed by a DBMS. In the relational model data sits in tables called relations. A column is an attribute, a row is a tuple, and the set of allowed values for a column is its domain. The number of columns is the degree; the number of rows is the cardinality. A candidate key is any column (or set) that can identify every row uniquely; the one chosen is the primary key and the others are alternate keys. A foreign key is a column in one table that refers to the primary key of another table, linking them.
- Web Services: What Happens When You Open a Website – The World Wide Web (WWW) is a system of linked web pages that live on the Internet and are reached with a browser. Web pages are written in HTML, which uses fixed tags to show content; XML uses tags you make yourself to store and carry data. Every website has a domain name, like example.org, which DNS turns into an IP address. A URL is the full address of one resource: protocol, domain and path. A website is a set of related web pages. A web browser asks for pages and shows them; a web server stores them and sends them; web hosting is renting space on such a server so your site is online all the time.