Всероссийская инженерная олимпиада для старшеклассников: BigData и Интеллектуальные энергетические системы

в 18:11, , рубрики: "Всегда готов!", big data, BigData, rusventure, ВДЦ "Орленок", Занимательные задачки, математика, машинное обучение, Олимпиада НТИ, олимпиады, Промышленное программирование, рвк

Всероссийская инженерная олимпиада для старшеклассников: BigData и Интеллектуальные энергетические системы - 1

— Вовочка, бросай свои эксперименты с холодным ядерным синтезом, иди к ЕГЭ готовься.
— Ща, мам.

Олимпиады — это круто. Они позволили такому раздолбаю свободолюбивому и умном, как я, поступить в университет без экзаменов.

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

— Что вы сегодня на час опоздали?
— Да так, в универ поступали.

Я очень рад, что нашлись инициативные ребята, которым не все равно, что талантливый школьник-инженер тратит свои последние беззаботные годы, судорожно готовясь к сдачи ЕГЭ, вместо того, чтобы строить реактивные ранцы или программировать зародыш искусственного интеллекта.

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

Недавно в ВДЦ «Орленок» прошел «тест-драйв» Всероссийской инженерной олимпиады. Участвовали 5000 детей со всей России, до финала дошли около 100 человек. Призов много, но самое полезное — по +10 очков к ЕГЭ.

Я за всем присматривал и готов поделиться своими впечатлениями.

Олимпиада шла по четырем профилям.

Про первые два профиля расскажу здесь (чуток задач и фоток), про вторые два — немного попозже на GT.

Организация

Олимпиада состояла из двух заочных этапов и двух очных (индивидуальный и командный).

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

Однако есть определенные критерии, определением которых занимается организация под названием Российский совет олимпиад школьников (РСОШ), которые накладывают определенные рамки: задачи должны быть предметными, работы — индивидуальными, и не даже не думайте пользоваться интернетом.

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

В общем, после окончания олимпиады организаторы две недели готовили «кирпич» на 1000 страниц с описанием всего, что только можно, отправили в РСОШ и теперь сидят на низком старте, чтобы начать готовить олимпиаду следующего года. Официальный ответ будет 1 сентября, но орги рисковые ребята и начнут писать задачи и готовить лекции с хакатонами уже летом.

Итоги Олимпиады — nti-contest.ru/results2016
Мануал на 400 страниц по олимпиаде лежит тут.

Орленок

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

Встречают вас «противотанковыми ежами»
Всероссийская инженерная олимпиада для старшеклассников: BigData и Интеллектуальные энергетические системы - 2

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

Учебно-боевой самолет

Всероссийская инженерная олимпиада для старшеклассников: BigData и Интеллектуальные энергетические системы - 4

Всероссийская инженерная олимпиада для старшеклассников: BigData и Интеллектуальные энергетические системы - 5
Рядом с корпусом «Космический»

Всероссийская инженерная олимпиада для старшеклассников: BigData и Интеллектуальные энергетические системы - 6
Сразу вспомнился Кастанеда

Всероссийская инженерная олимпиада для старшеклассников: BigData и Интеллектуальные энергетические системы - 7

Big Data

Немного о том, что было на треке по большим данным и машинному обучению.

image

image
Это Иван. Он большой и добрый. Он читал мастер-класс по питону, рассказывал про числодробилки и о том, какие задачи человек решает лучше чем компьютер (принадлежность точки к группе, например)

Первый отборочный этап

Первый отборочный этап

Первый отборочный тур проводится индивидуально в сети интернет, работы оцениваются автоматически средствами системы онлайн-тестирования. На решение задач первого отборочного этапа участникам давалось 3 недели. Решение каждой задачи дает определенное количество баллов. Для всех участников предлагается общий набор задач, но за решение задач участникам разных уровней (9 класс или 10-11 класс) давались разные баллы. Баллы зачисляются в полном объеме за правильное решение задачи. Участники получают оценку за решение задач в совокупности по всем предметам данного профиля (математика и информатика) — суммарно от 0 до 20 баллов.

Примеры задач:
Задача по математике 1.1.6 (1 балл)
Незадачливый космонавт Иннокентий почувствовал себя плохо после центрифуги и не может определить направление, он находится в 5 метрах от комиссии и движется по прямой. Каждую секунду он с равной вероятностью либо приближается на метр к ней, либо отдаляется. Если он дошел до комиссии, то больше уже никуда не идет. Найдите вероятность попадания в руки комиссии не позже чем на 10-й секунде.

Решение

Изобразим путь космонавта на графике. По вертикальной оси отложим время, а по горизонтальной расстояние. Изначально космонавт находится в точке s=0, а комиссия в точке s=5.

На рисунке обозначен путь для последовательности ППЛПППП:

Всероссийская инженерная олимпиада для старшеклассников: BigData и Интеллектуальные энергетические системы - 10

Заметим также, что космонавт может прийти к комиссии только на нечетных шагах.
Таким образом, нас интересует, сколько существует путей, ведущих к комиссии за 5, 7 и 9 секунд.
Переформулируем задачу: сколько существует путей, по сетке на рисунке ниже, ведущих к прямой s=5. Ходить можно только двигаясь вверх.

Всероссийская инженерная олимпиада для старшеклассников: BigData и Интеллектуальные энергетические системы - 11

Посчитаем количество таких путей для каждой точки, начиная от начальной.

