Конструктивен ли прямой перебор?

[Gagarin1968]

День добрый.
Делал я курсовую по теории множеств и доказал одну промежуточную лемму о существовании. Суть задачи неважна - там речь идёт о множестве лучей, исходящих из точки, координаты которой являются комплексными корнями, и на эти лучи ещё накладываются дополнительные условия - это всё не так важно.
Важно вот что. Моя профессорша указала мне на то, что моя лемма неконструктивна. Т.е. она доказывает существование множества, нет, давайте обобщим - доказывает существование какой-то математической структуры, но не предполагает никакого способа её построения. И просила подумать над заменой этой леммы на более конструктивную.
Хорошо, пусть доказательство неконструктивно. Но ведь у меня есть возможность построить искомую структуру (множество) прямым перебором. Тем более, что в моей задаче он совсем простой - программка на 8 строк, и через 10 сек. я получу искомую структуру.
И вот мой вопрос в сабже.
Что думаете?

[Brukvalub]

1. Доказательство существования какого-либо объекта или возможности выполнения какого-либо действия с объектами называют конструктивным, если оно явно или неявно содержит алгоритм, позволяющий за конечное число шагов построить этот объект.
Характерные примеры: т. Лагранже о существовании канонического базиса квадратичной формы, доказательство интегрируемости в квадратурах рац. дробей.
2. Примеры неконструктивных доказательств: т. Брауэра о неподвижной точке, т. о существовании базиса в каждом векторном пространстве.
По вашему описанию мне трудно понять, конструктивно ваше доказательство, или нет. Но дальше вы пишете, что умеете за конечное число шагов построить нужный объект, так почему бы не заменить "неудачное" доказательство на доказательство построением объекта, которое уж точно конструктивно?

[Brukvalub]

ewert в сообщении #1211270 писал(а):

Это безумно зауженное понимание конструктивности.

Целиком и полностью с Вами согласен. Я и не претендовал на точное определение конструктивности, а только пытался описАть ситуации, которые никто не осмелится назвать неконструктивными.

ewert в сообщении #1211270 писал(а):

Характерный пример:

Brukvalub в сообщении #1211219

писал(а):
Характерные примеры: т. Лагранже о существовании канонического базиса квадратичной формы
-- неконструктивна, т.к. за конечное количество шагов диагонализовать эту форму не удастся.

Это обычный неконструктивный "выверт от ewert"?
Например, здесь и еще на куче семинарских занятий в ВУЗах студентам раз за разом удается "за конечное количество шагов диагонализовать квадратичную форму".
Поэтому прошу Вас придать точный смысл процитированному мной Вашему заявлению.

[Gagarin1968]

Brukvalub в сообщении #1211219 писал(а):

вы пишете, что умеете за конечное число шагов построить нужный объект, так почему бы не заменить "неудачное" доказательство на доказательство построением объекта, которое уж точно конструктивно?

Brukvalub
Спасибо за совет, я изменил лемму. Теперь это доказательство существования, но оно указывает, правда неявно, на алгоритм прямого перебора.
Только смущает одна вещь. Случайно, совсем в другой теме, разбирая комбинаторную теорему Рамсея, нарвался вот на это:

Цитата:

Results in Ramsey theory are non-constructive, they may show that some structure exists, but they give no process for finding this structure (other than brute force search).

Так почему же здесь считается прямой перебор неконструктивным? Кому верить? Я в смятении.

[Munin]

Gagarin1968 в сообщении #1211213 писал(а):

Важно вот что. Моя профессорша

Важно вот что. Называть профессора профессоршей - оскорбление. Профессорша - это жена профессора, а не женщина, которая сама профессор. По-немецки есть слово Professorin, по-французски professeure, professeuse, professoresse, а по-русски нет: говорят "профессор".

(Уточню. Оскорбление в адрес профессора, не являющегося одновременно профессоршей :-)

[Aritaborian]

Gagarin1968 в сообщении #1211336 писал(а):

Так почему же здесь считается прямой перебор неконструктивным?

Конечный брутфорс однозначно конструктивен. Верьте мне ;-) Иное дело, что он может тыщу лет занять. Но это не имеет отношение к конструктивности.

Munin в сообщении #1211341 писал(а):

Важно вот что. Называть профессора профессоршей - оскорбление.

Что ж, это тоже важно.

