Модуль 2. Алгоритми та інженерний C++
Декомпозувати програми, оцінювати алгоритми та керувати ресурсами безпечними засобами C++
Модуль має один маршрут. Кожен блок завершується дією, яку ви вже можете виконати самостійно.
декомпозувати програму на функції з явними контрактами й тестами
реалізовувати пошук, сортування та рекурсивні алгоритми
оцінювати зростання обсягу роботи алгоритму
пояснювати володіння ресурсами та застосовувати RAII
моделювати дані й будувати програми з файлами, розбором та політикою помилок
Детальний маршрут
Функції й перевірювані контракти
Після блоку. Після блоку ви декомпонуєте програму, обираєте спосіб передавання даних і проєктуєте тести.
Л6Функції й узагальнення: декомпозиція, параметри та тестиЛекція. Будуємо функції з явними контрактами, вивчаємо параметри, перевантаження, значення за замовчуванням і перший простий шаблон функції.
ЛР11Рефакторинг у функціїЛабораторна. Монолітний фрагмент працює, але змішує три різні обчислення над однією послідовністю.
ЛР12Default arguments, overloads, function template і тестиЛабораторна. Невеликий набір helper-функцій має однаковий стиль виклику для кількох числових випадків.
Пошук і складність
Після блоку. Після блоку ви порівнюєте лінійний та двійковий пошук, формулюєте передумови й оцінюєте зростання роботи.
Л7Пошук у послідовності та обсяг роботиЛекція. Порівнюємо способи пошуку, рахуємо основні операції та досліджуємо, як обсяг роботи змінюється зі зростанням даних.
ЛР13Лінійний пошук: контракт і підрахунок операційЛабораторна. Потрібно знайти першу позицію цільового значення у невпорядкованій послідовності.
ЛР14Двійковий пошук і передумова впорядкованостіЛабораторна. Каталог уже впорядкований. Пошук звужує активний інтервал після кожної перевірки середини.
ЛР15Порівняння пошуків і проєктування тестівЛабораторна. Є два workloads: багато запитів до вже sorted data та один запит до невпорядкованої послідовності.
Сортування, рекурсія і поділ задачі
Після блоку. Після блоку ви трасуєте сортування та рекурсію й пояснюєте алгоритмічні компроміси.
Л8Сортування та поділ задачі на менші частиниЛекція. Впорядковуємо послідовності, оцінюємо вкладені проходи та простежуємо задачі, які розв’язуються через менші підзадачі.
ЛР16Сортування вибором і `std::sort`Лабораторна. Невеликий рейтинг треба впорядкувати та пояснити через invariant відсортованого префікса.
ЛР17Рекурсія і стек викликівЛабораторна. Рекурсивна функція підсумовує суфікс послідовності, переходячи до наступного індексу.
ЛР18Порівняння алгоритмів і рефакторингЛабораторна. Один aggregate обчислюється ітеративно та рекурсивним divide-and-conquer підходом.
Володіння ресурсами і модель даних
Після блоку. Після блоку ви застосовуєте RAII, моделюєте записи та підтримуєте допустимий стан даних.
Л9Моделювання даних, ресурси та стандартна бібліотека C++Лекція. Поєднуємо RAII, `struct`, `enum class`, `switch`, вибір контейнера, стандартні алгоритми та локальні lambda-вирази.
ЛР19Рефакторинг до RAIIЛабораторна. Starter code володіє ресурсом вручну та має control path, де cleanup легко пропустити.
ЛР20Записи, `enum class`, `switch` і колекціїЛабораторна. Набір заявок має id, назву, стан і числову вагу. Дані треба зібрати в предметні записи.
ЛР21Стандартні алгоритми, lambda й вибір контейнераЛабораторна. Послідовність треба знайти, відфільтрувати за predicate, трансформувати та впорядкувати.
ЛР22Записи, стани й перевірка інваріантівЛабораторна. Пакет records містить повторні id та некоректні quantity/price. Потрібно виділити допустиму частину.
Файли, розбір та інтеграція
Після блоку. Після блоку ви будуєте конвеєр обробки даних, формулюєте політику помилок і завершуєте C++ мініпроєкт.
Л10Файли, текстові дані й обробка помилокЛекція. Будуємо шлях від текстового рядка до перевірених даних, а потім додаємо читання, запис і явну обробку помилок.
ЛР23Текстові файли й чиста обробка данихЛабораторна. Добре сформований text file містить пари `name value`. Потрібно прочитати його й створити короткий report.
ЛР24Парсер, валідація і політика помилокЛабораторна. Text file містить записи `name quantity price`, серед яких є format errors і domain errors.
ЛР25Мініпроєкт C++: перевірені records і звітЛабораторна. Невеликий файл продажів містить `id category quantity price`. Програма має сформувати перевірений summary report.
МК2Модульний контроль 2Модульний контроль. Перевіряємо алгоритми, сучасний C++, роботу з пам’яттю, даними та помилками.
Робоче середовище
Лабораторні notebook відкриваються у спільному браузерному середовищі.