Всероссийская инженерная олимпиада для старшеклассников: BigData и Интеллектуальные энергетические системы - 12

За 5 шагов приводит 1 путь, за 7 — 5 путей, за 9 — 20 путей.

Значит искомая вероятность равна 1/32+5/128+20/512 = 7/64

Ответ: 7/64

Задача по информатике 1.2.2 «Корни» (3 балла)
У мальчика Пети есть число N. Но оно ему не нужно, в отличие от числа X. Чтобы его получить Петя может брать целочисленный корень, умножать и складывать числа.

Целочисленным корнем степени k из натурального числа n будем называть наибольшее натуральное число, для которого выполняется соотношение:Всероссийская инженерная олимпиада для старшеклассников: BigData и Интеллектуальные энергетические системы - 13 Например, целочисленным корнем пятой степени из тысячи будет тройка, так как Всероссийская инженерная олимпиада для старшеклассников: BigData и Интеллектуальные энергетические системы - 14 Обозначим это как Всероссийская инженерная олимпиада для старшеклассников: BigData и Интеллектуальные энергетические системы - 15 Также будем считать, что степенью корня могут быть только натуральные числа.

Для Пети взятие целочисленного корня — тяжёлая задача, и он хочет минимизировать суммарную степень корней, которые встречаются в формуле получения X.

А ещё у Пети есть старший брат. Которого зовут Дима. Этот Дима решил добавить интереса задачке Пети, и дать такие ограничения:

  1. Пете нельзя брать корни от чисел, отличных от N.
  2. Можно перемножать только те числа, которые Петя получил с помощью операции взятия корня или умножения других чисел.
  3. Складывать можно числа, которые получены как результат умножения, взятия корня или суммы других чисел.

Помогите Пете написать выражение, которое будет легко считаться и подходит под ограничения, наложенные Димой. Найдите минимальную сложность искомого выражения.

Формат входных данных:
В единственной строке даны два целых числа N и X Всероссийская инженерная олимпиада для старшеклассников: BigData и Интеллектуальные энергетические системы - 16

Пример ввода:
100 126

Формат выходных данных:
Выведите единственное натуральное число — ответ на задачу.

Пример вывода:
9

Пояснение к примеру: Всероссийская инженерная олимпиада для старшеклассников: BigData и Интеллектуальные энергетические системы - 17

Способ оценки работы
Для генерации уникального условия и проверки результата используется следующий код на языке Python. Функция generate возвращает условие варианта и правильный ответ:

def generate():
      return [('{} {}n'.format(n, x), ans) for n, x, ans in [
(100, 126, 9),
(10, 10, 1),
(1000, 1000, 1),
(1, 1, 1),
(1, 1000, 1000),
(1000, 1, 10),
(1000, 999, 17),
(722, 966, 16),
(774, 717, 21),
(664, 177, 16),
(655, 657, 7),
(659, 65, 9),
(901, 559, 21),
(813, 314, 18),
(528, 131, 16),
(882, 258, 19),
(516, 583, 12),
(801, 767, 19),
(147, 222, 11),
(67, 743, 13),
(413, 335, 21),
(453, 467, 7),
(600, 104, 9),
(323, 209, 19),
(462, 822, 18),
(126, 743, 16),
(77, 917, 17),
(100, 999, 27),
(1, 999, 999),
(1000, 894, 29),
(999, 712, 28),
(123, 944, 24),
(432, 277, 24),
(945, 616, 28),
(100, 999, 27),
(1000, 894, 29),
(999, 712, 28),
(123, 944, 24),
(432, 277, 24),
(945, 616, 28)
]]

def check(reply, clue):
      return int(reply.strip()) == int(clue)
Решение

Решение состоит из трёх этапов. На первом этапе нужно составить набор степеней и корней из N, которые может быть выгодно использовать. Если два корня с разной степенью равны, то нам выгодно использовать тот из них, степень которого меньше. Так как 210 > 1000, то для любого N будет не более 11 различных корней. На втором этапе методом динамического программирования получаем список чисел, которые можно получить перемножением корней с оптимальной суммарной степенью. На третьем этапе используя тот же метод получается список чисел, которые можно получить сложением чисел с предыдущего этапа с оптимальными суммами.

Пример программы, реализующей данный алгоритм на языке Python:

1. import sys
2.
3. INF = int(1e9)
4.
5. def getRoots(n, mx):
6.       ans = [INF, n]
7.       for x in range(n, 1, -1):
8.            while x ** len(ans) <= n:
9.                  ans.append(x)
10.                ans.append(1)
11.                 roots = dict()
12.                for i in range(len(ans)):
13.                     if ans[i] != ans[i - 1] and ans[i] <= mx:
14.                          roots[ans[i]] = i
15.    return roots
16.
17. def getProducts(roots, mx):
18.       ans = dict()
19.       ans[1] = 0
20.       for i in range(2, mx + 1):
21.            ans[i] = INF
22.            for k, v in roots.items():
23.                 if i % k == 0:
24.                    d = i // k
25.                    if d in ans and ans[d] + v < ans[i]:
26.                        ans[i] = ans[d] + v
27.            if ans[i] == INF:
28.                ans.pop(i, None)
29.      ans[1] = roots[1]
30.      prods = [(k, v) for k, v in sorted(ans.items())]
31.      return prods
32.
33. def getSums(prods, mx):
34.       ans = [INF] * (mx + 1)
35.       ans[0] = 0
36.       for i in range(len(ans)):
37.            for k, v in prods:
38.                 if k > i:
39.                     break
40.                 if ans[i - k] + v < ans[i]:
41.                     ans[i] = ans[i - k] + v
42.       ans[0] = INF
43.       return ans
44.
45. def solve(dataset):
46.       n, x = list(map(int, dataset.strip().split()))
47.       roots = getRoots(n, x);
48.       prods = getProducts(roots, x)
49.       ans = getSums(prods, x)
50.       return str(ans[x])
51.
52. solve(sys.stdin.read())

