×Закрыть

Математика в програмуванні

Я тут почитав кілька тем на форумі, де обговорювалося те, чи потрібна математика в програмуванні. І що цікаво, люди там демонстрували, як на мене, не зовсім вірне розуміння даного питання. Зараз спробую пояснити, що я маю на увазі.

Найбільше мене дивує те, що багато хто говорить, що математика в програмуванні — це написання програм для деякої математизованої предметної області. Мовляв, якщо ви не плануєте мати справу з такою предметною областю, то й математика вам не потрібна. Але невже ви думаєте, що суть математики полягає в використанні якихось алгоритмів і формул з певного домену знань? Суть програмування тоді, по-вашому, полягає в використанні фреймворків і мов програмування? Я веду до того, що оскільки людей, які роблять акцент лише на фреймворках і мовах програмування, ви називаєте «бидлокодерами», то чому ви тоді не бачите такої ж обмеженості в вашому поверховому трактуванні математики?

Як же тоді правильно трактувати математику (математику загалом й математику в програмуванні)? Я думаю, що математика загалом — це наука про дедуктивне мислення в рамках формалізованого середовища. Дедукція забезпечує рух від загального до більш конкретного: від аксіом до теорем, а формалізм породжує зрозумілий для всіх спосіб опису понять. Ось це і є математика! Не алгебри, геометрії чи абевегедетрії формують сутність математики, а саме дедукція + формалізм. Тому якщо ми говоримо про математику в програмуванні, то вона корисна тут перш за все тим, що дає можливість застосовувати дедукцію й формалізм. А ці дві речі є необхідними для будь-якого проекту, незалежно від математизованості його предметної області. Бо без дедукції й формалізму неможливо будувати архітектуру програмного забезпечення, та й взагалі будь-який системний розвиток цього програмного забезпечення без цих двох речей не є можливим. Адже дедукція в розробці програмного забезпечення являє собою шлях від створення приблизних абстракцій до їх поступового уточнення і нарешті реалізації, а це фундамент розробки. Формалізм же в розробці потрібен, щоб ці абстракції і їхні реалізації були описані якимось загальноприйнятим способом, інакше вони не будуть зрозумілими для тих суб’єктів, які з ними потім працюватимуть.

LinkedIn

Лучшие комментарии пропустить

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

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

А то, что вы называете математикой (дедукція + формалізм) — это логика и здравый смысл. Она нужна везде, а не только в программировании.

Допустимые теги: blockquote, a, pre, code, ul, ol, li, b, i, del.
Ctrl + Enter
Допустимые теги: blockquote, a, pre, code, ul, ol, li, b, i, del.
Ctrl + Enter

чтобы шлепать формы не надо ни синуса, ни косинуса, ни индукции, ни дедукции

Хочу відповісти на наведений нижче коментар, написаний Зеппом Бранниганом.

У вас в рассуждениях идет подмена понятий.
Есть математика в широком смысле — абстракция (мат.модели), логика и здравый смысл.
А есть математика в узком смысле — интегралы, дифуры, матан, лагранжиан.
Когда большинство людей утверждает, что в программировании математика не нужна, они имеют в виду, что не нужна высшая математика — математика в узком смысле.
А то, что вы называете математикой (дедукція + формалізм) — это логика и здравый смысл. Она нужна везде, а не только в программировании.

Я з цим коментарем не зовсім згідний.

Бо математика в згаданому вузькому смислі в принципі не має особливого значення (це те саме «бидлокодерство», просто в сфері математики). Я якраз до того й веду, що наявність чи відсутність знань з такої вузької математики — це майже одне й те ж. Тобто наявність таких знань фактично нічим не краща від їхньої відсутності, тому й обговорювати їх зайвий раз не варто.

Потім ви кажете, що дедукція+формалізм — це не стільки математика, скільки здоровий глузд. Ну по-перше, в деяких сферах діяльності, здоровий глузд полягає в іншому, як на мене. А по-друге, якщо ви подивитесь на сфери, де здоровий глузд таки полягає в дедукціїї й формалізмі, то саме математика його й забезпечує (явно чи неявно). Саме математика. Більше того, забезпечення такого здорового глузду і є основою математики. Наприклад, суть математики полягає не в завчанні формул на пам’ять, а у вмінні їх вивести, а також у розумінні того, чому саме вміння вивести є єдиним, що має значення. До речі, в рамках середньої освіти не викладаються такі речі, наскільки я можу судити. Думаю, що й в рамках вищої освіти, не всюди це акцентується. Тому сприйняття математики багатьма людьми є дещо хибним.

Чому я про це говорю, бо час від часу ведуться розмови про те, що програмування систем, не зав’язаних на математизовану предметну область — це якась нижча ліга. А я не бачу ніякої вищоліговості в поверховій бездумній роботі з математизованою предметною областю. Ви скажете, а чому обов’язково поверховій і бездумній? А тому що більш кваліфікована робота в цій області — це вотчина скоріше чистих математиків. Тобто це вже зовсім інші сфера діяльності, і далеко не факт, що вона буде цікавою для програміста. В той же час будь-який програміст, навіть не працюючий з математизованою предметною областю, кожного дня стикається з математикою. Причому з самою її суттю (дедукцією й формалізмом). Ці дві речі пронизують роботу програміста, багато в чому будучи її фундаментом. Тобто якщо ви — в першу чергу програміст (старший програміст, архітектор тощо) і вас цікавить математика, то просто приділяйте увагу дедукції й формалізму в вашій повсякденній роботі і таким чином ви повністю зможете реалізувати себе як людину, яка в міру своєї професійної діяльності має прикладний інтерес до математики.

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

Не матиматика... Не завчити пару операцій з матрицями, чи дві пари тригонометричних функцій — потрібно бути імбіцилом. Це зовсім не те чого повинен прагнути ВТУЗ. Математик той хто добре оріентується в багатьох математичних підмножинах знаннь, і для кого математика більш-меньш континиум — тобто він знає так багато і так чітко що може виводити та доводити те чого не знає...

А «матрєці» в гемдеві це формулозадроцтво — а-ля магія.

Вот что бы перестать считать матрицы — магией, нужно учить математику. Суть тригонометрических функций, как они связаны с векторами. За счет чего умножение на матрицу
дает трансформацию вектору (как оно работает). Что знак результата операции означает на деле (к примеру, откуда появилась функция atan2). Без этого всего, самостоятельно можно только делать translate и rotate модельке, остальное — только за счет копипасты (к примеру если нужно сделать какую-то кастомную камеру в игре, или object picking математически).

Определяя всякий ссылочный тип в Java, который играет роль Entity/DomainObject, необходимо переопределить метод java.lang.Object.equals(Object). equals — обязано корректно определить отношение эквивалентности (т.е. должно быть рефлексивным, симметричным и транзитивным — иначе коллекции могут неадекватно себя вести).
А теперь вопрос:
class Point {
....double x;
....double y;
....public Point(int x, int y) {
........this.x = x;
........this.y = y;
....}
....public boolean equals(Object obj) {
........if (obj == null || obj.getClass() != Point.class) {
............return false;
........}
........Point that = (Point) obj;
........return Math.sqrt((this.x-that.x)*(this.x-that.x) + (this.y-that.y) * (this.y-that.y)) < 0.001;
....}
}
Корректно реализовал ли метод equals?
.
На этот вопрос должен отвечать всякий, кто претендует на позицию Java Junior. Object — это предок всех объектов и что в нем за методы обязан знать каждый. Определение новых классов, соответствующих предметной области — ежедневное занятие.
.
Ну и да, алгебра — бесполезная наука :)

Безотносдительно математики тебе двойка уже за это: «if (obj == null || obj.getClass() != Point.class)» так как поведение будет неправильно работать с потомками класса Point. Матчасть поучил бы что ли прежде чем других учить?

Если ты запустишь божественную IDE IDEA, то при попытке автоматически сгенерировать метод equals увидишь интересный вопрос — реализовывать ли сравнение для подклассов (instanceof) или нет (сравнение классов). Почему это? А?
Может потому, что реализация отношений эквивалентности на иерархиях приводит к нарушению свойства симметричности.
Пример нужен? Или мозгов хватит придумать?

