Вхід і реєстрація
Розробка · 17 липня 2013, 9:26 5235
Martin Rodrigez

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

Підписуйтеся на Telegram-канал «DOU #tech», щоб не пропустити нові технічні статті

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

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

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

Теми: математика, програмування
👍ПодобаєтьсяСподобалось0
До обраногоВ обраному0
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
Васисуалий Лоханкин 19.07.2013 10:30

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

Відповісти
Підтримати
Martin Rodrigez 19.07.2013 03:13

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

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

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

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

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

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

Відповісти
Підтримати
Sandro Zakusilov 18.07.2013 11:55

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

Відповісти
Підтримати
druid III 18.07.2013 12:35

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

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

Відповісти
Підтримати
Sandro Zakusilov
Sandro Zakusilov 18.07.2013 13:40

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

Відповісти
Підтримати
druid III
Ivan Golovach Scala/Java TechLead в Moebius Lab (Real-Time Bidding) 17.07.2013 23:35

Определяя всякий ссылочный тип в 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 — это предок всех объектов и что в нем за методы обязан знать каждый. Определение новых классов, соответствующих предметной области — ежедневное занятие.
.
Ну и да, алгебра — бесполезная наука :)

Відповісти
Підтримати
reality_hacker 17.07.2013 23:42

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

Відповісти
Підтримати
Ivan Golovach
Ivan Golovach Scala/Java TechLead в Moebius Lab (Real-Time Bidding) 18.07.2013 00:06

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

Відповісти
Підтримати
reality_hacker
reality_hacker 18.07.2013 00:07
Пример нужен? Или мозгов хватит придумать?
Да. Нужен пример пожалуйста.
Відповісти
Підтримати
Ivan Golovach
Ivan Golovach Scala/Java TechLead в Moebius Lab (Real-Time Bidding) 18.07.2013 00:11

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)

Відповісти
Підтримати
reality_hacker
reality_hacker 18.07.2013 00:12

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

Відповісти
Підтримати
Ivan Golovach
Ivan Golovach Scala/Java TechLead в Moebius Lab (Real-Time Bidding) 18.07.2013 18:14

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

Відповісти
Підтримати
reality_hacker
reality_hacker 18.07.2013 19:12

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

Відповісти
Підтримати
Ivan Golovach
Ivan Golovach Scala/Java TechLead в Moebius Lab (Real-Time Bidding) 19.07.2013 01:32

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

Відповісти
Підтримати
reality_hacker
reality_hacker 19.07.2013 01:51

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

Відповісти
Підтримати
Ivan Golovach
Martin Rodrigez 19.07.2013 05:19
Если ты поменяешь == на instanceof то все будет чики пуки.

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

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

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

Відповісти
Підтримати
reality_hacker
reality_hacker 19.07.2013 05:41

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

Відповісти
Підтримати
Martin Rodrigez
Martin Rodrigez 19.07.2013 06:14

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

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

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

Відповісти
Підтримати
reality_hacker
Ivan Golovach Scala/Java TechLead в Moebius Lab (Real-Time Bidding) 19.07.2013 13:37

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

Відповісти
Підтримати
Martin Rodrigez
Александр Колосов 18.07.2013 01:05

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

Відповісти
Підтримати
Ivan Golovach
reality_hacker 18.07.2013 01:15

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

Відповісти
Підтримати
Александр Колосов
Jack Jack 18.07.2013 04:28

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

Відповісти
Підтримати
Ivan Golovach
Jack Jack 18.07.2013 04:33

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

Відповісти
Підтримати
Ivan Golovach
reality_hacker 18.07.2013 05:01
проблема в неможливості реалізувати нетривіальний hashCode (нетривіальний = не «return 0;»).
Objects.hashCode(x, y) ?
Відповісти
Підтримати
Jack Jack
Jack Jack 18.07.2013 05:24

З документації:
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).

Відповісти
Підтримати
reality_hacker
Вася Петечкин 18.07.2013 08:20

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

Відповісти
Підтримати
Jack Jack
Jack Jack 18.07.2013 08:33

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

Відповісти
Підтримати
Вася Петечкин
Ivan Golovach Scala/Java TechLead в Moebius Lab (Real-Time Bidding) 18.07.2013 18:27

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

Відповісти
Підтримати
Jack Jack
reality_hacker 18.07.2013 19:49

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