Второй отборочный этап

Второй отборочный этап

Всероссийская инженерная олимпиада для старшеклассников: BigData и Интеллектуальные энергетические системы - 18

Второй отборочный этап проводится в командном формате в сети интернет, работы оцениваются автоматически средствами системы онлайн-тестирования. Продолжительность второго отборочного этапа составляет 2 недели. Задачи носят междисциплинарный характер
и в более простой форме воссоздают инженерную задачу заключительного этапа. Решение задач предполагало написание программ, допускалось использовать язык программирования Python. Решение каждой задачи дает определенное количество баллов. В данном этапе можно получить суммарно от 0 до 45 баллов.

Задачи по анализу данных

Задача 2.1.1 (10 баллов)
В летний лагерь приехало 1000 школьников. Когда школьник приезжал, его сразу переписывали (ставили порядковый номер начиная с нуля — каким школьник приехал в лагерь). Школьников сразу разбивали по отрядам с разным количеством человек в отряде:
первые n1 школьников определили в первый отряд, следующие n2 школьников — во второй отряд, следующие n3 — в третий и так далее.
Однажды все четные отряды увезли на экскурсию. И в лагерь приехала комиссия и переписала всех школьников, которые остались (каждый школьник назвал номер, каким его записали, когда он приехал в лагерь). По ошибке некоторых школьников переписали несколько раз. Как теперь разобраться, какой школьник в каком отряде?

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

За успешное решение задачи участники получают 10 баллов.

Пример ввода:
790 443 801 518 63 75 491 91… 420 371 89 389 453 488 892 932

Пример вывода:
[(0, 92), (93, 343), (344, 521), (522, 772), (773, 999)]

Ограничение по времени исполнения программы: 15 с

Ограничение по использованию оперативной памяти: 256 Мб

Решение есть тут на странице 174.

Задача 2.1.2 (15 баллов)
Картограф составлял для каждого города список городов, с которыми он связан
дорогами. Теперь его спрашивают о том, можно ли проехать между двумя далекими
городами.

На вход подается два названия города, которые нужно проверить и дальше идет идет
перечисление для городов, с какими другими городами он связан дорогой. Ответ необходимо
давать в формате True и False.

За успешное решение задачи участники получают 15 баллов.

Пример ввода:
{'find': ('d', 'f'), 'd': ['a', 'b', 'c', 'e', 'f', 'g'], 'b': ['a', 'c',
'd', 'e', 'f', 'g'], 'q': ['n', 'o', 'p', 'r', 's', 't', 'u'], 'f': ['a', 'b',
'c', 'd', 'e', 'g'], 'a': ['b', 'c', 'd', 'e', 'f', 'g'], 's': ['n', 'o', 'p',
'q', 'r', 't', 'u', 'c'], 'e': ['a', 'b', 'c', 'd', 'f', 'g'], 'u': ['n', 'o',
'p', 'q', 'r', 's', 't'], 'r': ['n', 'o', 'p', 'q', 's', 't', 'u'], 'p': ['n',
'o', 'q', 'r', 's', 't', 'u'], 'c': ['a', 'b', 'd', 'e', 'f', 'g'], 'g': ['a',
'b', 'c', 'd', 'e', 'f'], 'o': ['n', 'p', 'q', 'r', 's', 't', 'u'], 'n': ['o',
'p', 'q', 'r', 's', 't', 'u'], 't': ['n', 'o', 'p', 'q', 'r', 's', 'u']}

Ограничение по времени исполнения программы: 3000 с
Ограничение по использованию оперативной памяти: 256 Мб

Решение есть тут на странице 178.

Задача 2.1.3 (0-20 баллов)
В задаче фигурирует придуманный нами граф социальной сети (для каждого пользователя указано, какие пользователя добавили его в друзья). Для каждого пользователя вычисляется его популярность, она основана на том, сколько людей дружит с теми пользователями, с которым он дружит.

Популярность вычисляется как X — суммарное количество людей, которые дружат с его друзьями, считая его самого.
Необходимо рассчитать два перцентиль 50 и 90, т.е. два наименьших значения популярности такие, что с вероятностью 50% для первого и 90% для второго популярность случайного пользователя будет меньше данного значения.

Задачу необходимо решить у себя на компьютере и в систему загрузить решение в виде двух чисел для каждой задачи.

Если для всех тестов вы посчитали хотя бы перцентиль 50 (с вероятностью 50 процентов популярность окажется меньше), то вы получаете половину баллов от задачи.