Пример нужен? Или мозгов хватит придумать?
Да. Нужен пример пожалуйста.

class ColoredPoint extends Point {
....public boolean equals(Object obj) {
........if (...|| obj instanceof ColoredPoint) return false;
....}
}
.
Point p = new Point(10, 20);
ColoredPoint cp = new ColoredPoint(10, 20, Color.RED);
p.equals(cp) != cp.equals(p)

ЛОЛ, да ты задал несиметричное отношение, что совсем не обозначает что нельзя задать симетричное.

Если ColoredPoint будет сравним с Point, тогда нарушится транзитивность.
reality_hacker, пример показать или мозгов хватит придумать?

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

Point p = new Point(10, 20);
ColoredPoint black = new ColoredPoint(10, 20, Color.BLACK);
ColoredPoint white = new ColoredPoint(10, 20, Color.WHITE);
black.equals(p) == true
white.equals(p) == true
black.equals(white) == false

Я уже писал, да, ты придумал кривую реализацию equals, и теперь пытаешься доказать что она кривая? Где логика?
Если ты не понял в чем проблема, твоя реализация equals ломает все для потомков Point если они этот equals не переопределили, так как для ColorPoint a; a.equals(a) == false. Если ты поменяешь == на instanceof то все будет чики пуки. Есть конечно 100500 других вариаций этой проблематики, в том числе как правильно обрабатывать ситуации когда ColorPoint переопределяет equals как в твоем примере, но это уже тебе домашнее задание на дом.

Если ты поменяешь == на instanceof то все будет чики пуки.

Не буде. Це класична проблема, ознайомся з нею. Це також одна з причин, чому наслідування є більш проблемним, ніж композиція.

Підказка: якби ти спробував зрозуміти, що таке відношення еквівалентності серед класів і їхніх підкласів, то ти би навіть не намагався будувати такі відношення на базі instanceof.

Особисто я думаю, що не інші люди повинні наводити тобі приклади того, чому instanceof не підходить (бо це класика і бо це логічно). А ти маєш навести приклад того, чому instanceof підходить: опублікуй тут свою ієрархію класів, яка, по-твоєму, може щось обгрунтувати.

Опуская твои бла-бла-бла набросы, какие проблемы будут с иерархией Point & ColorPoint.

Скажу так. Все-таки є один випадок, коли використання instanceof при визначенні equals може приносити користь. Це випадок наступний: нащадку не потрібно перевизначати equals предка. Тобто випадок це специфічний, нащадок в такому випадку не є чимось особливо новим порівняно з предком.

Як би там не було, цей згаданий мною випадок не є випадком Point-ColorPoint, який обговорювався вище. Бо ColorPoint є повноцінним нащадком із модифікованим станом (і новою логікою еквівалентності, побудованою на базі цього нового стану).

Загалом про equals можеш почитати тут: www.artima.com/...s/equality.html

Ну или Блоха «Эффективная Java».

это крута, но почему 0.001, а не 0.01 или 0.0001?

Было бы веселее попросить Ивана корректно реализовать метод equals, правда я уже подозреваю чем это закончится.

Взагалі-то він правий, що в тій стрічці помилка. Правильна реалізація obj.getClass() != this.getClass(), а така реалізація як в оригіналі буде неправильно працювати з нащадками.

Цікавий приклад. В мене на проекті одного разу я чув пропозицію подібно equals реалізувати.
Крім проблеми транзитивності і симетричності тут ще проблема в неможливості реалізувати нетривіальний hashCode (нетривіальний = не «return 0;»).

проблема в неможливості реалізувати нетривіальний hashCode (нетривіальний = не «return 0;»).
Objects.hashCode(x, y) ?

З документації:
If two objects are equal according to the equals(Object) method, then calling the hashCode method on each of the two objects must produce the same integer result.

При такій реалізації методу equals яку подано вище, ця вимога буде порушуватися якщо x, y не рівні між собою але в межах похибки (заданої в equals).

Ты прав, здесь не поспоришь.

Почему невозможно? Вего-то надо в сравнении и вычислении хеша использовать не x, y, а round(x/0.001), round(y/0.001).

<edited>
Я мав на увазі, що неможливо написати нетривіальний hashCode саме для такого equals як в прикладі, а не в принципі для класу Point.
Проблема побудови хеш коду лежить в нетранзитивності операції. Можна довести, що будь-які дві точки повинні мати однаковий хеш-код, інакше контракт буде порушуватися.

Не задумывался, действительно.
И скорее всего, принципиально невозможно. Упремся во что-то типа: хотя множества R[0,1] и R[0,1]xR[0,1] равномощны, не существует в две стороны непрерывного отображения. В таком случае невозможно окрестности в RxR (для equals) отобразить в окрестности R (для hashCode).

Для каждой точки (0.a1a2a3a4a5..., 0.b1b2b3b4b5...) делаем отображение в 0.a1b1a2b2a3b3a4b4... Покажешь каким макаром это не биекция или не непрерывное отображение?

Диагональная конструкция Кантора (которую ты применил) порождает разрывное отображение.
0.2×0.3 -> 0.23
но
0.199×0.3 -> 0.1399.
Ты математику что-ли вообще не учил в ВУЗе?

Диагональная конструкция Кантора (которую ты применил) порождает разрывное отображение.
0.2×0.3 -> 0.23
но
0.199×0.3 -> 0.1399.
А ты не находишь что между числами 0.23 и 0.1399 есть еще туева хуча точек которые совершенно случайно могут соединить разрыв?
ы математику что-ли вообще не учил в ВУЗе?
Нет, только в детсаду.
еще туева хуча точек которые совершенно случайно могут соединить разрыв?
Я так понимаю ты не понимаешь разницы между непрерывным отображением и отображением, образ которого всюду плотен или односвязен?
.
Непрерывность — это рассуждения в терминах дельта-эпсилон.
И вот я тебе строю последовательность точек
(0.19, 0.3), (0.199, 0.3), (0.1999, 0.3), (0.19999, 0.3), (0.199999, 0.3) которая приближается к (0.2, 0.3), но ее образы — не приближаются.
.
Слушай, ну вот ты — хороший программист, но не силен в математике. Ну вот что тебя заставляет влезть и сюда еще? Шило?

Нет, я думаю что отлично понимаю.

Непрерывность — это рассуждения в терминах дельта-эпсилон.
И вот я тебе строю последовательность точек
(0.19, 0.3), (0.199, 0.3), (0.1999, 0.3), (0.19999, 0.3), (0.199999, 0.3) которая приближается к (0.2, 0.3), но ее образы — не приближаются.
.
Слушай, ну вот ты — хороший программист, но не силен в математике. Ну вот что тебя заставляет влезть и сюда еще? Шило?
Это конечно очень мило что ты редактируешь опосля свои коменты, и я действительно ошибся со своим примером, но это не делает твою ахенею сколь либо рациональной. То что нельзя построить не вырожденную хешкод функцию доказывается намного проще, без пространных разглагольствований о топологиях.

Предположим у тебя есть точка A(0, 0) и точка B(0.0001, 0), для них equals == true, значит хеш код тоже должен быть одинаков. Теперь есть точка C(0.0002, 0), equals(C, B) == true => hashcode© == hashcode(B), и так инкрементально мы можем распространить эсперимент на всю числовую прямую, а потом и на плоскость, т.е. при таком определении equals как у тебя все точки на плоскости вынуждены иметь одинаковый хешкод.

Структура топологии, индуцированной евклидовым расстоянием на RxR чем-то отличается от структуры топологии, индуцированной евклидовым расстоянием на R. Но вот чем именно — надо функан поднимать. В кэше нет.


Но вот чем именно — надо функан поднимать.
Размерностью © КО

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

Поэтому:


То что нельзя построить не вырожденную хешкод функцию доказывается намного проще, без пространных разглагольствований о топологиях.
Принцип Дирихле рулит и бибикает.
Размерностью © КО
Размерность — это свойство векторных линейных пространств. Это слишком сильная для нас структура. Невозможно даже построить взаимооднозначное отображение линейных векторных пространств с различной размерностью (RxR <-> R).
Но мы хотим строить. Поэтому отбрасываем векторность и берем более обширный и менее стесняющий класс — топологические пространства (с топологией индуцированной евклидовым расстоянием). В рамках топологических пространств reality_hacker построил (через диагональную конструкцию Кантора) взаимооднозначное отображение, и я утверждаю, что всякое такое отображение принципиально не может быть непрерывным.
В рамках топологических пространств reality_hacker построил (через диагональную конструкцию Кантора) взаимооднозначное отображение, и я утверждаю, что всякое такое отображение принципиально не может быть непрерывным.
А зачем нужна эта непрерывность? Как уже сказали в компьютерах математика дискретна, т.е. непрерывность иррелевантна.

Нетривиальный hashCode, согласованный с equals c семантикой «быть близко» — это огрубление отображения RxR -> R до RxR -> int.
А огрублять то и нечего.
Это к вопросу — построить нетривиальный hashCode для Point с equals с семантикой — быть близко на плоскости.

Во первых не R а небольшое подмножество рациональных чисел, во вторых второе отображение прерывно по определению, нафига тебе непрерывность?


Размерность — это свойство векторных линейных пространств.
Нет, размерность задается на любом топологическом пространстве.

Невозможно даже построить взаимооднозначное отображение линейных векторных пространств с различной размерностью (RxR <-> R).
Нет, вы грубо ошибаетесь.
Нет, вы грубо ошибаетесь.
Из википедии:

«Rm and Rn are not homeomorphic for m ≠ n.»

А вы путаете гомеоморфизм и биекцию.

Да, я не правильно прочел, в другой цитате Иван говорит еще и о непрерывности.

Нет, размерность задается на любом топологическом пространстве.
Размерность векторного пространства — это мощность базиса. А что такое размерность топологического пространства? Мощность множества всех открытых множеств?

А что такое размерность топологического пространства?
Как ни странно, топологическая размерность))
Она же размерность Лебега.

Да, забыл сказать спасибо, тогда резко ушел _пытаться_читать_ Александрова «Введение в теорию размерности», хотя это для меня уже далековато:(

Мені здається, що головна проблема цього методу equals в тому, що він задає нетранзитивне відношення (все решта другорядне). Тобто через нетранзитивність цей метод треба відкинути зразу, обговорювати будь-які інші деталі роботи в рамках описаної ним логіки таким чином немає смислу.

Ну наконец то в топике появился Капитан. Мы так долго ждали тебя!

Это да.
Но тогда вопрос, какую наиболее близкую к этой (основанной на понятии лежать рядом (малое евклидово расстояние)), но корректную математичеcки реализацию можно дать?
Мне пока приходит в голову только округлять x и y до «центров квадратов», скажем до (int)(1000 * x) и (int)(1000 * y) и сравнивать их. Это явно лучше для double/float чем точное сравнение чисел с плавающей точкой.
Можно ли придумать что-то лучше или другое?

Напевно заокруглювати x і y. (Правда, не зовсім розумію, що таке заокруглювати x і y до «центрів квадратів».)

Мені здається, що навіть комп’ютер з безмежною пам’яттю не зміг би представити всі точки дійсної площини, бо їх там не тільки безмежно багато, а їх ще й незліченна кількість. Тобто в принципі не існує алгоритму, за допомогою якого їх всіх можна було б віртуально пронумерувати й таким чином взяти до уваги.

Товарищи читающие, очень прошу вас обратите внимание на

Корректно реализовал ли метод equals?
Да, я знаю, что метод реализован некорректно, нарушается свойство транзитивности. Это, блин, я его нарушил. Специально.
Вопрос к «нелюбителям математики» — могут ли они определить корректен ли метод. Ответ — некорректен («любители математики» легко справляются).

Если тебе кто-то скажет что математика не нужна в программировании, согласись, не спорь. Пусть им она не будет нужна.

Если спросит начинающий программист, то скажи что нужна

В одном проценте нужна серьёзная и в пяти процентах уровня средней школы

ось так, наприклад, думає й пише людина яка знає математику — thedeemon.livejournal.com/65083.html — круто ж!

ИМХО.
1. Можно ли заработать на хлеб с маслом не зная математики? Ответ да можно.
2. Программист(как собственно и любой инженер) не знающий математики это быдлокодер. И не надо кричать, что ты своим быдлокодом заработал на 10 зеркалок, 5 велосипедов итд, гаишник зарабатывает не меньше тебя.
PS сам, к сожалению, знаю математику не очень.

Кстати, найти человека, который вообще не знает математику — этож постараться надо. Так что наверное все таки стоит говорить о каких то особых разделах?

Кстати, найти человека, который вообще не знает математику — этож постараться надо.
Точней говоря невозможно. Те совершенный быдлокодер в вакууме это понятие абстрактное. Впрочем тот кто не может вывести, диф-уравнение маятника довольно к этому близок.
Так что наверное все таки стоит говорить о каких то особых разделах?
Думаю следует говорить об уровне который позволит изучить особые разделы если такая необходимость возникнет. Курса математики технического вуза для этого вполне достаточно.
Впрочем тот кто не может вывести, диф-уравнение маятника довольно к этому близок.
Нууу, вот вы и зафейлили подавляющее большинство программистов. Они конечно отмажутся, и стянут в википедии формулу, но мы то знаем...

Хотя, если честно, я не вижу в этом необходимости. В упор не могу найти реального применения (кроме как: если сделал — мозги есть)

Вы серьёзно хотите на собеседованиях давать интегральчик решать?

Нууу, вот вы и зафейлили подавляющее большинство программистов.
Да не, не все так плохо. Обычно после 10-20 сек ступора потихоньку начинают вспоминать, я эксперимент на коллегах проводил :)
В упор не могу найти реального применения (кроме как: если сделал — мозги есть)
Разве «мозги есть» не важно?
Вы серьёзно хотите на собеседованиях давать интегральчик решать?
А это зависит от того кто вам нужен. Зачем, к примеру, формошлепу дифуры?
Разве «мозги есть» не важно?
Важно. Но у человека может быть пробел именно в дифурах. Правильное собеседование — это искать что человек знает, а не стараться его зафейлить.
Зачем, к примеру, формошлепу дифуры?
не знаю. Расскажете кому они нужны? А заодно, и кто такие формошлёпы? И зачем они кому-то нужны.
Важно. Но у человека может быть пробел именно в дифурах.
Тогда ему однозначно не стоит писать, софт для обработки ЭКГ, управления станками, итд.
Правильное собеседование — это искать что человек знает, а не стараться его зафейлить.
Ищите, но помните...
Тогда ему однозначно не стоит писать, софт для обработки ЭКГ
Из-за одной формулы? Предлагаете екомерс-программистов исключительно из бывших бухгалтеров/заведующих складом наберать?

Я сам часто «перегибаю палку» в плане необходимости чего-либо, но подумайте — сколько времени решение дифуров займёт от рабочего времени? 1%? 0.5%?

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

На счет екомерс не знаю никогда в этой области не работал, но думаю знание предметной области все-таки важно.
Конечно важно. Поэтому внимательно слушаешь бухгалтера, пишешь истории/алгоритмы и тщательно их согласовываешь. Вплоть до подписи.

А теперь представте, сколько вы потратите времени на поиск человека, который был бы и хорошим программистом и отличным бухгалтером. И сколько он будет стоить.

Со всеми остальными областями — таже фигня. Берём спеца, который офигенно знает предметную область, и выковыриваем из него знания.

И важно не сколько времени придется решать, скорей всего вообще не придется. Просто важен сам факт знания.
Кому важен то? :) Вам эта фраза абсурдом не кажется? А если подсмотрит в википедии — всё ок, можно работать?
Берём спеца, который офигенно знает предметную область, и выковыриваем из него знания.
Вам со спецом придется говорить «на одном языке». Представьте себе спец говорит кодеру — тут лучше применить окно Ханна, а тот не то что про Ханна, но и про ДПФ ничего не слышал, все, немая сцена.
Кому важен то? :) Вам эта фраза абсурдом не кажется? А если подсмотрит в википедии — всё ок, можно работать?
Нет, не кажется. Пусть смотрит, если поймет то все ОК. С прошитыми знаниями как-бы никто не рождается.
Вам со спецом придется говорить «на одном языке».
Вы думаете я всегда понимал бухгалтеров? Непонятный термин — спрашивай. В чём проблема то? На то и нужен спец, чтоб формулы/алгоритмы расписал. А уж как его запрограммировать, хранить и использовать — это мы придумаем.

