Постановка задачи поиска в строке

Часто приходится сталкиваться со специфическим поиском, так называемым поиском строки (поиском в строке). Пусть есть некоторый текст Т и слово (или образ) W. Необходимо найти первое вхождение этого слова в указанном тексте. Это действие типично для любых систем обработки текстов. (Элементы массивов Т и W – символы некоторого конечного алфавита – например, {0, 1}, или {a, …, z}, или {а, …, я}.)

Наиболее типичным приложением такой задачи является документальный поиск: задан фонд документов, состоящих из последовательности библиографических ссылок, каждая ссылка сопровождается «дескриптором», указывающим тему соответствующей ссылки. Надо найти некоторые ключевые слова, встречающиеся среди дескрипторов. Мог бы иметь место, например, запрос «Программирование» и «Java». Такой запрос можно трактовать следующим образом: существуют ли статьи, обладающие дескрипторами «Программирование» и «Java».

Поиск строки формально определяется следующим образом. Пусть задан массив Т из N элементов и массив W из M элементов, причем 0<M≤N. Поиск строки обнаруживает первое вхождение W в Т, результатом будем считать индекс i, указывающий на первое с начала строки (с начала массива Т) совпадение с образом (словом).
Пример. Требуется найти все вхождения образца W = abaa в текст T=abcabaabcabca.

Образец входит в текст только один раз, со сдвигом S=3, индекс i=4.

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

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

Существует давняя традиция. Под новый год учёные, инженеры, бизнесмены, да все, кому не лень, пытаются предсказать будущее. Блокчейн – это серьёзная технология, или очередное модное словечко? Убьют ли боты в 2017-м мобильные приложения? Перестанет ли в этом году погружение в виртуальную реальность вызывать морскую болезнь?


Телеграф убивает живое общение

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

Есть и еще один тренд, менее заметный, так как его результаты для внешних наблюдателей выглядят не так впечатляюще, но не менее важный — автоматизация машинного обучения. В связи с его стремительным развитием вновь актуальным становится вопрос о том, не будут ли data scientist’ы в конце концов автоматизированы и вытеснены искусственным интеллектом.

Сегодня День защитника Отечества! Всех сопричастных с праздником! Бойцам несущим службу в Вооруженных силах РФ — неизбежного дембеля. А для тех, кто не служил или только собирается отдать долг Родине, под катом любопытный рассказ про умные железяки. Не исключено, если вы шарите в технике, компьютерах и ПО, вам посчастливится не только оттрубить в штабе писарем, но и к чему-нибудь из описанного ниже прикоснуться. Ну и надеюсь, что меня не загребут за разглашение всяческих там государственных секретов.

История — это опыт, который позволяет современному поколению не наступить вновь на грабли. Но в программировании, как и в других активно развивающихся областях, такой идеальный сценарий не всегда возможен. Почему? Потому что появляются новые языки программирования, многие процессы становятся сложнее, а машины умнее. В этой статье я приведу две реальные истории. Что их объединяет? Во-первых, время — все они произошли в СССР; во-вторых, люди — каждая история могла пойти по другому сценарию, если бы главные герои не проявили свои лучшие/худшие человеческие качества; в-третьих, конечно же, программирование, иначе статья была бы просто неуместна в нашем блоге.

В этой статье я хотел бы поделиться своим опытом создания SaaS-сервиса на базе LAMP стека, Postio и доведения сервиса до состояния, когда он стал приносить 3 700 долларов ежемесячно (до обрушения рубля было почти 7 000). Сразу надо сказать, что эта история не имеет ничего общего с инвесторами, с золотой лихорадкой Кремниевой долины и с какой-то сверхсовременной технологией. Просто незамысловатая история от независимого разработчика о создании прибыльного SaaS-сервиса, который может сделать любой. Этот веб-сервис был сделан для внутреннего рынка России, поэтому я перевёл всё на английский и в доллары для удобства (пожалуйста, обратите внимание, что это перевод моей статьи, которая изначально была написана для англоязычной аудитории). Но, с другой стороны, этот опыт является довольно универсальным и может быть применён везде. По сути, это инструкция по созданию проектов такого рода.

Три года назад я решил заняться SMM, и самым простым способом сделать это показалось запустить свою собственную группу в какой-нибудь нише и попытаться развить её. Facebook был уже, мягко говоря, довольно конкурентным на тот момент, поэтому я запустил свою тестовую группу на базе «ВКонтакте». Я выбрал очень популярную нишу, потому что всё, что я хотел, — это научиться, а не доминировать на рынке.

Наверное, я должен немного отвлечься и сказать, что VK.com имел и до сих пор имеет процветающую «экосистему» таких групп, которая приносит прибыль их владельцам. Это — своеобразный рынок, который Facebook прикрыл уже давно. И этот базар является прекрасной средой для обучения и экспериментов.

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

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

В некоторых внутренних системах для быстрого поиска по большому битовому массиву мы в Badoo используем JIT. Это очень интересная и не самая известная тема. И, чтобы исправить такую досадную ситуацию, я перевел полезную статью Элая Бендерски о том, что такое JIT и как его использовать.

Очень часто, созданию базы данных CDR отводится мало места в описаниях настройки. Как правило, все сводится к цитате SQL команд и обещанию, что если кинуть ее в консоль то «все будет ОК».