Відповісти
Підтримати
Ivan Golovach
Ivan Golovach Scala/Java TechLead в Moebius Lab (Real-Time Bidding) 18.07.2013 20:37

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

Відповісти
Підтримати
reality_hacker
reality_hacker 18.07.2013 20:48
Диагональная конструкция Кантора (которую ты применил) порождает разрывное отображение.
0.2×0.3 -> 0.23
но
0.199×0.3 -> 0.1399.
А ты не находишь что между числами 0.23 и 0.1399 есть еще туева хуча точек которые совершенно случайно могут соединить разрыв?
ы математику что-ли вообще не учил в ВУЗе?
Нет, только в детсаду.
Відповісти
Підтримати
Ivan Golovach
Ivan Golovach Scala/Java TechLead в Moebius Lab (Real-Time Bidding) 18.07.2013 20:55
еще туева хуча точек которые совершенно случайно могут соединить разрыв?
Я так понимаю ты не понимаешь разницы между непрерывным отображением и отображением, образ которого всюду плотен или односвязен?
.
Непрерывность — это рассуждения в терминах дельта-эпсилон.
И вот я тебе строю последовательность точек
(0.19, 0.3), (0.199, 0.3), (0.1999, 0.3), (0.19999, 0.3), (0.199999, 0.3) которая приближается к (0.2, 0.3), но ее образы — не приближаются.
.
Слушай, ну вот ты — хороший программист, но не силен в математике. Ну вот что тебя заставляет влезть и сюда еще? Шило?
Відповісти
Підтримати
reality_hacker
reality_hacker 18.07.2013 20:56

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

Відповісти
Підтримати
Ivan Golovach
reality_hacker 18.07.2013 21:22
Непрерывность — это рассуждения в терминах дельта-эпсилон.
И вот я тебе строю последовательность точек
(0.19, 0.3), (0.199, 0.3), (0.1999, 0.3), (0.19999, 0.3), (0.199999, 0.3) которая приближается к (0.2, 0.3), но ее образы — не приближаются.
.
Слушай, ну вот ты — хороший программист, но не силен в математике. Ну вот что тебя заставляет влезть и сюда еще? Шило?
Это конечно очень мило что ты редактируешь опосля свои коменты, и я действительно ошибся со своим примером, но это не делает твою ахенею сколь либо рациональной. То что нельзя построить не вырожденную хешкод функцию доказывается намного проще, без пространных разглагольствований о топологиях.
Відповісти
Підтримати
Ivan Golovach
Ivan Golovach Scala/Java TechLead в Moebius Lab (Real-Time Bidding) 19.07.2013 01:35

А ну?

Відповісти
Підтримати
reality_hacker
reality_hacker 19.07.2013 01:57

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

Відповісти
Підтримати
Ivan Golovach
Ivan Golovach Scala/Java TechLead в Moebius Lab (Real-Time Bidding) 18.07.2013 20:53

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

Відповісти
Підтримати
Ivan Golovach
Andrey Shiray 18.07.2013 21:34

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

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

Поэтому:


То что нельзя построить не вырожденную хешкод функцию доказывается намного проще, без пространных разглагольствований о топологиях.
Принцип Дирихле рулит и бибикает.
Відповісти
Підтримати
Ivan Golovach
Ivan Golovach Scala/Java TechLead в Moebius Lab (Real-Time Bidding) 18.07.2013 22:01
Размерностью © КО
Размерность — это свойство векторных линейных пространств. Это слишком сильная для нас структура. Невозможно даже построить взаимооднозначное отображение линейных векторных пространств с различной размерностью (RxR <-> R).
Но мы хотим строить. Поэтому отбрасываем векторность и берем более обширный и менее стесняющий класс — топологические пространства (с топологией индуцированной евклидовым расстоянием). В рамках топологических пространств reality_hacker построил (через диагональную конструкцию Кантора) взаимооднозначное отображение, и я утверждаю, что всякое такое отображение принципиально не может быть непрерывным.
Відповісти
Підтримати
Andrey Shiray
reality_hacker 18.07.2013 22:09
В рамках топологических пространств reality_hacker построил (через диагональную конструкцию Кантора) взаимооднозначное отображение, и я утверждаю, что всякое такое отображение принципиально не может быть непрерывным.
А зачем нужна эта непрерывность? Как уже сказали в компьютерах математика дискретна, т.е. непрерывность иррелевантна.
Відповісти
Підтримати
Ivan Golovach
Ivan Golovach Scala/Java TechLead в Moebius Lab (Real-Time Bidding) 18.07.2013 22:21

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