Или как, тыжпрограммист, обязан ВСЁ знать. Кстати, чего только математика? А химия? Биология? Медецина? Астрофизика? Вдруг вас об этом спросят?

Вы думаете я всегда понимал бухгалтеров? Непонятный термин — спрашивай. В чём проблема то?
Проблема в том, что тратить время специалиста на чтение курса вышки, причем с неясным результатом, как минимум неразумно.
Или как, тыжпрограммист, обязан ВСЁ знать. Кстати, чего только математика? А химия? Биология? Медецина? Астрофизика? Вдруг вас об этом спросят?
Нет математики достаточно. Когда стоит задача моделирования чего-то или управления чем-то то прежде всего строится мат-модель и вот ее-то программист и должен понять.

>>>Тогда ему однозначно не стоит писать, софт для обработки ЭКГ, управления станками, итд.

і да і ні... Тільки як я почав писати такого роду программи почав перевідкривати для себе математику...

P.S.: ...про сумне — у Києві це не особливо комерційні напрямки.

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

>>>PS Холтеровские мониторы?
Ні, але схоже...

>>>Так переоткрывать то намного проще, а если в свое время ничего не учил и все надо с нуля?
...і знову і да і ні... Коли перевідкривав то зрозумів, що багато чого таким макаром як у ВТУЗі неможливо було вивчити взагалі... Даром втрачена молодість ##@"!!ля...

И не надо кричать, что ты своим быдлокодом заработал на 10 зеркалок, 5 велосипедов итд, гаишник зарабатывает не меньше тебя.
Надо федя, надо.
Так как применив логику и здравый смысл, мы таки прийдем к тому, что чобы заработать на 10 зеркалок и 5 велосипедов — математика не нужна. А то что у вас и вам подобным комплекс неполноценности, и вы напрвао и на лево кричите «быдлокодер», это другой, на самом деле, не важный фактор.

да просто понятие «быдлокодер» у всех разное. Для кого то это тот, кто пишет на php. Для других — тот кто делает «говносайты», а не крутые мат. проекты. И так далее.

Каждый самоутверждается в меру своих возможностей, и с этим ничего не сделаешь. И самый простой способ самоутвердится — назвать другого идиотом (быдлокодером)

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

Дык, а если бы вы 5 лет потратили на некую фигню — признались бы, что выкинули время на ветер?

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

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

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

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

А то, что вы называете математикой (дедукція + формалізм) — это логика и здравый смысл. Она нужна везде, а не только в программировании.

Процентов 70 программистов не могут прикинуть время подбора 5-значного id из 30 символов. На самом деле, такая нужда бывает редко, но когда видишь, как на ней стопорится «сениор» — теряешь к нему уважение.

Но может, это только моя придурь, не обращайте внимания.

wtf «5-значного id из 30 символов» ?

Иногда, нужно сгенерировать идентификатор для.. Ну не знаю — сессии, запроса, ключа доступа — фиг его знает чего. И иногда возникают вопросы секьюрности, типа — «вот ты сгенерировал идентификатор длиной 5 знаков из набора 30 знаков. Какова его надёжность?» (числа — не суть важно).

Я доходчиво обьяснил?

Надо генерировать GUID’ы, а не придумывать свои, чтобы потом гадать — взламываются/подбираются они на современных машинах или нет.

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

Надо генерировать GUID’ы, а не придумывать свои, чтобы потом гадать — взламываются/подбираются они на современных машинах или нет.
Возьми готовое, не надо будет включать мозг. Всё правильно. Именно поэтому я и писал, что основное для программиста, в большинстве случаев — это стиль кода, копи-паст и «делай как тут». И это работает.

Опытный математик:
— Используй теорию дифференциальных уравнений.
Вы:
— «Возьми готовое, не надо будет включать мозг». Нет, не надо использовать готовую проверенную теорию, нужно придумать свою. А все кто не придумывают свою — просто быдломатематики. Так получается?

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

В программировании так же. Десятки людей с опытом по 10-20 лет пишут современные фреймвоки, потом десятки тысяч опробуют их. Затем фиксятся баги и пишется новая версия. И так снова и снова.

В программировании мы называем это фреймворками, в математике — теорией.
Но общее у них в том, что
а) Хорошую теорию, как и хороший фреймворк написать трудно
б) Они пишутся для того чтобы тысячи людей использовали их, а не писали свои.

Нет, не надо использовать готовую проверенную теорию, нужно придумать свою. А все кто не придумывают свою — просто быдломатематики. Так получается?
Ну и где я это говорил? Я вообще где то говорил что фреймворки и использование наработок — это плохо?

Сравнение теории и фреймворков — полный бред. Хотя бы потому, что фреймворки никто не доказывает, а недоказанными теориями никто не пользуется.

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

Основная причина этому в том, что основная масса программирования — это «производство», а не «научная работа». А значит и методы надо применять как в производстве.

Нет, сравнение теории и фреймворков очень точное. И то и то — инструмент, чтобы решать поставленные задачи.

Мы используем мат.аппарат и различные математические теории для решения различных математических задач.

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

Создание новой теории в математике очень точная аналогия нового фреймворка в программировании — появился новый удобный инструмент.

Нет, сравнение теории и фреймворков очень точное. И то и то — инструмент, чтобы решать поставленные задачи.
Сравнение молотка и фреймворка — более менее точно. А теорию нужно и сравнивать с теорией. Её в программировании тоже много.

Использование теории гарантирует правильное решение задачи. Т.е. гипотенуза равна корню из суммы квадратов катетов — всё, задача решена правильно.

Использование фреймворка вообще ничего не гарантирует, это как записывать решение на бумаге — так решать проще, но не факт что задачу решите.

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

Вы хоть один такой фреймворк видели? Логически обоснован для использования на классе задач, а не «чуваки, я попробовал, прикольно!»

Ну как бы надёжность не в сложности перебора самих идентификаторов, для примера, я могу 256 битный ключ перебрать где-то за 10 секунд, а в сложности проверки является ли этот ключ подходящим. Если для атаки man-in-the-middle нужно подобрать сессионный ключ длиной 5 знаков из набора 30 знаков, но система даёт ответ раз в секунду и сессионный ключ действителен 60 секунд, то это вполне надежный идентификатор, но есть вероятность случайного угадывания за 60 попыток довольно-таки высокая.

но есть вероятность случайного угадывания за 60 попыток довольно-таки высокая.
~n/400 000 , Где n — кол-во валидных ключей. Вот это посчитать как раз могут далеко не все. О чём и речь.

256 за 10 сек?
2^256 ~ 1.58 * 10^77. Если перебирать 1000000*10^9 комбинаций в сек это уйдет (1.58 * 10^(77-12))/(3600 * 24 * 365) = 3.67*10^57 лет. Возраст вселенной, для сравнения, около 14*10^9 лет.

Нда, не заметил, хотя и показалось странным. Но может Mike имел ввиду не «перебрать все возможные значения от 0 до 2^256»? Интересно было бы услышать его комментарий.

Спасибо, я этот вопрос буду задавать на собеседовании :) Естественно, задача на подумать, а не решать в лоб. Например, способ хранения может быть не классическим, можно использовать 32Gb RAM, и т.д. Способов множество, 10 секунд можно заменить на at an early date, если смущает.

Что-то не совсем понятно. Если стоит задача подобрать ключ к чем-то зашифрованному криптостойким алгоритмом, если это ключ не генерится как хеш от пароля, то что можно сделать кроме тупого перебора?

Хм, это уже интереснее. тактовая частота процессора допустим 4 ГГц (4*10^9). Допустим также, что нам нужно просто инкриментировать счётчик, и это занимает 1 такт. Также, процес неплохо параллелизируется, так что запустим его в 4 потока.

