Еще немного наблюдений о вайбкодинге
Буду разбавлять посты про алгоритмы более простыми "насущными" темами.
Буквально вчера до меня начала доходить мысль, что существует два вида вайбкодинга: над одним постоянно смеются, а другой используется в компаниях. И это два кардинально противоположных метода с одним названием.
Сравните два запроса:
"Создай страницу Корзина, где пользователи могут оплачивать товары."
и
"Изучи эти два файла и этот сниппет. В одном файле ты найдешь модели таблиц в базе данных и примеры запросов / ендпонитов. В другом требования к написанию кода. Требуется сделать функционал для покупки выбранных товаров на странице checkout. Твоя задача: 1/2/3/4/5. Перед выполнением задачи составь план и дождись моего подтверждения."
И там, и там по запросу нужен практически идентичный функционал, только во втором случае даны конкретные требования к самому коду, примеры и доступы. В первом случае, запрос писал пользователь без знаний языков программирования, во втором - как минимум понимающий что-то о своем коде.
Это именно то, что и отличают оба вида вайбкодинга - инструкции с примерами. Нейросеть делает не то, что вы хотите, а что вы ей говорите сделать. Она не делает различий между "говнокодом" и "сеньором". При открытой задача (как в первом варианте), она просто берет свои случайные знания из памяти и соединяет их.
Так в одном проекте у вас может быть и код на Python, Ruby, JS и вообще смесь всего. Это вполне может работать. Вопрос в том, как...
Для другого пользователя, который знает и понимает код, разбирается в структуре своего проекта и умеет давать четкие инструкции к нейросети - результаты получаются гораздо лучше.
Задумайтесь также и о том, что даже сеньор может давать четкие указания по редактированию своего кода и нейронка прекрасно справится с задачей, использую декораторы и стиль самого сеньора. Какой код получится в этом случае?
В свое время, да и порой сейчас, многие смеются над PHP языком и у разработчиков была такая шутка: "PHP, как самокат. Из-за того, что любой дурак может сесть на него и поехать, репутация у этой штуки так себе". Вот примерно тоже самое и с вайбкодингом.
Запрос написанный сеньором - приведет к коду уровня сеньор, запрос от школьника - приведет к соответствующему результату.
Поэтому в следующий раз, когда увидите плохой код или ужасную архитектуру, то спросите прежде, кто и как писал это код, а не вините нейронку.
#vibecoding
Буду разбавлять посты про алгоритмы более простыми "насущными" темами.
Буквально вчера до меня начала доходить мысль, что существует два вида вайбкодинга: над одним постоянно смеются, а другой используется в компаниях. И это два кардинально противоположных метода с одним названием.
Сравните два запроса:
"Создай страницу Корзина, где пользователи могут оплачивать товары."
и
"Изучи эти два файла и этот сниппет. В одном файле ты найдешь модели таблиц в базе данных и примеры запросов / ендпонитов. В другом требования к написанию кода. Требуется сделать функционал для покупки выбранных товаров на странице checkout. Твоя задача: 1/2/3/4/5. Перед выполнением задачи составь план и дождись моего подтверждения."
И там, и там по запросу нужен практически идентичный функционал, только во втором случае даны конкретные требования к самому коду, примеры и доступы. В первом случае, запрос писал пользователь без знаний языков программирования, во втором - как минимум понимающий что-то о своем коде.
Это именно то, что и отличают оба вида вайбкодинга - инструкции с примерами. Нейросеть делает не то, что вы хотите, а что вы ей говорите сделать. Она не делает различий между "говнокодом" и "сеньором". При открытой задача (как в первом варианте), она просто берет свои случайные знания из памяти и соединяет их.
Так в одном проекте у вас может быть и код на Python, Ruby, JS и вообще смесь всего. Это вполне может работать. Вопрос в том, как...
Для другого пользователя, который знает и понимает код, разбирается в структуре своего проекта и умеет давать четкие инструкции к нейросети - результаты получаются гораздо лучше.
Задумайтесь также и о том, что даже сеньор может давать четкие указания по редактированию своего кода и нейронка прекрасно справится с задачей, использую декораторы и стиль самого сеньора. Какой код получится в этом случае?
В свое время, да и порой сейчас, многие смеются над PHP языком и у разработчиков была такая шутка: "PHP, как самокат. Из-за того, что любой дурак может сесть на него и поехать, репутация у этой штуки так себе". Вот примерно тоже самое и с вайбкодингом.
Запрос написанный сеньором - приведет к коду уровня сеньор, запрос от школьника - приведет к соответствующему результату.
Поэтому в следующий раз, когда увидите плохой код или ужасную архитектуру, то спросите прежде, кто и как писал это код, а не вините нейронку.
#vibecoding
👍11🔥1
Анонс платформы самоучителя по Solidity
Я планировал потрать еще некоторое время, чтобы полностью доработать платформу, где будут выложены все модули курса по Solidity + модуль по Foundry + модуль с практикой аудита кода, но текущие веяния в области ограничений Телеграмма, заставляют выпускать все раньше.
Сама платформа готова на 98% - 99%, я все еще просматривая материал на предмет каких-либо недочетов, некорректного отображения, мелких багов и т.д. И, в целом, все готово к открытию.
Вчера я открыл доступ к платформе для учеников Летнего модуля 3 потока. Собираю пока обратную связь. Кстати, если вы проходили Летний и 3 модуль 2 потока, то для вас доступ будет бесплатный, как я и обещал ранее. У вас будет доступ не только к материалам на каналах Телеграм, но и на одном ресурсе все вместе, в удобном формате.
Для всех желающих до конца февраля будет специальная цена на весь курс - 5000 рублей. Позже цена будет выше, и можно будет купить модули по отдельности.
Отличия самоучителя от курса в Телеграм то, что не будет проверок домашних заданий. В любом случае вы все равно сможете задавать вопросы в чате канала и получать ответ не только от меня, но и от других опытных участников.
Если после первых тестов на платформе все будет хорошо, то общий доступ открою уже в следующую среду - 18 февраля.
Всем хорошего дня и продуктивной работы!
#solidity
Я планировал потрать еще некоторое время, чтобы полностью доработать платформу, где будут выложены все модули курса по Solidity + модуль по Foundry + модуль с практикой аудита кода, но текущие веяния в области ограничений Телеграмма, заставляют выпускать все раньше.
Сама платформа готова на 98% - 99%, я все еще просматривая материал на предмет каких-либо недочетов, некорректного отображения, мелких багов и т.д. И, в целом, все готово к открытию.
Вчера я открыл доступ к платформе для учеников Летнего модуля 3 потока. Собираю пока обратную связь. Кстати, если вы проходили Летний и 3 модуль 2 потока, то для вас доступ будет бесплатный, как я и обещал ранее. У вас будет доступ не только к материалам на каналах Телеграм, но и на одном ресурсе все вместе, в удобном формате.
Для всех желающих до конца февраля будет специальная цена на весь курс - 5000 рублей. Позже цена будет выше, и можно будет купить модули по отдельности.
Отличия самоучителя от курса в Телеграм то, что не будет проверок домашних заданий. В любом случае вы все равно сможете задавать вопросы в чате канала и получать ответ не только от меня, но и от других опытных участников.
Если после первых тестов на платформе все будет хорошо, то общий доступ открою уже в следующую среду - 18 февраля.
Всем хорошего дня и продуктивной работы!
#solidity
1🎉17❤4🔥4
Что будет с Solidity и блокчейном?
На выходных в компании друзей подняли эту тему и пришли к выводу, что будет застой до одного переломного момента...
Драйвером роста в начале 2020 годов послужило то, что это были "новые деньги", где можно было быстро заработать. Появилось множество обменников и первые DeFi приложения, которые поняли смысл торговых операций и быстро вошли в топ на фоне, того, что остальные клепали свои токены.
Затем маркетинг и NFT подлили масла в огонь, и тогда "вход" в крипту через картинки стал проще. Знаменитости и артисты продавали NFT своим подписчикам и это считалось писком моды.
Затем были мемкоины... Даже простой обыватель мог один раз кликнуть на кнопку на сайте и запустить свой мем.
И все сошло на нет на 80% - 90%. Про NFT все забыли, мемкоины остались спекулянтам, а web3 захватили институционалы и правительство разных стран.
Solidity и блокчейн никуда не денется, туда вложено слишком много денег. Но и однотипные "Uniswap" / "Aave" / "GMX" уже всем приелись: инвесторы не дают деньги на их развитие командам, а без хорошего маркетинга ни один проект не взлетит.
Так что же за переломный момент, к которому мы пришли в компании?
На зарубежных сайтах я все чаще вижу возможность оплатить криптой за какой-либо сервис или товар. Представьте на секунду, что будет если такие платежи адаптирует Steam, Amazon, Spotify и другой популярный маркетплейс! А это уже потихоньку на подходе.
И это первая часть такого момента. Дальше будет внедрение крипты в мелкие магазинчики, чтобы можно было банально "купить хлеб за биткоин". И это уже тоже есть и развивается!
Конечно, многим странам до такой адаптации еще очень долго, но кто нам запретит, скажем, покупать на Amazon товары и доставлять их к себе?
Это даст очень большой буст всей сфере. Будут появляться уже не финансовые проекты в web3, а много SaaS, агентов и т.д., которые начнут упрощать жизнь и продавцам и покупателям.
Когда это будет? Думаю, когда все успокоятся с ИИ и агентами. А там, кто его знает. Но тенденции идут.
А как вы думаете?
#web3
На выходных в компании друзей подняли эту тему и пришли к выводу, что будет застой до одного переломного момента...
Драйвером роста в начале 2020 годов послужило то, что это были "новые деньги", где можно было быстро заработать. Появилось множество обменников и первые DeFi приложения, которые поняли смысл торговых операций и быстро вошли в топ на фоне, того, что остальные клепали свои токены.
Затем маркетинг и NFT подлили масла в огонь, и тогда "вход" в крипту через картинки стал проще. Знаменитости и артисты продавали NFT своим подписчикам и это считалось писком моды.
Затем были мемкоины... Даже простой обыватель мог один раз кликнуть на кнопку на сайте и запустить свой мем.
И все сошло на нет на 80% - 90%. Про NFT все забыли, мемкоины остались спекулянтам, а web3 захватили институционалы и правительство разных стран.
Solidity и блокчейн никуда не денется, туда вложено слишком много денег. Но и однотипные "Uniswap" / "Aave" / "GMX" уже всем приелись: инвесторы не дают деньги на их развитие командам, а без хорошего маркетинга ни один проект не взлетит.
Так что же за переломный момент, к которому мы пришли в компании?
На зарубежных сайтах я все чаще вижу возможность оплатить криптой за какой-либо сервис или товар. Представьте на секунду, что будет если такие платежи адаптирует Steam, Amazon, Spotify и другой популярный маркетплейс! А это уже потихоньку на подходе.
И это первая часть такого момента. Дальше будет внедрение крипты в мелкие магазинчики, чтобы можно было банально "купить хлеб за биткоин". И это уже тоже есть и развивается!
Конечно, многим странам до такой адаптации еще очень долго, но кто нам запретит, скажем, покупать на Amazon товары и доставлять их к себе?
Это даст очень большой буст всей сфере. Будут появляться уже не финансовые проекты в web3, а много SaaS, агентов и т.д., которые начнут упрощать жизнь и продавцам и покупателям.
Когда это будет? Думаю, когда все успокоятся с ИИ и агентами. А там, кто его знает. Но тенденции идут.
А как вы думаете?
#web3
👍15🤔4🔥1
🎉🎉🎉 Запуск платформы SoliditySet 🎉🎉🎉
Как и обещал, сегодня запускаю платформу самоучителя по Solidity с нуля для всех!
Для меня эта платформа очень ценна, так как это результат моей работы последних трех лет в обучении других языку Solidity. Каждый урок я писал сам, перерабатывая знания и стараясь сделать информацию максимально понятной и простой для новичков (и это заметили первые ученики на модулях!).
В итоге на платформе собрано:
1. 100+ уроков для тех, кто никогда ранее не программировал;
2. 20+ уроков по тестированию смарт контрактов в среде Foundry;
3. 70+ заданий для практики аудита кода;
4. 80+ практических заданий;
5. 50+ продвинутых челленджей для практики;
6. 150+ вопросов для самопроверки и подготовки к собеседованию;
7. 5 практикумов для проверки навыков после каждого модуля;
8. 10+ возможных проектов для портфолио;
9. 32 переведенные экспертные статьи, 23 из которых по темам DeFi протоколов;
Это, вероятно, самый большой и полный самоучитель по Solidity в ру сегменте!
И все это на удобной платформе, где вы можете отслеживать прогресс и проходить каждый урок в своем темпе!
P.S. Важно сказать, что там нет видео уроков! Я никогда не записывал видео и вся информация там в текстовом формате!
Задавать вопросы вы можете в чате нашего канала, я, либо другие участники, всегда ответим на ваши вопросы.
Стоимость доступа будет повышаться со временем.
С апреля она составляет 6000 рублей (75 USDT).
На данном этапе я еще не добавил опцию покупки на сайте. Поэтому после регистрации на платформе, вам нужно написать мне (@zaevlad). Я пришлю актуальные реквизиты для оплаты и открою доступ.
Сайт самоучителя - SoliditySet
Там открыты первые три урока для общего доступа, чтобы вы могли оценить, подходит ли вам этот формат или нет перед покупкой.
Всем легкого обучения!
#solidityset
Как и обещал, сегодня запускаю платформу самоучителя по Solidity с нуля для всех!
Для меня эта платформа очень ценна, так как это результат моей работы последних трех лет в обучении других языку Solidity. Каждый урок я писал сам, перерабатывая знания и стараясь сделать информацию максимально понятной и простой для новичков (и это заметили первые ученики на модулях!).
В итоге на платформе собрано:
1. 100+ уроков для тех, кто никогда ранее не программировал;
2. 20+ уроков по тестированию смарт контрактов в среде Foundry;
3. 70+ заданий для практики аудита кода;
4. 80+ практических заданий;
5. 50+ продвинутых челленджей для практики;
6. 150+ вопросов для самопроверки и подготовки к собеседованию;
7. 5 практикумов для проверки навыков после каждого модуля;
8. 10+ возможных проектов для портфолио;
9. 32 переведенные экспертные статьи, 23 из которых по темам DeFi протоколов;
Это, вероятно, самый большой и полный самоучитель по Solidity в ру сегменте!
И все это на удобной платформе, где вы можете отслеживать прогресс и проходить каждый урок в своем темпе!
P.S. Важно сказать, что там нет видео уроков! Я никогда не записывал видео и вся информация там в текстовом формате!
Задавать вопросы вы можете в чате нашего канала, я, либо другие участники, всегда ответим на ваши вопросы.
Стоимость доступа будет повышаться со временем.
С апреля она составляет 6000 рублей (75 USDT).
На данном этапе я еще не добавил опцию покупки на сайте. Поэтому после регистрации на платформе, вам нужно написать мне (@zaevlad). Я пришлю актуальные реквизиты для оплаты и открою доступ.
Сайт самоучителя - SoliditySet
Там открыты первые три урока для общего доступа, чтобы вы могли оценить, подходит ли вам этот формат или нет перед покупкой.
Всем легкого обучения!
#solidityset
2❤14🔥12🎉12
Ошибка в Solidity и новый бенчмарк
Недавно произошло сразу два события, которые хорошо показывают, как меняется ландшафт безопасности смарт-контрактов: с одной стороны, нас подстерегают старые добрые ошибки в компиляторе, а с другой — на горизонте уже маячит искусственный интеллект, который учится взламывать и чинить код быстрее человека.
Команда Solidity раскрыла детали критической ошибки, которая пряталась в версиях компилятора с 0.8.28 по 0.8.33. Проблема проявлялась только при использовании IR-конвейера и была связана с коллизией имён вспомогательных функций. Если в коде одновременно использовалась очистка переменной временного хранилища и постоянного хранилища одного типа, компилятор путал инструкции. Вместо очистки временной ячейки он мог обнулить слот в постоянной памяти, что потенциально способно «сбросить» владельца контракта или нарушить логику блокировок. Ошибка уже исправлена в версии 0.8.34. Хотя в мейннете нашлось всего три уязвимых контракта, инцидент напоминает о том, как важно следить за обновлениями инструментов, особенно при использовании новых фич вроде transient storage.
Параллельно с этим исследователи безопасности представили бенчмарк EVMbench, созданный для тестирования ИИ-агентов. Учитывая, что под управлением смарт-контрактов находятся активы на сотни миллиардов долларов, важно понимать, насколько искусственный интеллект способен находить уязвимости или проводить атаки. В основе бенчмарка — 120 реальных багов из аудитов и соревнований. Тестирование показало, что современные модели уже более чем вдвое лучше справляются с задачей взлома контрактов по сравнению с версиями полугодовой давности. Однако задачи комплексного обнаружения всех проблем и аккуратного исправления кода без поломки функциональности пока даются ИИ сложнее. Разработчики выложили бенчмарк в открытый доступ и выделяют гранты на исследования в этой области, подчёркивая, что гонка вооружений между атакующими и защищающимися ИИ-агентами только начинается.
#news
Недавно произошло сразу два события, которые хорошо показывают, как меняется ландшафт безопасности смарт-контрактов: с одной стороны, нас подстерегают старые добрые ошибки в компиляторе, а с другой — на горизонте уже маячит искусственный интеллект, который учится взламывать и чинить код быстрее человека.
Команда Solidity раскрыла детали критической ошибки, которая пряталась в версиях компилятора с 0.8.28 по 0.8.33. Проблема проявлялась только при использовании IR-конвейера и была связана с коллизией имён вспомогательных функций. Если в коде одновременно использовалась очистка переменной временного хранилища и постоянного хранилища одного типа, компилятор путал инструкции. Вместо очистки временной ячейки он мог обнулить слот в постоянной памяти, что потенциально способно «сбросить» владельца контракта или нарушить логику блокировок. Ошибка уже исправлена в версии 0.8.34. Хотя в мейннете нашлось всего три уязвимых контракта, инцидент напоминает о том, как важно следить за обновлениями инструментов, особенно при использовании новых фич вроде transient storage.
Параллельно с этим исследователи безопасности представили бенчмарк EVMbench, созданный для тестирования ИИ-агентов. Учитывая, что под управлением смарт-контрактов находятся активы на сотни миллиардов долларов, важно понимать, насколько искусственный интеллект способен находить уязвимости или проводить атаки. В основе бенчмарка — 120 реальных багов из аудитов и соревнований. Тестирование показало, что современные модели уже более чем вдвое лучше справляются с задачей взлома контрактов по сравнению с версиями полугодовой давности. Однако задачи комплексного обнаружения всех проблем и аккуратного исправления кода без поломки функциональности пока даются ИИ сложнее. Разработчики выложили бенчмарк в открытый доступ и выделяют гранты на исследования в этой области, подчёркивая, что гонка вооружений между атакующими и защищающимися ИИ-агентами только начинается.
#news
👍6❤1🔥1
Что почитать?
Проснулся сегодня с явным нежеланием работать. На улице хоть и -2, но солнце светит уже по весеннему, и хочется просто отдыхать, а не фиксить баги и учить MatPlotLib...
Поэтому сегодня, в качестве оффтопа, решил поделиться с вами рекомендациями книг, которые читал или буду читать в ближайшее время.
1. System Design. Подготовка к сложному интервью. Алекс Сюй.
Первая книга, которую должны прочитать все вайбкодеры, да и просто начинающие разработчики. Здесь в понятной манере и простым языком объясняются базовые принципы архитектур компьютерных систем: какую базу данных выбрать, как работает кеш, что такое CDN, распределение трафика, нагрузка и организация серверной части. Очень достойная книга, чтобы начать разбираться в этих понятиях!
2. System Design. Машинное обучение. Али Аминиан, Алекс Сюй.
Еще одна книга от того же автора, но уже в соавторстве с Али Аминианом. Купил ее только потому что понравилась первая часть. Здесь также в простом формате раскрываются вопросы про машинное обучение, которые могут задавать на собеседовании: как выбирать модель, как обучать ее, рекомендация событий и данных для пользователей, организация поиска и т.д. В общем, я ожидаю, что она дополнит мои знания про ML. Еще не читал.
3. Прикладное машинное обучении и искусственный интеллект для инженеров. Джеф Просиз.
Вот это отличная книга для тех, кто уже познакомился с нейронками и хочет копнуть глубже с тем, как работают сети в своей основе. Тут раскрываются темы регрессионного анализа, классификационных моделей, опорные векторы, обучение с помощью keras/tensorflow, обнаружение лиц и распознавание изображений и т.д. Много примеров с кодом. Единственное что, может быть сложной в языке: если вы никогда ранее не сталкивались с определениями в машинном обучении, то придется много гуглить.
4. Байесовская статистика. Star Wars, резиновые уточки и многое другое.
Книга за которой долго гонялся. Не мог найти в РФ и ждал ее несколько недель из Китая. Еще не успел прочитать ее, только просмотрел несколько глав. Прекрасное, легкое и очень простое объяснение предсказательной статистики и вероятностных моделей. Как вы можете знать, что современные нейронные сети "под капотом" используют предсказательные алгоритмы для генерации токенов. Эта книга может помочь вам понять на простых примерах, как это все работает в сетях.
5. Алгоритмы искусственного интеллекта. Ришал Харбанс.
С использованием этой книги я позже буду делать посты про алгоритмы в нейронных сетях, когда мы закончим цикл про основные алгоритмы в программировании на канале. Еще не открывал ее даже, хочу погрузиться в нее чуть позже.
6. Высоконагруженные приложения. Мартин Клепман.
Еще одна книга, до которой не дошел, но очень жду. Очень много рекомендаций ее изучить видел в Твиттере. Тут рассказывается о подходе к работе над информационными системами, моделях данных и языках запросов, системах хранения данных, репликации, секционировании, проблемах и т.д.
Полагаю, что читать ее лучше после первой книги Алекса Сюя, чтобы складывалось общее понимание работы систем.
7. Поиск на основе искусственного интеллекта. Трей Грейнджер, Дуг Тернбул, Макс Ирвин.
Вот это отличная книга о том, как работает поиск. Читаю ее сейчас. Если вы когда-нибудь задумывались, почему поиск на сайте работает так "криво", или почему он выдает массу результатов подобных моим прошлым запросов - эта книга для вас. Детально разбираются системы алгоритмов поиска и рекомендаций, а также использование нейронных сетей для выдачи релевантных результатов. Книга огонь!
8. Конструкции. Джейсм Гордон. Это книгу давно забросил в корзину и все никак не мог купить ее. Пришлось просить в подарок на Новый Год. Единственное, о чем пожалел: почему я не купил ее раньше!
Проснулся сегодня с явным нежеланием работать. На улице хоть и -2, но солнце светит уже по весеннему, и хочется просто отдыхать, а не фиксить баги и учить MatPlotLib...
Поэтому сегодня, в качестве оффтопа, решил поделиться с вами рекомендациями книг, которые читал или буду читать в ближайшее время.
1. System Design. Подготовка к сложному интервью. Алекс Сюй.
Первая книга, которую должны прочитать все вайбкодеры, да и просто начинающие разработчики. Здесь в понятной манере и простым языком объясняются базовые принципы архитектур компьютерных систем: какую базу данных выбрать, как работает кеш, что такое CDN, распределение трафика, нагрузка и организация серверной части. Очень достойная книга, чтобы начать разбираться в этих понятиях!
2. System Design. Машинное обучение. Али Аминиан, Алекс Сюй.
Еще одна книга от того же автора, но уже в соавторстве с Али Аминианом. Купил ее только потому что понравилась первая часть. Здесь также в простом формате раскрываются вопросы про машинное обучение, которые могут задавать на собеседовании: как выбирать модель, как обучать ее, рекомендация событий и данных для пользователей, организация поиска и т.д. В общем, я ожидаю, что она дополнит мои знания про ML. Еще не читал.
3. Прикладное машинное обучении и искусственный интеллект для инженеров. Джеф Просиз.
Вот это отличная книга для тех, кто уже познакомился с нейронками и хочет копнуть глубже с тем, как работают сети в своей основе. Тут раскрываются темы регрессионного анализа, классификационных моделей, опорные векторы, обучение с помощью keras/tensorflow, обнаружение лиц и распознавание изображений и т.д. Много примеров с кодом. Единственное что, может быть сложной в языке: если вы никогда ранее не сталкивались с определениями в машинном обучении, то придется много гуглить.
4. Байесовская статистика. Star Wars, резиновые уточки и многое другое.
Книга за которой долго гонялся. Не мог найти в РФ и ждал ее несколько недель из Китая. Еще не успел прочитать ее, только просмотрел несколько глав. Прекрасное, легкое и очень простое объяснение предсказательной статистики и вероятностных моделей. Как вы можете знать, что современные нейронные сети "под капотом" используют предсказательные алгоритмы для генерации токенов. Эта книга может помочь вам понять на простых примерах, как это все работает в сетях.
5. Алгоритмы искусственного интеллекта. Ришал Харбанс.
С использованием этой книги я позже буду делать посты про алгоритмы в нейронных сетях, когда мы закончим цикл про основные алгоритмы в программировании на канале. Еще не открывал ее даже, хочу погрузиться в нее чуть позже.
6. Высоконагруженные приложения. Мартин Клепман.
Еще одна книга, до которой не дошел, но очень жду. Очень много рекомендаций ее изучить видел в Твиттере. Тут рассказывается о подходе к работе над информационными системами, моделях данных и языках запросов, системах хранения данных, репликации, секционировании, проблемах и т.д.
Полагаю, что читать ее лучше после первой книги Алекса Сюя, чтобы складывалось общее понимание работы систем.
7. Поиск на основе искусственного интеллекта. Трей Грейнджер, Дуг Тернбул, Макс Ирвин.
Вот это отличная книга о том, как работает поиск. Читаю ее сейчас. Если вы когда-нибудь задумывались, почему поиск на сайте работает так "криво", или почему он выдает массу результатов подобных моим прошлым запросов - эта книга для вас. Детально разбираются системы алгоритмов поиска и рекомендаций, а также использование нейронных сетей для выдачи релевантных результатов. Книга огонь!
8. Конструкции. Джейсм Гордон. Это книгу давно забросил в корзину и все никак не мог купить ее. Пришлось просить в подарок на Новый Год. Единственное, о чем пожалел: почему я не купил ее раньше!
❤7👍3🔥1
Эта книга не про IT, это больше популярное чтиво о том, как работает физика в конструкциях. Язык и объяснения невероятно простые. Если бы так физику преподавали в школе, я бы точно получал одни пятерки! Потрясающие графики и фотографии, рисунки и силуэты, описания базовых принципов растяжения и деформации и много другое! Просто зачитываюсь в свободное время и наслаждаюсь, как можно просто писать о таких сложных вещах!
Есть еще несколько других интересных книг, но расскажу о них позже, если вам зайдет такой формат в постах.
Так же буду рад получить от вас другие рекомендации, что еще моно почитать!
#books
Есть еще несколько других интересных книг, но расскажу о них позже, если вам зайдет такой формат в постах.
Так же буду рад получить от вас другие рекомендации, что еще моно почитать!
#books
👍9🔥2❤1
Алгоритмы. Обход в глубину (DFS)
После небольшой паузы мы продолжаем разбирать различные алгоритмы.
Обход в глубину (DFS) — это один из фундаментальных алгоритмов на графах, и его легче всего понять через аналогию с исследованием пещеры. Представь, что ты стоишь в системе туннелей с множеством разветвлений. Твоя стратегия заключается в том, чтобы выбрать первый попавшийся проход и идти по нему до тех пор, пока не упрешься в тупик. Только тогда ты возвращаешься назад к последнему перекрестку, где еще есть неисследованные пути, и пробуешь следующий туннель. Эта логика, где глубина проникновения важнее ширины охвата, и лежит в основе алгоритма DFS.
Рассмотрим небольшой граф. Предположим, у нас есть узлы, соединенные между собой: A связан с B и C; B связан с A, D и E; C связан с A и F; D связан только с B; E связан с B и F, а F, в свою очередь, связан с C и E. Если начать обход с узла A, DFS будет двигаться следующим образом: сначала мы попадаем в A, затем углубляемся в B, оттуда — в D. Достигнув D, мы понимаем, что это тупик (сосед B уже посещен), поэтому возвращаемся обратно в B и идем по следующему пути в E. Из E переходим в F, который тоже оказывается тупиком (все соседи посещены или ведут назад). После возврата в E и затем в B, мы наконец возвращаемся в A и идем в C, но обнаруживаем, что C уже был посещен через F. Итоговый порядок посещения узлов будет таким: A, B, D, E, F, C.
В этом заключается ключевое отличие DFS от другого известного алгоритма — поиска в ширину (BFS). BFS работает подобно кругам на воде: сначала исследуются все соседние узлы, затем их соседи, распространяясь равномерно во все стороны. DFS же напоминает нить Ариадны в лабиринте: он всегда идет до конца по выбранному пути и лишь затем возвращается.
Для реализации DFS можно использовать два основных подхода, которые делают одно и то же, но разными средствами: рекурсию и явный стек. Рекурсивный метод полагается на стек вызовов самой программы. Когда мы пишем функцию, которая вызывает саму себя для обработки соседей, язык программирования автоматически запоминает точку возврата. Однако здесь есть важная особенность Python: не стоит задавать значение аргумента
Пример 1
Чтобы лучше понять, как работает рекурсия, можно проследить её выполнение по шагам. Входя в узел A, мы помечаем его как посещенный и записываем в результат. Затем смотрим на соседа B, который еще не посещен, и вызываем функцию для B. Внутри вызова для B повторяется та же логика: добавляем B в путь и идем к его первому непосещенному соседу D. В D тупик, и функция возвращает результат обратно. Далее в B очередь доходит до следующего соседа — E. Из E попадаем в F, а из F — в C. Когда все пути исчерпаны, результаты склеиваются и возвращаются наверх.
Пример 2
Второй способ реализации — итеративный с использованием явного стека. Стек работает по принципу «последним пришел — первым вышел» (LIFO). Это как стопка тарелок: новую тарелку кладут сверху, и первую берут тоже сверху. В коде мы сами управляем этим стеком, помещая туда узлы для последующей обработки. Важный нюанс: чтобы порядок обхода совпадал с рекурсивной версией, соседей часто добавляют в обратном порядке. Если просто положить соседей в стек по порядку, то из-за механизма LIFO первым будет извлечен последний сосед, и обход пойдет в другую сторону.
Пример 3
После небольшой паузы мы продолжаем разбирать различные алгоритмы.
Обход в глубину (DFS) — это один из фундаментальных алгоритмов на графах, и его легче всего понять через аналогию с исследованием пещеры. Представь, что ты стоишь в системе туннелей с множеством разветвлений. Твоя стратегия заключается в том, чтобы выбрать первый попавшийся проход и идти по нему до тех пор, пока не упрешься в тупик. Только тогда ты возвращаешься назад к последнему перекрестку, где еще есть неисследованные пути, и пробуешь следующий туннель. Эта логика, где глубина проникновения важнее ширины охвата, и лежит в основе алгоритма DFS.
Рассмотрим небольшой граф. Предположим, у нас есть узлы, соединенные между собой: A связан с B и C; B связан с A, D и E; C связан с A и F; D связан только с B; E связан с B и F, а F, в свою очередь, связан с C и E. Если начать обход с узла A, DFS будет двигаться следующим образом: сначала мы попадаем в A, затем углубляемся в B, оттуда — в D. Достигнув D, мы понимаем, что это тупик (сосед B уже посещен), поэтому возвращаемся обратно в B и идем по следующему пути в E. Из E переходим в F, который тоже оказывается тупиком (все соседи посещены или ведут назад). После возврата в E и затем в B, мы наконец возвращаемся в A и идем в C, но обнаруживаем, что C уже был посещен через F. Итоговый порядок посещения узлов будет таким: A, B, D, E, F, C.
Граф:
A
/ \
B C
/ \ \
D E F
\ /
(F связан с E и C)
DFS от A пойдёт так:
A → B → D (тупик, назад) → E → F (тупик, назад) → назад → C (уже посещён через F)
Порядок посещения: A, B, D, E, F, C
В этом заключается ключевое отличие DFS от другого известного алгоритма — поиска в ширину (BFS). BFS работает подобно кругам на воде: сначала исследуются все соседние узлы, затем их соседи, распространяясь равномерно во все стороны. DFS же напоминает нить Ариадны в лабиринте: он всегда идет до конца по выбранному пути и лишь затем возвращается.
Граф: BFS (в ширину): DFS (в глубину):
A Уровень за уровнем Ветка за веткой
/ \ A A
B C B, C B, D, E, F, C
/ \ \ D, E, F
D E F
Для реализации DFS можно использовать два основных подхода, которые делают одно и то же, но разными средствами: рекурсию и явный стек. Рекурсивный метод полагается на стек вызовов самой программы. Когда мы пишем функцию, которая вызывает саму себя для обработки соседей, язык программирования автоматически запоминает точку возврата. Однако здесь есть важная особенность Python: не стоит задавать значение аргумента
visited по умолчанию как пустое множество (set()), так как изменяемые объекты создаются один раз и будут переиспользованы во всех вызовах функции. Вместо этого нужно создавать его внутри функции, если оно не передано.Пример 1
Чтобы лучше понять, как работает рекурсия, можно проследить её выполнение по шагам. Входя в узел A, мы помечаем его как посещенный и записываем в результат. Затем смотрим на соседа B, который еще не посещен, и вызываем функцию для B. Внутри вызова для B повторяется та же логика: добавляем B в путь и идем к его первому непосещенному соседу D. В D тупик, и функция возвращает результат обратно. Далее в B очередь доходит до следующего соседа — E. Из E попадаем в F, а из F — в C. Когда все пути исчерпаны, результаты склеиваются и возвращаются наверх.
Пример 2
Второй способ реализации — итеративный с использованием явного стека. Стек работает по принципу «последним пришел — первым вышел» (LIFO). Это как стопка тарелок: новую тарелку кладут сверху, и первую берут тоже сверху. В коде мы сами управляем этим стеком, помещая туда узлы для последующей обработки. Важный нюанс: чтобы порядок обхода совпадал с рекурсивной версией, соседей часто добавляют в обратном порядке. Если просто положить соседей в стек по порядку, то из-за механизма LIFO первым будет извлечен последний сосед, и обход пойдет в другую сторону.
Пример 3
🔥1
Процесс итеративного обхода можно наглядно представить в виде таблицы, где видно, как меняется содержимое стека на каждом шаге. Начинаем со стеком, содержащим A. Извлекаем A, помечаем его и добавляем в результат, а затем кладем в стек его соседей C и B в обратном порядке (чтобы B оказался сверху). Затем извлекаем B, затем D, и так далее, пока стек не опустеет.
Этот код, по сути, является готовой реализацией итеративного DFS, где стек берет на себя работу, которую в рекурсивной версии выполняет стек вызовов. Каждая часть здесь важна: множество
Одна из классических задач, решаемых с помощью DFS, — поиск циклов в графе. Цикл — это ситуация, когда, двигаясь по графу, мы возвращаемся в узел, который уже встречали на текущем пути. Важно отличать просто посещенный узел от узла, находящегося в текущем стеке рекурсии. Ведь если мы видим уже посещенный узел, который не является частью текущего пути, это может быть просто пересечение, а не цикл. Поэтому в алгоритме используются два множества:
Алгоритм запускает проверку из каждой вершины, чтобы учесть возможную несвязность графа. Если в процессе обхода мы наталкиваемся на соседа, который уже есть в
Пример 4
Как именно это работает, можно увидеть на примере графа с циклом. Начиная с A, мы идем в B, затем в D. В узле D видим соседа B, который уже есть в
Пример 5
Еще одно важное практическое применение DFS — поиск пути в лабиринте. Здесь выбор между DFS и BFS зависит от конкретной задачи. Если нам нужно просто найти любой путь к выходу, DFS часто оказывается предпочтительнее. Он идет по одному пути до упора и, если лабиринт не слишком разветвлен, может найти выход довольно быстро. При этом DFS использует меньше памяти, так как хранит лишь текущий путь.
Пример 6
Однако если стоит задача найти кратчайший путь, DFS не подходит. Он может углубиться в длинную ветку и найти путь, который окажется далеко не самым коротким, в то время как существует более прямой маршрут. В такой ситуации BFS гарантированно найдет кратчайший путь, хотя и потребует больше памяти для хранения всех узлов текущего уровня.
Шаг | Стек (вершина →) | Берём | visited | result
----|--------------------|-------|-----------------|------------------
0 | [A] | A | {A} | [A]
1 | [C, B] | B | {A,B} | [A,B]
2 | [C, E, D] | D | {A,B,D} | [A,B,D]
3 | [C, E] | E | {A,B,D,E} | [A,B,D,E]
4 | [C, F] | F | {A,B,D,E,F} | [A,B,D,E,F]
5 | [C, E*, C] | C | {A,B,D,E,F,C} | [A,B,D,E,F,C]
(* E уже в visited — пропустим при извлечении)
Финальный результат: [A, B, D, E, F, C] ✓
Этот код, по сути, является готовой реализацией итеративного DFS, где стек берет на себя работу, которую в рекурсивной версии выполняет стек вызовов. Каждая часть здесь важна: множество
visited отслеживает уже обработанные узлы, список stack хранит узлы, которые предстоит обработать, а цикл while работает, пока есть что извлекать.Одна из классических задач, решаемых с помощью DFS, — поиск циклов в графе. Цикл — это ситуация, когда, двигаясь по графу, мы возвращаемся в узел, который уже встречали на текущем пути. Важно отличать просто посещенный узел от узла, находящегося в текущем стеке рекурсии. Ведь если мы видим уже посещенный узел, который не является частью текущего пути, это может быть просто пересечение, а не цикл. Поэтому в алгоритме используются два множества:
visited для всех узлов, которые когда-либо посещались, и rec_stack для узлов, в которых мы находимся прямо сейчас в процессе рекурсивного спуска.Граф БЕЗ цикла: Граф С циклом:
A A
/ \ / \
B C B C
| |\ /
D | X
|/ \
D E
Алгоритм запускает проверку из каждой вершины, чтобы учесть возможную несвязность графа. Если в процессе обхода мы наталкиваемся на соседа, который уже есть в
rec_stack, это означает обнаружение цикла.Пример 4
Как именно это работает, можно увидеть на примере графа с циклом. Начиная с A, мы идем в B, затем в D. В узле D видим соседа B, который уже есть в
rec_stack. Это и есть сигнал о наличии цикла.Пример 5
Еще одно важное практическое применение DFS — поиск пути в лабиринте. Здесь выбор между DFS и BFS зависит от конкретной задачи. Если нам нужно просто найти любой путь к выходу, DFS часто оказывается предпочтительнее. Он идет по одному пути до упора и, если лабиринт не слишком разветвлен, может найти выход довольно быстро. При этом DFS использует меньше памяти, так как хранит лишь текущий путь.
Пример 6
Однако если стоит задача найти кратчайший путь, DFS не подходит. Он может углубиться в длинную ветку и найти путь, который окажется далеко не самым коротким, в то время как существует более прямой маршрут. В такой ситуации BFS гарантированно найдет кратчайший путь, хотя и потребует больше памяти для хранения всех узлов текущего уровня.
Лабиринт: DFS может пойти так: BFS пойдёт так:
S S→A→C→E→EXIT S→A (длина 1)
/ \ (длина 4) S→B (длина 1)
A B Хотя существует S→A→C, S→B→EXIT
| | S→B→EXIT Найдёт S→B→EXIT
C EXIT (длина 2)! (длина 2) первым
\ /
E
|
EXIT
DFS нашёл путь длиной 4, хотя есть путь длиной 2.
BFS всегда находит кратчайший путь.
🔥1
Сравнивая эти два подхода для лабиринта, можно выделить несколько критериев. Для задачи нахождения любого выхода оба алгоритма работают, но DFS требует меньше памяти. Для поиска кратчайшего пути BFS гарантирует результат, а DFS — нет. В глубоких лабиринтах рекурсивный DFS рискует переполнить стек, тогда как итеративный и BFS безопасны. В широких лабиринтах BFS может потребить много памяти, а DFS остается эффективным.
Что касается вычислительной сложности, то и для DFS, и для BFS она одинакова. Временная сложность составляет O(V + E), где V — количество вершин (узлов), а E — количество ребер. Это объясняется тем, что алгоритм посещает каждую вершину ровно один раз и просматривает каждое ребро также один раз. Пространственная сложность в худшем случае составляет O(V) — память нужна для хранения множества посещенных узлов и, в случае итеративной реализации, стека.
Подводя итог, можно сказать, что DFS — это алгоритм, который идет вглубь до упора, а затем возвращается. Его можно реализовать элегантно через рекурсию или более контролируемо через явный стек. Он применяется для поиска любого пути, обнаружения циклов, топологической сортировки и обхода деревьев, но не гарантирует нахождения кратчайшего маршрута.
#algorithm
Что касается вычислительной сложности, то и для DFS, и для BFS она одинакова. Временная сложность составляет O(V + E), где V — количество вершин (узлов), а E — количество ребер. Это объясняется тем, что алгоритм посещает каждую вершину ровно один раз и просматривает каждое ребро также один раз. Пространственная сложность в худшем случае составляет O(V) — память нужна для хранения множества посещенных узлов и, в случае итеративной реализации, стека.
Подводя итог, можно сказать, что DFS — это алгоритм, который идет вглубь до упора, а затем возвращается. Его можно реализовать элегантно через рекурсию или более контролируемо через явный стек. Он применяется для поиска любого пути, обнаружения циклов, топологической сортировки и обхода деревьев, но не гарантирует нахождения кратчайшего маршрута.
#algorithm
❤6👍2🔥1
Фиксы SoliditySet
Спасибо всем, кто сообщал мне о проблемах на платформе и подсказывал лучшие решения для тех или иных случаев. Сегодня был выполнен очередной фикс:
1. Были исправлены некоторые не работающие ссылки;
2. Обновлено отображение на мобильных экранах: немного удобнее использовать на планшетах;
3. К нумерации уроков были добавлены заголовки уроков;
4. Подсказки и ответы для модуля 5 (практика поиска уязвимостей) были скрыты под спойлером. (Тут я еще думаю как сделать это красивее...).
5. Исправлен порядок вывода некоторых уроков.
6. Откорректированы мелкие недочеты.
Спасибо, что помогаете сделать платформу лучше! В марте я планирую добавить несколько новых уроков, и если все пойдет как надо: новый раздел с переводами зарубежных статей.
#solidityset
Спасибо всем, кто сообщал мне о проблемах на платформе и подсказывал лучшие решения для тех или иных случаев. Сегодня был выполнен очередной фикс:
1. Были исправлены некоторые не работающие ссылки;
2. Обновлено отображение на мобильных экранах: немного удобнее использовать на планшетах;
3. К нумерации уроков были добавлены заголовки уроков;
4. Подсказки и ответы для модуля 5 (практика поиска уязвимостей) были скрыты под спойлером. (Тут я еще думаю как сделать это красивее...).
5. Исправлен порядок вывода некоторых уроков.
6. Откорректированы мелкие недочеты.
Спасибо, что помогаете сделать платформу лучше! В марте я планирую добавить несколько новых уроков, и если все пойдет как надо: новый раздел с переводами зарубежных статей.
#solidityset
👍9❤1🔥1
Алгоритмы. Алгоритм Дейкстры
Рассматривая этот алгоритм, я все никак не мог привыкнуть читать его как Дейкстры. Каждый раз в голове крутился образ персонажа из Ведьмака - шпиона Диикстры. При этом на английском языке они пишутся одинаково - Dijkstra. Но забудем об этом и вернемся к нашему алгоритму.
Представьте карту городов, соединённых дорогами. Каждый город можно представить как вершину графа, каждая дорога — как ребро, а расстояние между городами — как вес ребра. Например, рассмотрим такой граф:
Если мы хотим добраться из A в D по кратчайшему пути, то на глаз ответ не всегда очевиден. Именно для решения таких задач и существует алгоритм Дейкстры, который находит кратчайшие пути от одной вершины до всех остальных во взвешенном графе с неотрицательными весами рёбер.
Прежде чем углубляться, стоит уточнить ключевые понятия. Граф — это набор точек (вершин), соединённых линиями (рёбрами). Вес ребра — это число, стоящее на ребре и обозначающее стоимость перехода (расстояние, время, цена и т.п.). Взвешенный граф — это граф, где у каждого ребра есть вес. Кратчайший путь — это маршрут с минимальной суммой весов рёбер. Алгоритм Дейкстры относится к классу жадных алгоритмов: на каждом шаге он выбирает локально лучший вариант, то есть вершину с наименьшим известным расстоянием от старта.
Идею алгоритма можно объяснить простыми словами: вы стоите в начальной точке и хотите узнать расстояния до всех остальных городов. Вы постепенно открываете для себя новые города, всегда переходя сначала в тот, до которого сейчас ближе всего. При этом, попадая в новый город, вы проверяете, не стали ли теперь известные пути до его соседей короче. Этот процесс повторяется, пока не будут обработаны все вершины. Иными словами, на каждом шаге мы идём в ближайший ещё не посещённый город и обновляем расстояния до его соседей.
Рассмотрим работу алгоритма на конкретном примере. Пусть дан граф:
Рёбра и их веса:
- A–B: 1
- A–C: 4
- B–C: 2
- B–D: 5
- C–D: 1
Начальная вершина — A. В начальный момент мы знаем расстояние только до самой себя (ноль), а до всех остальных вершин расстояние полагаем бесконечным. Состояние можно описать так:
Извлекаем из очереди вершину A с расстоянием 0. Рассматриваем её соседей: до B можно добраться за 0+1=1, что меньше бесконечности, поэтому обновляем расстояние до B. До C можно добраться за 0+4=4, обновляем C. После этого состояния становятся такими:
Теперь из очереди выбираем вершину с наименьшим расстоянием — это B (расстояние 1). Из B можно пойти к A (но расстояние 1+1=2 больше уже известного 0, поэтому пропускаем), к C (1+2=3, что меньше текущего 4, обновляем C до 3) и к D (1+5=6, обновляем D с бесконечности до 6). После этого:
Обратите внимание: в очереди теперь есть два элемента для вершины C: (3, C) и (4, C_old). Это старая запись, которая будет проигнорирована позже.
Следующая ближайшая вершина — C с расстоянием 3. Проверяем соседей: до A (3+4=7 > 0), до B (3+2=5 > 1), до D (3+1=4 < 6) — обновляем D до 4. После обновления:
Наконец, извлекаем D с расстоянием 4. Её соседи уже посещены или не дают улучшений. Алгоритм завершается. Итоговые расстояния:
- A = 0
- B = 1
- C = 3
- D = 4
Кратчайшие пути из A:
- A → A : 0
- A → B : A → B (вес 1)
- A → C : A → B → C (1 + 2 = 3)
- A → D : A → B → C → D (1 + 2 + 1 = 4)
Рассматривая этот алгоритм, я все никак не мог привыкнуть читать его как Дейкстры. Каждый раз в голове крутился образ персонажа из Ведьмака - шпиона Диикстры. При этом на английском языке они пишутся одинаково - Dijkstra. Но забудем об этом и вернемся к нашему алгоритму.
Представьте карту городов, соединённых дорогами. Каждый город можно представить как вершину графа, каждая дорога — как ребро, а расстояние между городами — как вес ребра. Например, рассмотрим такой граф:
A ──1── B
│ │
4 2
│ │
C ──────D
1
Если мы хотим добраться из A в D по кратчайшему пути, то на глаз ответ не всегда очевиден. Именно для решения таких задач и существует алгоритм Дейкстры, который находит кратчайшие пути от одной вершины до всех остальных во взвешенном графе с неотрицательными весами рёбер.
Прежде чем углубляться, стоит уточнить ключевые понятия. Граф — это набор точек (вершин), соединённых линиями (рёбрами). Вес ребра — это число, стоящее на ребре и обозначающее стоимость перехода (расстояние, время, цена и т.п.). Взвешенный граф — это граф, где у каждого ребра есть вес. Кратчайший путь — это маршрут с минимальной суммой весов рёбер. Алгоритм Дейкстры относится к классу жадных алгоритмов: на каждом шаге он выбирает локально лучший вариант, то есть вершину с наименьшим известным расстоянием от старта.
Идею алгоритма можно объяснить простыми словами: вы стоите в начальной точке и хотите узнать расстояния до всех остальных городов. Вы постепенно открываете для себя новые города, всегда переходя сначала в тот, до которого сейчас ближе всего. При этом, попадая в новый город, вы проверяете, не стали ли теперь известные пути до его соседей короче. Этот процесс повторяется, пока не будут обработаны все вершины. Иными словами, на каждом шаге мы идём в ближайший ещё не посещённый город и обновляем расстояния до его соседей.
Рассмотрим работу алгоритма на конкретном примере. Пусть дан граф:
A ──1── B
│ ╱ │
4 2 5
│ ╱ │
C ──1── D
Рёбра и их веса:
- A–B: 1
- A–C: 4
- B–C: 2
- B–D: 5
- C–D: 1
Начальная вершина — A. В начальный момент мы знаем расстояние только до самой себя (ноль), а до всех остальных вершин расстояние полагаем бесконечным. Состояние можно описать так:
Расстояния: A=0, B=∞, C=∞, D=∞
Посещены: {}
Очередь: [(0, A)]
Извлекаем из очереди вершину A с расстоянием 0. Рассматриваем её соседей: до B можно добраться за 0+1=1, что меньше бесконечности, поэтому обновляем расстояние до B. До C можно добраться за 0+4=4, обновляем C. После этого состояния становятся такими:
Расстояния: A=0, B=1, C=4, D=∞
Посещены: {A}
Очередь: [(1, B), (4, C)]
Теперь из очереди выбираем вершину с наименьшим расстоянием — это B (расстояние 1). Из B можно пойти к A (но расстояние 1+1=2 больше уже известного 0, поэтому пропускаем), к C (1+2=3, что меньше текущего 4, обновляем C до 3) и к D (1+5=6, обновляем D с бесконечности до 6). После этого:
Расстояния: A=0, B=1, C=3, D=6
Посещены: {A, B}
Очередь: [(3, C), (4, C_old), (6, D)]
Обратите внимание: в очереди теперь есть два элемента для вершины C: (3, C) и (4, C_old). Это старая запись, которая будет проигнорирована позже.
Следующая ближайшая вершина — C с расстоянием 3. Проверяем соседей: до A (3+4=7 > 0), до B (3+2=5 > 1), до D (3+1=4 < 6) — обновляем D до 4. После обновления:
Расстояния: A=0, B=1, C=3, D=4
Посещены: {A, B, C}
Очередь: [(4, D), (4, C_old), (6, D_old)]
Наконец, извлекаем D с расстоянием 4. Её соседи уже посещены или не дают улучшений. Алгоритм завершается. Итоговые расстояния:
- A = 0
- B = 1
- C = 3
- D = 4
Кратчайшие пути из A:
- A → A : 0
- A → B : A → B (вес 1)
- A → C : A → B → C (1 + 2 = 3)
- A → D : A → B → C → D (1 + 2 + 1 = 4)
🔥1
Теперь разберём реализацию алгоритма на языке Python с использованием модуля heapq, который предоставляет приоритетную очередь. Приоритетная очередь отличается от обычной тем, что всегда возвращает элемент с наименьшим ключом (в нашем случае — расстоянием). Это как раз соответствует жадному выбору ближайшей вершины.
Поясним некоторые детали реализации. Строка
Важно понимать, почему используется именно приоритетная очередь. Если бы мы каждый раз искали минимум простым перебором, сложность стала бы квадратичной. Благодаря этому мы получаем эффективность: каждая операция извлечения минимума и вставки стоит O(log V), где V — число вершин.
Сложность алгоритма Дейкстры с приоритетной очередью составляет O((V + E) log V), где V — количество вершин, E — количество рёбер. Для большинства реальных задач, таких как прокладка маршрутов на карте или в сетях, это приемлемо быстро.
Однако у алгоритма Дейкстры есть важное ограничение: он работает только с неотрицательными весами рёбер. Почему это так? Дело в том, что алгоритм основан на гарантии: когда вершина извлекается из очереди с минимальным расстоянием, это расстояние уже окончательное и не может быть улучшено позже. Если бы существовали отрицательные рёбра, то путь через другую вершину, ещё не обработанную, мог бы дать меньшее расстояние, даже если текущая вершина уже «закрыта». Рассмотрим простой пример:
Дейкстра из A сначала установит расстояния: B=2, C=4. Затем извлечёт B (расстояние 2) и пометит его как финальное. При обработке B он обновит C: 2 + (−5) = −3, и это станет новым расстоянием до C. Однако теперь уже поздно пересматривать пути через другие вершины, потому что B уже обработан. В этом конкретном случае мы всё же получим правильный ответ, но в более сложных графах с отрицательными весами могут возникнуть ситуации, когда оптимальный путь требует пересмотра уже обработанных вершин, что невозможно в рамках алгоритма Дейкстры. Более того, отрицательные веса могут создавать циклы с отрицательной суммой, которые делают понятие кратчайшего пути вообще неопределённым (можно бесконечно уменьшать стоимость, обходя цикл).
Если в графе присутствуют отрицательные веса, следует использовать алгоритм Беллмана–Форда. Он не полагается на жадный выбор и не делает предположений о финальности расстояний. Вместо этого алгоритм выполняет V−1 проходов по всем рёбрам, каждый раз пытаясь улучшить расстояния. Вот его простая реализация:
import heapq # Модуль для приоритетной очереди (мин-куча)
def dijkstra(graph, start):
# 1. Инициализация: все расстояния = бесконечность
distances = {node: float("infinity") for node in graph}
distances[start] = 0 # До стартовой вершины — 0
# 2. Приоритетная очередь: (расстояние, вершина)
# heapq всегда отдаёт элемент с МИНИМАЛЬНЫМ расстоянием первым
priority_queue = [(0, start)]
while priority_queue:
# 3. Извлекаем вершину с наименьшим расстоянием
current_distance, current_node = heapq.heappop(priority_queue)
# 4. Устаревшая запись? Пропускаем
# (в очереди могут быть старые версии с большим расстоянием)
if current_distance > distances[current_node]:
continue
# 5. Обходим соседей
for neighbor, weight in graph[current_node].items():
distance = current_distance + weight
# 6. Нашли более короткий путь? Обновляем!
if distance < distances[neighbor]:
distances[neighbor] = distance
heapq.heappush(priority_queue, (distance, neighbor))
return distances
Поясним некоторые детали реализации. Строка
if current_distance > distances[current_node]: continue необходима для отбрасывания устаревших записей в очереди. Когда мы обновляем расстояние до вершины (например, C с 4 на 3), старая запись (4, C) остаётся в куче. Когда она позже извлекается, мы проверяем, что её расстояние больше текущего известного, и просто пропускаем её. Это экономит время и корректирует работу алгоритма.Важно понимать, почему используется именно приоритетная очередь. Если бы мы каждый раз искали минимум простым перебором, сложность стала бы квадратичной. Благодаря этому мы получаем эффективность: каждая операция извлечения минимума и вставки стоит O(log V), где V — число вершин.
Сложность алгоритма Дейкстры с приоритетной очередью составляет O((V + E) log V), где V — количество вершин, E — количество рёбер. Для большинства реальных задач, таких как прокладка маршрутов на карте или в сетях, это приемлемо быстро.
Однако у алгоритма Дейкстры есть важное ограничение: он работает только с неотрицательными весами рёбер. Почему это так? Дело в том, что алгоритм основан на гарантии: когда вершина извлекается из очереди с минимальным расстоянием, это расстояние уже окончательное и не может быть улучшено позже. Если бы существовали отрицательные рёбра, то путь через другую вершину, ещё не обработанную, мог бы дать меньшее расстояние, даже если текущая вершина уже «закрыта». Рассмотрим простой пример:
A ──2── B ──(−5)── C
A ─────────4───── C
Дейкстра из A сначала установит расстояния: B=2, C=4. Затем извлечёт B (расстояние 2) и пометит его как финальное. При обработке B он обновит C: 2 + (−5) = −3, и это станет новым расстоянием до C. Однако теперь уже поздно пересматривать пути через другие вершины, потому что B уже обработан. В этом конкретном случае мы всё же получим правильный ответ, но в более сложных графах с отрицательными весами могут возникнуть ситуации, когда оптимальный путь требует пересмотра уже обработанных вершин, что невозможно в рамках алгоритма Дейкстры. Более того, отрицательные веса могут создавать циклы с отрицательной суммой, которые делают понятие кратчайшего пути вообще неопределённым (можно бесконечно уменьшать стоимость, обходя цикл).
Если в графе присутствуют отрицательные веса, следует использовать алгоритм Беллмана–Форда. Он не полагается на жадный выбор и не делает предположений о финальности расстояний. Вместо этого алгоритм выполняет V−1 проходов по всем рёбрам, каждый раз пытаясь улучшить расстояния. Вот его простая реализация:
🔥1
def bellman_ford(graph, start):
distances = {node: float("infinity") for node in graph}
distances[start] = 0
for _ in range(len(graph) - 1): # V-1 итераций
for node in graph:
for neighbor, weight in graph[node].items():
if distances[node] + weight < distances[neighbor]:
distances[neighbor] = distances[node] + weight
return distances
Сложность Беллмана–Форда выше — O(V·E), но он способен обнаруживать отрицательные циклы и, соответственно, определять, что задача не имеет решения. Сравним два подхода:
- Дейкстра: работает только с неотрицательными весами, быстрее (O((V+E) log V)).
- Беллман–Форд: работает с любыми весами, медленнее (O(V·E)), может обнаруживать отрицательные циклы.
В реальной жизни алгоритм Дейкстра широко применяется. Например, в GPS-навигаторах (Google Maps, Яндекс.Карты) города или перекрёстки — это вершины, дороги — рёбра, а весом может быть время в пути. Алгоритм находит маршрут с минимальным временем. В интернете протоколы маршрутизации, такие как OSPF, используют алгоритм Дейкстры для определения кратчайшего пути передачи пакетов данных (вершины — роутеры, рёбра — каналы связи, вес — задержка или пропускная способность). В игровых движках NPC (неигровые персонажи) находят путь по карте с препятствиями. В системах поиска авиабилетов вершинами выступают аэропорты, рёбрами — рейсы, а весом — стоимость или время, что позволяет находить самые дешёвые или быстрые маршруты с пересадками.
#algorithm
👍3🔥1
Разбор репо с Copilot
Пока не успеваю написать следующий пост про алгоритмы, хочу поделиться с вами прикольным способом изучать репо. Вероятно, многие из вас уже знают об этом, но другим этот вариант может быть будет полезен.
P.S. Вероятнее всего, будет работать с изменением локации через сторонние сервисы.
Когда вы заходите на страницу проекта на GitHub через компьютер или ноутбук, то в правом верхнем углу есть иконка Copilot - ИИ агента от Microsoft. При нажатии на эту кнопку открывается страница с чатом, где пользователь может задавать свои вопросы по архитектуре и коду проекта. Для ответов используется достойная модель Claude Haiku 4.5 (но можно выбрать и другие).
Самое прикольное то, что бот имеет доступ к коммитам репо, т.е. вы можете использовать его для изучения изменений в коде.
Лимиты, скорее всего, есть, при этом мне его хватало всегда для достаточно хорошего разбора архитектуры.
При изучении Solidity это может стать очень удобным инструментом для изучения кода протокола в общем и целом, а также его конкретных частей кода.
Таким способом я сейчас изучаю опенсорсные проекты с агентами (тот же нашумевший OpenClaw).
#copilot
Пока не успеваю написать следующий пост про алгоритмы, хочу поделиться с вами прикольным способом изучать репо. Вероятно, многие из вас уже знают об этом, но другим этот вариант может быть будет полезен.
P.S. Вероятнее всего, будет работать с изменением локации через сторонние сервисы.
Когда вы заходите на страницу проекта на GitHub через компьютер или ноутбук, то в правом верхнем углу есть иконка Copilot - ИИ агента от Microsoft. При нажатии на эту кнопку открывается страница с чатом, где пользователь может задавать свои вопросы по архитектуре и коду проекта. Для ответов используется достойная модель Claude Haiku 4.5 (но можно выбрать и другие).
Самое прикольное то, что бот имеет доступ к коммитам репо, т.е. вы можете использовать его для изучения изменений в коде.
Лимиты, скорее всего, есть, при этом мне его хватало всегда для достаточно хорошего разбора архитектуры.
При изучении Solidity это может стать очень удобным инструментом для изучения кода протокола в общем и целом, а также его конкретных частей кода.
Таким способом я сейчас изучаю опенсорсные проекты с агентами (тот же нашумевший OpenClaw).
#copilot
👍8🔥1
Алгоритмы. Жадные алгоритмы
Представьте себе, что вы стоите перед шведским столом и хотите утолить голод максимально быстро и эффективно. Вместо того чтобы тщательно продумывать последовательность блюд, вы просто каждый раз выбираете то, что кажется самым сытным в данный момент. Эта интуитивная стратегия, когда вы делаете лучший выбор прямо сейчас, не заглядывая далеко в будущее, и лежит в основе жадных алгоритмов. Формально, жадный алгоритм — это подход, при котором на каждом шаге решения принимается локально оптимальный выбор, то есть наилучший из доступных вариантов на текущий момент, в надежде, что итоговое решение окажется глобально оптимальным, то есть наилучшим для всей задачи в целом.
Важно понимать, что жадные алгоритмы работают безошибочно далеко не для всех задач. Их успех гарантирован только для тех задач, которые обладают особым свойством, о котором мы поговорим ниже.
Чтобы лучше понять механику, нужно разобраться с двумя ключевыми понятиями. Локально оптимальный выбор — это лучший вариант, который виден непосредственно на данном шаге, без учета долгосрочных последствий. Представьте, что вы идете по лесу и на каждом перекрестке выбираете ту тропинку, которая кажется короче, не зная всего маршрута заранее. Глобально оптимальное решение — это наилучший результат по итогу всей задачи, например, самый короткий путь из точки А в точку Б, известный по полной карте местности. Задача поддается жадному алгоритму, если она обладает свойством жадного выбора (Greedy Choice Property). Это означает, что локально оптимальный выбор на каждом шаге гарантированно приведет к глобально оптимальному итогу.
Классическим примером применения жадной стратегии является задача о сдаче (Coin Change). Представьте, что вам нужно набрать заданную сумму минимальным количеством монет, имея неограниченный запас монет определенных номиналов. Жадный подход здесь предельно прост: на каждом шаге нужно брать наибольшую монету, которая не превышает оставшуюся сумму. Рассмотрим это на примере: у нас есть сумма 63 и монеты номиналом 1, 2, 5, 10 и 25. Логика работы будет следующей: мы начинаем с самой крупной монеты (25) и проверяем, можем ли мы ее взять. Остаток после первого шага — 38, мы снова берем 25, получая остаток 13. Далее 25 уже не подходит, поэтому берем 10 (остаток 3), затем 2 (остаток 1) и, наконец, 1. В итоге мы получаем набор из пяти монет [25, 25, 10, 2, 1]. Эту логику реализует следующий код:
Пример 1
В этом коде сначала монеты сортируются по убыванию, чтобы начинать с самых крупных. Затем в цикле для каждого номинала мы, пока это возможно, вычитаем его из оставшейся суммы и добавляем в результат. Если в конце сумма обнуляется, мы возвращаем список монет; в противном случае задача не имеет решения с данным набором номиналов.
Однако крайне важно помнить, что жадный алгоритм для размена монет работает не всегда. Классический пример провала — набор номиналов
Представьте себе, что вы стоите перед шведским столом и хотите утолить голод максимально быстро и эффективно. Вместо того чтобы тщательно продумывать последовательность блюд, вы просто каждый раз выбираете то, что кажется самым сытным в данный момент. Эта интуитивная стратегия, когда вы делаете лучший выбор прямо сейчас, не заглядывая далеко в будущее, и лежит в основе жадных алгоритмов. Формально, жадный алгоритм — это подход, при котором на каждом шаге решения принимается локально оптимальный выбор, то есть наилучший из доступных вариантов на текущий момент, в надежде, что итоговое решение окажется глобально оптимальным, то есть наилучшим для всей задачи в целом.
Шаг 1 → выбрать лучшее из доступного
Шаг 2 → снова выбрать лучшее из доступного
Шаг 3 → снова выбрать лучшее из доступного
...
Конец → надеемся, что итог — оптимальный
Важно понимать, что жадные алгоритмы работают безошибочно далеко не для всех задач. Их успех гарантирован только для тех задач, которые обладают особым свойством, о котором мы поговорим ниже.
Чтобы лучше понять механику, нужно разобраться с двумя ключевыми понятиями. Локально оптимальный выбор — это лучший вариант, который виден непосредственно на данном шаге, без учета долгосрочных последствий. Представьте, что вы идете по лесу и на каждом перекрестке выбираете ту тропинку, которая кажется короче, не зная всего маршрута заранее. Глобально оптимальное решение — это наилучший результат по итогу всей задачи, например, самый короткий путь из точки А в точку Б, известный по полной карте местности. Задача поддается жадному алгоритму, если она обладает свойством жадного выбора (Greedy Choice Property). Это означает, что локально оптимальный выбор на каждом шаге гарантированно приведет к глобально оптимальному итогу.
Классическим примером применения жадной стратегии является задача о сдаче (Coin Change). Представьте, что вам нужно набрать заданную сумму минимальным количеством монет, имея неограниченный запас монет определенных номиналов. Жадный подход здесь предельно прост: на каждом шаге нужно брать наибольшую монету, которая не превышает оставшуюся сумму. Рассмотрим это на примере: у нас есть сумма 63 и монеты номиналом 1, 2, 5, 10 и 25. Логика работы будет следующей: мы начинаем с самой крупной монеты (25) и проверяем, можем ли мы ее взять. Остаток после первого шага — 38, мы снова берем 25, получая остаток 13. Далее 25 уже не подходит, поэтому берем 10 (остаток 3), затем 2 (остаток 1) и, наконец, 1. В итоге мы получаем набор из пяти монет [25, 25, 10, 2, 1]. Эту логику реализует следующий код:
Пример 1
В этом коде сначала монеты сортируются по убыванию, чтобы начинать с самых крупных. Затем в цикле для каждого номинала мы, пока это возможно, вычитаем его из оставшейся суммы и добавляем в результат. Если в конце сумма обнуляется, мы возвращаем список монет; в противном случае задача не имеет решения с данным набором номиналов.
Однако крайне важно помнить, что жадный алгоритм для размена монет работает не всегда. Классический пример провала — набор номиналов
[1, 3, 4] для суммы 6. Жадный алгоритм, следуя своей логике, сначала возьмет монету 4, затем две монеты по 1, получив в итоге три монеты [4, 1, 1]. В то время как оптимальное решение — это всего две монеты: [3, 3]. Почему так происходит? Потому что жадный алгоритм, "увидев" самую крупную монету 4, жадно взял её, не предусмотрев, что это помешает использовать более выгодную комбинацию из двух троек. Набор номиналов [1, 3, 4] не обладает свойством жадного выбора, в отличие от, скажем, стандартных монет США [1, 5, 10, 25]. Другой наглядный пример — набор [1, 6, 10] для суммы 12. Жадный подход даст три монеты [10, 1, 1], хотя оптимальных решения — две монеты по 6. Таким образом, жадный алгоритм для задачи о сдаче дает верный результат только для так называемых канонических систем номиналов, подобных реальным валютам. Для произвольных наборов монет необходимо применять другие методы, например, динамическое программирование.🔥1
Другая известная задача, где жадный подход блестяще работает, — это задача о выборе заявок (Activity Selection Problem). Представьте, что у вас есть множество мероприятий, каждое из которых имеет время начала и окончания. Вам нужно выбрать максимальное количество непересекающихся мероприятий, то есть таких, которые не накладываются друг на друга по времени. Жадная стратегия здесь заключается в сортировке всех мероприятий по времени окончания. Логика проста: чем раньше заканчивается текущее мероприятие, тем больше времени остается для всех последующих. Рассмотрим мероприятия: А (1-4), В (2-6), С (5-8), D (7-9) и Е (3-5). Отсортировав их по времени конца, получим последовательность: А(1-4), Е(3-5), В(2-6), С(5-8), D(7-9). Первым мы всегда берем мероприятие, которое заканчивается раньше всех — это А. Его конец в 4. Далее мы пропускаем все мероприятия, которые начинаются раньше или в момент 4 (это Е и В), так как они пересекаются с А. Следующее подходящее — С, начинающееся в 5, что позже 4, поэтому мы берем его. После С с концом в 8, мероприятие D (начало в 7) пересекается с ним и не подходит. В итоге получаем набор из двух мероприятий
Пример 2
Еще одним ярким примером жадного подхода является алгоритм Хаффмана, используемый для сжатия данных. Идея сжатия заключается в том, чтобы представить символы не фиксированным количеством бит (например, 8), а переменным: частым символам давать короткие коды, а редким — длинные. Возьмем строку
Пример 3
В итоге, можно сказать, что жадный алгоритм — это мощный и элегантный метод, идея которого заключается в принятии последовательных локально оптимальных решений. Он блестяще работает для таких задач, как размен монет в канонической системе, выбор непересекающихся заявок или сжатие данных по Хаффману. Однако главное правило его применения — это предварительная проверка или доказательство того, что задача обладает свойством жадного выбора. В противном случае алгоритм, будучи примененным формально, скорее всего, даст неверный или неоптимальный результат, как это произошло с нетривиальными наборами монет.
#algorithm
[A, C], что является максимально возможным количеством. Этот подход работает, потому что задача обладает свойством жадного выбора: мероприятие с самым ранним окончанием всегда входит в какое-либо оптимальное расписание. Это можно строго доказать, показав, что если в оптимальном решении первым стоит не самое раннее мероприятие, его можно заменить на самое раннее, не ухудшив результат. Реализуется алгоритм следующим образом:Пример 2
Еще одним ярким примером жадного подхода является алгоритм Хаффмана, используемый для сжатия данных. Идея сжатия заключается в том, чтобы представить символы не фиксированным количеством бит (например, 8), а переменным: частым символам давать короткие коды, а редким — длинные. Возьмем строку
"aaaaabbc", где 'a' встречается 5 раз, 'b' — 2, а 'c' — 1. При стандартном кодировании каждый символ занял бы 3 бита, и вся строка — 24 бита. Оптимальное кодирование может быть таким: a='0' (1 бит), b='10' (2 бита), c='11' (2 бита). Тогда строка займет всего 5*1 + 2*2 + 1*2 = 11 бит. Алгоритм Хаффмана строит дерево кодирования, где путь от корня до символа определяет его код (0 — переход к левому потомку, 1 — к правому). Его жадная стратегия заключается в следующем: на каждом шаге два символа (или группы символов) с наименьшими частотами объединяются в один узел-родитель, чья частота равна сумме частот потомков. Начнем с отдельных узлов: [a:5], [b:2], [c:1]. На первом шаге выбираем самые редкие — b и c — и объединяем их в узел [bc:3] с двумя потомками. Теперь у нас есть узлы [a:5] и [bc:3]. Снова выбираем два с наименьшей частотой (a и bc) и объединяем их в корень дерева [abc:8]. После этого, двигаясь от корня к листьям и присваивая левым ветвям 0, а правым — 1, мы получим коды: a=0, b=10, c=11. Это жадный алгоритм, так как на каждом шаге мы, не думая о будущей структуре дерева, делаем локально наилучший выбор — объединяем два самых непопулярных элемента, что в итоге и гарантирует минимальную общую длину кода.Пример 3
В итоге, можно сказать, что жадный алгоритм — это мощный и элегантный метод, идея которого заключается в принятии последовательных локально оптимальных решений. Он блестяще работает для таких задач, как размен монет в канонической системе, выбор непересекающихся заявок или сжатие данных по Хаффману. Однако главное правило его применения — это предварительная проверка или доказательство того, что задача обладает свойством жадного выбора. В противном случае алгоритм, будучи примененным формально, скорее всего, даст неверный или неоптимальный результат, как это произошло с нетривиальными наборами монет.
#algorithm
👍3❤2🔥1
Алгоритмы. Динамическое программирование
Динамическое программирование (ДП) — это метод решения сложных задач путем разбиения их на более простые подзадачи, с тем важным условием, что эти подзадачи перекрываются. Представь, что тебе нужно посчитать количество возможных маршрутов из левого верхнего угла сетки в правый нижний. В процессе подсчета ты заметишь, что постоянно пересчитываешь одни и те же участки пути. Динамическое программирование предлагает элегантное решение: вместо того чтобы вычислять одно и то же многократно, мы сохраняем результат каждой подзадачи и используем его как строительный блок для решения более крупных задач. Формально говоря, этот подход работает в три этапа: задача разбивается на перекрывающиеся подзадачи (одни и те же маленькие задачи встречаются в решении снова и снова), каждая подзадача решается ровно один раз, а её результат сохраняется и переиспользуется при необходимости. Именно наличие перекрывающихся подзадач — верный сигнал о том, что ДП применимо.
Чтобы понять, почему без ДП возникают проблемы, рассмотрим классический пример — вычисление чисел Фибоначчи, где каждое следующее число является суммой двух предыдущих. При наивном рекурсивном подходе мы сталкиваемся с катастрофической неэффективностью. Например, при вычислении F(5) дерево вызовов будет выглядеть так: F(5) раскладывается на F(4) и F(3), те в свою очередь на свои составляющие, и в итоге F(3) вычисляется дважды, а F(2) — целых три раза. При росте n количество повторных вычислений взрывается, и сложность алгоритма становится экспоненциальной — O(2ⁿ). Динамическое программирование решает эту проблему кардинально: «посчитал F(3) — запиши, понадобился снова — возьми из записей».
Существует два основных способа реализовать эту идею. Первый способ — мемоизация, или подход «сверху вниз» (top-down). Это всё та же рекурсия, но с использованием блокнота (кэша, обычно словаря). Перед тем как вычислить значение, функция проверяет: «А я это уже считал?». Если ответ найден в словаре, она сразу его возвращает, избегая повторных вычислений. Каждое уникальное значение вычисляется строго один раз.
Второй способ — табуляция, или подход «снизу вверх» (bottom-up). Здесь мы отказываемся от рекурсии и начинаем строить решение с самых маленьких, очевидных подзадач, постепенно заполняя таблицу (обычно массив) и двигаясь к искомому результату. Мы точно знаем, что для вычисления следующего значения нам нужны только предыдущие, поэтому просто идем по порядку.
Для вычисления числа Фибоначчи мы можем пойти дальше и оптимизировать использование памяти. Так как для текущего значения нужны только два предыдущих, можно хранить лишь их, а не всю таблицу. Это снижает затраты памяти с O(n) до O(1).
Динамическое программирование (ДП) — это метод решения сложных задач путем разбиения их на более простые подзадачи, с тем важным условием, что эти подзадачи перекрываются. Представь, что тебе нужно посчитать количество возможных маршрутов из левого верхнего угла сетки в правый нижний. В процессе подсчета ты заметишь, что постоянно пересчитываешь одни и те же участки пути. Динамическое программирование предлагает элегантное решение: вместо того чтобы вычислять одно и то же многократно, мы сохраняем результат каждой подзадачи и используем его как строительный блок для решения более крупных задач. Формально говоря, этот подход работает в три этапа: задача разбивается на перекрывающиеся подзадачи (одни и те же маленькие задачи встречаются в решении снова и снова), каждая подзадача решается ровно один раз, а её результат сохраняется и переиспользуется при необходимости. Именно наличие перекрывающихся подзадач — верный сигнал о том, что ДП применимо.
Чтобы понять, почему без ДП возникают проблемы, рассмотрим классический пример — вычисление чисел Фибоначчи, где каждое следующее число является суммой двух предыдущих. При наивном рекурсивном подходе мы сталкиваемся с катастрофической неэффективностью. Например, при вычислении F(5) дерево вызовов будет выглядеть так: F(5) раскладывается на F(4) и F(3), те в свою очередь на свои составляющие, и в итоге F(3) вычисляется дважды, а F(2) — целых три раза. При росте n количество повторных вычислений взрывается, и сложность алгоритма становится экспоненциальной — O(2ⁿ). Динамическое программирование решает эту проблему кардинально: «посчитал F(3) — запиши, понадобился снова — возьми из записей».
Существует два основных способа реализовать эту идею. Первый способ — мемоизация, или подход «сверху вниз» (top-down). Это всё та же рекурсия, но с использованием блокнота (кэша, обычно словаря). Перед тем как вычислить значение, функция проверяет: «А я это уже считал?». Если ответ найден в словаре, она сразу его возвращает, избегая повторных вычислений. Каждое уникальное значение вычисляется строго один раз.
def fibonacci_dp(n, memo=None):
"""Вычисление чисел Фибоначчи с помощью ДП (мемоизация)."""
if memo is None:
memo = {}
if n in memo:
return memo[n]
if n <= 1:
return n
memo[n] = fibonacci_dp(n - 1, memo) + fibonacci_dp(n - 2, memo)
return memo[n]
print(fibonacci_dp(10)) # 55
Второй способ — табуляция, или подход «снизу вверх» (bottom-up). Здесь мы отказываемся от рекурсии и начинаем строить решение с самых маленьких, очевидных подзадач, постепенно заполняя таблицу (обычно массив) и двигаясь к искомому результату. Мы точно знаем, что для вычисления следующего значения нам нужны только предыдущие, поэтому просто идем по порядку.
def fibonacci_tabulation(n):
"""Вычисление чисел Фибоначчи с помощью ДП (табуляция)."""
if n <= 1:
return n
dp = [0] * (n + 1)
dp[0] = 0
dp[1] = 1
for i in range(2, n + 1):
dp[i] = dp[i - 1] + dp[i - 2]
return dp[n]
print(fibonacci_tabulation(10)) # 55
Для вычисления числа Фибоначчи мы можем пойти дальше и оптимизировать использование памяти. Так как для текущего значения нужны только два предыдущих, можно хранить лишь их, а не всю таблицу. Это снижает затраты памяти с O(n) до O(1).
def fibonacci_optimized(n):
if n <= 1:
return n
prev2, prev1 = 0, 1
for _ in range(2, n + 1):
current = prev1 + prev2
prev2 = prev1
prev1 = current
return prev1
print(fibonacci_optimized(10)) # 55
❤2🔥1
Важно понимать разницу между динамическим программированием и подходом «Разделяй и властвуй». Оба метода дробят задачу, но делают это по-разному. В «Разделяй и властвуй» подзадачи независимы и не перекрываются — каждая решается отдельно и больше не встречается. Классический пример — сортировка слиянием (Merge Sort), где массив делится на независимые половины, которые сортируются сами по себе и никогда не влияют на вычисление друг друга. В динамическом программировании подзадачи обязательно перекрываются: результат одной и той же маленькой задачи требуется при решении нескольких более крупных. Правило выбора подхода простое: если подзадачи перекрываются — используем ДП, если нет — «Разделяй и властвуй».
Классической задачей на ДП является задача о рюкзаке (Knapsack problem). Представь, что у тебя есть рюкзак вместимостью W и набор из n предметов, каждый из которых имеет свой вес w[i] и ценность v[i]. Цель — набрать предметы так, чтобы их суммарная ценность была максимальной, а суммарный вес не превысил W. Например, при вместимости рюкзака W = 7 и предметах с весами и ценностями (1, 1), (3, 4), (4, 5), (5, 7) лучшим выбором будут предметы 2 и 3 (вес 3+4=7, ценность 4+5=9). Почему это задача ДП? Потому что при решении вопроса «брать или не брать предмет i» мы приходим к подзадачам, которые будут переиспользоваться. Если мы берем предмет, нам нужно решить ту же задачу для оставшихся предметов с вместимостью W - w[i]. Если не берем — для оставшихся предметов с той же вместимостью W. Эти подзадачи постоянно повторяются в разных комбинациях. Решается задача методом табуляции. Мы создаем таблицу dp[i][w], где значение в ячейке — это максимальная ценность, которую можно получить, используя первые i предметов при вместимости рюкзака w. Логика заполнения таблицы такова: если вес текущего предмета больше текущей вместимости w, он просто не помещается, и мы берем значение сверху (без этого предмета): dp[i][w] = dp[i-1][w]. Если же предмет помещается, у нас есть два варианта: не брать его (dp[i-1][w]) или взять, добавив его ценность к оптимальному решению для оставшегося места (dp[i-1][w - w_i] + v_i). Выбираем максимум.
Временная сложность этого алгоритма составляет O(n × W), что называется псевдополиномиальной, так как зависит не только от количества предметов, но и от значения вместимости W.
Итак, резюмируя, динамическое программирование — это мощный инструмент, который подходит для задач, обладающих двумя ключевыми свойствами: оптимальной подструктурой (решение большой задачи строится из решений подзадач) и перекрывающимися подзадачами (одни и те же подзадачи решаются многократно). В зависимости от контекста мы можем использовать либо нисходящее рекурсивное решение с кэшированием (мемоизация), либо восходящее итеративное заполнение таблицы (табуляция). Это принципиально отличает ДП от подхода «Разделяй и властвуй», где подзадачи всегда независимы.
#algorithm
Классической задачей на ДП является задача о рюкзаке (Knapsack problem). Представь, что у тебя есть рюкзак вместимостью W и набор из n предметов, каждый из которых имеет свой вес w[i] и ценность v[i]. Цель — набрать предметы так, чтобы их суммарная ценность была максимальной, а суммарный вес не превысил W. Например, при вместимости рюкзака W = 7 и предметах с весами и ценностями (1, 1), (3, 4), (4, 5), (5, 7) лучшим выбором будут предметы 2 и 3 (вес 3+4=7, ценность 4+5=9). Почему это задача ДП? Потому что при решении вопроса «брать или не брать предмет i» мы приходим к подзадачам, которые будут переиспользоваться. Если мы берем предмет, нам нужно решить ту же задачу для оставшихся предметов с вместимостью W - w[i]. Если не берем — для оставшихся предметов с той же вместимостью W. Эти подзадачи постоянно повторяются в разных комбинациях. Решается задача методом табуляции. Мы создаем таблицу dp[i][w], где значение в ячейке — это максимальная ценность, которую можно получить, используя первые i предметов при вместимости рюкзака w. Логика заполнения таблицы такова: если вес текущего предмета больше текущей вместимости w, он просто не помещается, и мы берем значение сверху (без этого предмета): dp[i][w] = dp[i-1][w]. Если же предмет помещается, у нас есть два варианта: не брать его (dp[i-1][w]) или взять, добавив его ценность к оптимальному решению для оставшегося места (dp[i-1][w - w_i] + v_i). Выбираем максимум.
def knapsack(weights, values, W):
"""
Решение задачи о рюкзаке методом ДП (табуляция).
weights — список весов предметов
values — список ценностей предметов
W — вместимость рюкзака
"""
n = len(weights)
dp = [[0] * (W + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
w_i = weights[i - 1]
v_i = values[i - 1]
for w in range(W + 1):
dp[i][w] = dp[i - 1][w]
if w_i <= w:
dp[i][w] = max(dp[i][w], dp[i - 1][w - w_i] + v_i)
return dp[n][W]
weights = [1, 3, 4, 5]
values = [1, 4, 5, 7]
W = 7
print(knapsack(weights, values, W)) # 9
Временная сложность этого алгоритма составляет O(n × W), что называется псевдополиномиальной, так как зависит не только от количества предметов, но и от значения вместимости W.
Итак, резюмируя, динамическое программирование — это мощный инструмент, который подходит для задач, обладающих двумя ключевыми свойствами: оптимальной подструктурой (решение большой задачи строится из решений подзадач) и перекрывающимися подзадачами (одни и те же подзадачи решаются многократно). В зависимости от контекста мы можем использовать либо нисходящее рекурсивное решение с кэшированием (мемоизация), либо восходящее итеративное заполнение таблицы (табуляция). Это принципиально отличает ДП от подхода «Разделяй и властвуй», где подзадачи всегда независимы.
#algorithm
👍5🔥1
Wallet-centric Web3
Нашел недавно небольшую статью о намечающейся парадигме в мире web3, где ключевую роль будут играть именно кошельки, а не сами смарт контракты и сети. Прилагаю ее перевод.
Представь себе, как устроен твой обычный день в Web3. Скорее всего, это выглядит так: ты открываешь браузер, находишь нужный сайт децентрализованного приложения, нажимаешь «Подключить кошелек», видишь всплывающее окно, подписываешь сообщение, а затем еще и подтверждаешь транзакцию. А если это взаимодействие с ликвидностью, то добавляется еще и одобрение токена. Это та реальность, в которой мы жили последние годы, и для многих она стала привычной, хоть и не самой удобной. Но сейчас в индустрии назревает фундаментальный сдвиг, который перевернет этот опыт с ног на голову. Речь о концепции wallet-centric Web3, где кошелек перестает быть просто пассивным инструментом для подписи и превращается в настоящий центр пользовательской вселенной.
В старой парадигме кошелек был лишь придатком к сайту, необходимым звеном в цепочке «пользователь — сайт — всплывающее окно — контракт». Сайт диктовал условия, а кошелек покорно подчинялся. В новой модели всё иначе: пользователь живет внутри кошелька. Само приложение кошелька становится операционной системой, а dApp — всего лишь модулем или плагином внутри нее. Это как перейти от модели, где каждая программа требует отдельного включения компьютера, к смартфону, где все приложения всегда под рукой на одном экране.
Почему же мы движемся именно в эту сторону? Главная причина — катастрофический пользовательский опыт классических dApp. Для обычного человека, не погруженного в крипто-культуру, каждый шаг с попапами и подписями — это испытание. Wallet-centric подход решает эту проблему, предлагая единый, привычный интерфейс, автоматизацию и меньше отвлекающих действий. Вопрос безопасности здесь также выходит на первый план. Подавляющее большинство атак происходит через фишинговые сайты или поддельные интерфейсы. Когда же все взаимодействия замкнуты внутри проверенного приложения кошелька, поверхность для атак радикально сокращается.
Ключевую роль в этой трансформации играет технология смарт-кошельков и стандарт ERC-4337. Как только кошелек сам становится смарт-контрактом, он обретает суперсилы. Появляется кастомная логика: социальное восстановление, мультиподпись, а главное — сессионные ключи. Теперь кошелек может выдать временный ключ игровому dApp, и все действия внутри игры будут подписываться автоматически, без бесконечных попапов, создавая опыт, неотличимый от Web2. Добавьте сюда абстракцию газа: кошелек может сам оплачивать комиссии, использовать paymaster или батчить транзакции. Пользователь может вообще забыть о существовании газа. В такой архитектуре кошелек становится не просто хранилищем средств, а цифровой идентичностью, репутацией и профилем пользователя.
Экономическая модель Web3 тоже претерпевает изменения. Если кошелек — это центр, то он контролирует доступ пользователя к приложениям, порядок транзакций и, что самое важное, интерфейс. Это открывает эру монетизации на уровне кошелька. Кошелек может получать комиссии за роутинг свапов, за порядок исполнения транзакций или за решение интентов. Появляется новый тип dApp — wallet-native. Это приложения, у которых может вообще не быть веб-сайта. Пользователь просто открывает кошелек, нажимает на нужное действие и получает результат. Всё взаимодействие происходит внутри.
Это колоссальный сдвиг, который перераспределяет власть в индустрии. Раньше доминировали протоколы, теперь же на первый план выходят кошельки. Тот, кто контролирует кошелек, контролирует пользователя и его опыт. Это, безусловно, несет и риски. Мы можем прийти к новой централизации, где крупные кошельки, подобно Apple App Store или Google Play, будут диктовать условия разработчикам, контролируя UX, роутинг и доступность приложений. Также возникают риски MEV на уровне кошелька, где он может переставлять транзакции пользователя для своей выгоды.
Нашел недавно небольшую статью о намечающейся парадигме в мире web3, где ключевую роль будут играть именно кошельки, а не сами смарт контракты и сети. Прилагаю ее перевод.
Представь себе, как устроен твой обычный день в Web3. Скорее всего, это выглядит так: ты открываешь браузер, находишь нужный сайт децентрализованного приложения, нажимаешь «Подключить кошелек», видишь всплывающее окно, подписываешь сообщение, а затем еще и подтверждаешь транзакцию. А если это взаимодействие с ликвидностью, то добавляется еще и одобрение токена. Это та реальность, в которой мы жили последние годы, и для многих она стала привычной, хоть и не самой удобной. Но сейчас в индустрии назревает фундаментальный сдвиг, который перевернет этот опыт с ног на голову. Речь о концепции wallet-centric Web3, где кошелек перестает быть просто пассивным инструментом для подписи и превращается в настоящий центр пользовательской вселенной.
В старой парадигме кошелек был лишь придатком к сайту, необходимым звеном в цепочке «пользователь — сайт — всплывающее окно — контракт». Сайт диктовал условия, а кошелек покорно подчинялся. В новой модели всё иначе: пользователь живет внутри кошелька. Само приложение кошелька становится операционной системой, а dApp — всего лишь модулем или плагином внутри нее. Это как перейти от модели, где каждая программа требует отдельного включения компьютера, к смартфону, где все приложения всегда под рукой на одном экране.
Почему же мы движемся именно в эту сторону? Главная причина — катастрофический пользовательский опыт классических dApp. Для обычного человека, не погруженного в крипто-культуру, каждый шаг с попапами и подписями — это испытание. Wallet-centric подход решает эту проблему, предлагая единый, привычный интерфейс, автоматизацию и меньше отвлекающих действий. Вопрос безопасности здесь также выходит на первый план. Подавляющее большинство атак происходит через фишинговые сайты или поддельные интерфейсы. Когда же все взаимодействия замкнуты внутри проверенного приложения кошелька, поверхность для атак радикально сокращается.
Ключевую роль в этой трансформации играет технология смарт-кошельков и стандарт ERC-4337. Как только кошелек сам становится смарт-контрактом, он обретает суперсилы. Появляется кастомная логика: социальное восстановление, мультиподпись, а главное — сессионные ключи. Теперь кошелек может выдать временный ключ игровому dApp, и все действия внутри игры будут подписываться автоматически, без бесконечных попапов, создавая опыт, неотличимый от Web2. Добавьте сюда абстракцию газа: кошелек может сам оплачивать комиссии, использовать paymaster или батчить транзакции. Пользователь может вообще забыть о существовании газа. В такой архитектуре кошелек становится не просто хранилищем средств, а цифровой идентичностью, репутацией и профилем пользователя.
Экономическая модель Web3 тоже претерпевает изменения. Если кошелек — это центр, то он контролирует доступ пользователя к приложениям, порядок транзакций и, что самое важное, интерфейс. Это открывает эру монетизации на уровне кошелька. Кошелек может получать комиссии за роутинг свапов, за порядок исполнения транзакций или за решение интентов. Появляется новый тип dApp — wallet-native. Это приложения, у которых может вообще не быть веб-сайта. Пользователь просто открывает кошелек, нажимает на нужное действие и получает результат. Всё взаимодействие происходит внутри.
Это колоссальный сдвиг, который перераспределяет власть в индустрии. Раньше доминировали протоколы, теперь же на первый план выходят кошельки. Тот, кто контролирует кошелек, контролирует пользователя и его опыт. Это, безусловно, несет и риски. Мы можем прийти к новой централизации, где крупные кошельки, подобно Apple App Store или Google Play, будут диктовать условия разработчикам, контролируя UX, роутинг и доступность приложений. Также возникают риски MEV на уровне кошелька, где он может переставлять транзакции пользователя для своей выгоды.
❤4