Материалы для подготовки (промышленное программирование)

2024/2025 учебный год

Методические рекомендации

О подготовке к олимпиаде

Подготовка к олимпиаде по промышленному программированию требует комплексного подхода. Прежде всего, это знание основ алгоритмов и структур данных, которое будет проверяться на олимпиаде. Для успешного участия также необходимо владение одним из языков программирования (Python, Go, C++ или Java), навыками работы с данными (JSON, XML, CSV), базами данных и SQL, а также знание основ фронтенд-разработки (HTML, CSS) и протоколов интернет-связи (HTTP, TCP, UDP).

Особое внимание стоит уделить практике: регулярное решение прикладных задач и прохождение профильных курсов или участие в летних школах помогут развить навыки, необходимые для успешного участия в олимпиаде. Для подготовки можно познакомиться с демонстрационным вариантом и образовательными ресурсами, которые помогут вам освоить необходимые технологии и подходы.

Не забывайте, что каждая задача — это шаг к достижению вашей мечты. Успешное участие в олимпиаде откроет вам двери в ведущие университеты страны и станет важным шагом на пути к карьерным достижениям в IT.

Темы для подготовки

Теория

• Измерение информации

• Системы счисления

• Кодирование информации

• Алгоритмы для исполнителей

• Логические основы компьютерной техники

• Математические модели

• Компьютерные сети

Алгоритмы

• Базовый синтаксис высокоуровневого языка программирования

• Переменные, типы, выражения

• Базовый ввод-вывод

• Условные конструкции, логические выражения

• Циклы

• Функции, передача параметров, рекурсия

• Базовые типы данных (целый, вещественный, логический, символьный)

• Массивы (в т. ч. многомерные) и их обработка

• Строки и их обработка

• Графы и деревья

• Представление об асимптотической сложности алгоритмов

• Навыки оценки применимости алгоритма для заданных ограничений размера входных данных, времени и памяти

• Решения на основе полного перебора (итеративного или рекурсивного)

• Жадные алгоритмы

• Разделяй-и-властвуй

• Динамическое программирование

• Свойства целых чисел (четность, делимость и др.)

• Дроби, проценты

• Системы счисления

• НОД, НОК

• Простые числа, решето Эратосфена

• Быстрое возведение в степень

• Базовая геометрия на плоскости

• Линейный поиск в массиве

• Двоичный поиск

• Алгоритмы сортировки со сложностью O(NlogN)

• Стек и очередь

• Двоичная куча

• Двоичные деревья поиска

• Хеш-таблицы

• Основы теории графов (способы задания графа, основные свойства графов)

• Обходы деревьев

• Обход графа в глубину и его применения

• Поиск кратчайших путей в графах

Данные

• Файловый ввод-вывод

• Сортировка данных во внутренней памяти по произвольным критериям

• Чтение, запись и обработка текстовых форматов хранения и обмена данными (CSV, JSON)

• Обработка данных в электронных таблицах (Excel, OpenOffice Calc)

• Обработка данных на языке Python с помощью библиотеки pandas

• Выполнение запросов на языке SQL к многотабличной базе данных, представленной в формате файловой СУБД SQLite

• Проектирование реляционной модели данных на диалекте  СУБД SQLite в следующем объеме: таблицы, первичные и внешние ключи, индексы, представления данных

Frontеnd

• Язык HTML и каскадные таблицы стилей CSS

• Язык программирования JavaScript

• Основы блочной верстки

Backеnd

• Клиент-серверная архитектура

• Обработка HTTP-запросов

• Сетевое взаимодействие и потенциальные проблемы

• Обработка ошибок

• Применение простых алгоритмов на практике

Литература и источники для подготовки

Теория

• УМК «Информатика» К.Ю. Полякова, Е.А. Еремина, 10-11 классы. Базовый и углубленный уровни. https://lbz.ru/books/742/ 

• Угринович, Н. Информатика и информационные технологии / Н. Угринович. — М.: Бином. Лаборатория знаний, 2017. — 512 c.

• https://kpolyakov.spb.ru/

• https://inf-ege.sdamgia.ru/

Алгоритмы

• Алгоритмы: построение и анализ / Томас Х. Кормен, Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн. — 3-е изд. — М.: Вильямс, 2013. — 1328 с.

• Дасгупта С., Пападимитриу Х., Вазирани У. Алгоритмы / С. Дасгупта, Х. Пападимитриу, У. Вазирани. — М.: МЦНМО, 2014. — 320 с.

• Лааксонен А. Олимпиадное программирование. / Антти Лааксонен. — 2-е изд. — М.: ДМК Пресс, 2020. — 328 с.

• Московские олимпиады по информатике / Под ред. Е. В. Андреевой, В. М. Гуровица и В. А. Матюхина. — М.: МЦНМО, 2006. — 256 с.

• Халим С., Халим Ф. Спортивное программирование / пер. с англ. Н. Б. Желновой, А. В. Снастина. — М.: ДМК Пресс, 2020. — 604 с.

• https://e-maxx.ru

• https://neerc.ifmo.ru/wiki/index.php

• https://brestprog.by/topics

• https://ru.algorithmica.org

• https://acm.khpnets.info

• https://informatics.msk.ru

• https://codeforces.com

• https://acmp.ru

Данные

• Маккинни У. Python и анализ данных. — 3-е изд. — М.: ДМК Пресс, 2023. — 537 с

• SQL учебник для чайников: https://html5css.ru/sql/default.php 

• Самоучитель SQL: https://practicum.yandex.ru/blog/samouchitel-sql/

Frontend

• Резиг, Бибо, Марас: Секреты JavaScript ниндзя

• Дэвид Фленаган: JavaScript. Полное руководство. 7-е издание.

• Современный учебник JavaScript https://learn.javascript.ru/

Backend

• Clean Architecture by Rober Martin

• Clean Code by Rober Martin

• Core Python Programming by Wesley Chun

• Effective Python by Brett Slatkin

• Learning Python by Mark Lutz

• The Go Programming Language by Alan A. A. Donovan and Brian W. Kernighan

• Effective Go by the Go Team

• Interconnections by Radia Perlman

• Site Reliability Engineering: How Google Runs Production Systems, edited by Betsy Beyer, Chris Jones, Jennifer Petoff, and Niall Murphy

• The Site Reliability Workbook, edited by Betsy Beyer, Niall Murphy, David Rensin, Kent Kawahara, and Stephen Thorne

• Google Hacks, Tara Calishain and Rael Dornfest

• Real World SRE, Nat Welch

• Implementing Service Level Objectives, Alex Hidalgo

• The C++ Programming Language (4th Edition), Bjarne Stroustrup

• The C++ Standard Library, Nicolai M. Josuttis

• Python Web Development with Django by Forcier, Bissex, and Chun

• Design Patterns, Erich Gamma, et al.

• Refactoring to Patterns (Addison-Wesley Signature Series), Joshua Kerievsky

• Security Engineering, Ross Anderson

• Building Secure & Reliable Systems, Heather Adkins, Betsy Beyer, Paul Blankinship, Ana Oprea, Piotr Lewandowski, Adam Stubblefield

• How Google Tests Software, Whittaker

• Programming with POSIX(R) Threads, David R. Butenhof