Итого, мы получим 1.6 *10^10 чисел в секунду. Полный перебор пройдёт за ~10^67 секунд, или ~ 3*10*59 лет.
Фигово.

Берём GeForce Titan: ~3000 ядер, ~1ГГц (сильно округляю в большую сторону, и да, я слабо представляю как такое запустить на GPU, но пусть это возможно). 3* 10^12 чисел в секунду, полный перебор за 10^57 лет. Всё равно дофига.

Пусть в мире есть 10^10 таких чипов, задействуем их всех — 10^47 лет.

Mike, расскажите, пожалуйста свой способ, перебрать все числа хотя бы за 1 год.

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

Квантовый компьютер должен(!) помочь в разложении числа на простые множетели, но у нас то вопрос про перебор значений, верно? А это классика делает весьма хорошо.

А это классика делает весьма хорошо.
Ну с 256-ю битами вроде как то слабо справляется?

Я к тому, что КК сделает это не быстрее. Да и пока это ещё далекое(?) будущее.

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

Ни разу. Предложи алгоритм / конструкцию КК которая решит это быстрее. Так же интересен размер этого кк.


задача как раз под квантовые компы
Квантовый компьютер может ускорить неупорядоченный поиск с N до sqrt(N), не более.
Прикол с факторизацией в том, что разложение на простые множители единственно и поэтому КК может факторизовать за полиномиальное время.

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


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

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

Если у вас есть задача коммивояжёра, и случайно окажется, что есть, скажем 10 оптимальных вариантов, то вы не сможете решить ее каким-то хитрым способом. Более того, вы не можете заранее сказать что тут не единственное оптимальное решение не решив саму задачу.

Интуитивно считайте, что единственность факторизации дает алгоритму Шора эвристику, благодаря которой он решает задачу не тупым перебором и поэтому за полиномиальное время.

Если у вас есть задача коммивояжёра, и случайно окажется, что есть, скажем 10 оптимальных вариантов, то вы не сможете решить ее каким-то хитрым способом. Более того, вы не можете заранее сказать что тут не единственное оптимальное решение не решив саму задачу.
А как из того что ты написал получается несуществование хитрого способа?
Интуитивно считайте, что единственность факторизации дает алгоритму Шора эвристику, благодаря которой он решает задачу не тупым перебором и поэтому за полиномиальное время.
Я не понял мысли. Еще раз, в нашем тупом переборе тоже единственный правильный верный вариант. И в зависимости от функции преобразования все вполне может свестись к факторизации чисел как в алгоритме Шора.

А как из того что ты написал получается несуществование хитрого способа?
А я не объяснял почему, я привел пример.
А отсутствие хитрого способа будет следовать из NP-полноты задачи.

Я не понял мысли. Еще раз, в нашем тупом переборе тоже единственный правильный верный вариант. И в зависимости от функции преобразования все вполне может свестись к факторизации чисел как в алгоритме Шора.
Еще уточняю — под перебором я подразумеваю NP-полные задачи, вы их не можете решить иначе, чем за экспоненциальное время. Это «общий случай» — вы ищите иголку в стоге сена и ни каких подсказок нет.
В случае факторизации — она есть.
Что не ясно?
А я не объяснял почему, я привел пример.
А отсутствие хитрого способа будет следовать из NP-полноты задачи.
НУ факторизация чисел тоже далеко не П, а поди ж ты.
Еще уточняю — под перебором я подразумеваю NP-полные задачи, вы их не можете решить иначе, чем за экспоненциальное время. Это «общий случай» — вы ищите иголку в стоге сена и ни каких подсказок нет.
В случае факторизации — она есть.
Что не ясно?
Не ясно то что не зная функции преобразования ты заключил что никаких подсказок нет.

Фактизация в BQP и это не в NP, отсюда и профит от КК.


Не ясно то что не зная функции преобразования ты заключил что никаких подсказок нет.
Предположим я ищу число в не отсортированном массиве. Какие у меня подсказки и с чего я должен считать, что они должны быть?
Фактизация в BQP и это не в NP, отсюда и профит от КК.
То что BQP не пересекается с NPC я так понимаю еще не доказано.
Предположим я ищу число в не отсортированном массиве. Какие у меня подсказки и с чего я должен считать, что они должны быть?
Ну это уже другая задача, сильно отличающаяся от исходной, какой смысл ее обсуждать.

То что BQP не пересекается с NPC я так понимаю еще не доказано.
То, что второе начало термодинамики не доказано, пока вдохновляет только создателей вечных двигателей.

Все известные NPC полиномиально сводимы друг к другу и в том числе к поиску по неупорядоченной БД.
Алгоритм Гровера дает O(sqrt(N)), где N=2^n.
И это нижняя грань, которая упирается в линейность квантовой механики.

Все возможные ускорения потребуют маловероятных физических условий:
— При нелинейной квантовой механике мы можем добиться экспоненциального прироста. Попутно экспоненциально размножив ошибку. Fail.
— Любители вуду и теорий скрытого параметра может ускорится аж до О(N^1/3), что тоже погоды не делает. Fail.
— И только путешественники во времени могут полиномиально решать почти все, что угодно. Только постройте сначала машину времени. Я не специалист по космологии, но первый и самый известный случай решения уравнений Эйнштейна, допускающий путешествия во времени — Геделева метрика не допускает расширения Вселенной, что противоречит наблюдаемым данным. Fail.

Именно поэтому результат Шора и заставил всех сцать кипятком. Если бы он показал, что факторизация лежит в QMA(квантовый «аналог» NP), то всех бы это волновало бы даже меньше чем соблюдение Гаагских деклараций.


Ну это уже другая задача, сильно отличающаяся от исходной, какой смысл ее обсуждать.
Поиск и подбор пароля именно ею и является. Если разработчик криптосистемы нигде не налажал, естественно. А атаки на реализацию — это частный случай, и опять таки тут должна быть дополнительная информация — как реализован генератор псевдослучайных чисел, особенности самой реализации, технические детали оборудования.
То, что второе начало термодинамики не доказано, пока вдохновляет только создателей вечных двигателей.
Ну когда то люди тоже думали что земля плоская.
Все известные NPC полиномиально сводимы друг к другу и в том числе к поиску по неупорядоченной БД.
Это очевидно потому что их NPCшность доказана сведением, что не исключает того что есть куча еще не сведенных задач, некоторые из них вполне могут быть NPC.
Поиск и подбор пароля именно ею и является. Если разработчик криптосистемы нигде не налажал, естественно.
Та нет, последовательность арифметических действий, коей является классическая функция преобразования вполне может выражаться в квантовой арифметике, а поиск по массиву в 2^256 элементов(или сколько там ты предлагаешь) свести к такой арифметике несколько сложнее по понятным причинам.

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

Та нет, последовательность арифметических действий, коей является классическая функция преобразования вполне может выражаться в квантовой арифметике,
Далась вам «функция преобразования». Как показала практика информацию можно эффективно шифровать и на классическом компьютере. Всем интерисует как быстро можно взломать криптосистему.

а поиск по массиву в 2^256 элементов(или сколько там ты предлагаешь) свести к такой арифметике несколько сложнее по понятным причинам.
Да нефиг делать — алгоритм Гровера работает же.
Я тут пытаюсь сколько-то постов объяснить, что он не поможет брутфорсить, так как не дает экспоненциального прироста в скорости.

Так что под угрозой от КК только классические асимметричные криптосистемы.

Если вы не читали мой пост, то там я в 2154 символах объясняю почему факторизация не будет в NPC.
Так ты поспеши разместить эти символы в каком нибудь журнале, потому что насколько я понимаю это тоже еще не доказано что факторизация не npc. Причем это доказательство имело бы еще и более далекие последствия в плане установления отношения между bqp и npc, и некоторыми другими классами. Но что-то мне подсказывает что ты ерунду написал.
Далась вам «функция преобразования». Как показала практика информацию можно эффективно шифровать и на классическом компьютере. Всем интерисует как быстро можно взломать криптосистему.
Я не понял мысли, да, можно шифровать, с помощью некоторой функции.
Да нефиг делать — алгоритм Гровера работает же.
А алгоритм Гровера вдруг стал искать числа в неотсортированном массиве?
Я тут пытаюсь сколько-то постов объяснить, что он не поможет брутфорсить, так как не дает экспоненциального прироста в скорости.
В том то и дело что брутфорс брутфорсу рознь, и пример с массивом совсем не в тему.