Пример ввода:
[{0: [5, 8], 1: [7, 2], 2: [8], 3: [10, 0], 4: [0, 10, 2, 1], 5: [1, 5,
3, 7], 6: [7, 3, 0], 7: [12, 13, 0, 8], 8: [8, 11], 9: [6, 2, 13], 10: [13], 11:
[2, 0, 8], 12: [0, 13], 13: [4, 11, 8], 14: [0, 4, 12, 2]}, {0: [14, 11], 1: [7,
14, 1], 2: [0], 3: [10], 4: [13], 5: [8, 0], 6: [5, 3], 7: [2, 11, 8, 10], 8:
[3, 10, 14, 7], 9: [0, 11, 7, 4], 10: [1, 7], 11: [10, 5, 12, 4], 12: [14, 5],
13: [7, 6, 3, 1], 14: [10, 6, 0, 8]}]

Пример вывода:
[(4, 6), (7, 9)]

Ограничение по использованию оперативной памяти: 256 Мб
Время одной попытки: 5 мин

Решение есть тут на странице 186.

Заключительный этап

Заключительный этап: индивидуальная и командные части

Всероссийская инженерная олимпиада для старшеклассников: BigData и Интеллектуальные энергетические системы - 19
А это школьники, которых неоднократно побеждал в футбол встречал в лагерях GOTO и на хакатоне.

Заключительный этап олимпиады состоит из двух частей: индивидуальное решение задач по предметам (математика, информатика) и командное решение инженерное задачи. На индивидуальное решение задач дается по 2 часа на один предмет. Задачи по математике и информатике общие на параллели 9 и 10-11 класс. Решение каждой задачи дает определенное количество баллов (см. критерии оценки далее). По математике за каждую задачу можно получить от 0 до указанного количества баллов в соответствии с описанными критериями.

Баллы по информатике зачисляются в полном объеме за правильное решение задачи.

Решение задач по информатике подразумевало написание задач на языке Python. Участники получают оценку за решение задач в совокупности по всем предметам данного профиля (математика и информатика) — суммарно от 0 до 24 баллов.

Задание по математике 3.1.1в (2 балла).
Группа граждан страны А эмигрировала в страну Б, а группа граждан Б – в страну В. В результате этого рейтинги каждой страны оказались выше первоначальных. После этого направление миграционных потоков изменилось на противоположное — часть жителей В переехала в Б, а часть жителей Б – в А. Оказалось, что в результате рейтинги всех трех стран опять выросли (по сравнению с теми, которые были после первого переезда, но до начала второго). (Так, во всяком случае, утверждают информационные агентства этих стран.) Может ли такое быть (если да, то как, если нет, то почему)? (Предполагается, что за рассматриваемое время Q граждан не изменилось, никто не умер и не родился.)

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

  • у всех, кто в этом сообществе, меньше половины друзей были в нем же;
  • у всех, кто не в этом сообществе, не меньше половины друзей были в нем.

Всегда ли им удастся создать такое сообщество?
(Предполагается, что пользователи не сами вступают в сообщество, а распределяются администрацией социальной сети)

Решение есть тут на странице 191.

Задача по информатике 3.2.4 «Итоговая аттестация» (3 балла)
Конец года — беспокойное время не только для школьников, которые готовятся к экзаменам, но и для составителей экзаменационных заданий. Составляя любой тест, необходимо учитывать, насколько сложной будет задача для школьников, и определить, сколько учащихся сдадут тест успешно.

В этом году было решено провести тестовый экзамен, пригласив 100 учеников разных школ решить 5 задач. Каждая задача оценивается в ai баллов. Задача либо решена на полный балл, либо не решена совсем, а значит за нее не начисляются баллы. Частичные решения проверяющие не учитывают. После экзамена составители получили результаты школьников. Для каждого школьника известны результаты проверки всех задач.
Необходимо посчитать, сколько школьников получит не менее K баллов, если экзамен будут сдавать 1000000 школьников.

Обратите внимание, что невозможно достаточно надежно найти вероятность решить определенный набор задач, но будем считать, что возможно достаточно надежно оценить вероятность решить одну задачу.

Формат входных данных:
В первой строке дано число K — число баллов, необходимое для успешной сдачи теста. Во второй строке 5 натуральных чисел — баллы за задачи. Первое число соответствует баллам за первую задачу, второе — за вторую и так далее. Далее следует 100 строк. В каждой строке 5 чисел, обозначающих, решена ли соответствующая по номеру задача или нет. На первом месте в строке указано решена ли первая задача, на втором решена ли вторая, и так далее. Если задача решена, то в строке будет указана 1, если нет — 0.

Формат выходных данных:
В единственной строке выведите ожидаемое число людей, которые успешно сдадут тот же тест если решать его будет 1000000 школьников.

Решение есть тут на странице 200.

Командная часть

Всероссийская инженерная олимпиада для старшеклассников: BigData и Интеллектуальные энергетические системы - 20

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

Участники должны были писать программы на языке Python. Продолжительность командной части заключительного этапа — 3 дня (всего 18 астрономических часов). Участники имели доступ к сети Интернет и могли пользоваться своими телефонами и ноутбуками.
Всего командам предлагалось 3 задачи — по одной на каждый день. Условие задачи становилось известно участникам утром соответствующего дня. Для каждой задачи было подготовлено два подграфа реальной социальной сети «Одноклассники»:

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

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

Описание исходных данных
Во всех задачах участникам предоставлялся граф пользователей (связи между пользователями) и файл с демографией (анонимизированные данные по каждому пользователю).

