Ukraine 11 клас Informatics (profile level)
Chapters: 4
1. Databases
Data modelling · Working with a relational DB
- 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.
- SQL for Class 12: Build Tables, Ask Questions, Join Tables – SQL is the language used to create and query relational databases. DDL commands (CREATE, ALTER, DROP) build structure; DML commands (INSERT, UPDATE, DELETE) change rows; SELECT reads data. Columns get data types (CHAR, VARCHAR, INT, FLOAT, DATE) and constraints (NOT NULL, UNIQUE, PRIMARY KEY, DEFAULT, FOREIGN KEY). SELECT can use aliases, DISTINCT, WHERE with relational and logical operators, IN, BETWEEN, LIKE and IS NULL, and ORDER BY. Aggregate functions (MAX, MIN, AVG, SUM, COUNT) summarise many rows; GROUP BY makes groups and HAVING filters groups. A Cartesian product pairs every row of one table with every row of another; an equi-join keeps only pairs whose common column matches; a natural join does the same and shows the common column once.
2. Algorithms
Algorithm design and complexity · Number theory · Sorting and searching · Strings and graphs · Advanced techniques · Computational geometry
- Algorithm Complexity: How Fast Does an Algorithm Grow? – Many algorithms can solve the same problem, but some need far more steps. We measure an algorithm by counting its basic steps as the input size n grows, not by stopwatch seconds. Big O notation names the growth: O(1) constant, O(log n) logarithmic, O(n) linear, O(n log n), and O(n²) quadratic. Linear search is O(n), binary search is O(log n); bubble sort is O(n²), merge sort is O(n log n). Memory used is space complexity.
- Sorting Algorithms – A sorting algorithm puts a list in order. Bubble sort swaps neighbours, insertion sort slides each item into a sorted part, selection sort picks the smallest each time, and merge sort splits the list and merges sorted halves. Merge sort needs far fewer comparisons on long lists (about n log₂ n instead of about n²/2).
- Graph Algorithms – A graph is a set of vertices joined by edges, which can carry weights. Breadth-first search (BFS) explores in layers using a queue and finds the fewest-edge path. Depth-first search (DFS) goes deep using a stack or recursion and backtracks. Trees can be traversed pre-order, in-order and post-order. Dijkstra's algorithm finds shortest paths from one vertex when weights are non-negative. Kruskal's and Prim's algorithms build a minimum spanning tree. Route inspection finds the shortest closed route using every edge; the travelling salesperson problem asks for the shortest tour of every vertex. In a flow network, the maximum flow equals the capacity of the minimum cut.
- 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. Web technologies
Web design and development
- Web Development: How HTML, CSS and JavaScript Build a Web Page – A web page is a set of text files. The browser (client) asks a server for them using a URL and HTTP. HTML gives the page its structure: headings, paragraphs, links, images, lists, tables and forms. CSS gives style: colours, fonts, spacing and layout. JavaScript gives behaviour: it reacts to clicks and changes the page. Responsive design makes one page fit both phones and computers. Good pages are also accessible, fast and safe.
4. Programming paradigms and technologies
Software engineering process
- Software Development: From Idea to Working App – Good software is built in stages: analyse the problem and write requirements, design the solution, code it in small parts, test it with normal, boundary and erroneous data, deploy it to users and maintain it. Waterfall does each stage once in order; agile repeats short cycles. Robust programs validate input, and teams use version control, clear roles and feedback from users.