Так ты поспеши разместить эти символы в каком нибудь журнале, потому что насколько я понимаю это тоже еще не доказано что факторизация не npc. Причем это доказательство имело бы еще и более далекие последствия в плане установления отношения между bqp и npc, и некоторыми другими классами. Но что-то мне подсказывает что ты ерунду написал.
Risus abundat in ore stultorum.
Поскольку ваше что-то явно не знакомо с квантовой теорией сложностью и квантовой информатикой, то ваш сарказм убог и неуместен.

Dixi.

Лол, ты же сам полную херню написал. Или давай пожалуйста доказательство npc-шности факторизации в студию

Я написал почему факторизация НЕ в NPC.
Если не осилил — твои проблемы.

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

Я написал почему факторизация НЕ в NPC.
Так я тебе посоветовал, опубликуй свои обьяснения, прославишся и осчастливишь научный мир.
Если не осилил — твои проблемы.
А поскольку ты постоянно меняешь свои утверждения по ходу дискуссии, то ты страдаешь деменцией или скучающий тролль.
Какой унылый пердеж в лужу.

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

Какой унылый пердеж в лужу.
Ну покажи, что ты не унылый пердун, как я — приведи тут мои цитаты, где я несу ерунду и объяснения для непосвященной аудитории(вроде меня).

А то вдруг окажется, что это я виноват в катастрофическом падении уровня образования студентов, а я в силу своей некомпетентности не знаю. :S

Эта информация озаряет научный мир уже давно.
А можно по конкретнее, а то я где только не читал, везде написано что это не доказанная гипотеза.
Ну покажи, что ты не унылый пердун, как я — приведи тут мои цитаты, где я несу ерунду и объяснения для непосвященной аудитории(вроде меня).
А то вдруг окажется, что это я виноват в катастрофическом падении уровня образования студентов, а я в силу своей некомпетентности не знаю. :S
Я тебе в четырех последних постах пытаюсь втолковать, ссылок-аргументов на обратное я как то не вижу пока.

А можно по конкретнее,
Почему факторизация в BQP — оригинальная статья Шора
Оптимальности алгоритма Гровера просвещенно так много статей, что ссылки на целую пачку можно найти даже в википедии, и почти в любых лекциях по квантовым вычислениям.

При нелинейной квантовой механике мы можем добиться экспоненциального прироста. Попутно экспоненциально размножив ошибку. Fail.
Nonlinear quantum mechanics implies polynomial-time solution for NP-complete and #P problems
arXiv:quant-ph/9801041

Любители вуду и теорий скрытого параметра может ускорится аж до О(N^1/3), что тоже погоды не делает. Fail.
Quantum Computing and Hidden Variables
quant-ph/0408035

И только путешественники во времени могут полиномиально решать почти все, что угодно. Только постройте сначала машину времени. Я не специалист по космологии, но первый и самый известный случай решения уравнений Эйнштейна, допускающий путешествия во времени — Геделева метрика не допускает расширения Вселенной, что противоречит наблюдаемым данным. Fail.
Closed Timelike Curves Make Quantum and Classical Computing Equivalent
arXiv:0808.2669

Ну и аналитический литобзор Ааронсона по этой проблеме:
NP-complete Problems and Physical Reality
arXiv:quant-ph/0502072


Я тебе в четырех последних постах пытаюсь втолковать, ссылок-аргументов на обратное я как то не вижу пока.
Конкретику, конкретику.
Цитаты где я ошибся и объяснение почему.

Ты не ошибся, у тебя просто напрочь отсуствует какое либо доказательство.

При нелинейной квантовой механике мы можем добиться экспоненциального прироста. Попутно экспоненциально размножив ошибку. Fail.
Это не доказывает что не существует алгоритма с экспоненциальным приростом без размножения ошибки. Такие же претензии к практически каждому твоему переходу. Еще раз, не npc-шность факторизации — это очень сильное утверждение, вполне смогущее наделать шуму в научном мире. Отошли свое доказательство в какой нибудь журнал, что бы его там посмотрели, им за это деньги платят. Выискивать рациональные крупицы в дампе мозга очередного интернет самодура мне не досуг. Ты говоришь что не npc-шность факторизации давно доказана и очевидна? Ссылку пожалуйста, спрашиваю в четвертый раз.

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

Ну там действительно нету ничего о том что факторизация не в NPC. Вот, например, на Википедии написано, что неизвестно соотношение между классами BQP и NP ( en.wikipedia.org/wiki/BQP ).

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

Кстати,

Если у вас есть задача коммивояжёра, и случайно окажется, что есть, скажем 10 оптимальных вариантов, то вы не сможете решить ее каким-то хитрым способом. Более того, вы не можете заранее сказать что тут не единственное оптимальное решение не решив саму задачу.

правильно ли я понял, что ты видишь здесь проблему в том что невозможно быстро проверить, что данное решение есть оптимальным? Если да, то задачу можно переформулировать как-то так: найти путь коммивояжера длины L, где L — наперед заданое число. В такой формулировке можно вполне быстро определить подходит путь или нет.


на Википедии написано, что неизвестно соотношение между классами BQP и NP
Это возможно только при равенстве P и NP, что невозможно физически, о чем я тут и талдычу и о чем подробно написано в приведенном мною литобзоре.

Вообще, интуитивно вроде как понятно о чем ты говоришь, но пруфов пока нет (всмысле человечество их еще не нашло).
Фактически вы требуете пруфов, что скорость света ограничена с, а второе начала термодинамики таки работает.

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

Если да, то задачу можно переформулировать как-то так: найти путь коммивояжера длины L, где L — наперед заданое число. В такой формулировке можно вполне быстро определить подходит путь или нет.
Коммивояжер должен объехать все города, длина его пути всегда n.

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

Это возможно только при равенстве P и NP, что невозможно физически
Фактически вы требуете пруфов, что скорость света ограничена с, а второе начала термодинамики таки работает.

Это далеко не одно и то же, странно упрекать кого-то за требование доказательств в разговоре о математике. А аргумент типа «это физически невозможно» это уже совсем. Может еще будем теоремы принимать голосованием, типа большинству кажется что P не равно NP?

Коммивояжер должен объехать все города, длина его пути всегда n.

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


Но вот твои способы доказательства/утверждения вызывают у меня баттхерт.
Science: If you’re not pissing people off, you’re not doing it right©
abstrusegoose.com/47

А аргумент типа «это физически невозможно» это уже совсем.
Приведите пример «серьезного» доказательства.

Может еще будем теоремы принимать голосованием, типа большинству кажется что P не равно NP?
А аксиомы нам были даны Богом, триедином в виде Архимеда, Ньютона и Гаусса?

Все аксиомы, затрагивающие бесконечные объекты де-факто принимаются «голосованием», так как мы не можем провести физический эксперимент, их подтверждающий.


Ну обычно коммивояжер определяется на взвешенном графе, странно, что ты не понял, что я имею в виду.
Ну я так понял вы обозвали длиной стоимость пути.
А аксиомы нам были даны Богом, триедином в виде Архимеда, Ньютона и Гаусса?
Все аксиомы, затрагивающие бесконечные объекты де-факто принимаются «голосованием», так как мы не можем провести физический эксперимент, их подтверждающий.
Аксиомы то такое, можешь хоть сам свою аксиоматическую теорию написать. Но ты же претендуешь на истинность недоказанных утверждений в чужой аксиоматической теории, вот тут и возникает нестыковочка.
Science: If you’re not pissing people off, you’re not doing it right©
abstrusegoose.com/47

лол, «не льсти себе, подойди поближе».

Приведите пример «серьезного» доказательства.

ммм, что ты имеешь ввиду? «серьйозное» доказательство это какой-то специальный термин типа «прелестного» кварка?

