Эффективные алгоритмы

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

Статья посвящена описанию kd-деревьев и их применению в разработанном методе и алгоритме поиска пересечения луча с треугольниками в оптической системе. Они позволяют уменьшить количество просматриваемых элементов при поиске и, как следствие, ускорить процесс поиска пересечения луча с некоторой областью. Рассмотрены наиболее популярные разновидности деревьев, используемые при компьютерном моделировании, а также сущность, достоинства и недостатки kd-деревьев по сравнению с другими. Для описания оптимизирующих структур введены необходимые программные абстракции, используемые в разработанном комплексе. Подробно описан алгоритм трассировки лучей, оптимизированный с помощью kd-деревьев, произведена оценка его сложности. Для пояснения принципа SAH был приведен пример определения наилучшего расположения секущей плоскости для группы элементов, ограниченных одних объемом. Описан алгоритм подсчета числа элементов по обе стороны от плоскости разбиения. Представлен рекурсивный алгоритм обхода kd-дерева. Применение kd-деревьев позволяет значительно ускорить процесс моделирования трассировки лучей в оптической системе светового прибора для дальнейшего анализа его светотехнических характеристик.

В данной работе с помощью алгоритма Берлекэмпа-Месси произведена оценка линейной сложности сигналов, генерируемых системами связи, моделирование которых было проведено в работе [5]. Дополнительно к этому произведена оценка линейной сложности системы связи с простыми сигналами, представленной синусоидой [13]. В результате расчетов установлено, что из рассматриваемых систем связи наибольшей линейной сложностью обладают системы связи с хаотическими сигналами (за исключением системы связи на основе хаотической маскировки, в которой в качестве генератора хаотических сигналов используется аттрактор Ресслера). Среди рассмотренных систем связи с хаотическими сигналами наибольшей линейной сложностью обладает система связи на основе хаотической модуляции. Наименьшей линейной сложностью обладает система связи на основе простых сигналов. Системы связи на основе «классических» шумоподобных сигналов имеют линейную сложность значительно большую, чем системы связи с простыми сигналами, но меньшую, чем системы связи с хаотическими сигналами. Установлено, что системы связи с хаотическими сигналами в целом являются более предпочтительными для защищенных систем связи, чем системы связи на основе «классических» шумоподобных сигналов.

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

Управление распределенными системами, которые невозможно постоянно наблюдать визуально, обычно ведется через формирование виртуальных моделей таких систем. Моделей, обеспечивающих как выработку управляющих воздействий, так и управление их реализацией. Анализ показывает, что в доинформационную эпоху такие модели формировались в нематериальном виде, на основе логико-аналитических рассуждений управленцев, по данным сбора обстановки. Впоследствии средства автоматизации обеспечили сбор информации, ее обработку и представление пользователю, упростив формирование модели системы. Но они обеспечивали эту задачу не в полном объеме, не доведя ее до логического завершения – описания целостной динамической модели управляемой системы. Надежда на решение проблемы появилась с развитием технологий «виртуальной реальности», которые позволяют формировать и визуализировать модели с требуемой детализацией и оперативностью, практически в автоматическом режиме. С учетом потребностей процесса управления и возможностей технологий виртуализации, в статье сформулированы предложения по методам описания и применения виртуальных моделей управляемой системы. Предложены и алгоритмически описаны основные направления применения виртуализации: при планировании действий и управлении реализацией планов.

Рассматривается система индексации серверов на базе протокола FTP. В статье описан набор функционала для индексации файлов и поисковой системы. Подробно рассмотрены основные проблемы, встречающиеся при обработке ответов на запросы по протоколу FTP и методы их решения. Несмотря на эволюцию файловых хранилищ, прошедшую за 34 года после создания протокола FTP, проблема индексации остается актуальной благодаря огромному массиву данных, хранящихся на существующих серверах. Разработанная система индексации состоит из трех основных частей: робота-индексатора, базы данных и Web-сервиса. Робот-индексатор способен работать с большинством типов FTP серверов и обрабатывать возвращаемые ими данные, избегая ссылочные ловушки и сохраняя результаты в базу данных. Web-сервис принимает запросы от конечного пользователя и возвращает результат поиска по базе данных. Пользователь может указать полное или частичное имя файла, тип файла и его размер. Ключевым отличием от существующих систем является отслеживание истории изменений файлов и серверов.