Відповісти
Підтримати
reality_hacker
reality_hacker 18.07.2013 22:24

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

Відповісти
Підтримати
Ivan Golovach
Andrey Shiray 18.07.2013 23:47

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

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

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

Відповісти
Підтримати
Andrey Shiray
Andrey Shiray 19.07.2013 00:26

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

Відповісти
Підтримати
reality_hacker
reality_hacker 19.07.2013 00:28

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

Відповісти
Підтримати
Andrey Shiray
Ivan Golovach Scala/Java TechLead в Moebius Lab (Real-Time Bidding) 19.07.2013 01:27
Нет, размерность задается на любом топологическом пространстве.
Размерность векторного пространства — это мощность базиса. А что такое размерность топологического пространства? Мощность множества всех открытых множеств?
Відповісти
Підтримати
Andrey Shiray
Andrey Shiray 19.07.2013 02:52

А что такое размерность топологического пространства?
Как ни странно, топологическая размерность))
Она же размерность Лебега.
Відповісти
Підтримати
Ivan Golovach
Ivan Golovach Scala/Java TechLead в Moebius Lab (Real-Time Bidding) 16.10.2013 16:22

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

Відповісти
Підтримати
Andrey Shiray
Martin Rodrigez 19.07.2013 05:26

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

Відповісти
Підтримати
Ivan Golovach
reality_hacker 19.07.2013 05:42

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

Відповісти
Підтримати
Martin Rodrigez
Ivan Golovach Scala/Java TechLead в Moebius Lab (Real-Time Bidding) 19.07.2013 13:46

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

Відповісти
Підтримати
Martin Rodrigez
Martin Rodrigez 22.07.2013 16:51

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

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

Відповісти
Підтримати
Ivan Golovach
Ivan Golovach Scala/Java TechLead в Moebius Lab (Real-Time Bidding) 19.07.2013 13:35

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

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

Коментар порушує правила спільноти і видалений модераторами.

Igor Petruk Software Engineer в Google 17.07.2013 17:31

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

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

Відповісти
Підтримати
Владимир Кожаев 17.07.2013 21:53

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

Відповісти
Підтримати
Igor Petruk
Андрій Серняк IT consultant в Consileon Ukraine 17.07.2013 12:55

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

Відповісти
Підтримати
Вася Петечкин 17.07.2013 12:34

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

Відповісти
Підтримати
Pavel Kruchina CTO 17.07.2013 13:01

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

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

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

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

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

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

Відповісти
Підтримати
Вася Петечкин
Вася Петечкин 17.07.2013 17:34

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

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

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

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

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

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

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

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

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

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

Відповісти
Підтримати
Вася Петечкин
Вася Петечкин 17.07.2013 18:04

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

Відповісти
Підтримати
druid III
druid III 18.07.2013 12:58

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

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

Відповісти
Підтримати
Вася Петечкин
Grez 17.07.2013 14:59
И не надо кричать, что ты своим быдлокодом заработал на 10 зеркалок, 5 велосипедов итд, гаишник зарабатывает не меньше тебя.
Надо федя, надо.
Так как применив логику и здравый смысл, мы таки прийдем к тому, что чобы заработать на 10 зеркалок и 5 велосипедов — математика не нужна. А то что у вас и вам подобным комплекс неполноценности, и вы напрвао и на лево кричите «быдлокодер», это другой, на самом деле, не важный фактор.
Відповісти
Підтримати
Вася Петечкин
Pavel Kruchina CTO 17.07.2013 15:14

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

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

Відповісти
Підтримати
Grez
Grez 17.07.2013 15:24

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

Відповісти
Підтримати
Pavel Kruchina
Pavel Kruchina CTO 17.07.2013 15:30

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

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

Відповісти
Підтримати
Grez
Вася Петечкин 17.07.2013 16:56

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

Відповісти
Підтримати
Grez
Зепп Бранниган 17.07.2013 10:14

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

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

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

Відповісти
Підтримати
Pavel Kruchina CTO 17.07.2013 10:35

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

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

Відповісти
Підтримати
Зепп Бранниган
Mike Gorchak Graphics Device Driver Developer в QNX Software Systems 17.07.2013 10:43

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