Все аксиомы, затрагивающие бесконечные объекты де-факто принимаются «голосованием», так как мы не можем провести физический эксперимент, их подтверждающий.

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

Ну я так понял вы обозвали длиной стоимость пути.

Длина пути — число дуг пути (или сумма длин его дуг, если последние заданы). ( ru.wikipedia.org/...й_теории_графов ), так что не понимаю почему ты придираешся.

только один ключ является правильным.
Не факт.

нет, задача с которой мы столкнулись называется «перебрать 256-битный ключ за 10 секунд». Т.е. прощёлкать 256-разрядный счётчик

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

Есть 256-ти битовые идентификаторы, которые раскладываются на 8-ем32-ух битовых слова. Первое слово являлась командой, а остальные семь модификаторами и атрибутами, но не битовыми масками. Пусть будет абстрактное устройство, которому в зависимости от присланной команды нужно выдать ответ, который, ну пусть, будет равен 256 бит по размеру.

В памяти были расположены таблицы смещений на структуры ответов, таблица команд занимала 4байта*4Gb=16Gb в памяти. Модификторы и атрибуты 7*4байта*4Gb=112Gb. Всё это создавалось в памяти за ~10-60 секунд в зависимости от платформы. Таким нехитрым образом покрываются все полные 256 бит входных комбинаций.

Естественно записать числа 0 до 99 проще как две таблицы от 0 до 9, комбинация из которых даст искомое число, чем 100 чисел подряд в памяти.

Согласен, это далеко от классического перебора. Думаю, понятно объяснил.

это и не имеет ничего общего с перебором. Но и к «перебрать 256 бит» это тоже не относится.

Если у нас есть 12 карандашей, это не значит, что мы нарисовали все возможные картины, верно?

это и не имеет ничего общего с перебором. Но и к «перебрать 256 бит» это тоже не относится.
Вместо «перебрать» можно поставить слово «сохранить» все варианты. В каком виде — это уже другой вопрос.
Если у нас есть 12 карандашей, это не значит, что мы нарисовали все возможные картины, верно?
Что-то явно не то с этим сравнением.

И какой твой ответ, и цепочка рассуждений к нему приводящая?

не, теперь задачка моя. Хочешь — решай, не хочешь — молчи.

P.S. Вы блин издеваетесь? Я что, с 70% промазал, надо было 95% указывать? Это же школьный курс, и вообще банальная логика

Мои прикидки такие, на один виток внутреннего цикла нужнo наверное 20 тиков процессора, т.е. на все про все нужно 30^5*20 тиков, или 0.5 миллиарда, разделить на 2.5ГГЦ, получается 0.2 сек. Но мне кажется задача странной, потому что даже от языка программирования результат будет зависeть на порядки.

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

P.S. общее кол-во неплохо было бы разделить на 2 (не обязательно, что вы найдёте ключ последним числом) и на кол-во валидных ключей (но это уже зависит от задачи)

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

Всё зависит от задачи уже.

*Кстати, этот случай не придуман.Знаю «тимлида» поставившего подчинённым задачу взломать пароль одного аккаунта. Причем — методом перебора, а не по словарям.

Математик:
— Когда видишь, что программист не может умножать матрицы — теряешь к нему уважение.
Как можно не знать таких элементарных вещей?

«англичанин»:
— Когда видишь, что программист не знает английского — теряешь к нему уважение.
Английский — это язык современного ИТ.

Качек:
— Когда видишь, что программист не может выжать с груди 100 кг — теряешь к нему уважение.
Как можно быть таким дрыщем?

Вело-спортсмен:
— Когда видишь, что программист весит 100 кг — теряешь к нему уважение.
Как можно так мало двигаться? Купи уже велик и езди на нем на работу.

Если человек работает программистом и работодатель платит ему, например, $3000, значит человек справляется со своими обязанностями. И если его команда при этом на него не жалуется, значит он — хороший программист.

Что необходимо, чтобы быть программистом, а что нет, легко выясняется на любом собеседовании.

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

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

Т.е. то, что человек «умен в стандартном понимании» не означает, что он хороший программист. А если человек хороший программист — это не означает, что он «стандартно умен».

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

Лично я считаю, что человека надо спрашивать о том, чем он будет заниматся. Если не можете придумать ему ни одной реальной «задачи с математикой» — то она ему и не нужна.

P.S. Мы все любим людей похожих на нас самих, отсюда и подобные срачи

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


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

Как говорил наш препод по математике, «математика нужна прежде всего как тренировка мозгов. Остальное уже не так важно».

Не партесь, всё как всегда: те, у кого хорошо с математикой, кричат что без неё никуда (я к ним присоеденюсь). Те у кого с математикой не очень утверждают, что это ненужная никому хрень, да и вообще, интеграл им считать ещё не приходилось. А надо будет — глянут формулу в википедии.

Истина как всегда где-то рядом: в большинстве случаев программирование это рутина. Большинству программистов реально нужны только стандарты кодирования, копи-паст, и «делай как тут». Благо фреймворки в этом помогают. Реально интересные задачи встречаются редко, а там где встречаются — туда находят человека, который может их решать. Остальным остаётся опять таки рутина.

P.S. В пруф вышесказанного: на одной фирме, где я работал, был отдел «оптимизации». Его задача сводилась к тому, чтобы фиксить тормозящие участки кода, и подчищать дерьмо генерируемое другими отделами.

Физика тоже нехилая тренировка мозга. Как впрочем и программирование.

Истина как всегда где-то рядом: в большинстве случаев программирование это рутина не имеет ничего общего с математикой. Большинству программистов реально нужны только стандарты кодирования, копи-паст, и «делай как тут», а еще уметь работать в команде, выдерживать бизнес-процессы разработки, подстраиваться под постоянно меняющиеся требования, уметь разбираться в чужом коде, понять логику программистов с другой стороны земного шара, знать паттерны проектирования, уметь читать UML, проектировать архитектуру проекта, рефакторить, знать что такое «технический долг», уметь отличить хороший код от плохого, научить новичка, настроить test environment, работать с системой контроля версий (ветками и патчами), взять на себя ответственность в трудной ситуации, оптимизировать код, документировать код, разбираться в недокументированных фреймворках типа «черный ящик», дебажить многопотоковые приложения на удаленной машине, опознать баг по логу, знать особенности работы разных браузеров и протоколов, поддерживать версионинг и разбираться в лицензиях.

Физика без математики?! Не, не слышал. А программирование без построения алгоритмов — отупляет.

Социальные навыки нужны не только программисту, а выучить теорию — это не проблема.
Простой пример:

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

Так что ваш перечень содержит множество излишеств. Отсейте то, что можно выучить за неделю, и оставте то, что нужно делать «обычному» программисту.

P.S. Вы бы ещё сюда «уметь включать компьютер и печатать код» добавили. И «писать хороший код»

А программирование без построения алгоритмов — отупляет.

Я программист с 10-ним стажем (C++, Java). И к тому же призер студенческих ACM-олимпиад.
И вот что я вам скажу:
За 10 лет работы мне ни разу не понадобились мои навыки в теории алгоритмов.

Самое сложное в программировании:
а) понять логику чужого кода, когда нет/мало документации
б) понять как работает «черный ящик» — фреймворк/модуль, когда нет его исходников
в) написать хорошую архитектуру
г) выбрать правильный стек фреймворков

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

За 10 лет работы мне ни разу не понадобились мои навыки в теории алгоритмов.
Ну хоть алгоритмы то составляли? :)
а) понять логику чужого кода, когда нет/мало документации
да ладно, если есть возможность подебажить — обычно справляешься. Хотя, если код совсем плохой, и что делает — вообще не известно — то согласен.
понять как работает «черный ящик» — фреймворк/модуль, когда нет его исходников
вспоминаются логические задачки из серии «продолжи последовательность». Другое дело, как они относятся к математике...
написать хорошую архитектуру
О, тут знания статистики уже не помешают. А уж если у вас высоконагруженные проекты, обработка больших массивов информации и так далее — то тем более надо понимать с чем работаешь.
выбрать правильный стек фреймворков
Опыт :) И этому нигде не учат.

Самое смешное, что и это довольно редкие случаи, в повседенвной практике рядового программиста. Так что и без этого можно жить (наверное).

