• Задачка про парные числа
    0
    А в случае 16384-битных слов? Всё равно 32 счётчика?
    Правда, я не уверен, что решение с x^3 вообще работает.
  • Задачка про парные числа
    0
    Ваше решение разве не зависит от размера слова?

    Зависит — примерно как 3*N бит. А решение со счётчиками — примерно N^2 бит. Конечно, ограничения задачи становятся слегка другими, но O(N)<O(N^2).
  • Сортировка очереди без использования дополнительных ресурсов
    0
    Без счётчиков, но с дополнительным пустым элементом в очереди:
    queue.Push(new Item());
    for(;;){
        for(;;){
            temp=queue.Pop();
            if(queue.Get()==Item.Empty) goto _1;
            if(queue.Get()<=temp) break;
            queue.Push(temp);
        }
        for(;;){
            if(queue.Get()==Item.Empty){
                queue.Push(temp);   
                queue.Push(queue.Pop());
                break;
            }
            if(queue.Get()<temp) queue.Push(queue.Pop());
            else{
                queue.Push(temp);
                temp=queue.Pop();
            }
        }    
    }
    _1:
    queue.Pop();
  • Сортировка очереди без использования дополнительных ресурсов
    0
    Получается, что так. Либо можно что-нибудь посчитать, либо запомнить (или переставить) элементы в очереди — но не одновременно.
    С другой стороны, ничто не запрещает нам добавить новый пустой элемент в очередь и использовать его для сортировки пузырьком?
  • Сортировка очереди без использования дополнительных ресурсов
    0
    Есть разница между использованием О(1) и использованием ровно одной переменной. Мы, например, не можем переложить начало очереди в конец, не испортив какого-нибудь счётчика (если он зачем-то нужен).
  • Задачка про парные числа
    +1
    Давайте, чтобы не было разночтений — памяти у вас четыре килобайта.
  • Задачка про парные числа
    0
  • Американские математики обнаружили ранее неизвестное свойство простых чисел
    0
    Для чисел порядка 10^100 вероятности переходов получаются в диапазоне 24.0% — 26.0%.
    24.1677 25.4576 25.5158 24.8589
    24.9094 24.2796 25.2975 25.5136
    25.0930 25.2572 24.1206 25.5292
    25.6679 25.0855 25.0776 24.1690
    Для небольших делителей брал настоящие делимости, для больших — по вероятности.
  • Зачем программисту знать алгоритмы
    +2
    то так важно ли, что после переписывания его со знанием алгоритмов и структур данных, оно станет работать полсекунды или нет?

    И бозон Хиггса будет ловиться не 2 года, а 2000 лет? Да они сами безо всякой конкуренции захотят и с алгоритмистами, и с программистами сотрудничать в лучшем виде.
  • Зачем программисту знать алгоритмы
    0
    Сначала физика. Потом анализ задачи численными методами. Потом возвращаемся к физику, выясняем возможные инварианты, гладкость поля в пространстве и времени… Потом выбираем несколько численных моделей. Идём к программисту, спрашиваем, что он про них думает — в смысле эффективности, памяти, реализуемости вообще. Возможно, потребуется несколько итераций. После чего программист, зная повадки машины, превращает алгоритм в программу, и наконец, вычисляет эту траекторию.
  • Американские математики обнаружили ранее неизвестное свойство простых чисел
    0
    Похоже, что чтобы получить при всех переходах 24-26%, надо дойти до 10^400...
  • Американские математики обнаружили ранее неизвестное свойство простых чисел
    +1
    Если проанализировать числа в окрестности 2^40, получим карту переходов
    25.0019: 19.8492 28.6524 28.5576 22.9407
    25.0064: 24.5381 19.4783 27.4282 28.5554
    24.9994: 25.3014 26.5211 19.5236 28.6539
    24.9923: 30.3210 25.3753 24.4870 19.8167

    Если же взять числа в окрестности 2^57, получится
    25.0134: 21.0642 27.7100 27.5466 23.6792
    25.0067: 24.9007 20.9652 26.6990 27.4351
    24.9824: 25.2773 26.0573 20.9125 27.7530
    24.9975: 28.8142 25.2948 24.7668 21.1242

    Диапазон вероятностей переходов уменьшился с 10.8% до 7.9%. Возможно, рассматривая ещё более далёкие числа, можно ужаться и в 1%, и ещё меньше.
  • Американские математики обнаружили ранее неизвестное свойство простых чисел
    +3
    До 100 млн:
    1: 1440298
    3: 1440473
    7: 1440495
    9: 1440185
    Распределение выглядит очень равномерным (но на X^2 не проверял).
  • Большой опрос по алгоритмам
    +1
    Собственно, почему бы и нет? Если сравнение намного медленнее, чем проход по списку (например, сравнение алгебраических чисел или работа в интервальной арифметике), то бинарный поиск вполне оправдан.
  • Американские математики обнаружили ранее неизвестное свойство простых чисел
    +2
    До 10^8:
    1: 17.6996%, 30.3928%, 31.0334%, 20.8742%
    3: 23.6386%, 16.6670%, 28.6851%, 31.0093%
    7: 25.5825%, 27.3242%, 16.6752%, 30.4181%
    9: 33.0755%, 25.6244%, 23.6160%, 17.6841%
  • Большой опрос по алгоритмам
    0
    Все модификации быстрой сортировки похожи друг на друга и имеют сходное время.

    Интроспективная сортировка считается такой модификацией?
  • А нужно ли знать программисту алгоритмы?
    +1
    Интересно знать, кому (или для чего) должен знать алгоритмы человек, который называет себя программистом?
    И как же должен называться специалист, от которого требуется имитация отжига; Монте-Карло… далее по списку? Вы уже установили, что это не программист. Тогда кто же?
  • Вычисление значения многочлена. Все ли тривиально в этом вопросе?
    +1
    Судя по сигнатуре, EC-40. Хотя могла быть и СМ-1420. Спирт использовался для протирки поверхностей накопителя на магнитных дисках и головок самого накопителя.
  • Обзор примитивов синхронизации — спинлоки и тайны ядра процессора
    0
    Любопытно, что в версиях процессоров TI C64xx команды синхронизации LL/SC были, а в TI C66xx исчезли. Насколько я понял, их роль выполняют DMA, shared memory, ещё что-то… но от атомарных команд решили отказаться.
  • Обзор примитивов синхронизации — спинлоки и тайны ядра процессора
    0
    например, если LL и SC лежат в памяти слишком далеко

    В смысле исполняемые инструкции? Ячейка одна и та же.

    Рассмотрим два сценария.
    `

    0, #1, #2 выполнили LL
    #1 выполнило SC (удачно)
    #2 выполнило SC (неудачно)
    #3, #4 выполнили LL (с той же ячейкой)
    #0 выполнило SC (???)
    #3 выполнило SC (???)



    0, #1, #2 выполнили LL
    #1 выполнило SC (удачно)
    #2 выполнило SC (неудачно)
    #3, #4 выполнили LL (с той же ячейкой)
    #3 выполнило SC (???)
    #0 выполнило SC (???)

    `
    Сценарии различаются двумя последними строчками.
    Считается, что инициирована новая последовательность? Может ли #0 выполнить SC? Может ли #3 не выполнить SC?
  • Обзор примитивов синхронизации — спинлоки и тайны ядра процессора
    0
    Первая инструкция — load linked — просто читает значение из памяти. Но при этом в процессоре взводится триггер, который «следит» за считанной ячейкой — не было ли в неё записи.

    Вторая — store conditional — сохраняет значение в память. Но! Если со времени исполнения load linked в эту ячейку кто-то уже записал новое значение, store conditional вернёт признак неуспеха (и, конечно, ничего в ячейку памяти записывать не будет).

    А можно поподробнее?
    Допустим, несколько ядер (#0,1,2) обратились к одной ячейке. Одно (#1) успело что-то записать, другое (#2) — нет. После этого к ней обратились ядра #3 и #4. Ядро #0, а потом #3 попытались что-то записать. Будет ли хотя бы одна попытка записи успешной? Когда сеанс общения с ячейкой считается законченным, и после нового LL можно будет перезаписать ячейку?
  • Математика на пальцах: линейно-квадратичный регулятор
    0
    Мне показалось, что x_N — это финальное реально достигнутое состояние, а вовсе не цель. Штраф за недостижение цели они вводят отдельно: J = 1/2 xT(t1)F(t1)x(t1) + ...
  • Математика на пальцах: методы наименьших квадратов
    0
    "Константа" зависит от угла наклона прямой. В случае минимизации зелёных линий оптимальная прямая будет иметь несколько меньший угол наклона, чем в случае минимизации красных. Так что это не то же самое.
  • Математика на пальцах: линейно-квадратичный регулятор
    0
    del
  • Математика на пальцах: линейно-квадратичный регулятор
    0
    <зануда on>
    во второй строчке двойка должна быть перед последним слагаемым, а не перед предпоследним :)
    <зануда off>
  • Математика на пальцах: линейно-квадратичный регулятор
    0
    И, кстати, чтобы "из неправильной формулы восстановить правильную, так как за каждым значком стоит какой-то смысл", нужен довольно высокий уровень понимания математики. Надо продраться через все эти формулы, понять, что за координатами есть формализм векторов, за ними матрицы и тензоры, являющиеся самостоятельными объектами, дальше не знаю, что — оно зависит от направления; сейчас я, например, предпочитаю думать в терминах инвариантов и законов сохранения. Но при необходимости могу вернуться и к формулам.
    И можно ли объяснить интуитивный уровень тем, кто панически боится формул изначально — что-то сомневаюсь. "В геометрии нет царских путей", в математике в целом, вероятно, тоже.
  • Математика на пальцах: линейно-квадратичный регулятор
    +1
    В формулах бывают опечатки; я сам не способен написать ни одной правильной формулы.

    Тогда понятно. Потому что у меня получилось, что в вашей формуле для u_0 (у которой в знаменателе 2+2N) вместо x_n должен быть x_0 (тем более, n никак не определяется), перед двойной суммой должна быть двойка, а внутренняя сумма (по j) должна идти не от 0, а от 1 (а то u_0 получается и слева, и справа). Впрочем, насколько я понял, у вас эта двойная сумма всё равно не вычисляется?
  • Математика на пальцах: линейно-квадратичный регулятор
    0
    Так тогда можно было сразу брать пункт про "бесконечный горизонт". Там и F от индекса не зависит, и явная формула для неё приведена.
  • Математика на пальцах: линейно-квадратичный регулятор
    0
    Не очень понятно, каким образом уравнение uk = — Fk xk, где F зависит от времени (через уравнение Риккати) превратилось в uk = — F xk с постоянной матрицей F.
  • Математика на пальцах: методы наименьших квадратов
    0
    А определитель — это мера того, насколько линейное отображение далеко от единичного.

    Что-то здесь не то. "Мера того, насколько линейное отображение далеко от единичного" — это какая-нибудь норма матрицы A-E, например, используется при ответе на вопрос "насколько точно мы определили ориентацию камеры". Определитель, если применять его к отображениям — объём параллелепипеда, являющегося образом единичного куба. Ничего общего.
  • Математика на пальцах: методы наименьших квадратов
    0
    К применениям равенства определителя нулю ещё можно добавить поиск собственных значений (откуда следует много дальнейших применений), проверка наличия кратных корней многочлена или общих корней двух многочленов… Из применений самого значения детерминанта сходу вспоминаются только вычисление ориентации базиса и якобиан системы функций — для замены переменных в кратных интегралах.
    Но важнее то, что из-за нескольких свойств (полилинейность, антисимметричность, мультипликативность) с детерминантом очень удобно работать. Когда что-нибудь хорошо выражается, скажем, через перманент (например, число возможных паросочетаний), мы отмечаем это, как курьёзный факт, и ищем другие подходы.
  • Месье, ваши problem solving skills не на высоте, или как я провалил одно собеседование
    0
    Просто сейчас рука плохо работает, текст набирать трудно.
  • Математика на пальцах: методы наименьших квадратов
    +1
    Два метра сетки между двумя столбами натягивал. Если столбы хорошо вкопать, а поверху натянуть трос, то держится.
  • Математика на пальцах: методы наименьших квадратов
    0
    Дело в том, что табличка маскирует само наличие квадратного уравнения: выписывается не производная, а сам объём (и глазом ищется максимум). Квадратное уравнение возникает только при аналитическом решении.
  • Математика на пальцах: методы наименьших квадратов
    0
    Похоже, что тут без производной и квадратного уравнения не обойтись. Хотя можно просто построить табличку в Excel, это будет даже быстрее. И точнее: в решении квадратного уравнения проще допустить ошибку.
  • Как непродуманные предупреждения компиляторов помогают портить совершенно правильный код
    0
    Интересно, что бы сказали компиляторы на код
    if( (unsigned long)filelength >= min((size_t)-1,(unsigned long)-1) ) {
    При каких соотношениях типов будет предупреждение?
  • Математика на пальцах: методы наименьших квадратов
    0
    Гиперреальные числа только на пальцах и можно объяснить — они очень близко к базовым понятиям. Система подмножеств, фильтры с примерами, главные и неглавные ультрафильтры — и всё. Проблема — понять зачем они нужны. Я так и не понял их преимущества над полем каких-нибудь хитрых обобщённых степенных рядов. Там и упорядоченность есть, и нужная мощность, и бесконечно малые на любой вкус. И построение гораздо более конструктивно.
  • Математика на пальцах: методы наименьших квадратов
    +1
    А откуда взялся делитель sqrt(a^2+b^2)?

    Если мы будем минимизировать сумму (ax+by-c)^2, то алгоритм выдаст a=b=c=0, и ничего с ним не сделать.

    Если взять точки (-2,0), (0,0), (3,0), то оптимальная прямая при штрафе (ax+by-c)/sqrt(a^2+b^2) будет y=x+4/3, а при штрафе ax+c-y — y=(6x+9)/7. Разница невелика, но она есть.
  • Математика на пальцах: методы наименьших квадратов
    +2
    Потому, что среднее арифметическое не меньше среднего геометрического. Очевидно же!
  • Математика на пальцах: методы наименьших квадратов
    0
    Это теорема Пикара:

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