Алгоритмы и структуры данных

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

На обучение по образовательной программе принимаются школьники 13-16 лет, проявившие активный интерес к занятиям информатикой и программированием, продемонстрировавшие высокий результат в предварительном отборочном соревновании, или ставшие победителями или призерами олимпиад по программированию регионального или всероссийского уровня, или прошедшие обучение на образовательных программах Образовательного центра «Сириус» по информатике.

Педагоги

Гориховский Вячеслав Игоревич

Содержание программы

I сессия (40 часов)

  1. Начала теории сложности вычислений. Асимптотическая оценка сложности алгоритма. Линейные, квадратичные, переборные алгоритмы.

  2. Принципы построения алгоритмов. Конструктивные, итерационные, переборные алгоритмы.

  3. Алгоритмы в теории чисел. Арифметика остатков. Обратный элемент по простому модулю. Проверка числа на простоту. Алгоритм Евклида.

  4. Бинарный поиск. Последовательный и бинарный поиск. Левый и правый бинарный поиск.

  5. Линейные и алгоритмы. Поиск элементов с минимальной разностью. Метод двух указателей.

  6. Динамическое программирование. Рекуррентные соотношения. Одномерная динамика: подсчет количества вариантов решения, поиск оптимального решения.

  7. Рекурсия. Понятие рекурсии. Быстрое возведение в степень.

II сессия (40 часов)

  1. Алгоритмы в теории чисел. Основные теоретико-числовые функции.

  2. Рекурсия. Оценка эффективности рекурсивных алгоритмов

  3. Бинарный поиск. Бинарный поиск по ответу. Вещественный бинарный поиск.

  4. Структуры данных. Массивы

  5. Задача сортировки. Квадратичные сортировки.

  6. Префиксные суммы. Запросы на отрезке.

  7. Динамическое программирование. Псевдодвумерное динамическое программирование.

  8. Индивидуальная олимпиада

III сессия (40 часов)

  1. Структуры данных. Стек, очередь, дек.

  2. Структуры данных. Множества, словари.

  3. Алгоритмы на графах
  4. Жадные алгоритмы. Общая идея жадных алгоритмов

  5. Двумерное динамическое программирование

  6. Командная олимпиада

IV сессия (40 часов)

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

  2. Структуры данных. Бинарная куча. Пирамидальная сортировка. Деревья поиска.

  3. Алгоритмы на графах. Задачи о кратчайших путях в графе.

  4. Алгоритмы на графах. Минимальное остовное дерево Алгоритм Прима. Алгоритм Краскала.

  5. Основы вычислительной геометрии

Цели программы

  • Цель программы – создание фундамента для структурно-алгоритмического развития, формирование механизмов мышления, характерных для деятельности в области информатики и программирования, математическими и алгоритмическими знаниями и умениями, необходимыми для успешного изучения предмета на углубленном уровне.

    Задачи программы:

    развитие абстрактного мышления, в частности логического, алгоритмического и математического способов мышления;

    ·       знакомство с аксиоматическим подходом к построению математических и информационных моделей;

    ·       формирование математического и информационного языка и аппарата как одного из средств описания и исследования окружающего мира;

    ·       формирование умения характеризовать реальные процессы с точки зрения математического и компьютерного моделирования, составления необходимых оптимальных алгоритмов с их дальнейшей программной реализацией, на основе которой возможно провести качественный анализ исследуемого динамического процесса;

    ·       воспитание социально-личностных и общекультурных навыков, культуры мышления и общения, способности к восприятию, обобщению и анализу информации, постановке цели и выбору путей ее достижения посредством современных средств обработки информации и передачи данных.

    ·       мотивации к самообразованию за счет активизации самостоятельной познавательной деятельности;

    ·       формирование общих способов интеллектуальной деятельности, характерных для информатики и являющихся основой познавательной культуры, значимой для различных сфер человеческой деятельности;

    ·       привлечение к занятиям информатикой и программированием школьников, проявляющих интерес к техническим наукам, и формирование устойчивого интереса к информатике и программированию;

    ·       развитие коммуникативных навыков, умения работать в команде;

    ·       развитие логического мышления, алгоритмической культуры, пространственного воображения, математического и физического мышления и интуиции;

    ·       развитие общей культуры школьников путем знакомства с историей развития информатики, эволюцией алгоритмических идей;

    ·       подготовка школьников к соревнованиям, олимпиадам, турнирам, конференциям на региональном, национальном и международном уровне.

Результат программы

Планируется, что каждый выпускник программы:

  • приобретет навыки решения алгоритмических задач повышенной сложности;
  • приобретет умение формулировать решение задачи как в виде логически правильного и грамотного устного выступления, так и в виде корректной и эффективной программы;
  • приобретет навыки командной работы над задачей;
  • освоит новые разделы информатики и программирования;
  • повысит свою готовность к выступлениям на различных этапах Всероссийской олимпиады школьников, в других олимпиадах.

Особые условия проведения

Для обучения в рамках программы принимаются обучающиеся образовательных организаций Ленинградской области, проявившие интерес к предмету и продемонстрировавшие высокую результативность при освоении общеобразовательной программы, победители и призеры Регионального этапа Всероссийской олимпиады школьников по информатике, других конкурсных мероприятий регионального и всероссийского уровня, а также в соответствии с рейтингом отборочной олимпиады Национального исследовательского университета информационных технологий, механики и оптики (НИУ ИТМО).

Материально-техническая база

Для проведения практических занятий требуются компьютерные классы с доступом в Интернет, в том числе мобильные, оснащенные ноутбуками, подключаемыми к Интернету через сеть WI-FI. Количество компьютеров должно соответствовать количеству обучающихся. Для ряда теоретических занятий требуются помещения вместимостью до 100 человек, оборудованные стульями, маркерной доской с маркерами, проектором. Количество стульев должно соответствовать количеству обучающихся.