Авторский курс программирования "Ключевые алгоритмы и структуры данных Python
на основе игр, задач и головоломок" Куракина П.В.

 

С 1 февраля приглашаем учащихся на авторский курс программирования П.В. Куракина,

"Ключевые алгоритмы и структуры данных Python на основе игр, задач и головоломок".

(зачисление - по результатам тестирования*)

 

Курс рассчитан на учащихся 8-11 классов, владеющих начальными элементами программирования на любом языке.

Автор - Куракин Павел Вячеславович

Kurakin  

 

 

 

Научный сотрудник Института проблем управления им. В. А. Трапезникова РАН,
ассистент кафедры математического моделирования и прикладной математики МФТИ, 
преподаватель учебного центра «Физтех-Потенциал».

 

Акцент курса сделан на 2-х позициях.

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

2. Реализация (имплементация) необходимых алгоритмов.

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

 

Программа курса

«Базовые структуры данных и алгоритмы языка Python на примере задач информатики повышенного уровня»

Куракин П. В.

Институт проблем управления им. В. А. Трапезникова РАН

МФТИ - «Потенциал»



    I. Некоторые общие методы и подходы

Внимание. Эти темы и сопутствующие им задачи (они типовые) предполагаются обязательной и неизменной частью курса.

1. Рекурсия. Числа Фиббоначи. Простейший вариант рекурсии. Мемоизация. Автоматическая мемоизация. Задача о Ханойской башне. Начала динамического программирования. Задача о воришке. Задача о размене монет.

2. Задачи поиска. Поиск подстроки в строке на примере ДНК. Хранение ДНК – строки. Линейный поиск. Бинарный поиск. Задачи на прохождение лабиринта. Создание лабиринта. Мелкие детали лабиринта. Поиск в глубину. Поиск в ширину. Задача «Миссионеры и людоеда».

3. Задачи с ограничениями (CSP = constraint satisfaction problems). Разработка общего инструментария (framework) решения CSP – задач. Задача о раскраске карты Австралии. Задача о восьми ферзях. Задача о размещении электронных компнентов на печатной плате.

4. Задачи теории графов. Поиск кратчайшего пути в графе. Алгоритм Дейкстры. Поиск минимального связующего дерева.           

           

    II. Некоторые выделенные задачи.

 

Внимание. Набор задач может изменяться. В программе приведен ориентировочный набор задач олимпиадного уровня, для составления представления об общем типе разбираемых задач.

1. Попытка к бегству. Узник пытается бежать из замка, который состоит из MN квадратных комнат, расположенных в виде прямоугольника M×N. Между любыми двумя соседними комнатами есть дверь, однако некоторые комнаты закрыты и попасть в них нельзя. В начале узник находится в угловой комнате и для спасения ему надо попасть в противоположную угловую комнату. Времени у него немного, всего он может побывать не более, чем в M+N-1 комнате, включая начальную и конечную комнату на своем пути, то есть с каждым переходом в соседнюю комнату расстояние до выхода из замка должно уменьшаться. Требуется найти количество различных маршрутов, ведущих к спасению.

2. Банкомат. В некотором государстве в обращении находятся банкноты определенных номиналов. Национальный банк хочет, чтобы банкомат выдавал любую запрошенную сумму при помощи минимального числа банкнот, считая, что запас банкнот каждого номинала неограничен. Помогите Национальному банку решить эту задачу.

3. Расписание. На конференции работников народного образования с докладами об очередном улучшении финансирования желает выступить несколько министров правительства. Но поскольку министры, как правило, очень заняты, то каждый из министров назначил время, когда он хочет выступить с докладом. Естественно, министры не смогли распределить время между собой, поэтому заявленные ими времена пересекаются. Перед вами стоит задача выбрать из всех поданных заявок несколько непересекающихся, при этом максимизировать число выбранных заявок.

4. Рациональные дроби. Даны две положительные рациональные дроби: a/b и c/d. Найдите их сумму и запишите ответ в виде несократимой дроби.

5. Прямоугольники. Дано N прямоугольников со сторонами, параллельными осям координат. Требуется определить, на какое количество частей эти прямоугольники разбивают плоскость.

