Comments 43
Самые интересные статьи прилетают в мою ленту как правило из песочницы.
А по теме — жаль, что я в своё время не уделял должного внимания дискретной математике в университете.
А по теме — жаль, что я в своё время не уделял должного внимания дискретной математике в университете.
Немного оффтопика:
>Хорошо известные вездесущие числа Фибоначчи проще всего определяются рекурсивно
Сложно представить более неправильный способ. Во всех случаях нужно максимально избегать рекурсии, заменяя на линейный алгоритм.
>Хорошо известные вездесущие числа Фибоначчи проще всего определяются рекурсивно
Сложно представить более неправильный способ. Во всех случаях нужно максимально избегать рекурсии, заменяя на линейный алгоритм.
В чем разница между математическим определением и алгоритмом вычисления представляете?
В общем случае, линейный алгоритм может быть и рекурсивным – одно другое не исключает. Например, depth-first search.
UFO just landed and posted this here
«Итерация свойственна человеку, рекурсия божественна». Л. Питер Дойч
В некоторых случаях рекурсия дает очень красивое и элегантное решение/определение.
В некоторых случаях рекурсия дает очень красивое и элегантное решение/определение.
>В некоторых случаях рекурсия дает очень красивое и элегантное решение/определение.
Согласен, погорячился, в некоторых случаях да, но не в случае чисел Фибоначчи. То что устоявшееся определение данной последовательности в программировании через рекурсию, не означает что это правильно, поскольку дает нам экспоненциальных рост сложности алгоритма. Нетрудно посчитать сложность рекурсивной алгоритма при n=100, при этом если получить тоже число с помощью элементарного цикла от 2 до n, мы получим сложность функции О(n), при этом определение сложнее не будет.
Согласен, погорячился, в некоторых случаях да, но не в случае чисел Фибоначчи. То что устоявшееся определение данной последовательности в программировании через рекурсию, не означает что это правильно, поскольку дает нам экспоненциальных рост сложности алгоритма. Нетрудно посчитать сложность рекурсивной алгоритма при n=100, при этом если получить тоже число с помощью элементарного цикла от 2 до n, мы получим сложность функции О(n), при этом определение сложнее не будет.
Вам же уже сказали, что нужно отличать «Что такое числа Фибоначчи?» и «Как посчитать числа Фибоначчи?» И если вам не нравится текущее определение (а ведь и натуральные числа определяются рекурсивно, см. аксиомы Пеано), попробуйте дать своё.
Рекурсивное, однако весьма эффективное определение последовательности чисел Фибоначчи. Функция высшего порядка zipWith берет два списка и применяет к их элементам с одинаковыми указанную функцию (в данном случае — функцию сложения):
fibs = 1 : 1 : zipWith (+) fibs (tail fibs)
никогда не понимал заявлений о вездесущести чисел Фибоначчи и золотого сечения. фибоначчи — только филлотаксис, золотое сечение и вовсе миф.
Нам на первом курсе на Физтехе читал лекционный курс товарищ Стрыгин (я с РТ, но вроде он не только РТ читал). По ощущениям был сплав дикой тривиальщины и каких-то баек. Пару забавных методов и алгоритмов запомнилось, но, если честно, то по делу там почти ничего не было.
Надеюсь, что у вас получится значительно лучше!:)
Надеюсь, что у вас получится значительно лучше!:)
В моём универе дискретку, а также тервер вел примерно такого же типа препод. За лекцию он успевал рассказать очень мало, но настолько подробно, что становилось скучно. На практику времени практически не оставалось по этой причине, а также потому, что очень много времени тратилось на немногочисленные задачи из дз, которые тоже были жутко тривиальными.
Именно поэтому когда я увидел эту статью, сразу же записался дабы послушать адекватные лекции и порешать побольше разных задач. Очень хотелось бы увидеть аналогичный курс по терверу.
Именно поэтому когда я увидел эту статью, сразу же записался дабы послушать адекватные лекции и порешать побольше разных задач. Очень хотелось бы увидеть аналогичный курс по терверу.
А почему все думают что программистам нужна только дискретка? Попробуйте попрограммировать системы для биржевой торговли: тут вам и Ито и Маллиавэн и еще вагон всего.
Дмитрий, разве из статьи следует, что нужна только дискретка? Но она определённо важна – попробуйте попрограммировать те же системы для биржевой торговли, не зная дискретку.
Кстати, вводный курс по статистике уже идёт stepic.org/course/Основы-статистики-76/, а по матанализу скоро начинается – stepic.org/course/Введение-в-математический-анализ-95/.
Кстати, вводный курс по статистике уже идёт stepic.org/course/Основы-статистики-76/, а по матанализу скоро начинается – stepic.org/course/Введение-в-математический-анализ-95/.
Да, а, например, разработчикам 3D-шутеров нужен матан.
Каждый раздел математики может пригодиться для программирования некоторых задач. Но из всех разделов математики дискретка имеет наиболее широкое применение всякими программистами. Имхо.
Каждый раздел математики может пригодиться для программирования некоторых задач. Но из всех разделов математики дискретка имеет наиболее широкое применение всякими программистами. Имхо.
UFO just landed and posted this here
Не подскажете, каков процесс обучения на самой платформе? Не приходилось до сих пор принимать участия в онлайн курсах. Ряд видеолекций + регулярные задания? Задания проверяются, или делаются «для себя»?
Меня честно говоря во всей статье порадовал выбор картинки, она очень необычна и в то же время приятна — искусство со смесью математики и физики.
Не владею даже школьной математикой уровня физ-мат класса, но записался все равно, буду пытаться учить и понимать. Обещаю приложить максимум усилий, жаль отпуск не смогу взять на время обучения)
Я вот оказался ниасилятором. До сих пор на первом блоке, хотя открыт третий уже. К концу первого блока начал очень сильно буксовать: хорошо если получается одну задачу за день осилить. Мозги просто отказываются думать. Интересно, сколько задачи будут доступны для решения, а то хорошо, если к концу лета осилю :)
Что же, будем собратьями по «несчастью». Можем скооперироваться для прохождения, вдвоем все же легче, да и мотивация повышается.
Берите меня к себе:)
monah_tuk пока не ответил. Но уже больше одного и можно кооперироваться.
Я уже начал, можно организоваться с помощью слаки, либо любого другого канала коммуникации. Предупрежу, что времени для неподготовленного человека уходит порядочно. Хотя мне кажется, если думать совместно, то дело пойдет веселее.
В сторону… А что, в паскале уже можно присваивать оператором "=" без двоеточия? Я про пример с вложенными for.
Дискретные структуры: матан для айтишниковНедостаточно абсурда. Нужно так:
Дискретные структуры: матан для айтишников (на самом деле линейная алгебра твёрдого тела)
Плюсую курс.
Прослушал его лично от автора поста в качестве студента ФИВТ МФТИ.
Сначала думал, не понадобится.
А через год писал LCS через цепи в булеане.
Так что всем рекомендую)
Прослушал его лично от автора поста в качестве студента ФИВТ МФТИ.
Сначала думал, не понадобится.
А через год писал LCS через цепи в булеане.
Так что всем рекомендую)
какая из функций x^20 или 2^x растёт быстрее (чему равны производные функций)
Производные равны 20∙x^19 и 2^x∙ln(2) соответственно.
Пока я не вижу, как производные помогут ответить на вопрос (для x=10 у первой ф-ции производная больше, и что?)
Берем производную 20 раз и слева у нас оказывается константа, а справа — функция. Функция растет быстрее константы, хотя и к этому можно не прибегать, а взять производную в 21 раз. Тогда слева ноль, а справа — везде положительная функция. Вот и ответ.
Это вы подобрали принцип под мой конкретный пример, на другом примере он не сработает.
Сравните 2x и 22x
Сравните 2x и 22x
Отлично, логарифмируем по основанию 2 (очевидно, это не влияет на неравенство), после этого сравниваем х и 2^x. Дважды дифференцируем, получаем что 2^2^x > 2^x. ЧТД.
Можно доказать и иначе, 2^x = y, тогда y vs 2^y, дальше аналогичные вычисления и ответ.
Ну и чтобы 2 раза не вставать: как вы предлагаете оценивать рост функций без вычисления производных?
Можно доказать и иначе, 2^x = y, тогда y vs 2^y, дальше аналогичные вычисления и ответ.
Ну и чтобы 2 раза не вставать: как вы предлагаете оценивать рост функций без вычисления производных?
как вы предлагаете оценивать рост функций без вычисления производных?
Никак. Мне кажется, это алгоритмически неразрешимая задача.
Отлично, логарифмируем по основанию 2
Понятно, в чём причина наших споров. Я пытаюсь возразить против того, что взятие производных — универсальный достаточный механизм для оценки функций, а вы приводите примеры, как использовать производную в оценке в качестве одного из вспомогательных инструментов.
Да, инструмент хороший, но только как дополнительный, в связке с другими (а для некоторых примеров и не пригодится вовсе).
Если брать физический смысл, то производная от функции перемещения — это скорость. Чем больше скорость, тем быстрее растет пройденный путь.
Sign up to leave a comment.
Дискретные структуры: матан для айтишников