В статье представлена система имитационного моделирования Айвика (англ. Aivika), где особое внимание уделяется модулю распределенного моделирования, реализующего оптимистичный метод деформации времени. Показано, как в распределенной имитации можно использовать основные парадигмы дискретно-событийного моделирования, в частности, процесс-ориентированную парадигму. Также представлено, как в такой имитации можно использовать GPSS-подобный предметно-ориентированный язык. Описаны важные детали реализации. В конце приведены результаты тестирования распределенного модуля системы Айвики.

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

Алгоритмы – это всего лишь пошаговые алгоритмы решения задач, и большинство таких задач уже были кем-то решены, протестированы и проверены. Можно, конечно, погрузиться в глубокую фило¬софию гениального Кнута, изучить многостраничные фолианты с доказательствами и обоснованиями, но хотите ли вы тратить на это свое время? Откройте великолепно иллюстрированную книгу, и вы сразу поймете, что алгоритмы – это просто. А грокать алгоритмы – это веселое и увлекательное занятие. После приобретения книга будет также доступна в формате epub.

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

Программирование всегда было достаточно сложной задачей. Эта книга поможет вам легко преодолеть возникающие трудности с помощью библиотеки мощных алгоритмов, полностью реализованных в исходном коде Delphi. Вы узнаете, как выбрать способ, наиболее подходящий для решения конкретной задачи, и как добиться максимальной производительности вашего приложения. Рассматриваются типичные и наихудшие случаи реализации алгоритмов, что позволит вам вовремя распознать возможные трудности и при необходимости переписать или заменить часть программы. Подробно описываются важнейшие элементы алгоритмов хранения и обработки данных (списки, стеки, очереди, деревья, сортировка, поиск, хеширование и т.д.). Приводятся не только традиционные решения, но и методы, основанные на последних достижениях объектно-ориентированного программирования. Книга предназначена для начинающих программистов на Delphi, но благодаря четкой структуризации материала и богатой библиотеке готовых алгоритмов будет также интересна и специалистам.

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

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

Эта книга помогает познакомиться с олимпиадным программированием. Она подробно описывает, как проходят олимпиады, что требуется от участника, в чем их цель, как к ним готовиться. Подробно разобраны базовые темы, трюки и алгоритмы. Спортивное программирование – это самый перспективный интеллектуальный вид спорта, который можно назвать шахматами будущего. Уже сейчас им увлекаются лучшие умы планеты, и число участников растет год от года. Рост популярности олимпиадного программирования положительно влияет на другие сферы жизнедеятельности человека. Навыки быстрого решения сложнейших задач помогают сегодняшним студентам в будущем эффективно справляться с реальными проблемами человечества. Издание будет полезно прежде всего студентам, начинающим принимать участие в соревнованиях по программированию.

В этой книге, выхода которой с нетерпением ожидало сообщество сторонников гибких методологий разработки программного обеспечения, описывается процесс подготовки требований к разрабатываемой системе, который позволяет экономить время, избавляет от необходимости в переделках и ведет к созданию более совершенных программ. Лучший способ создать программное обеспечение, максимально полно удовлетворяющее потребностям пользователей, – начать с пользовательских историй. Это простые, понятные и краткие описания функциональности, которая представляет деловую ценность для реальных пользователей. В книге приводятся подробные рекомендации относительно того, как следует писать пользовательские истории и включать их в жизненные циклы разработки проекта. Вы узнаете, что такое хорошие пользовательские истории и что делает истории плохими. Вы познакомитесь с практическими методами сбора историй, позволяющими добиться хороших результатов даже тогда, когда возможность непосредственного общения с пользователями отсутствует. Автор демонстрирует, как систематизировать подготовленные пользовательские истории, установить для них приоритеты и эффективно применять для решения задач планирования, разработки и тестирования программного обеспечения. • Моделирование пользовательских ролей. • Сбор историй: опрос пользователей, анкетный метод, наблюдение, собрания. • Работа с менеджерами, инструкторами, продавцами и другими представителями пользователей. • Написание пользовательских историй для приемочного тестирования. • Использование историй для ранжирования задач, составления графиков работ и оценки трудозатрат. • В конце каждой главы приводится список контрольных вопросов и упражнений для самопроверки. Книга будет полезна разработчикам, тестировщикам, аналитикам и менеджерам проектов, использующим любую гибкую методологию программного обеспечения: ХР, Scrum… и даже собственный гибкий подход.