Граф пользователей
Граф сохранен в формате разреженной матрицы, где по каждой связи есть информация о ее типе (родственник, друг и т.д.) в виде битовой маски. Каждая строка матрицы соответствует друзьям одного пользователя и имеет формат:
ID_пользователя1 {(ID_друга1, маска1), (ID_друга2, маска2),…}

Матрица партиционирована по ID пользователя на 16 файлов, каждый из которых сжат стандартным протоколом сжатия GZip.
Пары в списке связей отсортированы по ID друга (по возрастанию). Пример записей из графа:
102416
{(5362439,0),(7321627,0),(7345280,0),(9939258,0),(9976393,0),(11260492,0),
(11924364,0),(16498676,0),(16513827,0),(21716731,0),(21826340,0),(23746537,0),
(23751503,0),(24412936,0),(24423533,0),(30287856,0),(32321147,0),(34243036,0),
(37592142,0),(39485706,0),(41505243,0),(42791620,0),(52012206,0),(52671472,0),
(54652307,0),(57293803,0),(59242794,0),(59252048,0),(62535397,0),(62563866,0),
(62567154,0),(64588902,0)}
102608
{(4167808,32784),(6019974,32),(6152844,16),(9570536,64),(10699806,33),
(13290514,0),(15064491,128),(16432948,512),(24473204,0),(24655822,0),
(25833075,256),(28000951,64),(30834507,2048),(34567533,16),(35766667,0),
(37385121,0),(40123805,512),(43134386,1024),(45439608,0),(45484652,0),
(47562525,0),(52378153,256),(52403136,512),(52493894,1024),(53483990,0),
(54048767,0),(54286279,2048),(57401158,0),(57956631,0),(58183281,0),
(61117236,32),(61898065,0),(61936634,0),(64512205,512),(65014849,0),
(65112662,0),(65259449,0)}

В маске связи могут быть установлены следующие биты:

  • Любовь
  • Супруг или Супруга
  • Родитель
  • Ребенок
  • Брат или сестра
  • Дядя или тетя
  • Родственники
  • Близкие друзья
  • Коллеги
  • Одноклассники
  • Племянник
  • Дед или бабушка
  • Внук или внучка
  • Однокурсник
  • Дружба в армии
  • Приемный родитель
  • Приемный ребенок
  • Крестный отец
  • Крестный сын
  • Совместная игра в спортивные игры

Помимо перечисленных битов в маске отношений может быть установлен, а может и не быть установлен нулевой бит. Этот бит играет чисто техническую роль и не имеет физического смысла. В итоге, например, отношение типа Ребенок может кодироваться числами 16 или 17.

Данные были подготовлены с использованием инструмента для хранения больших данных Apache Pig и содержат два соответствующих файла с заголовками, позволяющие участникам использовать этот инструмент и для предварительной обработки/фильтрации данных.

Демография пользователей
Данные о демографии предоставлены для того же миллиона пользователей, что и информация о социальных связях в формате списка атрибутов:
userId create_date birth_date gender ID_country ID_Location loginRegion
где:

  • userId – идентификатор пользователя
  • create_date – дата создания пользовательского аккаунта (количество миллисекунд от 01.01.1970)
  • birth_date – дата рождения пользователя (количество дней от 01.01.1970, может быть отрицательным!)
  • gender – пол пользователя (1 – мужчины, 2 – женщины)
  • ID_country – идентификатор страны, указанной в профиле
  • ID_Location – идентификатор региона/города, указанный в профиле.
  • loginRegion – идентификатор региона, откуда чаще всего авторизуются в данной социальную сети пользователь (может отсутствовать!)

Пример данных:
44053078 1166032023073 3067 1 10414533690 2423601 99
12495764 1177932393270 1138
2 10405172143 188081
25646929 1165304175170 3756 2 10414533690 3953941 22
25646999 1160728984480 3884 2 10414533690 241372 120
12495833 1176909723643 3363 2 10414533690 2724941 11

Демография партиционирована по той же схеме, что и граф, но не сжата (передается в виде открытых текстов). Так же может быть обработана с помощью стандартного инструмента хранения больших данных Apache Pig или любого другого инструмента, поддерживающего CSV.

Задачи

Задача 4.2.1 «Дата рождения»
Представленный для анализа фрагмент социального графа включает информацию о связях 100 тысяч пользователей, попавших в двухшаговую окрестность сотни случайно выбранных пользователей. Участникам предоставляются файлы графа социальной сети со всеми связями и файл демографии, в котором указан данные по пользователям, включая возраст, однако возраст указан не для всех пользователей.

По пользователям которые присутствуют в графе, но не присутствуют в демографии необходимо установить значение их атрибута birth_date (дату рождения).

Данные записываются в файл в формате:
(<id_ползователя>t(знак табуляции)<birth_date>)

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

Базовое решение задачи на стр 208.

Задача 4.2.2 «Регион»
Представленный для анализа фрагмент социального графа включает информацию о связях 100 тысяч пользователей, попавших в двухшаговую окрестность сотни случайно выбранных пользователей. Участникам предоставляются файлы графа социальной сети со всеми связями и файл демографии, в котором указан данные по пользователям, включая регион, однако регион указан не для всех пользователей.

По пользователям которые присутствуют в графе, но не присутствуют в демографии необходимо установить их аттрибут ID_Location (регион).

Ответ записывается в текстовый файл в формате:
(<id_ползователя>t(знак табуляции)<ID_Location>)

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

