Рубрика «вычислительная сложность»

в 15:35, , рубрики: R, Алгоритмы, вычислительная сложность, двоичный алгоритм, Занимательные задачки, информатика, оптимизация, Проектирование и рефакторинг

Как разработчику научного ПО мне приходится много программировать. И большинство людей из других научных областей склонны думать, что программирование — это «просто» набросать код и запустить его. У меня хорошие рабочие отношения со многими коллегами, в том числе из других стран… Физика, климатология, биология и т. д. Но когда дело доходит до разработки ПО, то складывается отчётливое впечатление, что они думают: «Эй, что тут может быть сложного?! Мы просто записываем несколько инструкций о том, что должен сделать компьютер, нажимаем кнопку „Выполнить” и готово — получаем ответ!»

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

Люди не понимают, что информатика учит вас теории вычислений, сложности алгоритмов, вычислимости (то есть можем ли мы действительно что-то вычислить? Слишком часто мы считаем само собой разумеющимся, что можем!) Информатика даёт знания, логику и методы анализа, помогающие написать код, который выполнится за минимальное количество времени или с минимальным использованием ресурсов.
Читать полностью »

в 7:00, , рубрики: вычислительная сложность, Гипотеза Конна о вложенности, гипотеза цирельсона, квантовая запутанность, квантовые технологии, математика

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

В 1935 году Альберт Эйнштейн совместно с Борисом Подольским и Натаном Розеном пытались справиться с возможностью, открывшейся вместе с новыми законами квантовой физики: с «запутанностью» двух частиц, которые при этом могут быть разделены огромным расстоянием.

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

в 13:41, , рубрики: windows management instrumentation, WMI, вычислительная сложность, Клиентская оптимизация, о большое, оптимизация кода, разработка под windows, реверс-инжиниринг, тормоза
image

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

Для меня очень важно подбирать хорошие заголовки для своих постов, но я сразу же вспомнил, что подходящее название «48 процессора заблокированы девятью инструкциями» уже занято [перевод на Хабре] постом, написанным меньше месяца назад. Количество заблокированных процессоров отличается, а цикл немного длиннее, но на самом деле всё это заставляет испытывать дежавю. Поэтому пока я объясняю новую найденную проблему, мне был хотелось поразмыслить над тем, почему это случается постоянно.

Почему это происходит?

Грубо говоря, такие проблемы возникают вследствие наблюдения, которое я назову Первым законом Доусона о вычислениях: O(n2) — это магнит для алгоритмов, которые плохо масштабируются: они достаточно быстры, чтобы попасть в продакшен, но достаточно медленны, чтобы всё портить, когда туда попадут.

Как линейное время превращается в Windows в O(n²) - 2

O(n2) в действии — данные взяты из моего случая
Читать полностью »

в 12:42, , рубрики: 8 ферзей, coq, Isabelle, np, smt, WhyML, z3, верификация программ, вычислительная сложность, для чайников, защита программ, информационная безопасность, логика Хоара, поиск уязвимостей, проблема остановки, решатель, Символьное выполнение, формальная верификация, формальная верификация для чайников, формальные методы

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

Я приведу такой пример из зарубежного источника, и дополню собственным решением известной задачи о переправе волка, козы и капусты на другую сторону реки.

Но вначале вкратце опишу, что из себя представляет формальная верификация и зачем она нужна.

Под формальной верификацией обычно понимают проверку одной программы либо алгоритма с помощью другой.

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

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

Однако в любом случае будет получен один из трёх ответов: программа корректна, некорректна, или же — вычислить ответ не удалось.

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

А применяется формальная верификация, например, в ядре Windows и операционных системах беспилотников Darpa, для обеспечения максимального уровня защиты.

Мы будем использовать Z3Prover, очень мощный инструмент для автоматизированного доказательства теорем и решения уравнения.

Причём Z3 именно решает уравнения, а не подбирает их значения грубым брутфорсом.
Это означает, что он способен находить ответ, даже в случаях когда комбинаций входных вариантов и 10^100.

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

Задача о 8 ферзях (Взята из англоязычного мануала).

Формальная верификация на примере задачи о волке, козе и капусте - 1
Читать полностью »

в 13:06, , рубрики: FRACTRAN, вычислительная сложность, делегация доверия, ИИ, информационная безопасность, искусственный интеллект, Компьютерное железо, Настольные компьютеры, полнота по Тьюрингу, Процессоры, странные машины, теория алгоритмов, тьюринг-полные системы

Каталог программных конструкций, языков и API, которые неожиданно являются полными по Тьюрингу; последствия этого для безопасности и надёжности. Приложение: сколько компьютеров в вашем компьютере?

Любая достаточно сложная программа на Си или Фортране содержит заново написанную, неспецифицированную, глючную и медленную реализацию половины языка Common Lisp. — Десятое правило Гринспена

Полнота по Тьюрингу (Turing-completeness, TC) — это свойство системы при некотором простом представлении ввода и вывода реализовать любую вычислимую функцию.

Тьюринг-полнота — фундаментальное понятие в информатике. Она помогает ответить на многие ключевые вопросы, например, почему невозможно создание идеальной антивирусной программы. Но в то же время она является поразительно распространённым явлением. Казалось бы, компьютерной системе трудно достичь такой универсальности, чтобы выполнять любую программу, но получается наоборот: трудно написать полезную систему, которая немедленно не обратится в полную по Тьюрингу. Оказывается, что даже небольшой контроль над входными данными и преобразованием их в результат, как правило, позволяет создать тьюринг-полную систему. Это может быть забавным, полезным (хотя обычно нет), вредным или чрезвычайно небезопасным и настоящим подарком для хакера (см. о «теоретико-языковой безопасности», которая изучает методы взлома «странных машин»1). Удивительные примеры такого поведения напоминают нам о том, что полнота по Тьюрингу таится повсюду, а защитить систему чрезвычайно сложно.
Читать полностью »

