2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




На страницу Пред.  1, 2
 
 Re: Сложность компьютерных алгоритмов
Сообщение30.05.2015, 14:56 
Sonic86 в сообщении #1021472 писал(а):
vlapay в сообщении #1021291 писал(а):
Вот именно, это направление меня интересует. Может кто-то знает, существует ли хоть один алгоритм, для которого доказано, что "не быстрее, чем за $O(n^2)$"?
Так я же Вам объясняю: пусть есть задача, у которой длина входа $=d(n)$, тогда время работы алгоритма $=\Omega(d(n))$ (за исключением каких-нибудь дурацких задач типа "вернуть 1-й элемент из массива длины $n$").
Пример: вычислить сумму квадратных матриц $n\times n$. Это нельзя сделать быстрее, чем за $O(n^2)$ просто потому, что в матрице $n^2$ разных элементов и они независимы друг от друга; просто потому, чтобы написать ответ потребуется $O(n^2)$ элементов.

Не пинайте сразу. Математика не мой конёк, о том, что означают многие математические символы, мне приходится только догадываться.
Цитата:
Еще раз говорю: Вы не сформулировали вопрос нормально. Что такое "универсальный алгоритм-ускоритель"? $N$ - это у Вас что? Откуда берется $N^2$?


vlapay в сообщении #1021429 писал(а):
Если есть универсальный алгоритм, то мы можем быстро получить доказательство любой теоремы (решение любой задачи), если такое вообще существует в природе.
Бред, доказательство теоремы - $NP$-полная задача.

Порылся в интернете и теперь могу сформулировать понятней. Есть нерешённая переборная задача, одна из семи задач тысячелетия. Универсальный алгоритм - недоказанное утверждение, что есть не только Равенство классов P и NP, но и что степень полиномиальной памяти и времени не превышает двойку. Причём, существование универсального алгоритма позволяет решить не только часть переборных задач, как доказал Левин, но и любую задачу математики.

 
 
 
 Re: Сложность компьютерных алгоритмов
Сообщение30.05.2015, 16:18 
Sonic86 в сообщении #1021472 писал(а):
Пример: вычислить сумму квадратных матриц $n\times n$. Это нельзя сделать быстрее, чем за $O(n^2)$ просто потому, что в матрице $n^2$ разных элементов и они независимы друг от друга; просто потому, чтобы написать ответ потребуется $O(n^2)$ элементов.
Насколько я понял, ТС хочет более, чем квадратичное время от размера всей использованной памяти. Кроме NP задач, я так сходу не смог ничего придумать. В матрицах вообще все алгоритмы максимум $O(n^{1.5})$ от количества элементов. С NP задачами, конечно, время будет экспоненциальным, но, насколько я знаю, этот факт не доказан.

 
 
 
 Re: Сложность компьютерных алгоритмов
Сообщение30.05.2015, 16:57 

(Оффтоп)

vlapay в сообщении #1021528 писал(а):
Универсальный алгоритм - недоказанное утверждение
vlapay в сообщении #1021528 писал(а):
есть не только Равенство классов P и NP, но и что степень полиномиальной памяти и времени не превышает двойку.
vlapay в сообщении #1021528 писал(а):
Причём, существование универсального алгоритма позволяет решить не только часть переборных задач, как доказал Левин, но и любую задачу математики.
А, понятно. Я пошел.
Лучше бы вместо "Левин" было написано "Ленин". Смешнее хотя бы.


venco в сообщении #1021548 писал(а):
Насколько я понял, ТС хочет более, чем квадратичное время от размера всей использованной памяти. Кроме NP задач, я так сходу не смог ничего придумать.
Проверка простоты числа вроде $O(n^6)$ :roll: Линейное-программирование вроде как долго работает.

 
 
 
 Re: Сложность компьютерных алгоритмов
Сообщение30.05.2015, 17:29 
Sonic86 в сообщении #1021557 писал(а):
[off]Проверка простоты числа вроде $O(n^6)$ :roll: Линейное-программирование вроде как долго работает.

Мало ли что долго работает. Нужно доказательство, что работать быстрее и менее объёмно нельзя в принципе. А такого доказательства, как я понял, нет. Собственно, это меня и интересует.

 
 
 
 Re: Сложность компьютерных алгоритмов