Более двадцати лет опытные программисты во всем мире использовали книгу Мартина Фаулера Рефакторинг, когда им нужно было улучшить проект существующего кода, повысить удобство сопровождения программного обеспечения или облегчить понимание существующего кода. Это – такое долгожданное – новое издание было полностью обновлено, чтобы отразить важные изменения в области программирования. Второе издание книги содержит обновленный каталог рефакторингов и включает примеры кода на JavaScript, а также новые функциональные примеры, демонстрирующие рефакторинг без классов. Как и в первом издании, здесь объясняется, что такое рефакторинг, почему вы должны прибегать к нему, как распознать код, который нуждается в рефакторинге, и как успешно провести его независимо от того, какой язык программирования вы используете. Основные темы книги: – Понимание процесса и общих принципов рефакторинга. – Быстрое применение полезных рефакторингов для облегчения понимания и изменения программ. – Распознавание запаха в коде, который сигнализирует о возможном применении рефакторинга. – Каталог рефакторингов с объяснениями, мотивацией, техникой применения и простыми примерами. – Создание надежных тестов для рефакторингов. – Компромиссы и препятствия на пути рефакторинга.

Байесовские методы пугают формулами многих «айтишников», но без анализа статистики и вероятностей сейчас не обойтись. Кэмерон Дэвидсон-Пайлон рассказывает о байесовском методе с точки зрения программиста-практика, работающего с многофункциональным языком PyMC и библиотеками NumPy, SciPy и Matplotlib. Раскрывая роль байесовских выводов при А/В-тестировании, выявлении мошенничества и в других насущных задачах, вы не только легко разберетесь в этой нетривиальной теме, но и начнете применять полученные знания для достижения своих целей.

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

Алгоритмы – это сердце и душа computer science. Без них не обойтись, они есть везде – от сетевой маршрутизации и расчетов по геномике до криптографии и машинного обучения. «Совершенный алгоритм» превратит вас в настоящего профи, который будет ставить задачи и мастерски их решать как в жизни, так и на собеседовании при приеме на работу в любую IT-компанию. В новой книге Тим Рафгарден расскажет о жадных алгоритмах (задача планирования, минимальные остовные деревья, кластеризация, коды Хаффмана) и динамическом программировании (задача о рюкзаке, выравнивание последовательностей, кратчайшие пути, оптимальные деревья поиска). Серия книг «Совершенный алгоритм» адресована тем, у кого уже есть опыт программирования, и основана на онлайн-курсах, которые регулярно проводятся с 2012 года. Вы перейдете на новый уровень, чтобы увидеть общую картину, разобраться в низкоуровневых концепциях и математических нюансах. Познакомиться с дополнительными материалами и видеороликами автора (на английском языке) можно на сайте www.algorithmsilluminated.org.

Даны основные сведения о структурах данных, рассмотрены алгоритмы работы с различными структурами данных. В пособии произведен подбор упражнений для отработки навыков по использованию алгоритмов. Оно адресовано студентам очного и заочного отделений высших учебных заведений, обучающихся по направлениям подготовки: 38.03.05 Бизнес-информатика; 09.03.03 Прикладная информатика; 44.03.05 Педагогическое образование (профиль программы Информатика и экономика). Может быть полезно всем изучающим основы алгоритмизации и программирования.