Відповісти
Підтримати
Pavel Kruchina
Pavel Kruchina CTO 17.07.2013 10:52

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

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

Відповісти
Підтримати
Mike Gorchak
Зепп Бранниган 17.07.2013 11:09

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

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

Відповісти
Підтримати
Pavel Kruchina
Pavel Kruchina CTO 17.07.2013 11:14
Надо генерировать GUID’ы, а не придумывать свои, чтобы потом гадать — взламываются/подбираются они на современных машинах или нет.
Возьми готовое, не надо будет включать мозг. Всё правильно. Именно поэтому я и писал, что основное для программиста, в большинстве случаев — это стиль кода, копи-паст и «делай как тут». И это работает.
Відповісти
Підтримати
Зепп Бранниган
Зепп Бранниган 17.07.2013 12:16

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

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

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

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

Відповісти
Підтримати
Pavel Kruchina
Pavel Kruchina CTO 17.07.2013 12:25
Нет, не надо использовать готовую проверенную теорию, нужно придумать свою. А все кто не придумывают свою — просто быдломатематики. Так получается?
Ну и где я это говорил? Я вообще где то говорил что фреймворки и использование наработок — это плохо?

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

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

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

Відповісти
Підтримати
Зепп Бранниган
Зепп Бранниган 17.07.2013 12:36

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

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

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

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

Відповісти
Підтримати
Pavel Kruchina
Pavel Kruchina CTO 17.07.2013 12:45
Нет, сравнение теории и фреймворков очень точное. И то и то — инструмент, чтобы решать поставленные задачи.
Сравнение молотка и фреймворка — более менее точно. А теорию нужно и сравнивать с теорией. Её в программировании тоже много.

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

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

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

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

Відповісти
Підтримати
Зепп Бранниган
Mike Gorchak Graphics Device Driver Developer в QNX Software Systems 17.07.2013 11:16

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

Відповісти
Підтримати
Pavel Kruchina
Pavel Kruchina CTO 17.07.2013 11:24
но есть вероятность случайного угадывания за 60 попыток довольно-таки высокая.
~n/400 000 , Где n — кол-во валидных ключей. Вот это посчитать как раз могут далеко не все. О чём и речь.
Відповісти
Підтримати
Mike Gorchak
Вася Петечкин 17.07.2013 12:00

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 Gorchak
Pavel Kruchina CTO 17.07.2013 12:11

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

Відповісти
Підтримати
Вася Петечкин
Mike Gorchak Graphics Device Driver Developer в QNX Software Systems 17.07.2013 19:06

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

Відповісти
Підтримати
Pavel Kruchina
Вася Петечкин 17.07.2013 22:45

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

Відповісти
Підтримати
Mike Gorchak
Pavel Kruchina CTO 18.07.2013 09:49

Хм, это уже интереснее. тактовая частота процессора допустим 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 Gorchak
reality_hacker 18.07.2013 09:54
Mike, расскажите, пожалуйста свой способ, перебрать все числа хотя бы за 1 год.
задача как раз под квантовые компы
Відповісти
Підтримати
Pavel Kruchina
Pavel Kruchina CTO 18.07.2013 10:30

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

Відповісти
Підтримати
reality_hacker
reality_hacker 18.07.2013 19:21
А это классика делает весьма хорошо.
Ну с 256-ю битами вроде как то слабо справляется?
Відповісти
Підтримати
Pavel Kruchina
Pavel Kruchina CTO 19.07.2013 10:21

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

Відповісти
Підтримати
reality_hacker
reality_hacker 19.07.2013 10:26

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

Відповісти
Підтримати
Pavel Kruchina
Pavel Kruchina CTO 19.07.2013 10:30

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

Відповісти
Підтримати
reality_hacker
Andrey Shiray 18.07.2013 13:25

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

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

Відповісти
Підтримати
Andrey Shiray
Andrey Shiray 18.07.2013 20:16

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

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

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

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

Відповісти
Підтримати
reality_hacker
reality_hacker 18.07.2013 20:45
Если у вас есть задача коммивояжёра, и случайно окажется, что есть, скажем 10 оптимальных вариантов, то вы не сможете решить ее каким-то хитрым способом. Более того, вы не можете заранее сказать что тут не единственное оптимальное решение не решив саму задачу.
А как из того что ты написал получается несуществование хитрого способа?
Интуитивно считайте, что единственность факторизации дает алгоритму Шора эвристику, благодаря которой он решает задачу не тупым перебором и поэтому за полиномиальное время.
Я не понял мысли. Еще раз, в нашем тупом переборе тоже единственный правильный верный вариант. И в зависимости от функции преобразования все вполне может свестись к факторизации чисел как в алгоритме Шора.
Відповісти
Підтримати
Andrey Shiray
Andrey Shiray 18.07.2013 21:03

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

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

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