[grizzly]

Gagarin1968
Попытаюсь объяснить что говорит англо-вики насчёт конструктивности в теории Рамсея в приведенной цитате.

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

[Gagarin1968]

(Оффтоп)

Munin в сообщении #1211341 писал(а):

Называть профессора профессоршей - оскорбление. Профессорша - это жена профессора, а не женщина, которая сама профессор. По-немецки есть слово Professorin, по-французски professeure, professeuse, professoresse, а по-русски нет: говорят "профессор"

Товарищ Munin, кроме того, что Вы нарушаете Правила данного форума (пункт 1ж - оффтопик), Вы коренным образом ошибаетесь. Вы, очевидно, хорошо владеете немецким и французским, а вот родной язык знаете не очень. У русского слова "профессорша" есть 2 значения. Цитата из толкового словаря:

Цитата:

ПРОФЕ́ССОРША -и; ж. Разг.
1. Жена профессора. Беседовать с профессоршей оказалось интереснее, чем с её мужем.
2. Женщина-профессор. В консультации принимала участие старенькая профессорша.

И уж, разумеется, оскорблением это являться не может. Согласны со мной?

[Munin]

Я в толковом словаре этого не нашёл.

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

[Aritaborian]

grizzly, как я понимаю, именно отсутствие явного способа (алгоритма) доказательства утверждения $P(a)$ для каждого элемента $a\in A$ делает данное доказательство неконструктивным. Но стоит такому алгоритму появиться, и доказательство станет таковым в том случае, если $A$ конечно. Вне зависимости от того, настолько быстр и эффективен этот способ. У меня выходит, что некоторые доказательства попросту висят в неизвестности между конструктивностью и неконструктивностью.

[Gagarin1968]

(Оффтоп)

Munin в сообщении #1211442 писал(а):

Я в толковом словаре этого не нашёл.

Плохо искали. Вот ссылка на Ушакова:http://dic.academic.ru/dic.nsf/ushakov/989078

Munin в сообщении #1211442 писал(а):

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

Я ещё раз хочу обратить внимание модераторов на то, что Заслуженный Участник Munin нарушает Правила форума:
пункт 1е - фамильярность (у нас принято обращаться друг к другу на "Вы", с большой буквы),
пункт 1ж - оффтопик. Моя тема о конструктивности прямого перебора, а не о семантике слова "профессорша".
То, что я отвечаю на оффтоп, это вынужденный ответ, но я, по крайней мере, заключаю его в тэги [off].
И, в-третьих, я не считаю себя ни правым, ни виноватым, и уж точно никого не желаю оскорбить. Я всего лишь хотел развеять свои сомнения о конструктивности прямого перебора.

[Lia]

Munin
Замечание за оффтоп.

Gagarin1968
Замечание за попытки самостоятельного модерирования.

Есть кнопка "жалоба", пользуйтесь. Так можно долго обращаться к модераторам.

[Gagarin1968]

Aritaborian в сообщении #1211459 писал(а):

Но стоит такому алгоритму появиться, и доказательство станет конструктивным в том случае, если $A$ конечно.

Aritaborian
Вот мои сомнения как раз поэтому.

[grizzly]

Aritaborian в сообщении #1211459 писал(а):

Но стоит такому алгоритму появиться, и доказательство станет таковым в том случае, если $A$ конечно.

Но это будет какое-то другое доказательство. Неконструктивное доказательство продолжит оставаться неконструктивным -- это зависит только от методов, которые были в нём использованы. Я так понимаю.

Aritaborian в сообщении #1211459 писал(а):

Вне зависимости от того, настолько быстр и эффективен этот способ.

Это в любом случае да.

Aritaborian в сообщении #1211459 писал(а):

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

У меня так не выходит. Доказательство либо оно есть, либо его нет (либо мы не согласны с законом исключения третьего :) И методы, которые в нём применяются, мы можем разложить по полочкам. (Но это всё имхо -- я не специалист в этих вопросах.)

[Aritaborian]

Кажется, понял, где у меня был провал. Можно доказать, что существует розовый единорог. Доказав это, вы не обязаны предъявлять его и не обязаны перебирать множество всех единорогов в поисках розовых. Кто-то другой, однажды предъявив обществу розового единорога, никак не пошатнёт ваше доказательство.
Короче, я затупил.