• Как волонтёры со всего мира создают прямой эфир ICPC-2019
    +1

    Разве что внутри одного суперрегиона (или даже региона), и то с натяжкой.

  • Нужно больше камер: у Nokia 9 их сразу 5
    +1
  • Наука находится на грани трансляции Твиттера прямо в ваш мозг
    0
    image
  • Программист на больничном
    0
    У меня друг однажды размечал корпус медицинских записей по пациентам, так он на третий день почти перестал испытывать какие-либо трудности.
  • Программист на больничном
    0
    В голову пришла мысль, что врачи могут всё писать на бумаге, чтобы было быстро, а потом эти бумаги уносят синкаться в базу.
    Выйгрыш в том, что вбивальщики просто сидят на конвеере, не отвлекаются на врача с пациентом и не сбивают ритм. И главное, их нужно гораздо меньше, чем в каждый кабинет.
    С чуваками ещё оставлять на смене какого-нибудь врача, чтобы он если что помогал.
  • Как и зачем мы сделали свои банкоматы
    0
    Вот это кстати тема. Идёшь по улице, тебе пуш на телефон приходит: «В 50 метрах можно положить наличку в наш банкомат и получить 2% сверху».
  • Новая профессия: «помощник виртуальных знакомств»
    +1

    Роберт Шекли, "Мой двойник — робот".

  • Шпаргалка для технического собеседования
    +5
    Основная разновидность — линейные массивы, или одноразмерные.
    Их размер статичен, то есть при объявлении линейного массива задаётся фиксированный размер.

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


    Вставка: линейный массив — недопустимо, динамический массив — O(n).

    Действительно, вставка в динамический массив происходит за O(n), но эта информация не очень полезна без того факта, что в силу мультипликативной стратегии реаллокации амортизиованная сложность вставки получается O(1), то есть последовательная вставка n элементов произойдёт не за O(n^2), как можно было бы подумать, а за O(n).


    Данные хранятся в узлах, указывающих на другие узлы.
    Узел содержит один элемент данных и одну ссылку (на другой узел).
    Связный список соединяет узлы друг с другом с помощью ссылок от одного узла к другому.

    Под определение, которое дано в статье подходит всякая ересь, например:


    image
    Оптимизированный поиск: связный список — O(n).

    Неясно, что такое оптимизированный поиск в связном списке.
    (оффтоп: чутка развив идею списка можно делать на нём аналог двоичного поиска, гуглить skip list).


    Этот процесс называется хэшированием: однозначным сопоставлением друг другу входных и выходных данных.

    Вот это жесть, конечно. Конечно, хэширование не занимается однозначным сопоставлением, потому что значений хэшей должно быть меньше, чем значений хэшируемых объектов, чтобы это имело хоть какой-то смысл.


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

    Решается она не так, конечно, а с помощью использования стратегий разрешения коллизий. Гуглить цепочки, линейное разрешение, двойное хэширование, хэширование кукушки.


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

    При этом у каждой вершины не больше одного левого сына и не больше одного правого.


    Индексирование: двоичное дерево поиска — O(log n).
    Поиск: двоичное дерево поиска — O(log n).
    Вставка: двоичное дерево поиска — O(log n).

    Все эти операции работают за O(высота дерева). Если дерево сбалансированное, то тогда это действительно O(log N), но само по себе дерево сбалансированным навряд ли станет.
    Существуют хитрые двоичные деревья, которые всегда остаются сбалансированными. Гуглить, например, красно-чёрное дерево, AVL-дерево, splay-дерево.


    Поиск в ширину оптимален для поиска по дереву, чья ширина превышает глубину.
    Это почему вдруг? С точки зрения времени алгоритм всегда обработает каждую вершину 1 раз, а каждое ребро – 2 или 1 раз (в зависимости от того, ориентированный граф или нет). Если же хочется пооптимизировать память, то поиск в ширину наоборот тратит меньше памяти на очередь на «глубоких узких» графах (потому что слои получаются маленькие).

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

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


    E — количество рёбер (граней?).

    Рёбер. Грань – область, ограниченная рёбрами в плоском графе и не содержащая внутри себя вершин и рёбер графа.


    [Поиск в глубину] Алгоритм оптимален для поиска по дереву, чья глубина превышает ширину.

    Аналогично, с точки зрения времени всё то же самое, а с точки зрения памяти всё ровно наоборот.


    Сравнение поисков в ширину и в глубину
    Выбирайте тип поиска в соответствии с размером и формой дерева.
    Для широких, мелких деревьев используйте поиск в ширину.
    Для глубоких, узких деревьев используйте поиск в глубину.

    Если уж заморачиваться, то ровно наоборот.


    Вообще, поиск в ширину и поиск в глубину – это базовые алгоритмы, из которых потом растут свои ответвления, например:


    • с помощью поиска в ширину можно искать кратчайшие пути в невзвешенном графе
    • с помощью поиска в глубину можно искать мосты и точки сочленения.

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

    Каша, мёд, говно и пчёлы. Сначала, я так понял, автор начал описывать рекурсивную реализацию, а потом описал итеративную.
    «Весь набор данных делится минимум на две группы» – первый шаг рекурсивного алгоритма. Затем каждая часть рекурсивно сортируется и сливается.


    Наилучший вариант сортировки: сортировка слиянием — O(n).
    Средний вариант сортировки: сортировка слиянием — O(n log n).
    Худший вариант сортировки: сортировка слиянием — O(n log n).

    Сортировка слиянием всегда работает ровно за O(n log n).


    Жадные алгоритмы используются для поиска оптимального решения данной проблемы.

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


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

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


    :(

  • На шаг ближе к С++20. Итоги встречи в Торонто
    +1
    Да и первая хороша
    SUM(a, b) * SUM(c, d) == a + b*c + d
  • Сheat-sheets «регулярные выражения»
    0
    Так можно и поматчить их как .*?, а чё, все правильные email адреса сматчатся, а на false-positive плевать. На практике, конечно, я согласен с тем, что матчить email адреса нужно по наличию ровно одного @ (ваш регэкс, кстати, сматчит и a@b@c), а затем просто слать email, если хочется удостовериться, что email валидный (и, более того, скорее всего настоящий).
  • Сheat-sheets «регулярные выражения»
    +1
    1. Пожалуйста, больше никогда не вываливайте набор символов вроде
    #([A-Fa-f0-9]{6}|[A-Fa-f0-9]{3})
    в немоноширинной гарнитуре, это призыв к насилию и вообще экстремизм
    2. Электронные адреса не соответствуют никакой регулярной грамматике, а потому и нельзя проверить их никаким регулярным выражением ¯\_(ツ)_/¯
    3. То, что должно матчить HTML-теги сматчит не только HTML-теги.
  • Манифест Ричарда Столлмана: How I do my computing
    +1
    GNU/Linux
    // Столлман мод
  • Сотню старичков могут выбросить на улицу
    0
    В Португалии занимаемся чартерной авиацией (http://jetway.to), нужно серверов восемь-десять для просчёта логистики.
    Забрать могу прямо из Утрехта во второй половине июля.
    mingalev@jetway.to
  • Twitter купил нейросеть Magic Pony для повышения резкости изображений и видео
    +3

    image

  • Питерцы чемпионы мира! Не хоккеем, так программированием
    +1
    > Context
    Contest?
  • Ищем замену Digital Ocean среди отечественных хостинговых компаний
    +3
    -_____-
    https://toster.ru/user/splastunov/answers
  • Теперь официально: люди плохо понимают значение используемых ими эмодзи
    0
    А как так получилось, что опрос проводили среди 300 человек, а на диаграмме всего 37?

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

  • Новый браузер Brave от сооснователя Mozilla будет платить пользователям за просмотр рекламы
    0
    Пользователи, которые не верифицировались, денег не получат, но их доля также просчитывается, и автоматически отправляется владельцам сайтов, которые сами эти пользователи посещают чаще других.

    Делаешь ферму неверифицированных кликеров, которые сидят на твоём сайте
  • Я знал, как валидировать email-адрес. Пока не прочитал RFC
    0
    Про сценарии различные согласен, разумеется.
    Вообще интересны какие-нибудь исследования про долю ошибок в поле емейла, которые отсекаются чем-то сложнее проверкой наличия коммерческого at и точки, отделяющей TLD.
  • Я знал, как валидировать email-адрес. Пока не прочитал RFC
    +38
    Лучший способ проверить email на валидность — отправить туда письмо.
  • Go в 2015 году
    –10
    На лицо в извращённом порно испоражняются.
  • Что может остановить плохого парня с дроном? Конечно же, хороший парень с дроном
    0
    South Park, 18 сезон, 5 серия.
  • Сооснователь Planetary Society считает, что человек никогда не выйдет за пределы Марса
    +3
    Звучит как отличный сценарий для фильма.
  • Наиболее частые проблемы Python и решения (перевод)
    0
    def bisect_left(a, x):
        lo, hi = 0, len(a)
        while lo < hi:
            mid = (lo+hi)//2
            if a[mid] < x:
                lo = mid+1
            else:
                hi = mid
        return lo
    
  • Наиболее частые проблемы Python и решения (перевод)
    +6
    Боги, какой жуткий бинпоиск.
    А вообще,
    import bisect
    
  • 2Mb веб-страницы — кого винить?
    +1
    По мне, так медиана была бы гораздо показательнее, чем среднее. И, думается мне, она меньше двух мегабайт.

    Про количество объектов — ждём http2 и мультиплексинг.
  • В чемпионате мира по программированию «Битва интеллектов» принимают участие лучшие студенты со всего мира
    +15
    1.Ссылки на источник я не увидел. www.prnewswire.com/news-releases/worlds-top-collegiate-computer-programmers-to-compete-at-ibm-sponsored-battle-of-the-brains-in-marrakech-morocco-300084514.html

    2. ACM ICPC World Finals ни «Battle of the brains», ни тем более «Битвой интеллектов» в среде людей, имеющих непосредственное отношение к соревнованию не называется.

    3. >> Финал чемпионата проходит 20 мая в 9:30 по местному времени
    Ну имейте ж уважение к читателям ресурса, которые по необъяснимым причинам не живут по марокканскому времени.

    4. >> Университет Бейлора
    -_\\ Ну приехали. Бейлорский университет.

    5. >> предлагая им для решения реальные бизнес-проблемы мирового масштаба
    Какие к чёрту бизнес-проблемы? Какого ещё мирового масштаба? Автор бы хоть из приличия задачи бы посмотрел.
    http://icpc.baylor.edu/worldfinals/problems/icpc2015.pdf

    Короче, у меня бомбануло. marks, иди на GT публицистику переводи.
    >> Финал — сегодня, и уже через пару часов мы узнаем финалиста
    ой, всё
  • Красивые математические GIF-анимации
    +2
    А, так он четырёхмерный. Забавно, спасибо.
  • Красивые математические GIF-анимации
    +1
    600-гранник не может быть платоновым телом.
  • Частная российская компания предлагает построить лунную базу за 10 лет
    +1
    Чтобы из номера года получить номер века, надо взять первые две цифры номера года и прибавить к ним единицу

    А ведь на самом деле год XY00 относится к веку XY, а не (XY+1).
    Ещё очень забавно, что начало нового тысячелетия праздновали в 2000, хотя началось оно в 2001, опять же.
    Короче, индексация с единицы — отстой.
  • Учёные ищут путешественников во времени
    +1
    К сожалению, создание полного клона противоречит принципу неопределённости Гейзенберга
  • Особенности отражения DDoS атак и история атаки на один крупный банк
    –1
    Не представляю, почему в профиле оказался '97, я на два года старше.
    С D7 я начал играться десять лет назад, закончил восемь-семь лет назад, так что да, ностальгия.
  • Особенности отражения DDoS атак и история атаки на один крупный банк
    0
    мимо
  • Особенности отражения DDoS атак и история атаки на один крупный банк
    –1
    Ностальгия.
    image
  • Маленький Hello World для маленького микроконтроллера — в 24 байта (и чужое решение в 12 байт)
    0
    Всё верно, заданную, но не наперёд.

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

    Наиболее интересная задача здесь — разработка такого компилятора и ЯВУ, который бы выдавал оптимизированный код (по какому-то критерию) и доказательство того, что на данном устройстве получить лучший код — невозможно.


    — такого не будет, если критерием считать размер программы.

    Поскольку в этом комментарии я не написал ничего нового, считаю диалог завершённым.
  • Маленький Hello World для маленького микроконтроллера — в 24 байта (и чужое решение в 12 байт)
    0
    Строку, очевидно, не наперёд заданную.
    Ещё раз. Не существует алгоритма A, такого, что он для любого S находит B=A(S), такое что B()->S, и не существует алгоритма C, такого что C()->B и |C|<|B|.

    На хабре была неплохая статья для человека, не знакомого близко с CS: habrahabr.ru/post/189742/
  • Маленький Hello World для маленького микроконтроллера — в 24 байта (и чужое решение в 12 байт)
    0
    Программирование на ассемблере является наиболее трудоемким способом получения программ, оптимизированных по размеру и скорости выполнения. Наиболее интересная задача здесь — разработка такого компилятора и ЯВУ, который бы выдавал оптимизированный код (по какому-то критерию) и доказательство того, что на данном устройстве получить лучший код — невозможно.


    К сожалению, из проблемы останова следует невозможность существования алгоритма, который в общем случае генерирует программу минимального размера, эквивалентную заданной. Более того, не может существовать даже алгоритма, который генерирует минималтную программу, просто выводящую заданную строку.
  • Инструменты для перевода произведений в общественное достояние
    +1
  • Как мы со школьниками мастерили сигнализацию на Raspberry для их собственной школы
    +5
    В метро входило пять Олегов
    А выходило ровно шесть
    Последний видимо скопился
    За предыдущие года
  • Microsoft, Oracle и ряд других компаний присоединяются к антироссийским санкциям
    0
    Так это ж ещё выжить надо