2014 dxdy logo

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

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





Начать новую тему Ответить на тему На страницу Пред.  1, 2
 
 Re: Конструктивен ли прямой перебор?
Сообщение22.04.2017, 00:16 
Заслуженный участник
Аватара пользователя


30/01/06
63039

(Оффтоп)

Gagarin1968 в сообщении #1211460 писал(а):
пункт 1е - фамильярность (у нас принято обращаться друг к другу на "Вы", с большой буквы),

А у нас - на "вы" с любой буквы.

 !  GAA:
Munin заблокирован на две недели за продолжение оффтопика после замечания модератора.

 Профиль  
                  
 
 Re: Конструктивен ли прямой перебор?
Сообщение22.04.2017, 00:33 


01/11/14
36
Aritaborian в сообщении #1211474 писал(а):
Можно доказать, что существует розовый единорог. Доказав это, вы не обязаны предъявлять его и не обязаны перебирать множество всех единорогов в поисках розовых.

Aritaborian
Так ведь это же и есть чистая теорема о существовании. Но она ведь неконструктивна. Или я ошибаюсь?

 Профиль  
                  
 
 Re: Конструктивен ли прямой перебор?
Сообщение22.04.2017, 13:48 
Заслуженный участник


16/02/13
2749
Владивосток
Aritaborian в сообщении #1211459 писал(а):
отсутствие явного способа (алгоритма) доказательства утверждения $P(a)$ для каждого элемента $a\in A$ делает данное доказательство неконструктивным
Как по мне, это делает данное доказательство вовсе не доказательством. Соответственно, нахождение такого способа делает рассуждение одновременно доказательством, и притом конструктивным.

 Профиль  
                  
 
 Re: Конструктивен ли прямой перебор?
Сообщение22.04.2017, 17:36 
Аватара пользователя


11/06/12
7187
Минск
Кстати, да:
grizzly в сообщении #1211361 писал(а):
В теории Рамсея результаты обычно получают неконструктивными методами -- доказывают существование искомого решения, не давая алгоритма его нахождения. Утверждение, что это решение может быть найдено методом полного перебора, само по себе ничего не доказывает до тех пор, пока это перебор не был осуществлён.
Меня снова подвела невнимательность. Перечитал. С одной стороны нечто называют результатом, с другой же — говорят, что никаким доказательством это не пахнет. И верно второе. Как можно тогда первое называть «результатом»?

 Профиль  
                  
 
 Re: Конструктивен ли прямой перебор?
Сообщение22.04.2017, 18:00 
Заслуженный участник
Аватара пользователя


09/09/14
3787
Aritaborian
Я лучше поясню на примере.
Вот мы покрасили все египетские дроби в 150 цветов. ("Покрасили" здесь означает, что мы указали конкретный алгоритм раскраски.) Одна из теорем теории Рамсея утверждает, что существует конечное одноцветное подмножество этих дробей, сумма которых будет равна 1. Это теорема. Она доказана. Но доказательство не даёт никакого способа найти искомое подмножество. На вопрос "а как найти?" есть пока только один ответ -- методом перебора.

Ещё раз: без теоремы существования утверждение: "можно найти методом перебора" является просто голословным. Когда методом перебора нужное множество будет найдено, можно будет сказать, что мы доказали утверждение конструктивно.

 Профиль  
                  
 
 Re: Конструктивен ли прямой перебор?
Сообщение22.04.2017, 18:40 
Заслуженный участник
Аватара пользователя


23/07/05
14493
Новомосковск
Aritaborian в сообщении #1211659 писал(а):
С одной стороны нечто называют результатом, с другой же — говорят, что никаким доказательством это не пахнет.
Перебор объектов, если он закончился предъявлением конкретного объекта, является конструктивным доказательством.

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

 Профиль  
                  
 
 Re: Конструктивен ли прямой перебор?
Сообщение23.04.2017, 21:59 
Аватара пользователя


11/06/12
7187
Минск
Спасибо за то, что присоединились, Someone, ваше мнение всегда ценно. Думал, что выйдя их трёх сосен, попаду на песчаный пляж, а выйдя, оказался в сосновом бору.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 22 ]  На страницу Пред.  1, 2

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group