Кратко: предложу содержание курса по модулям с практическими заданиями, как менять глубину для школьников и для студентов, и конкретные критерии оценивания с весами и рубриками.
1) Структура курса (модули + примеры практики)
- Введение: понятия алгоритма, сложность, тестирование.
- Задание: написать и протестировать поиск максимума в массиве; измерить время на разных n.
- Проверка: корректность, простая валидация на наборах данных.
- Базовые структуры: массив, связный список, стек, очередь, хеш-таблица.
- Задание: реализовать стек и очередь; реализовать простую хеш-таблицу с разрешением коллизий.
- Сортировки и поиск: вставками, выбором, пузырьком, быстрая сортировка, сортировка слиянием, бинарный поиск.
- Задание для школьников: реализовать вставки и измерить; для студентов: реализовать quicksort, mergesort, сравнить на худших/средних входах.
- Анализ: вывести асимптотику.
- Деревья: бинарные поисковые деревья, балансирующие (AVL/Красно-черные), деревья отрезков, Trie.
- Задание: реализовать BST с операциями вставки/удаления; студентам — AVL или RB, дерево отрезков для сумм на отрезке.
- Графы: представления (список/матрица), DFS/BFS, кратчайшие пути (Dijkstra, Bellman–Ford), MST (Kruskal, Prim).
- Задание: найти кратчайший путь на реальной карте (упрощённо), реализовать MST.
- Алгоритмический дизайн: жадные, динамическое программирование, разбиение и владение.
- Задание: классические DP (задача рюкзака, LCS); сложные варианты для студентов — оптимизация памяти, восстановление решения.
- Алгоритмическая сложность и сложность задач: O-нотации, доказательства нижних границ, NP-полнота (введение).
- Задание: доказать время алгоритма, свести NP-пример (студенты).
- Дополнительно: потоковые алгоритмы, хэширование для строк, параллельные/внешние алгоритмы (опционально для студентов).
- Финальный проект: от простого (визуализатор сортировок/структур) до сложного (малый поисковый движок, анализ графа реальных данных).
2) Как меняется глубина и подход
- Треки: базовый (школьники) и углублённый (студенты). Можно давать общий план с обязательной частью и набором опциональных задач.
- Для школьников:
- Цель: интуиция, реализации, отладка, визуализация.
- Акцент: пошаговые примеры, готовые тесты, меньше формальных доказательств.
- Задания: короткие (время выполнения ~$\le 2$ часа), больше визуальных/интерактивных.
- Для студентов:
- Цель: формальная строгость, оптимизация, анализ, доказательства корректности.
- Акцент: асимптотика, доказательства, амортизированный анализ, устойчивость в худших случаях.
- Задания: более крупные (по объёму и по сложности), исследовательские и проектные.
- Промежуточные меры в смешанном классе:
- Парная работа: школьник + студент (школьник реализует, студент доказывает/оптимизирует).
- Многоуровневые задания: базовые критерии (обязательные) + «челлендж»-подзадачи для студентов.
- Дифференцированные тесты: базовый набор тестов и набор сложных кейсов для продвинутых.
3) Примеры практических заданий по уровню
- Базовый (для школьников): реализовать очередь на массиве, написать unit-тесты, показать визуализацию.
- Средний (для всех/школьники+студенты): сравнить сортировки на случайных и почти отсортированных массивах; построить графики времени.
- Продвинутый (для студентов): реализовать Dijkstra с кучей Фибоначчи/биномиальной кучей и сравнить; доказать сложность.
- Проект: индексатор текста с хешированием и ранжированием по частоте; или веб-приложение с визуализацией алгоритмов.
4) Критерии оценивания (общая схема и рубрики)
- Предложенная схема весов (пример): домашние задания $40\%$, лабораторные/практики $25\%$, финальный проект $20\%$, контрольные/экзамен $15\%$.
- Рубрика для каждого задания:
- Корректность: автотесты — до $50\%$ баллов за задачу.
- Сложность/эффективность: оценка асимптотики решёного алгоритма — до $25\%$.
- Качество кода и документация: читаемость, комментарии, тесты — до $15\%$.
- Творчество/доп. фичи: оптимизации, расширения — до $10\%$.
- Пороговые критерии по уровням:
- Школьники: проходной уровень — корректность + базовые тесты; оптимизация — опциональна.
- Студенты: требуется корректность + обоснование асимптотики + доказательство/сложный тест-кейс.
- Формат оценки знаний:
- Автоматические тесты для базовой проверки.
- Ручная проверка кода (стиль, граничные случаи).
- Короткий устный/письменный экзамен для проверок понимания (доказательства/аргументы).
- За проекты — демонстрация + отчёт с анализом производительности.
- Примеры шкалы оценки (A/B/C):
- A: все тесты пройдены, алгоритм оптимален/обоснован, код чист, есть расширения.
- B: корректно, небольшие недочёты в оптимизации или документации.
- C: рабочее решение, но неэффективное или без объяснения сложности.
- Ниже C: существенные ошибки или невыполнение требований.
5) Методики преподавания и ресурсы
- Язык/инструменты: Python для быстрых реализаций (школьники), C++/Java для производительности (студенты), unit-test frameworks, визуализаторы (VisuAlgo, pythontutor), Git для проектов.
- Формат: лекции + лаборатории + офис-авторы/чаты поддержки + конкурсы (контесты) для мотивации.
- Оценка прогресса: частые короткие задачки (малые экзамены) и крупный завершающий проект.
Если нужно — пришлю конкретную разбивку по неделям на $12$ или $16$ занятий с конкретными заданиями и тест-кейсами.