Развитие мобильного широкополосного доступа выдвигает новые требования к беспроводным сетям. Во-первых, требуется обеспечить стабильное покрытие сетей 3G/4G, особенно в густонаселенных городах с большим трафиком данных, затем – удовлетворить стремительно растущий спрос на интернет-трафик. Однако на пути решения вышеуказанных задач мы сталкиваемся с проблемами, связанными с работой макро базовых станций.

Здравствуй, Хабрахабр. В настоящий момент я работаю над учебным пособием по олимпиадному программированию, один из параграфов которого посвящен динамическому программированию. Ниже приведена выдержка из данного параграфа. Пытаясь объяснить данную тему как можно проще, я постарался сложные моменты сопроводить иллюстрациями. Мне интересно ваше мнение о том, насколько понятным получился данный материал. Также буду рад советам, какие еще задачи стоит включить в данный раздел.

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

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

Такие задачи решают методом динамического программирования, а под самим динамическим программированием понимают сведение задачи к подзадачам.

Примечание. «Зомбирование» в данном контексте — многократное повторение ложной и/или неточной информации.

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

1. Люди замечают вещи, которые уже укрепились в памяти или часто повторяются.
2. Люди склонны замечать и запоминать скорее особенные, причудливые и смешные образы, чем непричудливые или несмешные.
3. Люди склонны замечать изменения.
4. Людей притягивает информация, которая подтверждает их убеждения.
5. Люди склонны лучше замечать ошибки у других, чем у себя.

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

Это телевидение.

Весь двадцатый век фантасты много и талантливо писали об освоении космоса. Герои «Хиуса» подарили человечеству богатства Урановой Голконды, пилот Пиркс работал капитаном космических сухогрузов, по Солнечной системе ходили лидер-контейнероносцы и балкер-трампы, и я уж не говорю про всякую мистику путешествий к таинственным монолитам. Однако 21 век не оправдал надежд. Человечество робко стоит в прихожей Космоса, не выбравшись на постоянной основе дальше земной орбиты. Почему так получилось и на что надеяться тем, кто хотел бы читать в новостях про повышение урожайности марсианских яблонь?

Сегодня без «жести», как вы просили

Уже есть пост про то, как лазер режет с помощью создания миллионов кавитационных пузырей в слое роговицы глаза, и разбор телеметрии с реальной операции по секундам с комментариями действий хирурга. И ещё история операций. Вы задали очень много вопросов. Теперь FAQ про разные сопутствующие вещи.

— Если я посмотрю в сторону во время работы лазера, что случится?

У вас попросту не выйдет. На самом деле сразу после обезболивания глаз прижимается к специальному пневмозахвату. Моргнуть у вас тоже не выйдет из-за фиксации (это небольно и недолго). Единственный момент, где можно серьёзно нарушить ход операции — это сильно дёрнуть головой, серьёзным волевым усилием вытащив её из подголовника. В этом случае операция мгновенно прекратится. Точнее, она прекратится даже до потери захвата (детали ниже).

— Как должна быть подготовлена операционная?

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

В 44-ю годовщину последнего шага человека по Луне, в московской промзоне прогремел взрыв, который ознаменовал выход на новый уровень частного ракетостроения в России. Частная компания и сколковский стартап "Лин индастриал" перешла к огневым испытаниям своего первого жидкостного ракетного двигателя. Испытания закончились взрывом, от которого пострадал непричастный человек.

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

Существуют очень разные прогнозы, но одно ясно точно — компьютерные науки никуда не денутся. Директор Американского центра развития Лизетт Партелоу (Lisette Partelow) в конце своей статьи пишет, что их изучение не привязано к коду как таковому, дает более общий и широкий набор знаний, поэтому по какому бы сценарию ни развивался мир, такие навыки можно будет применить во многих разных профессиях и в будущем.

Сборник вредных советов, составленный по собственным ошибкам и ошибкам моих руководителей, а также руководителей друзей и знакомых.

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

1. Не уважайте мнение экспертов. Хотя, какие там эксперты. Вы же их начальник, а значит и главный эксперт. Во всем! Ваше мнение самое верное! Ваш специалист, что-то предлагает? Нахал! Как он может?! Ведь вы лучше знаете как сделать! Высмейте его прилюдно и приведите убийственные аргументы, доказывающие, что его идея – плохая. Не хватает аргументов? – надавите авторитетом. Всегда найдутся разумные, думающие о своей карьере и лояльные бизнесу люди, которые вас поддержат.
   

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

Но как можно считать себя профессионалом в каком-либо (высокоуровневом) языке, если даже не знаешь, как именно работает процессор, как он выполняет вычисления, эффективным ли способом? Сегодня автоматическое управление памятью становится главной проблемой в большинстве высокоуровневых языков, и многие программисты подходят к её решению без достаточной теоретической базы. Я уверен, что знание низкоуровневых процессов сильно помогает в разработке эффективных высокоуровневых программ.

Введение

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

Довольно часто наблюдается странная ситуация: при скоростном проводе, с роутера раздаётся совсем узенький wifi-канал, не загружающий и половины провода. При этом, хотя формально Wi-Fi, особенно в его ac-версии поддерживает какие-то огромные скорости, при проверке оказывается, что либо Wi-Fi подключается на меньшей скорости, либо подключается, но не выдаёт скорости на практике, либо теряет пакеты, либо всё вместе.

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

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