Иван Тарасов (_navi_) wrote,
Иван Тарасов
_navi_

задачки

За время конференций я придумал пару „исследовательских” задачек, решения которых мне пока не очевидны. Beware: первая из них слишком неформальная.

Задача о языках

Имея заданное натуральное число n, определить набор из n естественных языков, таких что возможность понимать фразы на неизвестных тебе языках максимальна.

Другое возможное требование: набор должен быть таким, чтобы изучение следующих языков из соответствующих наборов из n+1, n+2, …, N языков было наиболее простым. (То есть, надо строго упорядочить набор языков, так чтобы любой хвост этого списка было „максимально просто” изучать)

Задача туриста

Предположим, у нас есть граф, представляющий собой карту города: вершины это перекрёстки и “points of interest”, а рёбра — это соединяющие их улицы. Одна из вершин — отель, в котором живёт турист. Надо составить d путей длиной не больше l, таких что все они начинаются и заканчиваются в вершине „отель” и покрывают максимальное (в каком-либо определённом смысле) количество интересных точек или наибольшую часть города.

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

Эта задача чем-то напоминает TSP, но тут нам надо построить несколько путей. Правда, можно подумать, можно ли свести это к поиску одного пути в модифицированном графе.

Вместе с этой задачей также стоит решать следующую практическую задачу: имея картинку с картой города из Google Maps, построить граф улиц/перекрёстков.

Tags: languages, problems, travel
Subscribe

  • Фотографии с Тахо

    На новый год мы ездили с друзьями в Тахо. Тахо — это совершенно прекрасное озеро на границе Калифорнии с Невадой, окружённое горами. В горах, в…

  • тудаблин

    Нет, всё же летать в восточном направлении как-то немилосердно. Просыпаешься утром рано-рано (где-нибудь так в 6:30), мчишься в аэропорт, съедаешь…

  • ICFPC

    27 утром лечу в Дублин на конференцию, поэтому с ICFPC, видимо, пролетаю. Разве что кому-нибудь с lightning помочь могу попробовать, тем более что у…

  • Post a new comment

    Error

    default userpic

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 5 comments