Базовое решение задачи на стр 213.

Задача 4.2.3 «Поиск связей»
Представленный для анализа фрагмент социального графа включает информацию о связях 1 миллиона пользователей, попавших в двухшаговую окрестность сотни случайно выбранных пользователей. Участникам предоставляются файлы графа и демографии по пользователям. Часть связей в предоставленном социальном графе скрыта и задачей участников является максимально полно и точно раскрыть их.

Сокрытие связей коснулось только пользователей из исходного миллиона, остаток от деления аттрибут ID которых на 11 равен 7 (id % 11 == 7), сокрытию подверглось порядка 10% связей для каждого из этих пользователей. Были скрыты только ведущие в исходный миллион связи.

В прогнозе достаточно восстановить наличие связи, ее тип не важен. Результаты прогноза нужно представить в формате CSV файла вида:
ID_пользователя1 ID_кандидата1.1 ID_кандидата1.2 ID_кандидата1.3
ID_пользователя2 ID_кандидата2.1 ID_кандидата2.2

Записи в файле отсортированы по ID пользователя (по возрастанию), а затем по предсказанной релевантности кандидатов (по убыванию, саму релевантность при этом в файл писать не надо). Пример результатов:
5111 178542 78754
18807 982346 1346 57243

Результаты участников оцениваются с помощью метрики Нормализованной скидочной совокупной выгоды (Normalized Discounted Cumulative Gain, NDCG), используемой в индустрии для оценки точности работы алгоритма для этой и аналогичных ей задач. Метрика рассчитывается отдельно по каждому из пользователей, для которых есть скрытые связи, а затем усредняться. Записи в файле результата, не имеющие отношения к
пользователям со скрытыми связями, при оценке результата учитываться не будут. Если по какому-то пользователю не будет предложено ни одного кандидата, то значение метрики для него будет считаться за 0.

Базовое решение задачи на стр 216.

image
Как бы мне выстроить непротиворечивую онтологию?

Всероссийская инженерная олимпиада для старшеклассников: BigData и Интеллектуальные энергетические системы - 22
Победители — команда «Математическое ожидание».

  • Жидков Всеволод, МБОУ «Воткинский лицей» (Воткинск), 8 класс
  • Татосьян Владимир, ГБОУ лицей №1568 им. Пабло Неруды (Москва), 9 класс
  • Шехирин Алексей, МБОУ гимназия №21 (Архангельск), 9 класс

Интеллектуальные энергетические системы

«А мы им еще потом неожиданно отключим центральную ЛЭП»
— организаторы

image

Первый отборочный этап

Первый отборочный этап

Первый отборочный тур проводится индивидуально в сети интернет, работы оцениваются автоматически средствами системы онлайн-тестирования. Для каждого из параллелей (9 класс или 10-11 класс) предлагается свой набор задач по физике, задачи по математике общие для всех участников. На решение задач первого отборочного этапа участникам давалось 3 недели. Решение каждой задачи дает определенное количество баллов. Баллы зачисляются в полном объеме за правильное решение задачи. Участники получают оценку за решение задач в совокупности по всем предметам данного профиля (математика и физика) — суммарно от 0 до 20 баллов.

Задача по физике 1.3.4 (5 баллов)
Сопротивление реостата определяется углом поворота ручки в пределах от 0˚ до 180˚ градусов. При нуле (крайнее правое положение) реостат имеет сопротивление 100 Ом, при максимальном угле поворота (крайнее левое положение) — 500 Ом. Найдите положение ручки реостата, при котором показания амперметра в приведенной схеме будут нулевыми.

Всероссийская инженерная олимпиада для старшеклассников: BigData и Интеллектуальные энергетические системы - 24

Запишите сопротивление реостата в этом положении, с точностью до сотых.

Второй отборочный этап

Второй отборочный этап

Второй отборочный этап проводится в командном формате в сети интернет, работы оцениваются автоматически средствами системы онлайн-тестирования. Продолжительность второго отборочного этапа — 2 недели. Задачи носят междисциплинарный характер и в более
простой форме воссоздают инженерную задачу заключительного этапа. Решение каждой задачи дает определенное количество баллов. Баллы зачисляются в полном объеме за правильное решение задачи. В данном этапе можно получить суммарно от 0 до 8 баллов.

Пример задач:
Задача по энергетике 2.1.4 (3 балла)
Вам нужно выбрать оптимальные параметры для некоторой (несуществующей) электростанции. Ее КПД можно весьма точно оценить по формуле:
Всероссийская инженерная олимпиада для старшеклассников: BigData и Интеллектуальные энергетические системы - 25
Параметрами x и y вы можете управлять. Значения x ограничены от 1 до 3, значения y — от 2 до 5.

Найдите такие значения параметров x и y, при которых КПД электростанции будет оптимальным при следующих параметрах a и b. Дайте ответ с точностью до третьего знака после запятой.

Пример входных данных:
a = 4.03 b = 74.64

Решение

КПД условной электростанции желательно должен быть максимально большим, таким образом, при заданных значениях параметров a и b задача сводится к отысканию максимума функции КПД.
Поскольку при решении задачи можно дать решение с точностью до третьего знака, задача может быть решена численно. Например, в MS Excel или с помощью написания простой программы эта задача может быть решена напрямую построением таблица значений функции КПД на сетке значений дискретных переменных с дальнейшим нахождением наибольшего из значений функции.
Таким образом можно найти, что КПД максимально при значениях x = 2,082; y = 4,981.