в 12:00, , рубрики: np, p, Алгоритмы, вычислительная сложность, математика

Что компьютеру сделать легко, а что почти невозможно? Эти вопросы лежат в основе вопроса вычислительной сложности. Представляем вам карту этого ландшафта.

Краткое руководство по сложным вычислительным задачам - 1
Различные классы сложности сортируют задачи в иерархическом виде. Один класс может содержать все задачи другого, плюс задачи, требующие дополнительных вычислительных ресурсов.

Какова фундаментальная сложность задачи? Такова постановка базовой задачи специалистов по информатике, пытающихся рассортировать задачи по т.н. классам сложности. Это группы, содержащие все вычислительные задачи, требующие не более фиксированного количества вычислительных ресурсов – таких, как время или память. Возьмём простой пример с большим числом типа 123 456 789 001. Можно задать вопрос: является ли оно простым числом – таким, которое делится только на 1 и себя? Специалисты по информатике могут ответить на него при помощи быстрых алгоритмов – таких, что не начинают тормозить на произвольно больших числах. В нашем случае окажется, что это число не является простым. Затем мы можем задать вопрос: каковы его простые множители? А вот для ответа на него быстрого алгоритма не существует – только если использовать квантовый компьютер. Поэтому специалисты по информатике считают, что две этих задачи относятся к разным классам сложности.
Читать полностью »

в 20:17, , рубрики: c++, вектор, векторная алгебра, высокая производительность, вычислительная сложность, математика, матрица, матрицы, операторы, оптимизация, счетчик ссылок

Введение

Ввиду того, что при решении задач оптимизации, дифференциальных игр, и в 2D и 3D расчётах, а вернее при написании софта, который проводит вычисления для их решения одними из наиболее часто выполняемых операций являются векторно-матричные преобразования типа $aX+bY$, где $a,b$ — скалярные значения, $X, Yin R^n$ — вектора или матрицы размерности $R^{ntimes m}$.
Собственно вот такие:
image
(источник).

Так, чтобы не углубляться в теорию оптимизации за примерами достаточно вспомнить формулу численного интегрирования Рунге-Кутты четвёртого порядка:

$Y_{n+1}=Y_n+frac{h}{6}(k_1 + 2 k_2 + 2 k_3+k_4),$

где $Y_i$ — очередное значение интегрируемой функции $f(t,Y)$ $h$ — шаг метода, а $k_i$, $i=1..4$ — значения интегрируемой функции в некоторых промежуточных точках — в общем случае векторах.

Как можно заметить основную массу математических операций как для векторов, так и для матриц составляют:

  • сложение и вычитание — более быстрые;
  • умножение и деление — более медленные.

О сложности вычислений хорошо написано в соответствующем курсе МФТИ.

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

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

Читать полностью »

в 10:18, , рубрики: busy beaver game, halting problem, hypercomputation, Алгоритмы, большие числа, высокая производительность, вычислительная сложность, математика, тьюринг, функции, метки:
Невычислимые функции на примере Busy Beaver Game - 1

IT технологии проникли в большинство сфер жизни человека и продолжают развиваться. Автопилот, банковская сфера, машинный перевод, медицина, финансовые рынки, полеты в космос — все это возможно благодаря одной простой идее.

В этой статье я предлагаю заглянуть за границы возможностей компьютеров и рассмотреть чего же они не могут. И почему. Алан Тьюринг еще в 30-е годы обозначил невозможные для компьютера задачи.

Читать полностью »

в 9:13, , рубрики: алгоритм, Алгоритмы, вычислительная сложность, задачи для программистов, математика, оптимизация, палиндром, Программирование, Спортивное программирование

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

«The decimal number 585 is 1001001001 in binary. It is palindromic in both bases. Find n-th palindromic number». Или, по-русски: «Десятичное число 585 в двоичной системе счисления выглядит как 1001001001. Оно является палиндромом в обеих системах счисления. Найдите n-й подобный палиндром».

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

В конце концов, алгоритм оказался не таким уж и сложным, зато, на мой взгляд, очень красивым.
Читать полностью »

в 12:18, , рубрики: Алгоритмы, вычислительная сложность, математика, Учебный процесс в IT, метки:

В предыдущей части были освещены общедоступные вопросы, касающиеся SAT и P-NP: история проблемы, интуитивные определения классов и задач, указаны основные приложения SAT и основные последствия, в случаи решения P ?= NP (там же можно найти достаточное число ссылок на различный материал для самостоятельного изучения тематики).

В данной статье мы рассмотрим техническую сторону вопроса, а так же формализуем и представим в деталях материал из предыдущей статьи.

Зачем нам всем нужен SAT и все эти P NP (часть вторая)

картинка из статьи Boolean Satisfiability: From Theoretical Hardness to Practical Success (Communications of ACM)

Читать полностью »

12
Главная   |  Архив новостей  |   Android  |   Google  |   Apple  |   Microsoft  |   Информационная безопасность  |   Веб – разработка
Публикации RSS  |  Комментарии RSS
https://ajax.googleapis.com/ajax/libs/jquery/3.4.1/jquery.min.js