IT-инфраструктура для бизнеса и творчества

Зарядка для мозга во время самоизоляции: шесть задач от школы анализа данных «Яндекса»

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

Кстати, похожие задачи будут в этом году на вступительном экзамене в ШАД, где для людей с опытом в ИТ мы придумали новый трек, который поможет им улучшить свои знания математики.

1. В ряд выложены пять красных, пять синих и пять зеленых шаров. С какой вероятностью никакие два синих шара не лежат рядом?

В подобных задачах обычно не нужны глубокие познания — достаточно хорошо понимать, что такое размещения, перестановки и сочетания. Но все же требуется большая аккуратность при работе с элементарными событиями, то есть базовыми равновероятными исходами, из которых мы и будем конструировать события в задаче. В противном случае легко впасть в заблуждения в духе «вероятность 50%: либо произойдет, либо нет».

В этой задаче можно сэкономить время и нервы, если решать её «конструктивно»: представив, что составляете расстановку шаров, удовлетворяющую условиям.

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

2. Электрическая цепь представляет собой связанный неориентированный граф без кратных ребер, в котором ребра (числом N) — это провода, а вершины — это либо лампочки, либо единственный источник тока. На каждом ребре размещено реле.

Лампочка горит, если существует путь, соединяющий ее с источником тока, вдоль которого все реле находятся в положении «включено». Известно, что ровно одно из реле бракованное и никогда не пропускает ток. Вы можете включать и отключать реле и видеть, горят ли лампочки. Изначально все выключатели находятся в положении «включено». Опишите способ нахождения неисправного реле за О(N) операций включения-выключения.

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

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

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

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

Впрочем, эту классическую задачу можно решить и очень коротким элегантным способом (достаточно рассмотреть одного человека и троих его знакомых, а если таких меньше трёх, то «инвертируем» граф знакомств, заменив все рёбра их отсутствиями и наоборот — задача от этого не поменяется). Если его найдете, сэкономите много времени!

4. На столе лежат четыре карточки, на которых сверху написано «А», «Б», «4», «5». Про то, что написано на обратных сторонах, ничего не известно. Какое наименьшее количество карточек надо перевернуть, чтобы проверить истинность утверждения «Если на одной стороне карточки написано четное число, то на другой — гласная буква»?

Еще одна задачка на тонкости логической связки «если — то». Тут важно разобраться, что под условие подходят карточки вида:

  • четное число, гласная буква;
  • нечетное число, что угодно.

И не подходят карточки вида:

  • четное число, согласная буква.

Теперь становится ясно: что бы ни было написано на обороте карточек «А» и «5», это не влияет на ситуацию; а чтобы проверить условие, нам достаточно перевернуть карточки «Б» и «4» и проверить, нет ли на обороте четного числа и согласной буквы соответственно.

5. Докажите, что равносторонний треугольник нельзя покрыть двумя меньшими равносторонними треугольниками.

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

6. Квадратная матрица такова, что след tr(AX) = 0 для любой матрицы X того же размера, имеющей нулевой след (след матрицы — сумма элементов на главной диагонали).

Докажите, что матрица является скалярной (т. е. имеет вид λE для некоторого λ, где E — единичная матрица).

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