Заключительный этап

Заключительный этап: индивидуальная и командная части

Аппаратная часть задачи

Каждой команде выдавался комплект, содержащий набор проводов и инструментов для разводки будущей электрической сети.
Всероссийская инженерная олимпиада для старшеклассников: BigData и Интеллектуальные энергетические системы - 26
С помощью этого комплекта участники должны были решить следующие задачи: подготовка проводов, разводка сети, определение корректности подключения и тестирование линии, обработка способа подключения элементов сети.

Всероссийская инженерная олимпиада для старшеклассников: BigData и Интеллектуальные энергетические системы - 27

Целью выполнения командного задания финального этапа Олимпиады является разработка такой локальной энергетической системы, которая позволила бы обеспечить максимально надежное электроснабжение заданного числа потребителей с учетом их категорийности и географического положения при минимальных затратах на ее создание и обеспечение топливно-энергетическими ресурсами, а также оперативное диспетчерское управление этой энергосистемой с целью обеспечения максимальной надежности электроснабжения заданных потребителей в условиях неопределенности климатических условий и реализации риска системной аварии и перехода на полностью локальное
энергоснабжение (сценарий «айлендинга»).

Командное задание финального этапа состоит из трех этапов:
Всероссийская инженерная олимпиада для старшеклассников: BigData и Интеллектуальные энергетические системы - 28

Цифро-натурный стенд игры «Энергосистема»
Всероссийская инженерная олимпиада для старшеклассников: BigData и Интеллектуальные энергетические системы - 29
Серая штука — большой вентилятор, «создает» ветер.

Элементы стенда

Всероссийская инженерная олимпиада для старшеклассников: BigData и Интеллектуальные энергетические системы - 30

Всероссийская инженерная олимпиада для старшеклассников: BigData и Интеллектуальные энергетические системы - 31

Всероссийская инженерная олимпиада для старшеклассников: BigData и Интеллектуальные энергетические системы - 32

Всероссийская инженерная олимпиада для старшеклассников: BigData и Интеллектуальные энергетические системы - 33

Всероссийская инженерная олимпиада для старшеклассников: BigData и Интеллектуальные энергетические системы - 34

Всероссийская инженерная олимпиада для старшеклассников: BigData и Интеллектуальные энергетические системы - 35

Всероссийская инженерная олимпиада для старшеклассников: BigData и Интеллектуальные энергетические системы - 36

Всероссийская инженерная олимпиада для старшеклассников: BigData и Интеллектуальные энергетические системы - 37

Третий этап производится в установленном рядом со стендом диспетчерском центре, представляющим собой подключенный к стенду компьютер с установленной игровой программой, имеющей пользовательский интерфейс (рис. 3, 4). Управляющие воздействия на третьем этапе выполнения задания вводятся в игровую программу при помощи пользовательского интерфейса, при этом команда не имеет доступа к стенду и права производить манипуляции на стенде.

Всероссийская инженерная олимпиада для старшеклассников: BigData и Интеллектуальные энергетические системы - 38
Интерфейс игровой программы игры «Энергосистема». Страница диспетчерского управления энергосистемой

Задание содержит открытую часть, известную командам, и закрытую часть, известную только членам жюри и техническим сотрудникам – инженерам стенда.
Задание включает в себя следующие сведения, сообщаемые командам:

  • Число потребителей с указанием категории надежности их электроснабжения;
  • Число и тип заданных объектов электрических сетей на территории;
  • Географическое положение («геометрию») всех заданных объектов на территории;
  • Климатические условия на территории с точностью до климатической зоны, средних значений скорости ветра и солнечной интенсивности на территории;
  • Правила игры «Энергосистема».

Задание включает в себя следующие сведения, известные только членам жюри и техническим сотрудникам:

  • Графики потребления каждого из потребителей по игровым тактам,
  • Сила ветра и солнечная интенсивность по игровым тактам,
  • График снабжения энергосистемы по магистральной ЛЭП и такт ее аварийного отключения.

Каждая команда проектирует одну энергосистему, монтирует ее, затем играет в две игры с разными условиями («пресетами»). В каждой игре 10 тактов длительностью 1 минута каждый. «Пресеты» в виде фрагмента программного кода вносятся техническим специалистом перед началом работы команд. Расчет игровых баллов за каждую из игр выполняется программой автоматически. Все действия команд и результаты игр фиксируются автоматически в виде игровых логов.

Правила игры «Энергосистема»

Игровое задание
В вашей энергосистеме вам будут заданы потребители электроэнергии, их тип, число, максимальная потребляемая мощность:
Всероссийская инженерная олимпиада для старшеклассников: BigData и Интеллектуальные энергетические системы - 39

Все потребители закреплены на стенде, их место менять нельзя.
Основным элементов энергосистемы является главная подстанция (ГПС), ее положение задано на стенде, его менять нельзя. ГПС имеет три реклоузера – точки подключения линий электропередач (ЛЭП), каждую из которых можно включать и отключать независимо от других.

К ГПС с материка подключена магистральная линия, питающая город. Максимальная мощность, приходящая по ЛЭП – 25 МВт.

Объекты энергосистемы, которые можно ставить на стенд
Всероссийская инженерная олимпиада для старшеклассников: BigData и Интеллектуальные энергетические системы - 40