Сообщение30.05.2015, 17:40 
vlapay в сообщении #1021570 писал(а):
Нужно доказательство, что работать быстрее и менее объёмно нельзя в принципе. А такого доказательства, как я понял, нет.
Sonic86 в сообщении #1021472 писал(а):
Так я же Вам объясняю: пусть есть задача, у которой длина входа $=d(n)$, тогда время работы алгоритма $=\Omega(d(n))$ (за исключением каких-нибудь дурацких задач типа "вернуть 1-й элемент из массива длины $n$").
Пример: вычислить сумму квадратных матриц $n\times n$. Это нельзя сделать быстрее, чем за $O(n^2)$ просто потому, что в матрице $n^2$ разных элементов и они независимы друг от друга; просто потому, чтобы написать ответ потребуется $O(n^2)$ элементов.

 
 
 
 Re: Сложность компьютерных алгоритмов
Сообщение30.05.2015, 17:59 

(Порядок сложности для матриц)

Забавно смотрится комбинация:
Sonic86 в сообщении #1021472 писал(а):
Пример: вычислить сумму квадратных матриц $n\times n$. Это нельзя сделать быстрее, чем за $O(n^2)$ просто потому, что в матрице $n^2$ разных элементов и они независимы друг от друга; просто потому, чтобы написать ответ потребуется $O(n^2)$ элементов.
venco в сообщении #1021548 писал(а):
В матрицах вообще все алгоритмы максимум $O(n^{1.5})$ от количества элементов.

 
 
 
 Re: Сложность компьютерных алгоритмов
Сообщение30.05.2015, 18:07 
Sonic86 в сообщении #1021576 писал(а):
vlapay в сообщении #1021570 писал(а):
Нужно доказательство, что работать быстрее и менее объёмно нельзя в принципе. А такого доказательства, как я понял, нет.
Sonic86 в сообщении #1021472 писал(а):
Так я же Вам объясняю: пусть есть задача, у которой длина входа $=d(n)$, тогда время работы алгоритма $=\Omega(d(n))$ (за исключением каких-нибудь дурацких задач типа "вернуть 1-й элемент из массива длины $n$").
Пример: вычислить сумму квадратных матриц $n\times n$. Это нельзя сделать быстрее, чем за $O(n^2)$ просто потому, что в матрице $n^2$ разных элементов и они независимы друг от друга; просто потому, чтобы написать ответ потребуется $O(n^2)$ элементов.

Сумма матриц делается в один слой, так как это параллельный процесс. Вам этот пример ничего не даёт, ведь $N$ это общее количество информации - транзисторов и памяти компьютера, а для квадратных матриц $N>n^2$

 
 
 
 Re: Сложность компьютерных алгоритмов
Сообщение30.05.2015, 18:19 
Sonic86 в сообщении #1021472 писал(а):
доказательство теоремы - $NP$-полная задача.
vlapay в сообщении #1021528 писал(а):
существование универсального алгоритма позволяет решить не только часть переборных задач, как доказал Левин, но и любую задачу математики.
venco в сообщении #1021548 писал(а):
В матрицах вообще все алгоритмы максимум $O(n^{1.5})$ от количества элементов.
venco в сообщении #1021548 писал(а):
С NP задачами, конечно, время будет экспоненциальным, но, насколько я знаю, этот факт не доказан.
vlapay в сообщении #1021590 писал(а):
Сумма матриц делается в один слой, так как это параллельный процесс.
vlapay в сообщении #1021528 писал(а):
Математика не мой конёк, о том, что означают многие математические символы, мне приходится только догадываться.
:twisted: Мне кажется, что тема уже не очень подходит для раздела ПРР(М) :twisted:

 
 
 
 Re: Сложность компьютерных алгоритмов
Сообщение30.05.2015, 18:27 

(Оффтоп)

vlapay в сообщении #1021590 писал(а):
Вам этот пример ничего не даёт, ведь $N$ это общее количество информации - транзисторов и памяти компьютера, а для квадратных матриц $N>n^2$
Вот опять зачем-то вылезло число транзисторов.

Не, товарищи, зачем читать бред? Пойду что-нибудь осмысленное почитаю...

 
 
 
 Re: Сложность компьютерных алгоритмов
Сообщение30.05.2015, 18:31 
patzer2097 в сообщении #1021596 писал(а):
Мне кажется, что тема уже не очень подходит для раздела ПРР(М) :twisted:

Да пожалуйста. То что мне надо было, я уже выяснил.
Спасибо всем участникам.

 
 
 
 Posted automatically
Сообщение30.05.2015, 20:01 
Аватара пользователя
 i  Тема перемещена из форума «Помогите решить / разобраться (М)» в форум «Пургаторий (М)»
Причина переноса: темы перенесена в соответствующий раздел как бессодержательная и ввиду бесперспективности дискуссии

 
 
 [ Сообщений: 26 ]  На страницу Пред.  1, 2


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group