6. Ферзя в угол. В левом нижнем углу доски M×N стоит ферзь. Двое игроков по очереди ходят ферзем, перемещая его на любое число клеток по вертикали вверх, по горизонтали вправо, или по диагонали вправо-вверх. Выигрывает тот, кто поставит ферзя в правый верхний угол доски. Определите, какой из игроков имеет выигрышную стратегию.

7. Удаление клеток. Из прямоугольного листа бумаги (M строк, N столбцов) удалили некоторые клетки. Определите, на сколько кусков распадается оставшаяся часть листа. Две клетки не распадаются, если они имеют общую сторону.

8. Морской бой. На прямоугольном поле для игры в морской бой размером M×N расположено несколько прямоугольных кораблей. Корабли не соприкасаются друг с другом. Ваша задача — определить всевозможные типы кораблей на поле и число кораблей каждого типа. Два корабля относятся к одному типу, если их размеры совпадают (корабли, которые могут быть получены друг из друга поворотом, также относятся к одному типу).

9. Шестеренки. На плоскости расположена система из N одинаковых шестеренок, которая приводится в движение вращением шестеренки 1 по часовой стрелке (`clockwise'). Требуется определить направление вращения каждой шестеренки системы, либо установить, что систему заклинит.

10. Красильщик. У красильщика имеется N предметов, которые он должен покрасить. Красильщик красит i-й предмет за время pi, после чего предмет сохнет время qi. Одновременно красильщик может красить только один предмет, а сохнуть одновременно может произвольное число предметов. Определите последовательность, в которой красильщик должен красить предметы, чтобы сделать суммарное время выполнения работы минимальным (время считается от начала работы до того момента, когда высохнут все предметы).

11. Вложенные ящики. Рассматриваются n-мерные ящики, заданные длинами своих сторон (двумерный ящик – это прямоугольник, трехмерный - параллелепипед). Необходимо проанализировать свойства группы таких ящиков. Надо найти в данной группе ящиков такую последовательность максимальной длины, что каждый следующий ящик можно «вложить» в предыдущий.

12. Десант. Отряд из  m (1 <= m <= 10) десантных кораблей прорывается к берегу прорывается к берегу через минное поле. План минного поля известен. Опасные места обозначены четырехугольниками. Обходить по контуру эти четырехугольники можно, а внутрь заходить нельзя. Всего имеется n (1 <= n <= 20) непересекающихся четырехугольников. Место высадки десанта для каждого корабля строго определнно. Требуется найти для десантных кораблей такие маршруты, чтобы сумма расстояний, пройденная всем кораблями была минимальной.

 

 

Занятия пройдут на платформе ZOOM.

Для участия необходимо пройти регистрацию

 

Расписание занятий

Группа День недели Время Количество часов в месяц/ за   курс, ак.ч. Стоимость пробного занятия Стоимость за 4 занятия
8-11 класс Среда 17:00 - 20:00 16ак.ч/48ак.ч 1750р 7000р
           

 

 

 

* Тестирование

 

ТЕСТ по курсу "Ключевые алгоритмы и структуры данных Python

на основе игр, задач и головоломок".

ФИО учащегося  
ФИО родителя  
Телефон  
Класс  

 

Задания

    1. Сформировать массив из случайных чисел, в которых ровно две единицы, стоящие на случайных позициях.

    2. Дан массив. Найдите два соседних элемента, сумма которых минимальна.

    3. Определите, каких чисел в массиве больше: которые делятся на первый элемент массива или которые делятся на последний элемент массива.

    4. Дан массив x из n элементов. Найдите x1xn+x2xn−1+…+xnx1.

    5. Найдите сумму чисел массива, которые стоят на нечетных местах и при этом превосходят сумму крайних элементов массива.

     6. Сформировать массив из случайных целых чисел от 0 до 9 , в котором количество единиц от 3 до 5 и двоек больше троек.

     7. (а) Придумайте свое правило генерации массива заданной длины (примеры таких правил в вышележащих задачах)

            (б) Определите, сгенерирован ли данный массив вашим правилом или нет.

     

ВАЖНО! Ответ на тест необходимо прислать в виде кода на PHYTON на электронную почту Этот адрес электронной почты защищён от спам-ботов. У вас должен быть включен JavaScript для просмотра.

----------------------------------

 

Звоните или оставляйте заявку на сайте!

т.8-495-542-65-62, 8-495-743-29-02.