Comments 212
Я итак жалею, что не учил математику, а вы меня здесь еще добиваете ((
Так ещё не поздно!
Мне 26, например. Я бросил на 3-м курсе. На дневное уже не пойду, а чтобы самостоятельно научиться составлять запросы гуглу, как минимум нужно уметь составлять запросы гуглу.
Все-таки, ложка хороша к обеду и образование необходимо, несмотря на все разочарования от того, как образовательная система в нашем государстве устроена.
Все-таки, ложка хороша к обеду и образование необходимо, несмотря на все разочарования от того, как образовательная система в нашем государстве устроена.
Могу предложить запрос «дискретная математика учебник» (без кавычек).
Сам недавно прикупил книжку «Конкретная математика» (Грэхем, Кнут, Паташник). Там и дискретка, и теория чисел, и асимптотика, и вообще много всякого интересного.
Сам недавно прикупил книжку «Конкретная математика» (Грэхем, Кнут, Паташник). Там и дискретка, и теория чисел, и асимптотика, и вообще много всякого интересного.
Я рад вашему приобретению, но «дискретная математика учебник», сам по себе, мне как собаке пятая нога. Мне пригодилась бы грамотно составленная программа параллельного обучения — с переплетением между собой дискретной математики и непрерывной, теории функций, волновой теории и что-нибудь тогда из физики — например про те же волны, только с магнетизмом и электричеством. А еще хорошо бы узнать как это работает на атомарном уровне.
Однобокое обучение рождает только стереотипы в голове и может сказаться не в лучшую сторону. Я, возможно, научусь видеть дискретность во всех вещах, научусь это выражать в коде, но я бы предпочел видеть картину происходящего целиком. Именно так — немножко дискретного, немножко непрерывного, немножко чего-то еще… Понемножку, хотя бы чтобы знать в какую сторону гуглить.
Существование словосочетания «оптимальное решение» намекает на то, что дискретной математикой все кончиться не должно.
Однобокое обучение рождает только стереотипы в голове и может сказаться не в лучшую сторону. Я, возможно, научусь видеть дискретность во всех вещах, научусь это выражать в коде, но я бы предпочел видеть картину происходящего целиком. Именно так — немножко дискретного, немножко непрерывного, немножко чего-то еще… Понемножку, хотя бы чтобы знать в какую сторону гуглить.
Существование словосочетания «оптимальное решение» намекает на то, что дискретной математикой все кончиться не должно.
Возможно Вы найдете для себя что-то полезное в блоге товарища Хеллера по тэгу «математика», верхний (на текущий момент) пост там как раз об этом + комментарии рулят как и на Хабре — heller.ru/blog/category/математика/
Не знаю, не знаю. Моя математика остановилась где-то в 8 классе. И где-то в 11 я понял, что она мне безумно нравится. Но поступил я на политологию и ее там не было в принципе (кроме избирательных систем). Как ни странно, я пришел к ней обратно, когда на первом курсе увлекся игрой на бирже. Мне так нравилось считать самому индикаторы и осциляторы, что я просто сидел и переписывал простейшие формулы, вспоминал что такое среднее и логарифмы (для логарифмических шкал), потом потихоньку пришел к более серьезному фин. анализу, где и формулы посложнее (всякие двойные сумирования, ковариации, кореляции) все это мне пришлось учить просто что бы понямать конкретные задачи (например построить эфективное множество Марковица). Все техническое и математическое, что я учил, мне очень и очень помогало и пригождалось.
Я сторонник подхода, когда ты учишь то, что действительно нужно и на мой взгляд знания тут и там по чуть-чуть, редко помогут видеть «картину целиком». Просто нет такой картины. Я до сих пор могу найти только простейшие производные и вообще не знаю как решаются интегральные уровнения, не знаю даже что такое векторы. Но я увлекся классификацией и кластеризацией, открыл лекции Воронцов, немножко простите за грубость прих*ел и взял в руки учебник для поступающих в ВУЗы по математике и сборник задач Сканави. Я уверен, что если не через месяц, то через год я пойму что там написано. И это на мой взгляд круто. Так что никогда не поздно заниматься тем, что нравится.
И в то же время я абсолютно согласен с автором. Если бы я обладал знаниями, которые я благополучно профукал, мно не пришлось бы мучится и тратить кучу времени на поиски и на решение проблемы «за что взяться». Я бы просто копал в нужном направлении.
Я сторонник подхода, когда ты учишь то, что действительно нужно и на мой взгляд знания тут и там по чуть-чуть, редко помогут видеть «картину целиком». Просто нет такой картины. Я до сих пор могу найти только простейшие производные и вообще не знаю как решаются интегральные уровнения, не знаю даже что такое векторы. Но я увлекся классификацией и кластеризацией, открыл лекции Воронцов, немножко простите за грубость прих*ел и взял в руки учебник для поступающих в ВУЗы по математике и сборник задач Сканави. Я уверен, что если не через месяц, то через год я пойму что там написано. И это на мой взгляд круто. Так что никогда не поздно заниматься тем, что нравится.
И в то же время я абсолютно согласен с автором. Если бы я обладал знаниями, которые я благополучно профукал, мно не пришлось бы мучится и тратить кучу времени на поиски и на решение проблемы «за что взяться». Я бы просто копал в нужном направлении.
Серьезно, «Дискретная математика» — Вам дали ХОРОШИЙ совет для программиста и в частности для тех кто хочет решить данные задачи. Курс дискретки — всего пол-года в универе и учебник можно прочесть самостоятельно. И ИМЕННО ОН позволит Вам решить указанные выше задачи.
Остальные набросанные Вами темы лишь отражают Ваше желание быть «всесторонне развитым человеком» без понимания как к этому подойти.
Остальные набросанные Вами темы лишь отражают Ваше желание быть «всесторонне развитым человеком» без понимания как к этому подойти.
Мне 36. Сейчас я подтягиваю английский чтобы сдать IELTS и на следующий год поехать в Канаду получать второе высшее с перспективой дальнейшей иммиграции. Охотно поменял бы свой возраст на ваши 26 )
Лично я за весь опыт программирования поймал себя на мысле что с математикой у меня проблемы только во время программирования шейдеров и 3д графики. В других местах гугл вполне спасал.
Но русский бы подтянуть не помешало. Вот вам пара запятых и «и», а «е» верните, она еще пригодится:,, и
Я сам выступаю за грамотность в интернете, но всё-таки разговор не о том ведётся.
Может я что-то упустил, но вопрос был про нужность образования. Образование в моем понимании — это составленный план параллельного изучения широкого круга дисциплин. В контексте статьи моя точка зрения поддерживается словами о том, что базовый уровень в дисциплинах должен быть.
То, что вы IT-специалист, не сужает статью только до программирования. Русский язык такая же дисциплина, я лишь про это намекнул человеку, сказавшему, что ему образование нигде не нужно, кроме работы с графикой. Я намекнул, что он просто, возможно, не замечает вещей, которые не хочет замечать, но жизнь то длинная. Понадобятся еще.
То, что вы IT-специалист, не сужает статью только до программирования. Русский язык такая же дисциплина, я лишь про это намекнул человеку, сказавшему, что ему образование нигде не нужно, кроме работы с графикой. Я намекнул, что он просто, возможно, не замечает вещей, которые не хочет замечать, но жизнь то длинная. Понадобятся еще.
Именно математика в каждом случае открывает подлинную истину, так как она знает каждый скрытый секрет и хранит ключ к любому тончайшему смыслу: поэтому тот, кто имеет бесстыдство изучать физику и в то же время отрицать математику, должен бы знать с самого начала, что он никогда не войдёт во врата мудрости. Томас Брадвардин, «Трактат о пропорциях», 1328
Первую задачу довольно просто решить без гугла, с помощью 6 вложенных циклов.
Быстрая версия
for a in range(0, 30):
days = (1 << a)
for b in range(a + 1, 30):
days |= (1 << b)
for c in range(b + 1, 30):
days |= (1 << c)
for d in range(c + 1, 30):
days |= (1 << d)
for e in range(d + 1, 30):
days |= (1 << e)
for f in range(e + 1, 30):
days |= (1 << f)
print('{0:030b}'.format(days))
days ^= (1 << f)
days ^= (1 << e)
days ^= (1 << d)
days ^= (1 << c)
days ^= (1 << b)
Понятная версия
import sys
for a in range(1, 31):
days = set()
days.add(a)
for b in range(a + 1, 31):
days.add(b)
for c in range(b + 1, 31):
days.add(c)
for d in range(c + 1, 31):
days.add(d)
for e in range(d + 1, 31):
days.add(e)
for f in range(e + 1, 31):
days.add(f)
for i in range(1, 31):
if i in days:
sys.stdout.write('1')
else:
sys.stdout.write('0')
sys.stdout.write('\n')
days.remove(f)
days.remove(e)
days.remove(d)
days.remove(c)
days.remove(b)
«Быстрая версия» на python? Really?
Еще проще решить ее без гугла с помощью рекурсии. Это будет быстрая понятная версия ))
Жуть!
А теперь усложним задачу, нужно поставить 72 смены в году. Всё ещё всё-всё понятно?
Вот тут получается что математика необходима:
Нужно найти кол-во расстановок(число сочетаний)
В данном случае ответ это число сочетаний из 30 по 6, что равно 30!/(24!*6!)
Для 72 аналогично;
Нужно найти кол-во расстановок(число сочетаний)
В данном случае ответ это число сочетаний из 30 по 6, что равно 30!/(24!*6!)
Для 72 аналогично;
365!/(72! * (365-72)!) = 273 006 156 974 909 857 191 698 064 211 495 824 023 787 375 309 942 920 160 255 531 407 695 855 512 225
Вы правда хотите просмотреть все варианты?
Вы правда хотите просмотреть все варианты?
Вроде верно.
import itertools
for locone in itertools.combinations(xrange(0, 30), 6):
result = [0] * 30
for loc in locone:
result[loc] = 1
print result
Можно быстрее, правда, по-читерски:
UPD.
Опс…
import itertools
for days in itertools.combinations(range(31), 6):
print bin(reduce(lambda x, d: x | (1<<d), days, 0))
UPD.
Опс…
while True:
print 'Я буду обновлять комментарии перед отправкой'
Недавно писал «тайного Санту», так в поиске пришлось вбивать «равномерная случайная генерация беспорядков». К слову, равномерный алгоритм так и не нашел :)
Простейший способ — просто генерировать равномерно перестановки и проверять на «беспорядок».
А в этой статье описан чуть более быстрый способ, хоть все равно вероятностный.
Вот так чтобы не вероятностный, было бы вообще здорово :) Но видимо таких нет, а вероятность все равно достаточно высокая. Я решил использовать Fisher-Yates shuffle (который равномерный) до тех пор, пока не появится беспорядок, но останавливать перемешивание как только это перестает быть беспорядком. Тоже немного ускоряет.
А можно в качестве подтверждения пользы математики привести какие-то более близкие к жизни задачи?
Например, та же задача 1, но при этом охранник может работать не более 2 суток подряд, и всего 5 охранников, каждый из которых работает не пересекаясь с другими. Сгененерировать равномерный график для всех охранников.
Что про эту задачу говорит математика?
Или например, можете привести соотношение задач, которые рассмотрены в математике, к тем которые не рассматриваются ею?
Как думаете, что важнее для программиста — изучить математику или научиться читать чужой код и отлаживать программы?
И последнее: что вы понимаете под математикой (для программиста)? Математику в целом или например только дискретную математику?
Например, та же задача 1, но при этом охранник может работать не более 2 суток подряд, и всего 5 охранников, каждый из которых работает не пересекаясь с другими. Сгененерировать равномерный график для всех охранников.
Что про эту задачу говорит математика?
Или например, можете привести соотношение задач, которые рассмотрены в математике, к тем которые не рассматриваются ею?
Как думаете, что важнее для программиста — изучить математику или научиться читать чужой код и отлаживать программы?
И последнее: что вы понимаете под математикой (для программиста)? Математику в целом или например только дискретную математику?
Сгененерировать равномерный график для всех охранников
123451234512345123451234512345
Меня умиляет ваша апелляция к жизненности. Могу привести сразу 2 жизненные задачи: написать говносайт за сутки за 6 т.р. и написать отчет в 1С в те же сроки и за те же деньги. Таких задач намного больше, чем тех, в которых нужно знание математики. Но сомневаюсь, что есть люди, которые бы хотели всю жизнь решать именно такие задачи.
Как думаете, что важнее для программиста — изучить математику или научиться читать чужой код и отлаживать программы?
Как вы думаете, что важнее для вас — сердце или печень?
Таких задач намного больше, чем тех, в которых нужно знание математики
Хорошо, что вы это осознаете.
Но сомневаюсь, что есть люди, которые бы хотели всю жизнь решать именно такие задачи.
Это смотря какие задачи. Есть очень много интересных.
И например, если брать этот ваш аргумент про интерес, то я бы не хотел всю жизнь решать задачи подобные вашим задачам 1-3.
Как вы думаете, что важнее для вас — сердце или печень?
Неуместная аналогия. Бывают программисты не умеющие либо то либо то, но не бывает людей без печени либо сердца.
Не так давно в комментах к одному из постов я приводил такой простой пример: Вы разрабатываете аналог фотошопа, вам требуется написать алгоритм Blur(пускай простой по Гауссу), как вы это будете делать?
en.wikipedia.org/wiki/Gaussian_blur — первая ссылка по «blur гаусс» в гугле. Недостаточно? Она не последняя.
Ну круто, в вики есть описание. Как вы будете конкретно это реализовывать?
з.ы. Для ясности вопроса поясню: я, как пользователь хочу, чтобы при больших размерах ядра(300*300 например) мне не приходилось ходить пить кофе ожидая результата.
з.ы. Для ясности вопроса поясню: я, как пользователь хочу, чтобы при больших размерах ядра(300*300 например) мне не приходилось ходить пить кофе ожидая результата.
Не могу ответить на ваш вопрос, поскольку не владею темой. Но за несколько лет изучания различных разделов ВМ (матанализ, дифуры, аналитическая геометрия, операционное исчисление, теорвер и матстастика — по памяти) мы об оптимизациях вычислений не говорили.
Ну вот, а владей вы по хорошему инструментом(математикой) вы бы по описанию на Вики поняли, что Размытие по Гауссу это по сути вычисление свертки, а вычислять свертки эффективно при помощи Быстрого Преобразования Фурье… и благодаря этим выводам написали бы качественную реализацию алгоритма, по скорости значительно превосходящую решение в лоб.
И таких задач в практике программиста встречается масса, и многие задачи через google не решаются вовсе.
И таких задач в практике программиста встречается масса, и многие задачи через google не решаются вовсе.
Я лично за поголовное владение математикой среди программистов, однако вы преувеличиваете объёмы и количество задач, в которых она применима. В любом крупном проекте таких задач единицы, всё остальное — прикладное программирование.
Зато задачи эти, как правило, ключевые. И от правильности их решения сильно зависит то, насколько ваш продукт будет хорош.
Решение (указание на алгоритмы или их описание) таких ключевых задач по-моему должно быть в ТЗ программиста. Это уровень аналитика или архитектора.
Алгоритмы часто бывают локальны. С архитектурой это несколько опосредовано связано (ну если только у вас в компании не 100000 человек и программисты — code monkey). Кто такие аналитики и чем занимаются — я не знаю.
Руководствуясь только описание алгоритма(без понимания математических принципов в него заложенных) программист не сможет эффективно его реализовать. Продумать как код будет взаимодействовать со всякими кэшами, как будет происходить синхронизация при много-поточном вычислении и т.п. — это чисто программистские задачи. Если программист считает что это тоже задача архитектора… ну тогда, пардон, встает вопрос о его квалификации и профпригодности.
какой солдат программист не мечтает стать генералом аналитиком/архитектором?
Я не мечтаю. Это же с людьми придется общаться :)
И это говорит человек, у которого over 32000 комментариев только на хабре :)
Забыл уточнить «в реале».
Вы интроверт?
Насколько я могу судить.
Ради интереса попробуйте тестик пройти, к примеру тут.
p.s: это всё оффтоп конечно, просто среди программистов интровертов довольно много.
p.s: это всё оффтоп конечно, просто среди программистов интровертов довольно много.
Ваш социотип: логико-интуитивный интроверт — «Робеспьер»
Мой тот же, Логико-интуитивный интроверт — «Аналитик» (Робеспьер, INTJ), а социотип дуала — Этико-сенсорный экстраверт — «Энтузиаст» (Гюго, ESFJ) :)
А по гороскопу вы кто?
Дева… упс, пойду профиль заполню. Надеюсь вы не троллили )
Не, это был саркастический вопрос нелюбителя соционики. Одно дело «Психологические типы» Юнга, а другое — то, во что это все превратилось, с тестами на 5 минут
Так то оно так, но под всеми этими тестами честно написано, что для правильного определения типа вам необходимо обратиться к специалисту. К тому же есть тесты и не на 5 минут, а гораздо более длительные, и соответственно более надёжные, предлагающие проанализировать фразы, описывающие некие события, а так же фотографии событий, но уже без текста.
Да, но, как правило, их решением занимается очень небольшой круг людей. Остальные же решают исключительно прикладные задачи.
Повторюсь, я считаю, что математика нужна программисту. Однако подавляюще большая масса нашей работы с нею мало связана.
Повторюсь, я считаю, что математика нужна программисту. Однако подавляюще большая масса нашей работы с нею мало связана.
Как показывает практика в первую очередь важно комплексное решение задач в проекте.
Для примера, вот заявление кардинально противоположное вашему, и как бы топорно оно не звучало, но «практически любая программа без хорошего гуя для ПК, или смартфона никогда не будет пользоваться популярностью» :)
В общем во всём нужна гармония.
Для примера, вот заявление кардинально противоположное вашему, и как бы топорно оно не звучало, но «практически любая программа без хорошего гуя для ПК, или смартфона никогда не будет пользоваться популярностью» :)
В общем во всём нужна гармония.
Что есть «прикладное программирование» в вашем понимании? И что есть «любой крупный проект»?
Вы надеюсь понимаете, что весь проект может провалиться из-за того, что подобная задача:
а) не решена вовсе
б) решена хуже чем у конкурентов(если продукт не уникален на рынке)
Вы надеюсь понимаете, что весь проект может провалиться из-за того, что подобная задача:
а) не решена вовсе
б) решена хуже чем у конкурентов(если продукт не уникален на рынке)
В моём понимании «прикладное программирование» — это, к примеру, бизнес-логика, интерфейсы.
И, как я уже в третий раз повторяю, есть задачи, требующие определённых математических познаний. И их должны решать люди, имеющие эти познания. Но эти задачи, как бы ни были они важны для проекта, не составляют основную массу. Хотите конкретных цифр по отношению наукоёмких задач и, так скажем, «обычных»? У меня их нет, мои слова основаны лишь на личном опыте.
И, как я уже в третий раз повторяю, есть задачи, требующие определённых математических познаний. И их должны решать люди, имеющие эти познания. Но эти задачи, как бы ни были они важны для проекта, не составляют основную массу. Хотите конкретных цифр по отношению наукоёмких задач и, так скажем, «обычных»? У меня их нет, мои слова основаны лишь на личном опыте.
Ну если карьерный рост не интересует, то конечно можно всю жизнь писать сайты на PHP, миллионы оберток к базам данных и т.д. и т.п. Только как-бы не пришлось к годам 40 осознать, что при увеличившихся зарплатынх ожиданиях(стажа то много уже), что уровень актуальных знаний остался по большому счету на уровне более дешевых 20-30 летних программистов. И конкурировать с ними будет очень сложно. Тогда как хорошего математика умеющего программировать с руками оторвет любая крупная компания.
Ну а насчет соотношения наукоемких задач, кроме как при разработке прикладного ПО, могу сказать следующее: во всем машиностроении(самолеты/машины/станки и тд и тп), во всех добывающих промышленностях, в энергетике, в финансовой аналитике — везде трудится немало программистов над наукоемкими проектами, просто про них обычно не вспоминают.
Ну а насчет соотношения наукоемких задач, кроме как при разработке прикладного ПО, могу сказать следующее: во всем машиностроении(самолеты/машины/станки и тд и тп), во всех добывающих промышленностях, в энергетике, в финансовой аналитике — везде трудится немало программистов над наукоемкими проектами, просто про них обычно не вспоминают.
Может вы и правы, но об этом думать нужно было даже не в 20 лет, а в 17-18. И, главное, даже не в образовании как таковом, а в поиске работы математиком, а не программистом.
По сути вопрос «нужна ли программисту математика» свелся к «математику нужно программирование» :)
По сути вопрос «нужна ли программисту математика» свелся к «математику нужно программирование» :)
В ваших словах как-то много презрения.
Так же как проект может провалиться, если программист плохо понимает работу с БД, или с асинхронностью у него проблемы, дедлоки, понимаешь, тут и там. На том о чем вы говорите свет клином не сошелся.
Хотя математика — гимнастика ума, да.
Хотя математика — гимнастика ума, да.
Вы так говорите, как будто реляционные БД не описываются алгеброй, а построение модели исполнения не поможет вам избежать дед-локов.
Для использования РСУБД знаний реляционной алгебры не нужно. Больше нужно уметь смотреть планы запросов и грамотно расставлять индексы.
тем не менее, знание теории баз данных поможет и «грамотно расставить индексы», и правильно составить запросы.
А при проектировании БД не надо её нормализовать с целью оптимизации? А при построении запросов не требуется расписать то, что мы хотим получить(дабы оптимизировать сам запрос)?
Тут вопрос сводится опять к тому, что без знания мат. составляющей БД можно решать задачу, но будет ли решение оптимальным и достаточного качества — это уже как повезет, тогда как проанализировав задачу с точки зрения математики в неё заложенной, можно обоснованно строить адекватные модели.
Тут вопрос сводится опять к тому, что без знания мат. составляющей БД можно решать задачу, но будет ли решение оптимальным и достаточного качества — это уже как повезет, тогда как проанализировав задачу с точки зрения математики в неё заложенной, можно обоснованно строить адекватные модели.
Вы знаете, для меня все ваши термины не откровение: и свертка, и БПФ — я их изучал и вузе, и потом приходилось сталкиваться по работе. Но чтобы я смог провести цепочку сейчас, мне нужно было бы последние 20 лет этим активно заниматься просто ради поддержания тех знаний в оперативной памяти только для того, чтобы ответить на ваш вопрос. Слишком большая цена, по-моему. На крайний случай выгоднее кому-то заплатить.
Мне кажется вы всё-таки довольно сильно лукавите, в плане того на сколько математика — это именно инструмент. Математик — математику рознь, и далеко не каждый изучал, и тем более изучал в должной степени свёртки и быстрые преобразования Фурье, для того что-бы прям так распознать в размытии по Гауссу их, и тем более реализовать. Например у нас в университете, алгебраисты, вместо них проходят теорию групп Ли, которая тоже важна, но вряд ли поможет в данном случае. С другой стороны, если культура математика достаточно высока, и образование достаточно хорошо, то он сможет быстрее и меньшей кровью разобраться в тех же преобразованиях Фурье, нежели программист не изучавший математику.
Если я правильно помню, то свертки и фурье-преобразование проходятся неоднократно в курсах математического анализа, комплексного анализа, и уравнений математической физики… все эти курсы общеобразовательные для любой боле мене математической специальности.
Ключевой посыл моего примера именно в том и заключался, что программист-математик имеет огромное преимущество перед самоучкой за счет того, что:
а) порог вхождения в любой проект для него ниже
б) он может генерировать более качественный алгоритмические решения(получение алгоритма с меньшей алгоритмической сложностью всегда в приоритете перед оптимизацией конкретной реализации)
в) когда возникнет задача, решение которой нет возможности найти в Google, программист-математик сможет решать её используя свои знания(или поиск аналогий в том-же Google и адаптация), тогда как у самоучки таких знаний банально нет.
А пример с Blur'ом был всего лишь «более живым» по сравнению с задачами предложенными ТС (комментатору, которому я отвечал не понравилась академичность этих задач). С тем-же успехом можно предложить и другие задачи использующие другие области из математики.
Ключевой посыл моего примера именно в том и заключался, что программист-математик имеет огромное преимущество перед самоучкой за счет того, что:
а) порог вхождения в любой проект для него ниже
б) он может генерировать более качественный алгоритмические решения(получение алгоритма с меньшей алгоритмической сложностью всегда в приоритете перед оптимизацией конкретной реализации)
в) когда возникнет задача, решение которой нет возможности найти в Google, программист-математик сможет решать её используя свои знания(или поиск аналогий в том-же Google и адаптация), тогда как у самоучки таких знаний банально нет.
А пример с Blur'ом был всего лишь «более живым» по сравнению с задачами предложенными ТС (комментатору, которому я отвечал не понравилась академичность этих задач). С тем-же успехом можно предложить и другие задачи использующие другие области из математики.
Вот я их прошел, сдал на отлично, использовал в работе (до того как прошел, понадобились раньше чем по программе у нас были) и ничем они мне не помогли для вашей задачи. Хотя, наверное, после вашей наводки мне её быстрее получится решить, если бы проходил что-то другое, ту же алгоритмическую сложность.
Кстати, из того, что вы назвали только матанализ был, хотя математика (теорвер с матстатом прежде всего) и физика (измерения) типа наш хлеб. В общем, считаю, что 4 года вышку зря по большому счету в профессиональном плане изучал, так, именно, что общеообразовательные курсы, типа истории или психологии — в теории могли бы пригодиться, если бы пошел работать по специальности и занимался измерительными системами и прочей метрологией, но не пригодились.
Кстати, из того, что вы назвали только матанализ был, хотя математика (теорвер с матстатом прежде всего) и физика (измерения) типа наш хлеб. В общем, считаю, что 4 года вышку зря по большому счету в профессиональном плане изучал, так, именно, что общеообразовательные курсы, типа истории или психологии — в теории могли бы пригодиться, если бы пошел работать по специальности и занимался измерительными системами и прочей метрологией, но не пригодились.
FFT для этой задачи не нужно. То же самое делается быстрее через IIR.
Вообще, реализация цильно зависит от деталей ТЗ. Например для нашей задачи и IIR оказался слишком медленным. Так что у нас теперь другое ;-)
Вообще, реализация цильно зависит от деталей ТЗ. Например для нашей задачи и IIR оказался слишком медленным. Так что у нас теперь другое ;-)
И это очень показательно. Фактически, обладающий знанием о FFT велосипедостроитель скорее всего сделает имплементацию хуже нулевого человека, который потратил пару часов на гугление всех достижений человечества по теме
А что будет делать «нулевой» человек, когда в Google не найдет решения?(не надо тут задвигать про «google знает всё», это далеко не так)
з.ы. товарисч valexey таки не «нулевой» человек в плане реализации Gaussian Blur, т.ч. и тут «Акелла промахнулся».
з.ы. товарисч valexey таки не «нулевой» человек в плане реализации Gaussian Blur, т.ч. и тут «Акелла промахнулся».
Ну, я всё же не совсем нулевой человек :-)
Во-первых я немного по работе с DSP возился (FFT, DCT, и всякие FIR & IIR — то было связано с обработкой данных с нашего фотоплетизмографа, нужно было выделять полезный сигнал, анализировать его (там много данных), давить шумы, детектировать и игнорировать motion artefacts и так далее).
Во-вторых конкретно с проблемой быстрого блюра со здоровенным ядром (то есть радиусом) я также сталкивался в нашем (пока-что) хобби-проекте, что родился на хакатоне: habrahabr.ru/company/intel/blog/176985/ — наш проект — Virtualens. С тех пор у нас алгоритмы улучшились, оно стало работать сильно быстрее и качество картинки существенно возросло. Теперь это реально расфокусировка.
Ну, а по теме — если вы пишете фотошоп, то вам необходимо как минимум уметь читать papers различных исследовательских работ по теме обработки изображений. То есть понимать их язык, не пугаться математики, и без проблем залезть в спец. литературу. То есть совсем-совсем без технического образования будет действительно тяжко, но и академиком быть не нужно.
А ещё очень здорово научиться читать патенты — там много интересного, но там такой язык и такой стиль изложения… Нет, я лучше очередной дисер прочитаю.
Во-первых я немного по работе с DSP возился (FFT, DCT, и всякие FIR & IIR — то было связано с обработкой данных с нашего фотоплетизмографа, нужно было выделять полезный сигнал, анализировать его (там много данных), давить шумы, детектировать и игнорировать motion artefacts и так далее).
Во-вторых конкретно с проблемой быстрого блюра со здоровенным ядром (то есть радиусом) я также сталкивался в нашем (пока-что) хобби-проекте, что родился на хакатоне: habrahabr.ru/company/intel/blog/176985/ — наш проект — Virtualens. С тех пор у нас алгоритмы улучшились, оно стало работать сильно быстрее и качество картинки существенно возросло. Теперь это реально расфокусировка.
Ну, а по теме — если вы пишете фотошоп, то вам необходимо как минимум уметь читать papers различных исследовательских работ по теме обработки изображений. То есть понимать их язык, не пугаться математики, и без проблем залезть в спец. литературу. То есть совсем-совсем без технического образования будет действительно тяжко, но и академиком быть не нужно.
А ещё очень здорово научиться читать патенты — там много интересного, но там такой язык и такой стиль изложения… Нет, я лучше очередной дисер прочитаю.
Я об этом и писал в сообщении внизу (http://habrahabr.ru/post/183448/#comment_6375246). От программиста не требуется быть математиком, требуется знать нотацию и уметь кодировать пейперы. И даже если «слышал звон» по поводу имплементации чего-либо, все равно нужно потратить несколько часов на поиск нужной информации.
Ну вроде пока никого в google не банят. Но в google не всегда есть нужный пейпер, и большинство статей пишутся левой пяткой, где теория не сходится с практикой и приходится додумывать за автора, что он там хотел написать.
О, исследовательские папиры это вообще пестня отдельная. Там обычно все хорошо работает на довольно узком множестве входных условий. Шаг влево-вправо, и всё, приплыли!
Это я помню, был один папир про компенсацию motion artefacts на фотоплетизмограмме через адаптивную фильтрацию. Всё было построено на том, что между ускорением и motion artefact'ом на фотоплетизмограмме имеется линейная корреляция. Приведены примеры, и у них там всё так хорошо было. Вот сигнал сырой (изображена страшная жесть), а вот сигнал восстановленный (вполне себе пульсовая волна, хоть и видно что слегка кривоватая). То есть у них всё было хорошо.
Но есть нюанс — не все motion artefacs линейно коррелируют с ускорением :-) То есть в результате эти самые артефакты поделились на три категории — там где есть линейная корелляция (ну, например если человек прыгает — там не то что корреляция, там есть прямая причинно-следственная связь), там где корреляция не линейная (и прямой причинно следственной связи нет, точнее так — и ускорение и motion artefact вызваны общей причиной, но ни один из них не является причиной другого. Это например отжимания), и там где корреляции нет вовсе.
И вот таких вот нюансов на самом деле море. Поэтому частенько нельзя взять, реализовать то что есть в папире и чтобы сразу все стало хорошо. Так или иначе нужно проводить свои исследования и составлять свой рецепт под свою задачу основываясь на результатах чужих исследований.
Это я помню, был один папир про компенсацию motion artefacts на фотоплетизмограмме через адаптивную фильтрацию. Всё было построено на том, что между ускорением и motion artefact'ом на фотоплетизмограмме имеется линейная корреляция. Приведены примеры, и у них там всё так хорошо было. Вот сигнал сырой (изображена страшная жесть), а вот сигнал восстановленный (вполне себе пульсовая волна, хоть и видно что слегка кривоватая). То есть у них всё было хорошо.
Но есть нюанс — не все motion artefacs линейно коррелируют с ускорением :-) То есть в результате эти самые артефакты поделились на три категории — там где есть линейная корелляция (ну, например если человек прыгает — там не то что корреляция, там есть прямая причинно-следственная связь), там где корреляция не линейная (и прямой причинно следственной связи нет, точнее так — и ускорение и motion artefact вызваны общей причиной, но ни один из них не является причиной другого. Это например отжимания), и там где корреляции нет вовсе.
И вот таких вот нюансов на самом деле море. Поэтому частенько нельзя взять, реализовать то что есть в папире и чтобы сразу все стало хорошо. Так или иначе нужно проводить свои исследования и составлять свой рецепт под свою задачу основываясь на результатах чужих исследований.
О, исследовательские папиры это вообще пестня отдельная.
Бумаги без reference implementation я бы вообще не смотрел (хотя довольно часто заказывают написание такой имплементации по какой-нибудь статье). А с ней проверяется достаточно быстро, стоящая вещь ли написана, или отписка для каких-либо конъюктурных целей.
И вот таких вот нюансов на самом деле море. Поэтому частенько нельзя взять, реализовать то что есть в папире и чтобы сразу все стало хорошо. Так или иначе нужно проводить свои исследования и составлять свой рецепт под свою задачу основываясь на результатах чужих исследований.
Является ли исследователь, проводящий сотни времени за такими экспериментами, программистом в общеприятом понимании этого слова. Workflow у такого человека, как и требуемые навыки, сильно другие.
Бумаги без reference implementation я бы вообще не смотрел (хотя довольно часто заказывают написание такой имплементации по какой-нибудь статье). А с ней проверяется достаточно быстро, стоящая вещь ли написана, или отписка для каких-либо конъюктурных целей.
Не знаю, может мне так «везло», но большинство бумаг, что я читал, были без реализации которую можно было бы взять, и попробовать сразу, без кодинга. Обычно реализовывать нужно было самому.
Является ли исследователь, проводящий сотни времени за такими экспериментами, программистом в общеприятом понимании этого слова. Workflow у такого человека, как и требуемые навыки, сильно другие.
Я бы отказался от самого понятия «общепринятое понимание» применительно к программистам. Программисты они сильно разные, область то очень широкая. Если проводить аналогию, то это всё равно что под «водителем транспортного средства», куда включены и те кто на самокатах да на велосипедах катается, гужевой транспорт, легковые автомобили, грузовые, автобусы, самолеты и космические корабли, подразумевать только какую-то одну категорию, ну например велосипедистов (а может какую-то другую, ведь про программистов то мы не уточняли!).
Должен ли водитель знать про двигатель внутреннего сгорания? :-)
Не знаю, может мне так «везло», но большинство бумаг, что я читал, были без реализации которую можно было бы взять, и попробовать сразу, без кодинга.
Обычно про это просто не пишут в самой статье, но если погуглить на каком-нибудь maltab central по имени автора, можно найти. Еще можно спросить. Или найти имплементацию не от автора. Если статье больше нескольких лет и она стоящая, что-нибудь, да будет. Если же она никого не заинтересовала, кто мог бы выложить исходники в сеть, может она не настолько хороша?
Программисты они сильно разные, область то очень широкая.
Ну если взять какого-нибудь эмбедщика, пищущего под RTOS, или backend web программиста, то, хотя и навыки требуются разные, стиль работы примерно один и тот же: довольно четкие задачи, примерно одни и те же от проекта к проекту, день начинается с svn co и заканчивается svn ci, основная творческая работа касается оптимизации. А исследователь может неделю дрючить 15 строк в матлабе с неизвестным результатом.
Водитель знать про двигатель внутреннего сгорания должен, но точно не должен его разрабатывать, а предприятие, на котором водитель вынужден настраивать карбюратор, скорее всего, не самое эффективное.
Водитель знать про двигатель внутреннего сгорания должен, но точно не должен его разрабатывать, а предприятие, на котором водитель вынужден настраивать карбюратор, скорее всего, не самое эффективное.
Зачем водителю велосипеда знать про двигатель внутреннего сгорания? ;-)
Смотря на каком уровне «нет нужного пейпера». Недавно у меня была задача, которая сводилась к generalized assignment problem. Естественно, если бы я не знал, что она к этому сводится, я бы нужный пейпер не нашел (хотя, вообще говоря, я нагуглил то, что она к этому сводится, на stackoverflow). Но как только я это узнал, все стало довольно простым. Такая эрудиция программисту, конечно, помогает, но нельзя угадать наперед, что именно тебе потребуется.
Другой вопрос, если задача вообще уникальная и ни к чему не сводится. Тогда нужно идти к начальству и спрашивать, готово ли оно оплачивать исследования (то есть штуку с неизвестным результатом), и почему этим должен заниматься программист, а не отдельный человек со своими навыками
Другой вопрос, если задача вообще уникальная и ни к чему не сводится. Тогда нужно идти к начальству и спрашивать, готово ли оно оплачивать исследования (то есть штуку с неизвестным результатом), и почему этим должен заниматься программист, а не отдельный человек со своими навыками
Тут есть один нюанс — нужно не только уметь читать рецепты и по им готовить, но нужно и понимать их и уметь изменять. То есть знаний на уровне пользователя стандартных алгоритмов из stl — не всегда достаточно.
Какой бы пример привести… Ну, например ту же реализацию сортировки из stl — по крайней мере в gcc эта сортировка не является квиксортом, или сортировкой слиянием. Она не является каким-то одним алгоритмом вычитанным в книжке. Там используется несколько стандартных алгоритмов + эвристики (на маленьких наборах используем одно, на больших другое и так далее). И обогнать эту стандартную сортировку, реализовав какой-то один чистый алгоритм из книжки — малореально.
Поэтому если задача не клепать клей между DB и вёбом, и не просто набор ифов (бизнеслогика), то сборник рецептов нужно не только уметь читать и использовать, но и пополнять собственными рецептами, а также видоизменять существующие (понимая к чему это приведет).
Впрочем, я вполне понимаю, что вероятно большинство программистов таки да, лепят очередной GUI (быстрый, удобный, прорывной), клеят базу данных с вёбом, пишут развесистую бизнес логику и так далее. Им вероятно не слишком то, что я описал выше, нужно. А если вдруг нужно — то в конторе есть кто-то кто в этом разбирается (не академик, нет) и сможет подсказать что где глянуть и почему вдруг не работает.
Какой бы пример привести… Ну, например ту же реализацию сортировки из stl — по крайней мере в gcc эта сортировка не является квиксортом, или сортировкой слиянием. Она не является каким-то одним алгоритмом вычитанным в книжке. Там используется несколько стандартных алгоритмов + эвристики (на маленьких наборах используем одно, на больших другое и так далее). И обогнать эту стандартную сортировку, реализовав какой-то один чистый алгоритм из книжки — малореально.
Поэтому если задача не клепать клей между DB и вёбом, и не просто набор ифов (бизнеслогика), то сборник рецептов нужно не только уметь читать и использовать, но и пополнять собственными рецептами, а также видоизменять существующие (понимая к чему это приведет).
Впрочем, я вполне понимаю, что вероятно большинство программистов таки да, лепят очередной GUI (быстрый, удобный, прорывной), клеят базу данных с вёбом, пишут развесистую бизнес логику и так далее. Им вероятно не слишком то, что я описал выше, нужно. А если вдруг нужно — то в конторе есть кто-то кто в этом разбирается (не академик, нет) и сможет подсказать что где глянуть и почему вдруг не работает.
Поэтому если задача не клепать клей между DB и вёбом, и не просто набор ифов (бизнеслогика), то сборник рецептов нужно не только уметь читать и использовать, но и пополнять собственными рецептами, а также видоизменять существующие (понимая к чему это приведет).
Помнится писал игрушку ещё в школе, понадобилась математическая библиотека — портировал в свой язык с ассемблера для другого языка толком не понимая большую часть действий типа вычисления синуса через ряды. А потом, оптмизируя, реализовал целочисленное (вернее как рациональное число с отдельным числителем и знаменателем) вычисление того же синуса. И всё это толком не понимая, что значок суммы означает.
Что значит быстрее? Для FFT оценка сложности будет O(n*log(n)), если не ошибаюсь, то за лучшее время посчитать свертку не получится, максимум что можно улучшить, это константу, но она тут обычно получается небольшая. Плюсом есть такая замечательная вещь как cufft, и используя FFT мы почти без изменений переносим код на CUDA.
з.ы. в любом случае решение будет лучше чем решение в лоб, у которого вроде как квадратичная асимптотика с большой константой.
з.ы. в любом случае решение будет лучше чем решение в лоб, у которого вроде как квадратичная асимптотика с большой константой.
Насколько я понимаю, в FFT для данной задачи n=w*h картинки, так? Так вот, IIR имеет сложность O(n).
Да, поясню — свёртка в лоб, это по сути FIR. Сложность соответственно: O(w*h*r^2) для 2D случая. (для 1D будет естественно O(w*r)). Это если без оптимизаций. С оптимизациями, учитывающими симметрию ядра, будет что-то вроде O(w*h*r).
Но всем известно что FIR в ряде случаев можно заменить на IIR, который имеет сложность O(w*h) в 2D и O(w) в 1D соответственно. То есть от «радиуса размытия» трудоёмкость не зависит. У IIR есть свои достоинства и свои недостатки, в частности его сложнее рассчитывать, можно получить неустойчивый фильтр. Ну и если хочется получить какую-то особую форму импульсной характеристики (например с плоской вершиной), то возможно придется городить фильтр высокого порядка. В частности и из за этого, мы от него и отказались (по крайней мере пока).
Но всем известно что FIR в ряде случаев можно заменить на IIR, который имеет сложность O(w*h) в 2D и O(w) в 1D соответственно. То есть от «радиуса размытия» трудоёмкость не зависит. У IIR есть свои достоинства и свои недостатки, в частности его сложнее рассчитывать, можно получить неустойчивый фильтр. Ну и если хочется получить какую-то особую форму импульсной характеристики (например с плоской вершиной), то возможно придется городить фильтр высокого порядка. В частности и из за этого, мы от него и отказались (по крайней мере пока).
Сложность одномерного iir-фильтра скорее o(n*m), где n — длина сигнала, а m — порядок фильтра. Какой требуется порядок IIR-фильра, чтобы работать как гауссов фильтр с размером ядра 200х200? Он меньше log(n)?
Если я не ошибаюсь, то при использовании IIR у вас получится, строго говоря, не гауссиана, а нечто на неё похожее. Ну да это лирика, вероятно такое решение будет лучше чем с FFT.
з.ы. сам не сталкивался с задачей вычисления Gaussian Blur, т.ч. пример был взят не «из жизни», если что)
з.ы. сам не сталкивался с задачей вычисления Gaussian Blur, т.ч. пример был взят не «из жизни», если что)
Ну, точной гауссианы у нас один фиг не выйдет, ведь у нас же в конечном итоге целые числа. Причем 8ми битные.
Короче, чтобы воду в ступе не толочь, вот статейка на тему: habrahabr.ru/post/151157/
:-)
Короче, чтобы воду в ступе не толочь, вот статейка на тему: habrahabr.ru/post/151157/
:-)
Бред пишите, хороший программист возьмёт готовую реализацию и не будет изобретать велосипед. Математика не нужна.
И кто по вашему должен написать эту «готовую реализацию»?)
Тот, чья работа заключается в реализации алгоритмов. Это, как правило, программисты-математики. Например, несколько лет обратно был разработан алгоритм контенто-зависимой модификации размеров изображения, это сделалистуденты математики вроде как. Компания Adobe купила алгоритм вместе с ребятами и встроила в Photoshop. Разработчики фотошопа, добавившие инструмент в интерфейс вряд ли изучали всю теорию того, что там внутри, просто нарисовали кнопку, сделали инклюд и повесили вызов функции на кнопку. Им пофиг что внутри.
Эмм… Идея то, конечно, правильная, но примеры, честно говоря, не самые лучшие. Первая задача решается рекурсивно за то же время, что и генерация сочетаний (вернее, алгоритм генерации с большой вероятностью будет тем же самым). Вы бы хотя бы спросили, сколько таких сочетаний может быть — тогда да, математика даёт быстрый ответ без необходимости искать все такие комбинации. Решение второй и третьей задач опирается на, мягко говоря, не самые известные разделы математики, которые всё-равно вряд ли будут включены в программу (лично я вообще раньше не слышал про такие понятия как остовное дерево и числа Каталана). Да и условия задач, честно говоря, высосаны из пальца.
Есть много других примеров, как математика используется в программировании. Например, за банальной хеш-таблицой скрывается мат. статистика и равномерное распределение — попробуйте выбрать плохую хеш-функцию, и сложность алгоритма тут же вырастет в разы. Сама сложность алгоритма, в общем-то, тоже упирается в математическое понятие Big O. Базы данных — это теория множеств и реляционная алгебра. Выведение типов в современных языках программирования — логика. Микроконтроллеры строятся на основании конечных автоматов. Любые сети (в том числе и социальные) — теория графов. А если брать ещё и отдельные направления в программировании, то оказывается, что практически под всеми из них лежит именно математическая основа: обработка изображений — сплошная линейная алгбера и дифференциальное исчисление, оптимизация в компиляторах и статический анализ программ — графы потока контроля, функциональное программирование — лямбда-исчисление, машинное обучение — статистика и т.д. и т.п.
Другое дело, что в университетах почему-то не принято проводить параллели между сухой математической теорией и использованием оной на практике. И вот это уже проблема, потому что к моменту появление подходящих задач вся математическая теория чаще всего уже забывается.
Есть много других примеров, как математика используется в программировании. Например, за банальной хеш-таблицой скрывается мат. статистика и равномерное распределение — попробуйте выбрать плохую хеш-функцию, и сложность алгоритма тут же вырастет в разы. Сама сложность алгоритма, в общем-то, тоже упирается в математическое понятие Big O. Базы данных — это теория множеств и реляционная алгебра. Выведение типов в современных языках программирования — логика. Микроконтроллеры строятся на основании конечных автоматов. Любые сети (в том числе и социальные) — теория графов. А если брать ещё и отдельные направления в программировании, то оказывается, что практически под всеми из них лежит именно математическая основа: обработка изображений — сплошная линейная алгбера и дифференциальное исчисление, оптимизация в компиляторах и статический анализ программ — графы потока контроля, функциональное программирование — лямбда-исчисление, машинное обучение — статистика и т.д. и т.п.
Другое дело, что в университетах почему-то не принято проводить параллели между сухой математической теорией и использованием оной на практике. И вот это уже проблема, потому что к моменту появление подходящих задач вся математическая теория чаще всего уже забывается.
Мнэм… Как-то Вы меня подвесили немного. Если Вы знаете хоть немного теорию графов — Вы не можете не знать остовных деревьев. А вообще, мне казалось, что комбинаторику и теорию графов (хотя бы в очень зачаточном виде) читают в курсе математики в любом приличном техническом ВУЗе на первых курсах. Это вещи как раз достаточно базовые, и иметь о них представление необходимо. (Это все на правах ИМХО, конечно же)
Теорию графов не читают в курсе мат. анализа. Теорию графов читают в курсах дискретной математики (вещи, очень отвязанной и от математики, и от прикладного программирования) и в курсах алгоритмов. Потом, базовая теория графов вообще не вписывается в моем понимании в что-то связанное с коль более-менее сложной или хотя бы среднего уровня сложности математикой. Т.е. если человек пишет калькулятор ему нужны базовые понятия о числах и арифметике (дальше по желанию, в зависимости от того как будет реализовывать калькулятор — либо через eval(), либо через распарсивание выражения в дерево, либо через перевод в обратную польскую нотацию, либо еще как), если пишет что-то связанное с графами — базовые понятия о графах. В спорах «нужна ли программисту математика» обычно задается вопрос в стиле «ну и зачем мне эти интегралы, если я пишу веб-сайты?»
Да, пардон, не уточнил. В курсе дискретной математики, конечно же. А разве его не читают на любой специальности, хоть как-то связанной с CS? Но тут я могу быть упорот и предвзят :)
Будете смеяться, но я как раз-таки пишу веб-сайты. И вернулся в институт учить математику как раз потому, что понял, что базовых знаний для решения текущих задач мне еще хватает, а вот для того, что маячит на горизонте — уже нет. А самообразование (по крайней мере, в моем случае) не работает, хоть ты тресни.
В спорах «нужна ли программисту математика» обычно задается вопрос в стиле «ну и зачем мне эти интегралы, если я пишу веб-сайты?»
Будете смеяться, но я как раз-таки пишу веб-сайты. И вернулся в институт учить математику как раз потому, что понял, что базовых знаний для решения текущих задач мне еще хватает, а вот для того, что маячит на горизонте — уже нет. А самообразование (по крайней мере, в моем случае) не работает, хоть ты тресни.
А можно поподробней, как вы собираетесь использовать математику при написании сайтов? Я сейчас как раз потихоньку готовлю цикл статей по использованию некоторых разделов оной на практике, так что истории из реальной жизни были бы очень полезны.
Я пару раз видел как людям не хватало математики для пагинации в собственном убер движке/framework/CMS.
«Пишу сайты» — это легкая самоирония, так же как и математика в данном контексте суть обобщение. На самом деле мы пишем большие web-приложения. Сейчас вот понадобится считать разные хитрые статистики, динамически делать оптимизации. Обрабатывать достаточно большие объемы данных, где решения «в лоб» почти всегда либо не работают, либо работают непозволительно долго. А тут уже и алгебра, и статистика, и теория графов, и базы данных, и еще до черта всякого.
Многие задачи, которые взрывают мозг, если решать их так, как они поставлены, довольно ненапряжно решаются стоит только посмотреть на них с точки зрения алгебры.
Живой пример какой-нибудь постараюсь придумать. Сходу не получается, ибо NDA.
Но да, чтобы клепать визитки и витрины математики точно особо не надо. Хотя базы данных знать неплохо, а это тоже математика, если уж так посмотреть.
Многие задачи, которые взрывают мозг, если решать их так, как они поставлены, довольно ненапряжно решаются стоит только посмотреть на них с точки зрения алгебры.
Живой пример какой-нибудь постараюсь придумать. Сходу не получается, ибо NDA.
Но да, чтобы клепать визитки и витрины математики точно особо не надо. Хотя базы данных знать неплохо, а это тоже математика, если уж так посмотреть.
Теорию графов не читают в курсе мат. анализа. Теорию графов читают в курсах дискретной математики (вещи, очень отвязанной и от математики, и от прикладного программирования) и в курсах алгоритмов.В общем-то, теорию графов могут вообще не изучать, так же как на другой специальности могут не учить численные методы решения уравнений матфизики. Это не делает, кстати, ни тот, ни другой курс отвязанным от математики.
На самом деле, английский термин — spanning trees — освежил память, но, в целом, никогда нельзя расчитывать, что человек будет знать какой-то конкретный термин или алгоритм. Это как на собеседовании: если дать задачу на что-то конкретное, кандидат может завалить собеседование просто потому что проспал одну лекцию или конкретно этой темы не было в его учебнике, а вот общее знание предмета вполне можно проверить. Соответсвенно, демонстрировать сильные стороны теории или области, на мой взгляд, тоже лучше на примере более общих задач. (Хотя я могу придираться :))
Ну тут согласен. Примеры действительно были не лучшими. Тут как: если знаешь теорию, но термин забыл — он гуглится мгновенно по всплывшему описанию. Не знаешь — будешь долго пытаться понять, а чего ж от тебя надо. Другое дело, мне сложно представить, как можно забыть остовное дерево :) Я ж именно с этого удивился.
Не поверите, но термин «остовное дерево» (вот именно русский вариант) я действительно слышу если не первый, то от силы второй-третий раз. В университете теория графов шла между делом в полугодовом курсе алгоритмов, а самыми сложными задачами были обход дерева и алгоритм Дейкстры (да что уж говорить, за 6 лет обучения я ни в одном курсе не услышал про Big O). Термин spanning trees я знаю уже по дополнительной литературе. При этом последние несколько лет работаю с околоматематическими областями, в т.ч. и с графами. Так что опыт — это очень субъективная штука ;)
Если у Вас был мат. ан., то про О большое (big O) вы не могли не слышать. А уж в алгоритмах — тем более.
Вполне может быть. 4 семестра только одного матана и ничего про большое О.
Конкретно мат. анализа, насколько я помню, у нас тоже не было: было 4 семестра «высшей математики», плюс теория вероятностей и пара специализированных областей типа теории массового обслуживния. И да, абсолютно серьёзно, за 6 лет на одном из лучших факультетов(тм) одного из лучших университетов(тм) страны ни разу не прозвучало словосочетание «большое О». К нам потом приходили на собеседование люди с 7+ годами стажа и замашками на тим. лида, и пытались на пальцах объяснить, почему обращение к n-ому элементу связного списка медленней, чем к n-ому элементу массива — вроде и глаза умные, и смысл понимают, а терминологии для нормального объяснения не хватает.
Справедливости ради, те, кто приходил из соседнего университета, вполне неплохо оперировали понятием сложности алгоритма и даже пару раз вспоминали NP-полные задачи.
Справедливости ради, те, кто приходил из соседнего университета, вполне неплохо оперировали понятием сложности алгоритма и даже пару раз вспоминали NP-полные задачи.
Упоминаемый факультет выпускает программистов?
Я не представляю, как можно давать алгоритмы без сравнения их эффективности. Без O() сложно объяснить, что такое сложность алгоритма, а это уже должно быть в базе любого курса по алгоритмам.
Я учился на факультете не выпускающем программистов: у нас не было дискретной математики, алгоритмов, теории компиляторов и многих других полезных разделов. Благо некоторая база была приобретена ещё в школьное время. Ну и саморазвитие никто не отменял.
Я не представляю, как можно давать алгоритмы без сравнения их эффективности. Без O() сложно объяснить, что такое сложность алгоритма, а это уже должно быть в базе любого курса по алгоритмам.
Я учился на факультете не выпускающем программистов: у нас не было дискретной математики, алгоритмов, теории компиляторов и многих других полезных разделов. Благо некоторая база была приобретена ещё в школьное время. Ну и саморазвитие никто не отменял.
Да, упомянутый факультет и особенно моя тогдашняя кафедра выпускает именно программистов. Причём выпускники факультета катируются на рынке довольно высоко, и, впринципе, не могу сказать, что безосновательно. Другое дело, что упор делался на изучения инструментария (языки, сетевые протоколы, базы данных), парадигмы (структурное, объектно-ориентированное, функциональное, логическое программирование) и процесс разработки (модели и методологии, надёжность программ, всякие UML-и и прочие диаграммы). А алгоритмы объяснялись на пальцах, мол, вот здесь понадобится столько проходов, а вот здесь вот столько, поэтому вот это быстрее.
В целом, это долгий разговор, и я вполне понимаю ваше негодование. Просто хотелось показать, что ситуации бывают разные, и у людей может быть очень разный бекграунд.
В целом, это долгий разговор, и я вполне понимаю ваше негодование. Просто хотелось показать, что ситуации бывают разные, и у людей может быть очень разный бекграунд.
Очень просто — «время выполнения этого алгоритма пропорционально числу элементов, а этого — логарифму от этого числа».
Задача 1
Prelude Data.List> map (concat.map show) $ permutations $ [1 | _<-[0..5] ] ++ [0 | _<-[0..23] ]
Задача 2
Если существует хоть одна точка, которая окружена замкнутой стеной, то данный лабиринт противоречит условиям задачи.
Задача 3
Уели =(
Интересно, сколько лет печатать будет:
def if6ones(string):
res = 0
for n in string:
if n == '1':
res += 1
if res > 6:
return False
if res == 6:
return True
else:
return False
i = 0
while i < 2**30:
bi = bin(i)
if if6ones(bi):
xx = bi[2:]+'0'*(32-len(bi))
print '(%d)'%len(xx), xx
i += 1
У вас очень плохие примеры.
Задача 1
Никакого знания математики не требуется. Генерация таких сочетаний — чисто прикладная простая задача. Если бы нужно было бы посчитать — окей, комбинаторика.
Задача 2
Сама постановка задачи несколько глупа. Если у нас цель обойти лабиринт, то это решается банальным DFS/BFS-обходом (не математика, просто примитивный алгоритм). Если же цель продемонстрировать обход по правилу левой руки (в принципе, это даже наверное красиво, ибо более медленно), то я вижу аж два решения:
1) Перегенерировать лабиринт до тех пор, пока не найдется не зацикливающийся. В крайнем случае сгенерировать множество лабиринтов сразу и задать их в compile-time — дубликаты среди 1000 лабиринтов все равно никто не найдет. Знания математики не нужно.
2) Обойти нормальным алгоритмом (это гуглится легко) из какой-то определенной точки, слева по трассе обхода залить стенками (не слева от точки трассы, а слева от робота, иначе робот может сам себе залить дорогу; да и до точки выхода добраться будет невозможно). Потом запускать алгоритм обхода по левой руке из той же точки. Если хотим, чтобы точки старта не совпадали (правда в такой постановке задачи — не знаю зачем), то пускаем нормальный алгоритм обхода из всех доступных нам точек. Внимание: в этом решении может быть нарушено условие полной связности лабиринта, но добраться до точки выхода всегда будет можно. Алгоритмическая сложность в худшем случае O(n^2), среднее — O(n), где n — количество клеток в лабиринте. Знания математики не нужно, нужны максимум базовые понятия теории графов, настолько базовые, что она даже в концепцию более-менее средней математики вообще не вписывается.
3) Еще какое-то. Больше в голову ничего не лезет, кроме веселых алгоритмов с экспоненциальной сложностью. Возможно есть красивое решение с хорошей асимптотикой, но вообще такого представить не могу
Задание 3
Никакого знания математики не требуется. Пишется готовый (пускай и медленный, даже очень медленный) код под эту задачу. Например (http://ideone.com/1Oeqji):
А потом забиваем получившиеся значения на сайт oeis.org/ и находим, что это числа Каталана и формулу их быстрого вычисления.
Вообще, все ваши задачи из разряда алгоритмических. Алгоритмика — это отдельная область, практически мало связанная с реальной математикой. Большинство прикладных программистов с такими алгоритмами вообще не столкнется, столкнется только с теми, которые уже реализованы в чьих-то библиотеках или в стандартном фреймворке (пример — хэш таблицы). Из прикладников с алгоритмами реально могут столкнуться только люди работающие с графикой/физикой (графический софт и игры).
А еще хочу привести цитату daspisch из топика «Необычный способ генерации лабиринтов» (http://habrahabr.ru/post/181265/#comment_6296855)
Задача 1
Никакого знания математики не требуется. Генерация таких сочетаний — чисто прикладная простая задача. Если бы нужно было бы посчитать — окей, комбинаторика.
Задача 2
Сама постановка задачи несколько глупа. Если у нас цель обойти лабиринт, то это решается банальным DFS/BFS-обходом (не математика, просто примитивный алгоритм). Если же цель продемонстрировать обход по правилу левой руки (в принципе, это даже наверное красиво, ибо более медленно), то я вижу аж два решения:
1) Перегенерировать лабиринт до тех пор, пока не найдется не зацикливающийся. В крайнем случае сгенерировать множество лабиринтов сразу и задать их в compile-time — дубликаты среди 1000 лабиринтов все равно никто не найдет. Знания математики не нужно.
2) Обойти нормальным алгоритмом (это гуглится легко) из какой-то определенной точки, слева по трассе обхода залить стенками (не слева от точки трассы, а слева от робота, иначе робот может сам себе залить дорогу; да и до точки выхода добраться будет невозможно). Потом запускать алгоритм обхода по левой руке из той же точки. Если хотим, чтобы точки старта не совпадали (правда в такой постановке задачи — не знаю зачем), то пускаем нормальный алгоритм обхода из всех доступных нам точек. Внимание: в этом решении может быть нарушено условие полной связности лабиринта, но добраться до точки выхода всегда будет можно. Алгоритмическая сложность в худшем случае O(n^2), среднее — O(n), где n — количество клеток в лабиринте. Знания математики не нужно, нужны максимум базовые понятия теории графов, настолько базовые, что она даже в концепцию более-менее средней математики вообще не вписывается.
3) Еще какое-то. Больше в голову ничего не лезет, кроме веселых алгоритмов с экспоненциальной сложностью. Возможно есть красивое решение с хорошей асимптотикой, но вообще такого представить не могу
Задание 3
Никакого знания математики не требуется. Пишется готовый (пускай и медленный, даже очень медленный) код под эту задачу. Например (http://ideone.com/1Oeqji):
Код на C#
using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
public class Test
{
enum Player
{
None = -1,
FirstPlayer = 0,
SecondPlayer = 1
};
public static bool CheckWin(int n, IEnumerable<int> coinSequence)
{
if (coinSequence == null || coinSequence.Count() != 2 * n)
throw new ArgumentException("coinSequence size must be equal 2*n");
var forcePlayer = Player.None;
var currentPlayer = Player.None;
var playerCoins = new int[2] { n, 0 };
var playerMoved = new int[2] { 0, 0 };
var coinsOnDesk = 0;
foreach (var coin in coinSequence)
{
currentPlayer = (Player)(coin == 1 ? 0 : 1);
// force player
{
if (playerMoved[(int)currentPlayer] > n)
{
switch (currentPlayer)
{
case Player.FirstPlayer: forcePlayer = Player.SecondPlayer; break;
case Player.SecondPlayer: forcePlayer = Player.FirstPlayer; break;
default: throw new Exception("Alg fail"); break;
}
}
if (forcePlayer != Player.None)
currentPlayer = forcePlayer;
}
switch (currentPlayer)
{
case Player.FirstPlayer:
if (playerCoins[0] != 0)
{
playerCoins[0]--;
coinsOnDesk++;
}
break;
case Player.SecondPlayer:
if (coinsOnDesk != 0)
{
coinsOnDesk--;
playerCoins[1]++;
}
break;
default: throw new Exception("Alg fail"); break;
}
playerMoved[(int)currentPlayer]++;
}
return (playerCoins[1] == n);
}
public static IEnumerable<IEnumerable<int>> GenerateCoins(int n)
{
if (n == 1)
{
yield return new int[] { 1 };
yield return new int[] { 2 };
yield break;
}
var smallerVariants = GenerateCoins(n - 1);
foreach (var smallerVariant in smallerVariants)
{
yield return smallerVariant.Concat(new int[] { 1 });
yield return smallerVariant.Concat(new int[] { 2 });
}
yield break;
}
public static int CountWinsSequences(int n)
{
return GenerateCoins(2 * n).Count(coinSequence => CheckWin(n, coinSequence));
}
public static void Main()
{
for (int n = 1; n <= 5; n++)
{
Console.WriteLine("n = {0}, wins = {1}", n, CountWinsSequences(n));
}
}
}
А потом забиваем получившиеся значения на сайт oeis.org/ и находим, что это числа Каталана и формулу их быстрого вычисления.
Вообще, все ваши задачи из разряда алгоритмических. Алгоритмика — это отдельная область, практически мало связанная с реальной математикой. Большинство прикладных программистов с такими алгоритмами вообще не столкнется, столкнется только с теми, которые уже реализованы в чьих-то библиотеках или в стандартном фреймворке (пример — хэш таблицы). Из прикладников с алгоритмами реально могут столкнуться только люди работающие с графикой/физикой (графический софт и игры).
А еще хочу привести цитату daspisch из топика «Необычный способ генерации лабиринтов» (http://habrahabr.ru/post/181265/#comment_6296855)
Ответ: Да, в частных случаях. В других частных случаях программисту нужна биохимия, экономика и куча других знаний необходимых для конкретного проекта.
Реально достали уже с этим «нужналипрограммистуматематика».
По поводу второй задачи в частности и оторванности от реальности в целом. Задача была написана по поводу реального скрин-сейвера из Windows 2000, который как раз демонстрировал об ход по правилу левой руки. И тут у разработчиков было 2 варианта — сразу генерировать лабиринт без циклов или генерировать любой и уничтожать циклы. Обе задачи математические.
«Перегенерировать лабиринт до тех пор, пока не найдется не зацикливающийся» — вы хотя бы примерно представляете вероятность при случайной генерации связанного графа получить дерево?
«В крайнем случае сгенерировать множество лабиринтов сразу» — и добавить к 5 килобайтам кода пару метров описаний лабиринтов. Если позволять себе такие выкрутасы в операционке, можно и Висту создать.
«Перегенерировать лабиринт до тех пор, пока не найдется не зацикливающийся» — вы хотя бы примерно представляете вероятность при случайной генерации связанного графа получить дерево?
«В крайнем случае сгенерировать множество лабиринтов сразу» — и добавить к 5 килобайтам кода пару метров описаний лабиринтов. Если позволять себе такие выкрутасы в операционке, можно и Висту создать.
Для начала, это довольно специфическая задача — обход лабиринта по правилу левой руки. И естественно из нее вытекает более специфическая задача — генерация лабиринта, обходимого по правилу левой руки. Т.е. задача не просто выполнить обход (или красивый/долгий обход) лабиринта, а ерунда высосанная из пальца. Я даже предполагаю почему и кто её высосал. Не какой-нибудь product manager, не дяденька, котоорый, делал постановку задачи, а программист. Ибо это красивая задача, стоящая быть решенной. Just for fun, просто для поддержания мозгов в порядке, а не совсем для того чтобы написать программный продукт.
Да, представляю, сколько это будет времени тратить и сколько весить.
Да, представляю, сколько это будет времени тратить и сколько весить.
Мда. Ваш пример решения второй задачи отлично показывает, сколько сомнительных решений можно придумать, если не знать математики.
Примеры, по-моему, неудачные. Для решения знаний математики не требуется, разве что решения могут быть менее эффективны, чем использующие «тайные знания».
Дело в том, что вы взяли математику и подогнали под нее условия задачи. В жизни все наоборот.
Как уже сказано многими выше — идея хорошая, реализация плохая, но комментарии к вечеру, пожалуй будут ломиться от правильных примеров.
Как уже сказано многими выше — идея хорошая, реализация плохая, но комментарии к вечеру, пожалуй будут ломиться от правильных примеров.
А вы уверены что вторая задача вообще имеет место быть (касательно лабиринта из заставки — в нём все стены тоже связны если не считать вход и выход за разрывы).?
Если обходящий зацикливается внутри лабиринта, значит существует сплошная стенка без разрывов, идущая по контуру этого пути. Следовательно в лабиринте есть две точки для которых пройти от одной до другой не представляется возможным, а значит лабиринт не связный
Более того — для решения этой задачи достаточно начать обходить лабиринт, и при прохождении уже посещённой стенки (условно говоря идущий по стенке рисует на стене линию) — начинаем отходить назад(стирая линию) и при первой же возможности строим стенку, перекрывающую проход так, чтобы при обходе этой стенки мы попадали на не обойдённую стену. После этого можно продолжать проверку. Тогда связность лабиринта гарантируется т.к. он может попасть в любую из точек своего пути уже пройденным путём, а остальной лабиринт уже связный по условию задачи.
Если обходящий зацикливается внутри лабиринта, значит существует сплошная стенка без разрывов, идущая по контуру этого пути. Следовательно в лабиринте есть две точки для которых пройти от одной до другой не представляется возможным, а значит лабиринт не связный
Более того — для решения этой задачи достаточно начать обходить лабиринт, и при прохождении уже посещённой стенки (условно говоря идущий по стенке рисует на стене линию) — начинаем отходить назад(стирая линию) и при первой же возможности строим стенку, перекрывающую проход так, чтобы при обходе этой стенки мы попадали на не обойдённую стену. После этого можно продолжать проверку. Тогда связность лабиринта гарантируется т.к. он может попасть в любую из точек своего пути уже пройденным путём, а остальной лабиринт уже связный по условию задачи.
UFO just landed and posted this here
Разрабатываю учетную систему. Требования знаний математики стремятся к нулю. Знания бизнес процесса и реалий стремтся к основной литературе.
Разрабатываю графические эффекты, примочки и дугие классные штуки для android — знания математики стремятся к большому чтению литературы, знания реалий стремятся к нулю.
…
Разрабываю что-то. Требования знаний для этого нужны, для другого не нужны.
В результате, я не знаю математику (основы, да и то не все), не знаю все реалий всех бизнес процессов. На протяжении любой разработки применение каких-то сложных и интересных алгоритмов присутствует, но не постоянно и не надо для этого держать всё это в голове.
Разрабатываю графические эффекты, примочки и дугие классные штуки для android — знания математики стремятся к большому чтению литературы, знания реалий стремятся к нулю.
…
Разрабываю что-то. Требования знаний для этого нужны, для другого не нужны.
В результате, я не знаю математику (основы, да и то не все), не знаю все реалий всех бизнес процессов. На протяжении любой разработки применение каких-то сложных и интересных алгоритмов присутствует, но не постоянно и не надо для этого держать всё это в голове.
Примерно так же. Более того. в тех РЕДЧАЙШИХ случаях, где математика все таки понадобилась (например уперлись в производительность), разораться в уже конкретной теме можно крайне быстро. Так что не вижу проблем. Программист не должен знать математику. Но программист должен уметь быстро разобраться и в ней в том числе. Ну или в крайнем проконсультироваться у математика :)
Программист просто должен уметь быстро разобраться в любой предметной области. Другое дело, что частенько она описывается на языке математики и некоторые знания «внутренней кухни» могут оказаться полезны. Даже такие простые как, например, определение синуса, что это не просто функция в виде черного ящика, а имеющая определенный геометрический смысл или разлагающаяся в определенный ряд.
Очень многое может оказаться полезным. Все знать не получится, а область применение программного обеспечения очень широкая.
Угадать что понадобится, а что нет, по-моему, сложно. Если не искать целенаправленно.
Вот как то так. Поэтому абсолютно не переживаю, что я там пропустил, а что нет. Что надо — нагоню.
Удивительно, что вас кто-то минусанул. Имхо, для программиста главное получить навык быстрого получения необходимого минимума знаний. Я не знаю как нынче дают вышку в элитных вузах на айтишных специальностях, но сомневаюсь, что дают абсолютно всё, что может потребоваться в принципе. Хотя бы потому что вэто всё увеличивается с каждым днём.
Тоже в свое время (сейчас уже заканчиваю университет) не учил математику:( Сейчас очень жалею об этом. А тем более что я собираюсь идти в аспирантуру связанную с математическим моделированием и разного рода программированием этого всего дела… придется заново учиться, но я буду только рад, если посоветуете с чего начать образовываться в сфере непрерывной математики и дискретки.
Если на работе только с такими задачами работать и прийдется, на следующий день написал бы заявление. Посчитал что куда-то не туда я попал.
А автор не замечает такой очевидной истины, что если люди не знают, значит оно им не нужно? Даже я уверен что многие и хотели бы математику хорошо знать, но в программе образования (школа, институт) таких тем: генерация сочетаний, остовное дерево, числа Каталана я не встречал.
Знание математики определяет потребность предлодений. Предлодения на рыкке труда не требуют знания математики. Не нужно путать понятия, программирование это программирование, а математика это математика. Знание математики конечно будет наруку очень немногому кругу работадателей, но это из той серии когда ищют сильнейшего скажем java программиста с глубоким знанием CSS 3.
Автор почему-то не принял во внимание, что программисты и так себя нормально чувствуют и без математики. Поэтому пост расцениваю как «строки комплекса не признанного обществои знатока математики». Так что не нужно нам рассказывать о наших проблемах в образовании, пишите в МОН. Автор первого комментария уже куписля на это. Вы еще напишите пост про структуры данных, кватернионы, тест на знание квантовой физики и он вообще повесится.
Всему свое время я считаю.
А автор не замечает такой очевидной истины, что если люди не знают, значит оно им не нужно? Даже я уверен что многие и хотели бы математику хорошо знать, но в программе образования (школа, институт) таких тем: генерация сочетаний, остовное дерево, числа Каталана я не встречал.
Знание математики определяет потребность предлодений. Предлодения на рыкке труда не требуют знания математики. Не нужно путать понятия, программирование это программирование, а математика это математика. Знание математики конечно будет наруку очень немногому кругу работадателей, но это из той серии когда ищют сильнейшего скажем java программиста с глубоким знанием CSS 3.
Автор почему-то не принял во внимание, что программисты и так себя нормально чувствуют и без математики. Поэтому пост расцениваю как «строки комплекса не признанного обществои знатока математики». Так что не нужно нам рассказывать о наших проблемах в образовании, пишите в МОН. Автор первого комментария уже куписля на это. Вы еще напишите пост про структуры данных, кватернионы, тест на знание квантовой физики и он вообще повесится.
Всему свое время я считаю.
Автору следует умерить пыл в защиту математики. Если кто-то считает, что она для его сферы программирования не нужна, то пусть этот несчастный и дальше живёт с данной мыслью. Каджый уважающий себя профессионал, сталкивающийся не только с программированием, но и в принципе с интеллектуальной деятельностью технического характера, понимает ценность математики (и не только её). Да, возможно прикладная часть спиноров для рнр-кодера сомнительна, однако тот один случай в жизни, когда они пригодятся, может принести конкурентное преимущество перед остальным ремесленническим миром и радикально повлиять на успех.
Для сравнение: ходить в спортзал стоит не потому, что каждый день вы мутузите гопников в переулках, а потому что ваше тело находится в тонусе, и в тот один единственный раз, когда надо будет в драке спасти свою жизнь, вы это сможете сделать, а другой — нет.
Для сравнение: ходить в спортзал стоит не потому, что каждый день вы мутузите гопников в переулках, а потому что ваше тело находится в тонусе, и в тот один единственный раз, когда надо будет в драке спасти свою жизнь, вы это сможете сделать, а другой — нет.
Ну вот случился у меня сейчас тот единственный раз в этом топике, а не вспомнил ничего из того, что не просто «сдал и забыл», а активно использовал в работе когда-то. Аналогия со спортзалом хорошая — нужно не просто знать математику, чтобы когда-то внезапно её использовать, а постоянно поддерживать себя в форме, придумывая себе тупые абстрактные задачи, чтобы столкнувшись с реальной увидеть что в ней нужна математика и какая именно.
Как прикажете понимать Ваш пример? Изучать математику стоит не потому, что каждый день вы решаете математические задачи, а потому, что ваш интеллект находится в тонусе, и в тот единственный раз, когда надо будет на работе спасти ваш проект, вы это сможете сделать, а другой — нет?! Довольно нерациональное использование собственных ресурсов, не находите? И, разве, выполняемая Вами профессиональная деятельность не поддерживает Ваш интеллект в тонусе?!
Я понял по другому — нужно регулярно и часто решать разнообразные математические задачи (из, грубо говоря, вузовского задачника), чтобы когда её аналог попадётся в реале, то быстро решить, хотя бы за счет более целенаправленного гугления.
Есть люди. занимающиеся в спортзале и держащие себя в тонусе. А есть неспортивные. И те и те могут быть успешными, но первые почему-то здоровее.
Есть программисты, тренирующие свой мозг математикой и читающие специализированную «прессу» фундаментального характера, а есть простые работяги, которые полагаются на гугление. И там и там достаточно успешных специалистов, но, опять же, среди топовых по зарплате специалистов первых поболе.
Вам до сих пор не понятна аналогия?
Есть программисты, тренирующие свой мозг математикой и читающие специализированную «прессу» фундаментального характера, а есть простые работяги, которые полагаются на гугление. И там и там достаточно успешных специалистов, но, опять же, среди топовых по зарплате специалистов первых поболе.
Вам до сих пор не понятна аналогия?
Знание математики не является ни необходимым условием ни достаточным. Как и знание английского языка, например, веб дизайна, UX и прочих непрофильных областей. Это все расширяет кругозор, повышает «конкурентность», но не делает программиста программистом.
Задачи дико синтетические.
UFO just landed and posted this here
А изучая программирование разве не изменяется мышление, логика и т. п.?
У вас видимо другие задачи. У меня >99% кода это архитектура кода, описание игровой или бизнес логики. Математика за 9 лет работы над очень разными проектами нужна была ровно 1 раз. Для бильярда. Нужные пробелы были восстановлены за 1 день.
Вот точно такие задачи задают на собеседовании, и точно так же наивно думают что выделяют из толпы специалиста. 90 процентов работы программиста рутина, а если есть архитектура (да такое бывает) то вообще никаких логических задач не требуется в разработке. На работе нужны специалисты, которые способны работать на разных уровнях абстракции системы, понимать ее и моддифицировать.
Я всего лишь пытался доказать, что отсутствие знаний заставит вас изобретать велосипед, вместо того, чтобы найти готовый алгоритм или ответ.
Сам придерживаюсь следующего жизненного кредо:
«In order to ask a question you must already know most of the answer» /Robert Sheckley/
«Для того, что-бы задать вопрос, вам следует знать большую часть ответа на него» /Роберт Шекли, «Верный вопрос»/
Однако порой, отсутствие знаний позволяет взяться за проблему и решить её, в то время как наличие знаний мешает даже рассмотреть задачу.
Весь тред показывает, что программисту не нужна математика, а нужен сборник рецептов по разным темам. Бывают рецепты лежащие в стандартной библиотеке (quicksort), лежащие на поверхности для человека с вышкой (свертка -> FFT), бывают достаточно сложные (например, МНК по ортогональным полиномам вместо степенных намного устойчивее), но это все — рецепты. От программиста никто не требует доказательств, поэтому половина страниц в математических учебниках пропускается. И математика, как таковая, программисту не нужна, нужен набор вавилонских табличек с рецептами, а также умение эти рецепты кодировать. Являлись ли вавилонские таблички с рецептами «математикой»? Не думаю.
Вопрос студентов обычно бывает в том, требуется ли программисту то, что принято называть «математикой» в советских вузах, то есть убогое натаскивание на символьные преобразования. Например, свертки мы проходили, и нам даже объясняли, что вместо свертку можно считать через преобразование Лапласа. Естественно никто этот факт не запомнил (не говоря уже о нетривиальном переходе к дискретным conv(a,b)=ifft(fft(a)*fft(b))), потому что основная цель обучения и задача на экзамене были посчитать какой-то хитрый интеграл свертки вручную. Такая математика никому не нужна, студенты воют и делают правильный вывод по этому поводу.
Кнутовские задачи вида «найди форумулу количества чего-нибудь из комбинаторики» (задача 3 топика) тоже не нужны
Вопрос студентов обычно бывает в том, требуется ли программисту то, что принято называть «математикой» в советских вузах, то есть убогое натаскивание на символьные преобразования. Например, свертки мы проходили, и нам даже объясняли, что вместо свертку можно считать через преобразование Лапласа. Естественно никто этот факт не запомнил (не говоря уже о нетривиальном переходе к дискретным conv(a,b)=ifft(fft(a)*fft(b))), потому что основная цель обучения и задача на экзамене были посчитать какой-то хитрый интеграл свертки вручную. Такая математика никому не нужна, студенты воют и делают правильный вывод по этому поводу.
Кнутовские задачи вида «найди форумулу количества чего-нибудь из комбинаторики» (задача 3 топика) тоже не нужны
Нужна не только и не столько математика, сколько строгое, логическое, четкое мышление, которое в условиях имеющейся системы образования формируется только в процессе изучения математики.
Очень язвительная и высокомерная статья. Автор, Вы вообще понимаете, что кол-во знаний, наличие которых избавит от изобретения велосипеда и улучшит качество работы программиста, мягко говоря, не ограничивается одной математикой?!
Всё на свете, увы, не освоить, но математика является базой для всех наук, по большому счёту.
С этим я не спорю, но в условиях ограниченных возможностей Вы, скорей всего, пожертвуете математикой в пользу конкретных (требуемых для решения задачи) наук, осваивая математику лишь вторично. Поэтому утверждать, что математика лучше других (конкретных) наук помогает в поиске готовых решение, на мой взгляд, безосновательно и нелепо.
Я хоть и возражаю, что математика (в рамках больших школьного курса) необходима программисту, но она помогает быстрее понять готовое решение, если оно выражено в понятных математических терминах. Банальные координаты и размер блока на экране выражаются в математических терминах, а если нужно круг нарисовать, то без математики никуда (если нет либы готовой). Просто так исторически сложилось, что многие дисциплины предпочитают выражать свои законы через математику. Когда через банальную арифметику (типа бухгалтерии). когда через такое что в вузах айтишникам уж точно не преподают (типа физики многомерных пространств в условиях неевклидовой геометрии).
Я хотел вложить в свои слова следующий смысл (но получилось, видимо, опять слишком озлобленно): изучать математику может быть проще через изучение других (менее абстрактных наук) наук, т.к. в отрыве от реальности математика может быть абсолютна непонятна. Т.е. изучать соответствующие математические абстракции лишь тогда, когда чувствуется потребность в систематизации накопившихся знаний. Это исключительно моё личное мнение (как человека, которому математика в чистом виде не даётся).
В такой трактовке согласен — так может быть эффективнее, если есть готовое решение вашей задачи, выраженное в виде формулы. Скажем, путь равен интегралу по времени от скорости и вам нужно найти путь при известной скорости. Почитаете про интегралы и найдете. Но вот если скорость надо будет найти и формулы, что она равна производной от пути вы не найдете, то что делать? Информации о том что дифференцирование есть операция обратной интегрированию может на глаза и не попасться при изучении интегралов.
но математика является базой для всех наук, по большому счёту.
Пожалуй, я всё же попробую возразить. Если математика является базой для всех других наук, то никакая другая наука не может существовать без математики. Но ведь это не так?! Математика может использоваться в других науках в качестве языка формализации полученных знаний, но можно ли утверждать, что она является их основой (базой) и, как следствие, другие науки являются исключительно её продолжением (дочерними науками)?
> Но ведь это не так?!
Да именно так. Другие науки не являются дочерними по отношению к ней, но без нее они не могу существовать.
Да именно так. Другие науки не являются дочерними по отношению к ней, но без нее они не могу существовать.
Я правильно понимаю, что такое утверждение основано на том определении математики, в котором присутствуют понятия, наличие которых в соответствующем определении науки (используемом в паре с таким определением математики) является обязательным (без которого к явлению нельзя будет применить термин «наука»).
Т.е. взяв, например, за определение математики «наука о структурах, порядке и отношениях, которая исторически сложилась на основе операций подсчёта, измерения и описания форм реальных объектов» (определение из Википедии со ссылкой на энциклопедию Британника) взять за определение науки такое определение, где выделение порядка и отношений между объектами считается неотъемлемой частью.
Кстати, в той же Википедии сказано: «Математика (от др.-греч. μάθημα — изучение, наука)». Занятно получается.
Т.е. взяв, например, за определение математики «наука о структурах, порядке и отношениях, которая исторически сложилась на основе операций подсчёта, измерения и описания форм реальных объектов» (определение из Википедии со ссылкой на энциклопедию Британника) взять за определение науки такое определение, где выделение порядка и отношений между объектами считается неотъемлемой частью.
Кстати, в той же Википедии сказано: «Математика (от др.-греч. μάθημα — изучение, наука)». Занятно получается.
Собственно да. Что за наука, которая не описывает порядок и отношения между своими объектами? Дали определения объектам, а дальше? Даже сравнение двух объектов (равны они или нет по каким-то критериям) уже требует математики. Допустим сравнение не требуют, можно обойтись терминами типа «такой же». Но вот как выразить какой не такой же без математики, хотя бы без больше и меньше?
Видимо в этом смысле математика и есть мать всех наук, что она появилась первой просто как наука, а уж затем от нее начали отпочковываться более прикладные дисциплины. Но отношения наследования тут не как в ООП, что наследники включают в себя все свойства родителя.
Видимо в этом смысле математика и есть мать всех наук, что она появилась первой просто как наука, а уж затем от нее начали отпочковываться более прикладные дисциплины. Но отношения наследования тут не как в ООП, что наследники включают в себя все свойства родителя.
Вспомнил — 20+ лет назад я поступал на специальность «прикладная математика» и очень хотелось по ней работать. писать программы оперирующие «тензорами десятого порядка». но когда поступить смог лишь на «информационно-измерительные системы» (не выспался перед физикой). то решив. что по этой специальности я ни дня не проработаю. к математике у меня стал чисто спортивный интерес. Аналогичный институтской физкультуре: пока заставляют — вроде прикольно. а по собственному желанию — на фиг-на фиг.
Прикольно, я и без гугла все решил, наверное чему-то научили на мехмате.
Но это первый раз за все время, когда мне понадобилась математика, эти задачки к жизни обычного программиста отношения не имеют, и смею предположить, именно об этом шла речь во время спора насчет ЕГЭ/математики
Но это первый раз за все время, когда мне понадобилась математика, эти задачки к жизни обычного программиста отношения не имеют, и смею предположить, именно об этом шла речь во время спора насчет ЕГЭ/математики
О да. Тоскую, глядя смущенно вслед уходящим знаниям, которые когда-то имел… Их уже не вернуть.
Всё же думаю, если нам приспичит, то мы их вернем быстрее, чем получат те, у кого их не было никогда.
Я первую задачу вообще решил вот так — скажите я нормален?
Я искренне щитаю что программисту нужна математика — но вместо математического решения я выдавил из своих мозгов это ;(
ideone.com/8nDLuA
Я искренне щитаю что программисту нужна математика — но вместо математического решения я выдавил из своих мозгов это ;(
ideone.com/8nDLuA
ideone.com/PojYKf — забыл что 30 дней (
Да, нормален.
Я увидел тут понимание двоичной системы исчисления, дискретную математику. Думаете если бы вы этого всего не знали, то-же самое бы написали?
Простое и очевидное решение. Но не оптимальное.
Я увидел тут понимание двоичной системы исчисления, дискретную математику. Думаете если бы вы этого всего не знали, то-же самое бы написали?
Простое и очевидное решение. Но не оптимальное.
Я скорее опирался на свою техническую компетентность, чем на математический аппарат — мне это и не нравится.
Ну да, куда программисту без математики, если инкремент счетчика цикла математическая операция :) А если бы вместо 1073741824 было бы 1<<30 (как оно и должно быть по идее) вы бы меньше математики увидели или больше?
Я увидел математику в преобразовании в двоичную систему исчисления. Математика не сложная, но все-же математика.
Нормальный перебор. Сам я выдавил
За пару минут все варианты перебираются. Да и очень наглядно выглядит кстати )
program Project1;
{$APPTYPE CONSOLE}
uses
SysUtils;
procedure f(s: string; k,n: integer);
var i: integer;
begin
if k=0 then begin
write(s);
for i:=1 to n do write('0');
writeln;
end
else if k=n then begin
write(s);
for i:=1 to n do write('1');
writeln;
end
else begin
f(s+'0',k,n-1);
f(s+'1',k-1,n-1);
end;
end;
begin
f('',6,30);
end.
За пару минут все варианты перебираются. Да и очень наглядно выглядит кстати )
Я просто оставлю здесь свой любимый ответ от Эрика Липперта на этот вечный вопрос: «нужна ли математика программисту?»
Sign up to leave a comment.
Три задачи для программистов, которым не нужна математика