Конкурсы
Задачки от декана факультета компьютерных наук Ивана Аржанцева
Задачи на конкурс ко Дню программиста (PDF, 31 Кб)
Приз: за три лучших результата решения - завтрак в Яндекс.Кафе с Иваном Аржанцевым
Решения Вы можете прислать на адрес computerscience@hse.ru сканом или фото (понятным для чтения). Также решения будут приниматься на самом мероприятии в Центре решения задач (волонтеры помогут Вам найти его).
Частичные продвижения по каждой из задач также приветствуются, и при выборе победителей будут учитываться продвижения по обеим задачам.
Решения принимаются до 9:00 по почте и до 14:00 волонтерами.
Открытое тестирование по программированию
В 2014 году в конце августа мы провели тестирование студентов 1 курса образовательной программы "Прикладная математика и информатика".
Мы решили дать возможность всем желающим написать тестирование по программированию и сравнить свои результаты с результатами наших первокурсников.
Трех школьников с наивысшими результатами мы наградим подарками от факультета.
ТестированиеТакже Вы можете сравнить свои результаты с результатами наших студентов.
Конечно, мы не будем раскрывать полные результаты вместе с именами наших первокурсников, мы выкладываем лишь анонимизированную таблицу результатов.
Анонимные результаты тестирования по программированию ФКН ВШЭ 2014(XLSX, 51 Кб)
Задачки по биоинформатике
Участникам будут предложены 3 задачи по биоинформатике:
Задачка 1. Кролики и числа Фибоначчи:
В 1202 году Леонардо Пизанский (более известный как Фибоначчи) исследовал задачу о размножении кроликов. Его интересовал следующий вопрос:
сколько будет кроликов через один год, если в место, огороженное со всех сторон стеной, посадить пару новорожденных кроликов.
При этом известно, что кролики каждый месяц производят на свет новую пару кроликов.
Видно, что через месяц пара кроликов вырастет, то есть у нас все еще будет одна пара кроликов.
После этого появится на свет новая пара кроликов, и через два месяца у нас уже будет две пары кроликов.
Через три месяца будет три пары кроликов, через четыре месяца пять пар кроликов и так далее.
Оказывается, что количество кроликов через n месяцев описывается с помощью рекуррентного соотношения:
F(n+1) = F(n) + F(n-1), причем F(0) = F(1) = 1. Описываемая этим соотношением последовательность чисел называется последовательностью Фибонначи.
Теперь предположим, что раз в месяц пара кроликов производит на свет не одну пару кроликов, а k пар. Сколько пар кроликов будет через n месяцев?
Задачка 2. Законы Менделевского наследования:
В данной задаче мы поговорим о наследственных заболеваниях. Самый распространенный тип наследственных болезней --- это моногенные заболевания, то есть заболевания, вызываемые поломкой одного гена.
Как все помнят из уроков по биологии у человека первые 22 хромосомы представлены в двух аллелях, то есть у каждого гена есть две копии.
Наследование таких заболеваний хорошо описывается классическими законами Менделя, то есть огранизм независимо и с одинаковой веростностью наследует одну из аллелей от каждого из родителей.
Будем обозначать хорошую версию гена буквой a, а поломанную буквой A. В данной задаче мы требуется посчитать вероятность каждого из трех генотипов aa, aA, AA огранизма, зная генотипы предков данного организма.
А именно, задано бинарное дерево, в котором корнем является исследуемый организм, а листья представляют собой потомков, у которых известны генотипы.
Задачка 3. Поиск максимальных повторов
Одним из механизмов защиты бактерий от вирусов (бактериофагов) является CRISPR (clustered regularly interspaced short palindromic repeats) комплекс.
Механизм его работы был открыт всего несколько лет назад и позволил создать инструменты для редакторивания ДНК организмов.
Вкратце данный механизм работает следующим образом. В ДНК бактерии есть специальный участок, называемый CRISPR, который имеет особый вид. Участок состоит из большого количество повторов c небольшими разнообразными участками между ними.
Условно CRISPR выглядит следующим образом S A1 S A2 S A3 S \ldots, где S – обозначает повторы, а A_i участки между ними. Оказывается, что участки между повоторами являются небольшими кусочками разных вирусных ДНК, когда-то проникавших в предков данной бактерии. Дальше механизм работает следующим образом: данный участок ДНК транслируется в РНК, которая под воздействием белка Cas9 разрезается по границам повторов и вырезает комплементарный участок из ДНК вируса, проникшего в бактерию, тем самым убивая вирус.
Одной из актуальных проблем в данной области является поиск CRISPR участков. В данной задаче требуется написать программу, которая возволит найти максимальные повторы в заданной последовательности ДНК.
На вход дается строка X, состоящая из букв A, C, T, G длиной не более 1000 символов. Максимальным нерасширяемым повтором называется подстрока Y, которая встречается в X не менее двух раз без перекрытий, и которая не может быть расширена ни в одну из сторон. Требуется найти все максимальные нерасширяемые повторы состоящии из не менее чем 20 букв.
Школьники, показавшие лучшие результаты, получат призы от факультета. Решения принимаются до 13 сентября, 10:00
Проба Кода с Samsung
Если вам от 14 до 17 лет и у вас есть опыт создания собственной программы для ПК, мобильного приложения или сайта, продемонстрируйте их нам! До 7 сентября загрузите вашу разработку и краткое описание на сайте конкурса.
Конкурс проходит по 3 номинациям: «Приложение для ПК», «Мобильное приложение», «Сайт». Победители будут объявлены 10 сентября. Авторы лучших проектов смогут пройти бесплатное годичное обучение по программе IT ШКОЛА SAMSUNG без дополнительных вступительных испытаний.
Список конкурсов будет пополняться. Следите за обновлениями на сайте Дня программиста и в группе факультета ВКонтакте.