Не ясно то что не зная функции преобразования ты заключил что никаких подсказок нет.
Предположим я ищу число в не отсортированном массиве. Какие у меня подсказки и с чего я должен считать, что они должны быть?
Відповісти
Підтримати
reality_hacker
reality_hacker 18.07.2013 21:29
Фактизация в BQP и это не в NP, отсюда и профит от КК.
То что BQP не пересекается с NPC я так понимаю еще не доказано.
Предположим я ищу число в не отсортированном массиве. Какие у меня подсказки и с чего я должен считать, что они должны быть?
Ну это уже другая задача, сильно отличающаяся от исходной, какой смысл ее обсуждать.
Відповісти
Підтримати
Andrey Shiray
Andrey Shiray 19.07.2013 00:20

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

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

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

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


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

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

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

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

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

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

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

Dixi.

Відповісти
Підтримати
reality_hacker
reality_hacker 19.07.2013 18:41

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

Відповісти
Підтримати
Andrey Shiray
Andrey Shiray 19.07.2013 20:31

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

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

Відповісти
Підтримати
reality_hacker
reality_hacker 19.07.2013 20:50
Я написал почему факторизация НЕ в NPC.
Так я тебе посоветовал, опубликуй свои обьяснения, прославишся и осчастливишь научный мир.
Если не осилил — твои проблемы.
А поскольку ты постоянно меняешь свои утверждения по ходу дискуссии, то ты страдаешь деменцией или скучающий тролль.
Какой унылый пердеж в лужу.
Відповісти
Підтримати
Andrey Shiray
Andrey Shiray 19.07.2013 21:04

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

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

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

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

А можно по конкретнее,
Почему факторизация в 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


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

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

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

Ссылку пожалуйста, спрашиваю в четвертый раз.
Я дал ссылку на 4 статьи(заметь, даже не мои), если действительно хочешь разобраться — читай.
Відповісти
Підтримати
reality_hacker
Volodymyr Kysenko 21.07.2013 20:00
Я дал ссылку на 4 статьи(заметь, даже не мои), если действительно хочешь разобраться — читай.

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

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

Кстати,

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

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

Відповісти
Підтримати
Andrey Shiray
Andrey Shiray 22.07.2013 15:50

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

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

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

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

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

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

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

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

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

Відповісти
Підтримати
Andrey Shiray
Andrey Shiray 25.07.2013 10:44

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

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

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

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


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

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

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

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

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

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

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

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

Відповісти
Підтримати
Andrey Shiray
Mike Gorchak Graphics Device Driver Developer в QNX Software Systems 18.07.2013 20:57
только один ключ является правильным.
Не факт.
Відповісти
Підтримати
reality_hacker
Pavel Kruchina CTO 19.07.2013 10:22

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

Відповісти
Підтримати
reality_hacker
Mike Gorchak Graphics Device Driver Developer в QNX Software Systems 18.07.2013 20:55
Mike, расскажите, пожалуйста свой способ, перебрать все числа хотя бы за 1 год.
Ну задача которую я делал все-же немного отличается от тупого перебора. Было так:

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

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

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

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

Відповісти
Підтримати
Pavel Kruchina
Pavel Kruchina CTO 19.07.2013 10:28

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

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

Відповісти
Підтримати
Mike Gorchak
Mike Gorchak Graphics Device Driver Developer в QNX Software Systems 19.07.2013 10:32
это и не имеет ничего общего с перебором. Но и к «перебрать 256 бит» это тоже не относится.
Вместо «перебрать» можно поставить слово «сохранить» все варианты. В каком виде — это уже другой вопрос.
Если у нас есть 12 карандашей, это не значит, что мы нарисовали все возможные картины, верно?
Что-то явно не то с этим сравнением.
Відповісти
Підтримати
Pavel Kruchina
reality_hacker 17.07.2013 10:44

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

Відповісти
Підтримати
Pavel Kruchina
Pavel Kruchina CTO 17.07.2013 10:53

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

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

