А.В.Шаповалов => Занятия и кружки => Московские сборы

Сборы московских школьников
в лагере "Команда" с 11 по 22 ноября 2013 г.
9 класс. Комбинаторика и олимпиады.

Пишите

Занятия двух групп. Листки сильно пересекаются, но группа 9-2 менее опытная, поэтому задачи там в среднем чуть проще.

гр9-1, гр9-2	Жадный алгоритм	11 ноября	Листок		Алгоритм – это способ достижения цели через жестко определенную последовательность шагов. Если цель – максимум какой-то величины, то ее часто достигают с помощью «жадного алгоритма», то есть, добиваясь максимально возможного приращения на каждом шаге.
гр9-1	Увидеть граф	12 ноября	Листок		В задачах на графы важно научиться строить подходящий граф из объектов любой природы. Далее часто хватает применения простейших фактов о графах.
гр9-2	Увидеть граф	12 ноября	Листок		Важный пример графа: вершины - позиции, рёбра ходы. Если граф окажется двудольным, то применима идея чередования.
гр9-1	Периодичность	13 ноября	Листок		Принцип зацикливания. Если система может находиться лишь в конечном числе состояний, и каждое следующее состояние зависит лишь от фиксированного числа предшествующих состояний, она с некоторого момента зациклится.
гр9-2	Увидеть граф-2	13 ноября	Листок		При подсчетах и оценках помогает разбиение на компоненты связности, в частности — разбиение на циклы и цепочки.
гр9-1, гр9-2	Письменная олимпиада	14 ноября	Olymp.doc	Решения	5 задач на 4,5 часа. Варианты разных групп отличаются одной задачей.
гр9-1	Увидеть граф-2	14 ноября	Листок		При оценках помогает подсчёт числа компонент связности, неравенство между числом вершин и рёбер в графе без циклов.
гр9-1	Узкие места	15 ноября	Листок		Зацепкой к решению часто служит та часть конструкции, где свобода выбора – наименьшая. Такие места служат препятствиями к построению конструкции, или кажутся таковыми. Именно их мы и назовем узкими местами.
гр9-2	Периодичность	15 ноября	Листок		Принцип зацикливания назад. Если система может находиться лишь в конечном числе состояний, и по фиксированному числу состояний однозначно определяется как следующее, так и предыдущее состояние, то система зацикливается без предпериода.
гр9-1	Разрезания: соответствие и счет узких мест	16 ноября	Листок		При разрезаниях фигур на части помогает счет углов, вершин, сторон, длин и площадей. Ищите узкие места – они подскажут, что именно надо считать.
9 и 10 класс	Пересечение путей короля и ладьи	17 ноября	Конспект лекции		Клетки прямоугольной доски раскрашены в синий и красный цвета. Тогда либо хромая ладья может пройти по синим клеткам с нижнего края на верхний, либо король может пройти с левого края на правый по красным клеткам (причем из двух возможностей всегда есть ровно одна!)
гр9-2	Узкие места	17 ноября	Листок		Узкие места обычно сочетаются с постепенным конструированием: выявив одно узкое место и использовав его для построения части конструкции, полезно поискать следующее узкое место.
гр9-1	Конструкции по индукции	18 ноября	Листок		Оформление доказательств через математическую индукцию нужно редко. Важнее показать, как индуктивное построение можно превратить в явный алгоритм.
гр9-2	Разрезания: соответствие и счет узких мест	18 ноября	Листок		При разрезаниях фигур на части помогает счет углов, вершин, сторон. Ищите узкие места – они подскажут, что именно надо считать. Подсчеты при соответствии часто удобно оформлять через двудольный граф.
гр9-1	Испытания и оценки	19 ноября	Листок		Пусть надо выявить один случай из N (и случаи могут не совпадать с предметами). Если вопрос имеет k возможных ответов, он делит все случаи на k групп. Лучше делить на такие группы, чтобы размер наибольшей был как можно меньше (в идеале – на равные группы).
гр9-2	Конструкции по индукции	19 ноября	Листок		Оформление доказательств через математическую индукцию нужно редко. Важнее показать, как индуктивное построение можно превратить в явный алгоритм.
гр9-1	Конечное и бесконечное	20 ноября	Листок		Складывая само с собой любое положительное число (даже очень малое), можно превзойти любое число (даже очень большое).Следует различать «сколь угодно большое» и «бесконечное».
гр9-2	Испытания и оценки	20 ноября	Листок		Пусть надо выявить один случай из N (и случаи могут не совпадать с предметами). Если вопрос имеет k возможных ответов, он делит все случаи на k групп. Лучше делить на такие группы, чтобы размер наибольшей был как можно меньше (в идеале – на равные группы).
гр9-1	Все зачётные задачи	21 ноября	Листок		Зачетные задачи единым списком. Решения, увы, разбирались устно, да и то далеко не у всех.
гр9-2	Все зачётные задачи	21 ноября	Листок		Зачетные задачи единым списком.