Курчатовская Олимпиада по информатике 2009 года

Правила проведения

Курчатовская олимпиада по информатике состоит из двух туров: заочного и очного. Очный тур будет происходить в Москве, в конце февраля 2009 года. Отбор участников очного тура происходит по результатам заочного тура. В олимпиаде может принимать участие любой школьник, обучающийся в 1-11 классе любой школы России.

Правила проведения заочного тура таковы: желающим предлагается две задачи, которые решаются дома, и не позднее 15 февраля 2009 года решения отсылаются по электронному адресу olymp09[at]inse.ru. Решения, присланные позднее 15 февраля, не рассматриваются ни при каких обстоятельствах. Дата поступления решений определяется днём получения нами вашего электронного письма. В присланных решениях должно содержаться следующее:

Требования к программам: программы могут быть написаны на любом из существующих процедурных компилируемых языков программирования под любую свободно-распространяемую операционную систему для PC или под Miscrosoft Windows. Исходный текст программы должен быть хорошо отформатирован и откомментирован. Запрещается использовать внешние библиотеки, не входящие в состав поставки компилятора, а также библиотеки компилятора, предназначенные специально для решения поставленной перед вами задачи. Очень приветствуется переносимость написанной программы на другие компиляторы/платформы.

Важное замечание: не обязательно делать обе программы. Если вы сделали только одну, или даже половину программы — присылайте получившееся нам, мы разберемся.

Очный тур будет проходить на территории РНЦ «Курчатовский Институт» в конце февраля 2009 года. Участники, допущенные до очного тура, будут извещены об этом по электронному адресу, с которого было отослано решение. Также, список участников будет опубликован на этой странице после окончания заочного тура.

Победители и лауреаты будут награждены ценными призами и красивыми грамотами.

Заочный тур

Задача: пентамино

Есть такая головоломка — Пентамино. Собственно говоря, по указанной ссылке все достаточно обстоятельно рассказано. В задаче нужно сделать следующее: найти все варианты заполнения выбранного прямоугольника площадью 60 единичных квадратов. При этом программе можно указать, что нужно либо

Задача: эмулятор Ethernet-коммутатора

Есть такие устройства — коммутаторы или, как их еще называют, сетевые мосты. Они используются для формирования интеллектуальных точек обмена трафиком на втором (канальном) уровне модели OSI.

Несмотря на обилие умных слов, базовая функциональность коммутаторов достаточно проста: им нужно передать сетевые пакеты из одного порта коммутатора в другой порт. Порт — это точка подключения либо пользовательского сетевого оборудования (например, компьютера), либо другого коммутатора. Каждый пакет содержит два адреса: адрес получателя пакета и адрес его отправителя. Эти адреса обычно называются MAC-адресами и, например, для Ethernet-устройств они являются 48-битными числами.

Нетривиальность поведения коммутаторов состоит в том, что когда в один из портов приходит пакет с каким-то адресом назначения, то коммутатор не всегда знает, в какой порт отправить этот пакет, чтобы он дошел по правильному адресу. Если это действительно так (то есть куда посылать — неясно), то коммутатор отправляет копии этого пакета во все свои порты, исключая порт через который вошел оригинальный пакет. Но для каждого входного пакета коммутатор делает еще одну вещь: он запоминает, что на данном порту находится устройство с MAC-адресом, указанном в пакете в качестве источника пакета. Таким образом коммутатор формирует некоторую таблицу соответствия портов и MAC-адресов, с которой он и консультируется, пытаясь куда-то отправить очередной пакет.

Строго говоря, эта самая таблица (иногда называемая «L2 FIB») обладает некоторыми дополнительными свойствами. Например, если от какого-то узла на данный порт не приходило пакетов, то соответствие между этим портом и MAC-адресом удаляется из таблицы. Кстати говоря, пакеты, поступающие в порт коммутатора, называются входящими или ingress, а выходящие из порта коммутатора — исходящими или egress). Таким образом, в таблице поддерживаются только более-менее свежие соответствия: FIB-таблица не «распухает», а коммутатор может отслеживать и реагировать на изменения транспортной топологии сети.