Відповісти
Підтримати
reality_hacker
reality_hacker 17.07.2013 10:57

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

Відповісти
Підтримати
Pavel Kruchina
Pavel Kruchina CTO 17.07.2013 11:01

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

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

Відповісти
Підтримати
reality_hacker
reality_hacker 17.07.2013 11:08

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

Відповісти
Підтримати
Pavel Kruchina
Pavel Kruchina CTO 17.07.2013 11:17

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

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

Відповісти
Підтримати
reality_hacker
Зепп Бранниган 17.07.2013 10:56

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

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

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

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

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

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

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

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

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

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

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

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

Відповісти
Підтримати
Зепп Бранниган
Anton P Software Engineer в Roku 17.07.2013 15:43

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

Відповісти
Підтримати
Зепп Бранниган
Andrey Shiray 17.07.2013 17:06

У вас в рассуждениях идет подмена понятий.
Есть математика в широком смысле — абстракция (мат.модели), логика и здравый смысл.
А есть математика в узком смысле — интегралы, дифуры, матан, лагранжиан.
Большинство проблем с практическим непониманием математики, которые я встречал, лежат именно в таком разделении. А точнее в непонимании, что тот же теормех с его лагранжианами является всего лишь моделью. И соответственно, как и у всякой модели, есть границы применимости.
Відповісти
Підтримати
Зепп Бранниган
Pavel Kruchina CTO 17.07.2013 09:48

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

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

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

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

Відповісти
Підтримати
Зепп Бранниган 17.07.2013 10:36

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

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

Відповісти
Підтримати
Pavel Kruchina
Pavel Kruchina CTO 17.07.2013 10:49

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

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

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

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

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

Відповісти
Підтримати
Зепп Бранниган
Зепп Бранниган 17.07.2013 12:25
А программирование без построения алгоритмов — отупляет.

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

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

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

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

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

Ни теории алгоритмов, ни математики, чтобы быть хорошим программистом, знать не надо.
Для большинства задач — вы абсолютно правы. И я вас за это ненавижу :)
Відповісти
Підтримати
Зепп Бранниган
Vladimir Kovrigin Теоретик 17.07.2013 11:33
«математика нужна прежде всего как тренировка мозгов. Остальное уже не так важно»
Эту хрен обычно говорят те, кто не могут объяснить зачем математика реально нужна в плане профессии, тем же программистам или экономистам.

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

Відповісти
Підтримати
Pavel Kruchina
Pavel Kruchina CTO 17.07.2013 11:36

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

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

Відповісти
Підтримати
Vladimir Kovrigin
Vladimir Kovrigin Теоретик 17.07.2013 11:47

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

Відповісти
Підтримати
Pavel Kruchina
Victor Prokopovych 17.07.2013 11:46
Эту хрен обычно говорят те, кто не могут объяснить зачем математика реально нужна в плане профессии, тем же программистам или экономистам.
Каждая лисица хвалит свой хвост,точно так же и преподаватель будет говорить что его предмет очень важен,потому что он его любит, вне зависимости на кого ты учишься. Сейчас ситуация такая что мало кто работает по специальности и многие преподы это понимают,по этому никто из них не может тебе точно сказать понадобится тебе математика или что то другое.Это понимание само должно прийти,когда ты поймешь кем хочешь стать.
Відповісти
Підтримати
Vladimir Kovrigin
Vladimir Kovrigin Теоретик 17.07.2013 11:48
Каждая лисица хвалит свой хвост,точно так же и преподаватель будет говорить что его предмет очень важен,потому что он его любит, вне зависимости на кого ты учишься.
Нормальный преподаватель доходчиво объяснит, почему его предмет важен.
Відповісти
Підтримати
Victor Prokopovych
Pavel Kruchina CTO 17.07.2013 11:52

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

Відповісти
Підтримати
Vladimir Kovrigin
Victor Prokopovych 17.07.2013 11:58

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

Відповісти
Підтримати
Vladimir Kovrigin
Grez 17.07.2013 15:11
Как говорил наш препод по математике, «математика нужна прежде всего как тренировка мозгов. Остальное уже не так важно».

Почему мозг нельзя тренировать собственно программированием ?
Відповісти
Підтримати
Pavel Kruchina
Pavel Kruchina CTO 17.07.2013 15:19

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

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

Відповісти
Підтримати
Grez
Grez 17.07.2013 15:30

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