Кроме того, для работы дизельных генераторов может быть закуплено дизельное топливо: только один раз перед началом управления энергосистемой, не более 30 тонн с шагом в 1 тонну, цена – 2 балла за тонну.

Изначально каждая команда получает 15 км ЛЭП (15 метров кабеля) бесплатно, плата за каждый километр сверх выданных 15 км – 2 балла.
Каждая команда получает в начале игры 500 баллов.

Дизельные генераторы и накопители можно устанавливать только на ГПС. Можно установить в сумме не более 3-х дизельных генераторов и накопителей.

Диспетчерское управление энергосистемой
Диспетчерское управление энергосистемой проводится в течение 10 тактов по 1 минуте на такт. Каждый такт моделирует 6 часов работы энергосистемы.

На каждом такте вводятся настройки на следующий такт, затем за 5 секунд до конца такта они сохраняются, на следующем такте на все время такта выдается текущая ситуация (включение и отключение линий и т.д.), вводятся настройки на следующий такт.

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

Действия при управлении

  • Включение и выключение линий электропередач на ГПС или ПС
  • Изменение мощности дизельных генераторов
  • Выдача предписания потребителю 2-й категории о снижении мощности потребления через такт (потребитель снизит мощность до 0,5 МВт на такте N+2)

Что видит команда при управлении

  • Схему сети (топология – каждый объект, на какой он линии)
  • Текущее потребление по каждому потребителю и по системе в целом
  • Прогноз потребления на такт N+1 по каждому потребителю и по системе в целом
  • Точность прогноза – 95%
  • Какие линии включены/отключены
  • Текущее значение и прогноз мощности по энергомосту
  • Текущее значение и прогноз по скорости ветра и солнечной освещенности
  • Текущее значение генерации по каждой солнечной батарее и по каждому ветрогенератору
  • Текущий заряд каждого накопителя
  • Текущая мощность каждого дизеля
  • Суммарный остаток топлива
  • Предписание заводам
  • Таймер – сколько осталось до конца такт

Расчет баллов
За каждый такт, на котором все потребители были снабжены электроэнергией (подключены) без снижения мощности начисляется по 5 баллов.

Штрафы
Штрафы начисляются (вычитаются из суммы оставшихся и полученных фишек) за отключение потребителей по следующим правилам:
Всероссийская инженерная олимпиада для старшеклассников: BigData и Интеллектуальные энергетические системы - 41

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

Всероссийская инженерная олимпиада для старшеклассников: BigData и Интеллектуальные энергетические системы - 43
Ажиотаж на финале.

Всероссийская инженерная олимпиада для старшеклассников: BigData и Интеллектуальные энергетические системы - 44
Победители — команда «1314».

  • Жиганов Даниил, ГБОУ школа №2090 (Москва), 11 класс
  • Михалин Дмитрий, ГБОУ школа №2090 (Москва), 10 класс
  • Николич Николай, ГБОУ школа №2090 (Москва), 11 класс
  • Рязанов Федор, ГБОУ школа №2090 (Москва), 11 класс

Итог

Несмотря на все тяготы (картошка на завтрак, на обед и на ужин) и лишения (нельзя купаться в море и загорать), все выжили.

Старшеклассники получили дипломы
Всероссийская инженерная олимпиада для старшеклассников: BigData и Интеллектуальные энергетические системы - 45

И космический сухпаек от ОРКК
image

Люди в пиджаках решали дальнейшую судьбу олимпиады и образования в целом.
Всероссийская инженерная олимпиада для старшеклассников: BigData и Интеллектуальные энергетические системы - 47

Организаторы получили +1500 золота и +1000 опыта
Всероссийская инженерная олимпиада для старшеклассников: BigData и Интеллектуальные энергетические системы - 48

И еще кое-что
Всероссийская инженерная олимпиада для старшеклассников: BigData и Интеллектуальные энергетические системы - 49

А я нашел «настоящего» комсомольца и попросил «по-настоящему» завязать пионерский галстук.
Всероссийская инженерная олимпиада для старшеклассников: BigData и Интеллектуальные энергетические системы - 50

Ну, а в конце «смены» мы все ж сумели разжечь «двухъядерный» костер, послушать легенды «Орленка», спеть «Катюшу».
image

Планы на будущее
«Следующий год мы уже начинаем готовить в июне, т.к. уже сейчас понятно, что заочный этап будет гораздо более продолжительным по времени. За счет этого удастся сильно прокачать образовательную составляющую и выйти на более интересные задачи в финале.
Думаю, что нужно развиваться в сторону MOOC-курса, поддержанного серией очных мероприятий. Будем проводить хакатоны в разных городах вместе с организациями-партнерами.»

— Юрий Молодых, организатор направления «Большие данные и машинное обучение»

Вот видео от Sci-one и статья на GT — Я у мамы инженер: финал олимпиады НТИ

СМИ
Научная Россия. Олимпиада НТИ: запуск прошел успешно
АСИ. Победители Всероссийской олимпиады НТИ получат +10 баллов к результатам ЕГЭ
GT. Я у мамы инженер: финал олимпиады НТИ

Благодарности
Лично хочу сказать спасибо Алене Ильиной, Ксении Макаровой, Юлии Грабовской, а так же компании РВК (говорят, если бы не они, то ничего бы не было).

Автор: MagisterLudi

Источник

Поделиться новостью

* - обязательные к заполнению поля