Таким образом, встретив подобную задачу, стоит сначала взять какие-нибудь конкретные (и желательно очень простые) матрицы X с нулевым следом и попробовать понять, что же нам дает условие tr(AX) = 0. В качестве таких матриц удобно взять матричные единицы (и матрицы, у которых на диагонали все нули, кроме двух элементов, равных 1 и (-1).

Собственно говоря, на этом задача и закончится: из условий tr(AX) = 0, которые вы распишете для таких матриц, сразу будет следовать ответ.

(function () { let cdnUrl = `https://specialsf378ef5-a.akamaihd.net/SelectelBranding/images/` let previousArticleNumber = null let currentArticleNumber = 0 let platform = 'Desktop' let articles = [ { name: 'camera', url: `${cdnUrl}CameraCat`, text: 'умную камеру для\u00A0наблюдения за\u00A0котиками', link: 'https://vc.ru/selectel/306690', num: 3 }, { name: 'chill', url: `${cdnUrl}ChillCat`, text: 'трекер, который подскажет, когда пора отдохнуть', link: 'https://vc.ru/promo/288561-eye-tracker', num: 1 }, { name: 'cloud', url: `${cdnUrl}CloudCat`, text: 'котика: даёшь ему «пять», а\u00A0он делает бэкап в облако', link: 'https://vc.ru/dev/294799-maneki-neko', num: 2 } ] let buttonCycle = document.querySelector('.button--cycle') let buttonChoose = document.querySelector('.button--choose') let buttonMobile = document.querySelector('.button--mobile') let textField = document.querySelector('.selectel-footer-subtitle') let imageAgent = document.querySelector('.image--agent') let banner = document.querySelector('.selectel-footer') buttonCycle.addEventListener('click', cycleClick) buttonChoose.addEventListener('click', () => sendEvent(`Promo ${articles[currentArticleNumber].num} Left`, 'Click')) buttonMobile.addEventListener('click', () => sendEvent(`Promo ${articles[currentArticleNumber].num} Left`, 'Click')) let media = window.matchMedia("(max-width: 570px)") media.addEventListener('change', matchMedia) function matchMedia() { if (media.matches) { platform = 'Mobile' } else { platform = 'Desktop' } update() } matchMedia() function cycleClick(event) { sendEvent(`Promo ${articles[currentArticleNumber].num} Right`, 'Click') if (event) { event.preventDefault() event.stopPropagation() } window.open('https://vc.ru/tag/selectelDIY', '_blank') //cycle(event) } function cycle(event) { // incrementArticleNumber() textField.innerHTML = generatedText() imageAgent.src = articles[currentArticleNumber].url + platform + '.svg?3' imageAgent.setAttribute("class", "") imageAgent.classList.add('image--agent', articles[currentArticleNumber].name) banner.href = articles[currentArticleNumber].link } function update() { banner.href = articles[currentArticleNumber].link imageAgent.src = articles[currentArticleNumber].url + platform + '.svg' textField.innerHTML = generatedText() } function incrementArticleNumber() { previousArticleNumber = currentArticleNumber if (currentArticleNumber >= articles.length - 1) { currentArticleNumber = 0 } else { currentArticleNumber++ } } const sendEvent = (label, action = 'Click') => { const value = `SelectelDIY — loc: Footer — ${label} — ${action}`; if (window.dataLayer !== undefined) { window.dataLayer.push({ event: 'data_event', data_description: value, }); } }; function generatedText() { let defaultText if (platform === 'Desktop') { defaultText = `Мы тут собрали %text%. Хотите научим?` } else { defaultText = `Мы тут собрали %text%.` } return defaultText.replace('%text%', articles[currentArticleNumber].text) } function getRandom(min, max) { min = Math.ceil(min) max = Math.floor(max) return Math.floor(Math.random() * (max - min + 1)) + min } (function create() { currentArticleNumber = getRandom(0, articles.length - 1) cycle() let page = document.querySelector('.page--entry') if (page) { function insertAfter() { let parents = page.querySelectorAll('[data-id="7"]') let referenceNode = parents[0] referenceNode.parentNode.insertBefore(banner, referenceNode.nextSibling); loaded() } setTimeout(() => insertAfter(), 0) } }()) function loaded() { banner.classList.add('loaded') } loadImages([ `${cdnUrl}CameraCatDesktop.svg`, `${cdnUrl}ChillCatDesktop.svg`, `${cdnUrl}CloudCatDesktop.svg`, `${cdnUrl}CameraCatMobile.svg`, `${cdnUrl}ChillCatMobile.svg`, `${cdnUrl}CloudCatMobile.svg?3`, ]) function loadImages(urls) { return Promise.all(urls.map(function (url) { return new Promise(function (resolve) { var img = document.createElement('img'); img.onload = resolve; img.onerror = resolve; img.src = url; }); })); } }())
0
16 комментариев
Популярные
По порядку
Написать комментарий...

В задаче 5 какая-то ошибка

1

Роман, спасибо! Конечно, тут "двумя" выпало. Вот пример того, как стилистические правки могут исказить суть.

1

Скажите пожалуйста, в первой задачке сам вопрос сформулирован корректно?
С какой вероятностью никакие два синих шара не лежат рядом?

...меня смущает слово "никакие", возможно там должно было быть "никогда".

1

Всё корректно) В переводе с математического жаргона это как раз и значит "два синих шара никогда не лежат рядом"

0

Ясно, спасибо.

0

А ещё у вас много интересных задач на thecode.media

0

А вы не могли бы перенести формулировки задач, например, во врезки? В заголовках они занимают слишком много места.

0

Готово :)

0

Здорово, спасибо большое!

0

А что за новый трек в ШАДе?

0

Мы создали его в этом году для тех, кто уже имеет опыт в IT и хочет развиваться дальше, но не так хорошо владеет высшей математикой, чтобы пройти через наш стандартный процесс отбора. При отборе мы будем учитывать умение программировать и знакомство с основами анализа данных, участие в проектах и наличие научных статей; математика же будет проверяться на гораздо более базовом уровне; собственно говоря, решать придётся задачи, похожие на задачи в этом посте. Поступивших ждёт адаптационный курс по высшей математике, который мы разработали специально для этого трека и который поможет им потом без проблем влиться в ШАДовский учебный процесс. Вот тут вы можете почитать подробнее про процесс поступления в ШАД: http://yandexdataschool.ru/enroll

0

Большое спасибо!

0

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

0

Задача 4: на обороте карточки "5" вполне может быть чётное число, что нарушит истинность утверждения. Так что её тоже надо перевернуть!

0

Тоже обратил на это внимание, подождем комментарий от автора)

0

В вашей ШАД много ошибок. Когда вы пишите: "В ряд выложены пять красных, пять синих и пять зеленых шаров.", то это означает что они выложены последовательно. Нужно либо добавлять в перемешку случайным образом. 

0
Читать все 16 комментариев
Бизнес — как ребенок: как мамы совмещают свое дело с заботой о детях

Как совмещать бизнес и семью? Ко Дню матери своими историями поделились бизнесвумен, которые работают c ЮKassa и занимаются детьми. Читайте, как им удается сохранять жизненный баланс и добиваться успеха.

Хочу кухню как у подруги: зачем в Циан сделали поиск квартир по фото

Рассказывает Юлия Зыкова, руководитель команды «Аудитория» в Циан.

Наследник Рокфеллера, сын Софи Лорен, боксёр и продюсер: история француза, обманувшего Рурка, Ван Дамма и других звёзд Статьи редакции

СМИ прозвали Кристофера Роканкура звёздным мошенником: его жертвами были голливудские знаменитости и американские предприниматели. Точная сумма ущерба от действий француза неизвестна, но сам он утверждает, что за свою жизнь «заработал» $40 млн.

Кристофер Роканкур и Наоми Кэмпбелл francetvinfo
Английский язык. Как это надо делать, если вернуть 2 года назад

Всегда считал себя неспособным к языкам, школу закончил, мягко говоря, с 0 знанием Английского языка. Как ,наверно, 95% населения нашей страны.

Из науки в IT: как создать свой стартап и стать преподавателем

Как перейти в IT из другой сферы? Как разработать курс, которому нет аналогов? Как студенту получить максимум пользы от занятий? Рассказывает преподаватель OTUS Сергей Окатов, руководитель курсов «Kotlin Backend Developer» и «Kotlin Developer. Basic».

Как я заработал свой первый миллион просмотров на лонгридах

Мой опыт ведения текстового блога на «Виси», «Пикабу», «Хабре», Дзене и еще пачке площадок. Сколько потратил на них сил и какую отдачу в итоге получил.

Как мы с двумя кошками из Москвы в Прагу летели

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

Завод по производству идей. Как работают акселераторы, зачем они нужны стартапам и куда идти с идеей прямо сейчас

По данным Startup Genome, 9 из 10 стартапов терпят неудачу. Возможных причин «смерти» много: недостаточно протестированная гипотеза, неподтвержденная юнит-экономика, неверная стратегия или просто неудача в подходе к продажам.

Мы сделали бот, который печатает и отправляет ваши фото маме. В 2 клика
Катя со свежими фотками для родителей

Мы запустили Kind Bot — доброго бота, которому в 2 клика можно скинуть свои фотки. Он их напечатает и отправит по почте вашей маме. Или другому близкому человеку.

Как у меня украли 600 тысяч с карты, а Тинькофф нарушает федеральный закон

Спойлер: я НЕ вводил никуда код, НЕ переходил по ссылкам и НЕ сообщал данные карты.

Я всегда считал себя финансово грамотным человеком, сам когда-то работал в банке, соблюдал цифровую гигиену, держал деньги на нескольких счетах, не привязывал основную карту в непонятных сервисах, в 90% оплат пользовался Google Pay. Когда родственники присылали…

Что Tele2 предлагает клиентам в «черную пятницу»

На главной распродаже года клиентов компании ждут сразу несколько интересных предложений: скидки на смартфоны, пакеты SMS и безлимитный трафик на YouTube, Яндекс.Карты, Яндекс.Навигатор.

null