Відповісти
Підтримати
Pavel Kruchina
Pavel Kruchina CTO 17.07.2013 15:36

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

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

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

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

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

Відповісти
Підтримати
Grez
Andrey Shiray 17.07.2013 17:02

Ну да, применил теорию, упростил уравнение, повторить до тех пор пока не будет решение.
Какая ирония. Современная Computer Science началась с доказательства того, что предложенный вами метод не работает.
Відповісти
Підтримати
Grez
Vladislav Lybachevskiy донецкий безработный в Skai 17.07.2013 17:19

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

Відповісти
Підтримати
Pavel Kruchina
Valeriy Zamaraiev (junior lisper) 17.07.2013 17:55

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

Відповісти
Підтримати
Vladislav Lybachevskiy
Pavel Kruchina CTO 17.07.2013 18:10

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

Відповісти
Підтримати
Valeriy Zamaraiev
Valeriy Zamaraiev (junior lisper) 17.07.2013 18:12

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

Відповісти
Підтримати
Pavel Kruchina
Apasnuy 17.07.2013 15:40

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

Відповісти
Підтримати
Grez
Anton P Software Engineer в Roku 17.07.2013 15:45

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

Відповісти
Підтримати
Grez
Pavel Kruchina CTO 17.07.2013 15:52

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

Відповісти
Підтримати
Anton P
Andrey Shiray 17.07.2013 16:55

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

Відповісти
Підтримати
Pavel Kruchina
Anton P Software Engineer в Roku 18.07.2013 12:16

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

Відповісти
Підтримати
Pavel Kruchina
Pavel Kruchina CTO 18.07.2013 12:28

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

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

Відповісти
Підтримати
Anton P
Anton P Software Engineer в Roku 18.07.2013 12:33

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

Відповісти
Підтримати
Pavel Kruchina
Pavel Kruchina CTO 18.07.2013 12:40

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

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

Відповісти
Підтримати
Anton P
Anton P Software Engineer в Roku 18.07.2013 12:53

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

Відповісти
Підтримати
Pavel Kruchina
Pavel Kruchina CTO 18.07.2013 12:58

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

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

Відповісти
Підтримати
Anton P
Nobody 18.07.2013 13:07
думаю, это проблема воспитания, слома ценностей и так далее, а не в том, что “дети плохие”
Да. Образование не воспринимается как социальный лифт прежде всего взрослым обществом. Зарабатывать 10-20-30 тысяч грн своим умом и руками, получив образование и профессию? — “та нє, це надо шоп хтось встроїв... ти можеш ото й мойого Хведю так встроїть, шоб він тоже тищу доларів получав? нє? ну так шо ти тут ето...”
Відповісти
Підтримати
Pavel Kruchina
Pavel Kruchina CTO 18.07.2013 13:18

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

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

Відповісти
Підтримати
Nobody
Nobody 18.07.2013 14:07
Т.е. образование, как диплом — вполне воспринимается, как социальный лифт
«Почувствуйте разницу»:
диплом — воспринимается.
образование — нет.
раз всё равно потом надо «шоб хтось встроїв», то смысл получать образование? достаточно «занести могорича» и получить диплом, ведь всё равно потом надо «шоб хтось встроїв» ... Замкнутый круг.
Відповісти
Підтримати
Pavel Kruchina
Grez 17.07.2013 16:17

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

Відповісти
Підтримати
Anton P
Sandro Zakusilov 18.07.2013 12:07

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

Відповісти
Підтримати
Grez
Anton P Software Engineer в Roku 18.07.2013 12:15

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

Відповісти
Підтримати
Grez
Grez 18.07.2013 12:23

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

Відповісти
Підтримати
Anton P
Anton P Software Engineer в Roku 18.07.2013 12:28

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

Відповісти
Підтримати
Grez
Pavel Kruchina CTO 18.07.2013 12:31

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

Відповісти
Підтримати
Grez
Grez 18.07.2013 12:39

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

Відповісти
Підтримати
Pavel Kruchina
Andrey Shiray 18.07.2013 13:26

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

Відповісти
Підтримати
Grez
druid III 18.07.2013 13:42

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

Відповісти
Підтримати
Andrey Shiray
Andrey Shiray 18.07.2013 14:01

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

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

Відповісти
Підтримати
druid III

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

Не підписуватись
Скористайтесь акаунтом
×
з умовами використання сайту і політикою конфіденційності.