Переходим к нашему эмулятору. В качестве MAC-адресов у нас будут использоваться обычные строки. Длина строки адреса и ее содержимое произвольны, например, «Мой ноутбук». Существует специальный MAC-адрес, называющийся «все». Если он используется в качестве адреса назначения, то такой пакет пересылается во все порты коммутатора, поэтому данный адрес называется «широковещательным» (broadcast). Поскольку моделировать кучу сетевых устройств с помощью отдельных программ — сложно, то мы поступим следующим образом: генератором пакетов у нас будет простой текстовой файл со следующим форматом строк,

номер порта||MAC-адрес назначения||MAC-адрес источника||содержимое пакета
Типичный файл будет выглядеть так:
2||Станция 2||все||А у кого тут есть ворованный Windows?
5||Компьютер 1||Станция 2||У меня!
7||Ноутбук 3||Станция 2||У меня!
2||Станция 2||Компьютер 1||А ну-ка быстренько ставим FreeBSD!
5||Компьютер 1||Станция 2||OK, сейчас попробуем...
2||Станция 2||Ноутбук 3||И не стыдно?
8||Ноутбук 3||Станция 2||Ни капельки.
2||Наладонник 8||Станция 2||И мне, и мне не стыдно ;))

Что касается выходных файлов, то у нас их будет много. Во-первых, по файлу на каждый номер порта коммутатора: в каждый из этих файлов записываются все приходящие в него пакеты. Эти файлы предлагается именовать номерами портов коммутатора.

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

В-третьих, у нас будет файл с журналом состояния таблицы «L2 FIB»: каждая строчка в нем будет соответствовать состоянию этой таблицы после поступления очередного пакета из входного файла в порт коммутатора. Каждая строка состоит из пар «порт=MAC», разделенных символами «!».

Например, для вышеприведенного входного файла эволюция таблицы FIB будет выглядеть так (при условии, что элементы этой таблицы, однажды в нее попав, никогда из нее не удаляются):

2=Станция 2
2=Станция 2!5=Компьютер 1
2=Станция 2!5=Компьютер 1!7=Ноутбук 3
2=Станция 2!5=Компьютер 1!7=Ноутбук 3
2=Станция 2!5=Компьютер 1!7=Ноутбук 3
2=Станция 2!5=Компьютер 1!7=Ноутбук 3
2=Станция 2!5=Компьютер 1!7=Ноутбук 3
2=Станция 2!5=Компьютер 1!7=Ноутбук 3!2=Наладонник 8
Обратите внимание, что на порту 2 у нас жили два устройства. Это абсолютно законно: вспомните, что к портам коммутатора могут подключаться другие коммутаторы.

Если в таблице FIB была запись о том, что какое-то устройство находилось на порту N, но от этого устройства приходит пакет в порт M, то запись о местоположении этого устройства в таблице FIB должна быть скорректирована соответствующим образом.

Дополнительно к этому правилу, ваш коммутатор обладает характеристикой, называющейся «время старения записи в таблице FIB». В нашем случае эта величина измеряется в количестве обработанных коммутатором пакетов и говорит коммутатору следущее: «Если от любого из узлов не будет поступать пакетов на протяжении указанного промежутка времени (вернее, если через коммутатор прошло данное количество пакетов, но от нашего узла входящих пакетов не было), то выкидывай соответствие для этого узла из таблицы FIB». Если пакет от какого-то узла был получен до истечения времени жизни его записи, то время жизни сбрасывается в начальное значение. Нулевое значение этой характеристики указывает на то, что записи в таблице FIB не «стареют» вообще и единожды попав в таблицу, запись остается в ней навечно.

Удачи!