Ни теории алгоритмов, ни математики, чтобы быть хорошим программистом, знать не надо.
Для большинства задач — вы абсолютно правы. И я вас за это ненавижу :)
«математика нужна прежде всего как тренировка мозгов. Остальное уже не так важно»
Эту хрен обычно говорят те, кто не могут объяснить зачем математика реально нужна в плане профессии, тем же программистам или экономистам.

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

Ну это уже притензия к образованию, почему математика живёт отдельно, а программирование — отдельно.

P.S. Нам на философии тоже пытались «рассказать» зачем нам это нужно. Но по факту — нужна была ставка преподу. Так что не рассказывать нужно, а демонстрировать. Показывать задачи и области применения.

Плохой у вас философ был. Нам наш сразу объяснил роль философии и науки логики в современной научной жизни.
Интересный был гегельянец. Начиная с того, что на сайте кафедры на фото он был запечатлен строго со спины, и заканчивая тем, что на первом семинаре он нам заявил «а мне пофиг, что у вас еще лекций не было. Давайте отвечайте на вопросы.»

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

«Обьяснить я и сам могу, мне бы понять...»

В таком случае существует два мнения,мнение преподавателя и неправельное.

Как говорил наш препод по математике, «математика нужна прежде всего как тренировка мозгов. Остальное уже не так важно».

Почему мозг нельзя тренировать собственно программированием ?

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

Тут знаете как: можно бегать, можно кататься на велосипеде, можно плавать. Лишь бы только не на заднице сидеть.

Я в универе не учился, но школу помню хорошо, дык я как не понимал, так и не понимаю, что там в математике тренерующего мозг.
Дано 100500 формул которые надо зазубрить, и еще столькоже готовых алгоритмов решений разного рода уравнений. Задача вспомнить эти алгоритмы и формулы и тупо применить.
Что в этом развивающего, что с этим так носяться?
Таже геометрия, физика и программирование — совсем другое дело.

Геометрия и физика — это чистой воды математика.
А насчёт уравнений — видно вам (не)повезло, что вас не насиловали «Сканави».

Задача вспомнить эти алгоритмы и формулы и тупо применить.
Вот это — бред чистой воды. Больше этого не пишите — засмеют, или всунут в зубы задачку. Главная проблема в серьёзных задачах — это подобрать ту теорию/алгоритм, которой задачка решится. И в интересных задачах алгоритм приходится придумывать на ходу, а теорий применять — далеко не одну.
Геометрия и физика — это чистой воды математика.

Совершенно не согласен.
А насчёт уравнений — видно вам (не)повезло, что вас не насиловали «Сканави».
Таки насиловал, там все тоже самое, только алгоритмов решения уравнений еще больше.
Главная проблема в серьёзных задачах — это подобрать ту теорию/алгоритм, которой задачка решится.
Дык я о чем, вначале тупо методом перебора, а после того как надрючишся, уже и так «видно» что нужно применить.
И в интересных задачах алгоритм приходится придумывать на ходу, а теорий применять — далеко не одну.

Ну да, применил теорию, упростил уравнение, повторить до тех пор пока не будет решение.
Совершенно не согласен.
Не согласен — обоснуй.
А пока вам пример: «машина выехала из А в В, t1 ехала со скоростью v1, t2 ехала со скоростью v2. Какова средняя скорость?» — это физика или математика? А если спросить про сложение скоростей? А про векторное сложение сил? :)
вначале тупо методом перебора
эээ Интересный подход.
Ну да, применил теорию, упростил уравнение, повторить до тех пор пока не будет решение.
Угу. Но если так как вы описываете, то программирование — это написал код, проверил на баги, пишешь код дальше. Всё, никаких проблем

Да, математика — это не магия, и не наука избранных. Но именно этот поиск решения и есть тренеровка для мозгов.


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

За Сканави — ПЯТЬ!

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

А вы дальше первых глав смотрели? Там целая глава вроде есть, на «докажите ...». А уж в задачках по планиметрии/стереометрии — так точно.

Извините, наверное, вы правы. Давно это было.

Ну тут напрашивается анология со слоном — вы его не видели, а он есть. Если в вашей конкретной школе вам давали только такие задачи это не значит, что нету других.

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

Мало где заставляют выводить формулы/доказывать теоремы, а не учить. И это беда образования, а не конкретного парня.

И самое печальное — общемировая тенденция.
gowers.wordpress.com/...arily-give-you

то есть школьники ноют что нужно учить доказательство теорем, а закончившие грустят, что этому не учили... славненко...

Школьники вообще не очень понимают, что и зачем делают. И многие учителя им в этом «помогают». Хотите сказать что вы в школе с первого класса знали что и зачем учите?

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

с первого нет. но в 9-11 уже вполне. отец и дед часто давали мне возможность применять знание геометрии, физики и химии на практике.

Ну вот. А есть люди, которые до 11 класса не очень варили, куда пойдут после школы (потому что родители рулили «поступишь в ВУЗ, выучишься, потом работать!»). Да и не все родители могут (а главное хотят) помогать.

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

вы пообщайтесь с тем кому сейчас 14, заодно узнаете какой вы неудачник, что зарабатываете всего 3,5к. «вон билл гейтс в универе не учился а миллиардер», «а эйнштейн.вообще по физике имел 3», «а во времена ньютона школ вообще не было», «менделееву приснилась таблица менделеева» и тому подобное в таком духе.

Это отдельный вопрос. И блин, не хочется мне выглядеть стариком, бубнящим «а вот в моё времяа!». И опять таки, думаю, это проблема воспитания, слома ценностей и так далее, а не в том, что «дети плохие».

Да, работать сейчас не в моде, но ведь моду задают не дети. Моду задают взрослые, и именно они, ноя что «вот я 20 лет у станка простоял, а он ...» формируют у подростков такой подход.

думаю, это проблема воспитания, слома ценностей и так далее, а не в том, что “дети плохие”
Да. Образование не воспринимается как социальный лифт прежде всего взрослым обществом. Зарабатывать 10-20-30 тысяч грн своим умом и руками, получив образование и профессию? — “та нє, це надо шоп хтось встроїв... ти можеш ото й мойого Хведю так встроїть, шоб він тоже тищу доларів получав? нє? ну так шо ти тут ето...”

Я не от одного человека, когда учился, не слышал фразы «ты должен знать *subject* для того, чтоб на работе выполнять вот такие функции». Обычно говорили что-то типа «диплом нужен...», «образование нужно..», «наши выпусники...» и так далее. Т.е. образование, как диплом — вполне воспринимается, как социальный лифт (иначе чего все родители стараются детей в ВУЗ сунуть?). А вот собственно знания — они «простому» человеку не видны.

И да, какой родитель открыто признает, что его «Хведя» редкостный мудак, проиграл в халву всю школу/пту/вуз, и теперь его «грандиозных познаний в компьютере» мало даже для эникейщика в госконторе? Диплом же есть! Почему его не берут?!

Т.е. образование, как диплом — вполне воспринимается, как социальный лифт
«Почувствуйте разницу»:
диплом — воспринимается.
образование — нет.
раз всё равно потом надо «шоб хтось встроїв», то смысл получать образование? достаточно «занести могорича» и получить диплом, ведь всё равно потом надо «шоб хтось встроїв» ... Замкнутый круг.

Именно что нужно было.
За шпаргалки — бан. Если не знать всех формул порою тупо не решиш уравнения.
Во вторых было прям задание выходить к доске (или с места), и рассказывать формулы. Не знаеш — садись 2.

Такие школы/ВУЗы — не нужны.

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

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

кое где да. их можно было даже купить (я о шпаргалках).

везде можно, если не палиться :). И да, многие формулы/теоремы вполне себе выводятся по ходу дела. Многие вещи из физики вообще по размерности можно вспомнить.

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

А чем докажешь, что сам не робот? :P

Як відомо роботів легко підвісити парадоксом Рассела... ))))

Не, они просто выдадут ошибку выведения типов.

Нам нужна геделевская каптча!
Типа такой:
www.scottaaronson.com/...gs/captcha.html

Подписаться на комментарии