 Форум мехмата МГУ по высшей математике
| Пользователям: | Аксиома — это истина, на которую не хватило доказательств. |
Все посты пользователя
Новости проекта «Математический форум», анонсы и обсуждение новых возможностей, общение с разработчиками, предложения по развитию сайта.
Можно проверять не все n; нижняя граница - 20 лет назад
Цитата ring0 писал(а) : я вот тоже думаю "не может быть", и это грустно, потому что алгоритм очень медленный получается. ...Целую часть от 1/|(х0-x1)| - это стартовое n, далее элементарно проверяем принадлежат ли иксы одной части, если нет, то уменьшаем n и тд. Можно проверять не все n, а как-нибудь выборочно: если какое-то n подошло, то дальше можно проверять только те, что больше. Савтор egor - Высшая математика
Ничего себе синус - 20 лет назад
Цитата дилетант писал: [10^n*n*sin(180/n)]/10^n :-) Наверное, тут подразумевается такой "синус", для которого sin(90)=1. Интересно, а что сейчас известно о цепной дроби числа пи? Может, кто-нибудь уже нашёл общие или возвратные формулы для неполных частных или подходящих дробей...автор egor - Высшая математика
Неплохо бы обобщить и уточнить - 20 лет назад
Цитата Студент2005 писал: Да, задачка действительно интересная, сам бы я с доказательством не справился... Стратегия фигуры I понятна, а вот идею первого и второго этапа мне подкинула одна знакомая (не математик ). Конечно, неплохо бы уточнить число ходов и обобщить на случай любого ограниченного односвязного клеточного поля на плоскости.автор egor - Высшая математика
Выигрышна жадная стратегия - 20 лет назад
Для фигуры I выигрышна "жадная" стратегия: I должна приближаться к II по той координате, по которой она дальше от II. Другими словами, каждым своим ходом фигура I должна уменьшать расстояние-максимум d(I,II)=max(|x1-x2|,|y1-y2|), где (x1,y1) - координаты I, (x2,y2) - координаты II. Докажем, что эта стратегия выигрышная. Начальное положение фигур несущественно, лишь бы перед ходом Iавтор egor - Высшая математика
Приближаться и отжимать от центра - 20 лет назад
Грубо говоря, фигура I на первом этапе должна встать между центром и II, а на втором этапе приближаться к II, отжимая II от центра и оставаясь между центром и II. На втором этапе I должна ходить так, чтобы после её хода и хода II уменьшилась величина f=|x1-x2|+|y1-y2|-|x2-c|-|y2-c|, где (x1,y1), (x2,y2) - координаты I и II, c=1001/2 - координата центра. Подробности пока что не получаюавтор egor - Высшая математика
(я неправильно прочитал условие) - 20 лет назад
Цитата Студент2005 писал: На шахматной доске (1000x1000) находятся две фигуры способные передвигаться за один ход на одно поле в вертикальном либо в горизонтальном направлении, требуется доказать что фигура выполняющая первый ход может за конечное количество ходов достигнуть поле на котором к этому времени будет находиться 2-я фигура, независимо от ходов последней. Изначально первая фигура находавтор egor - Высшая математика
Псевдополиномиальность и историческое замечание - 20 лет назад
Листаю книгу Гэри и Джонсона "Вычислительные машины и труднорешаемые задачи" (написана в 1978). В параграфе 4.2 (Задачи с числовыми параметрами и сильная NP-полнота) как раз подробно обсуждается задача о разбиении и алгоритм динамического программирования. К тому, что уже было сказано на форуме, можно добавить совсем чуть-чуть. Описанный здесь алгоритм с двумя циклами - классический павтор egor - Высшая математика
Понял, спасибо! - 20 лет назад
Цитата маткиб писал(а) : ...Например, можно положить n=0 и в качестве алгоритма A взять алгоритм, проверяющий данную формальную систему на противоречивость (тупым перебором доказательств). И по этому алгоритму построить диофантовое уравнение (многочлен). Спасибо. Теперь, когда ответ есть, он кажется очевидным.автор egor - Высшая математика
Например, диофантовы уравнения - 20 лет назад
Переформулирую изначальный вопрос для важного частного случая. Если P - многочлен с целочисленными коэффициентами, то через T_P и F_P обозначим следующие формулы: T_P - "существует целый корень многочлена P", F_P - "P не имеет целых корней". Воображаемая ситуация: построен многочлен P и для него доказано, что формулы T_P и F_P невыводимы в формальной арифметике. Возможна лавтор egor - Высшая математика
Переход от минимизации к распознаванию - 20 лет назад
Цитата egor писал(а) : Задача о минимальном линейном разложении (MinLinDecomp). Дано натуральное число M и векторы B,A^1,...,A^s в пространстве F^d. Вопрос: существует ли такой вектор u из F^s, что u имеет не более M ненулевых координат и \sum u_j A^j = B? maxal писал(а) : А где минимальность-то? Замечание не понял, но всё же попытаюсь ответить. Имеется в виду минимизация числа векторовавтор egor - Высшая математика
NP-полнота задачи о минимальном линейном разложении - 20 лет назад
Пока что не могу доказать NP-полноту задачи о минимальной линейно зависимой подсистеме (MinLinDep), зато вспомнил другую задачу, которая интересовала изначально. Через F буду обозначать поле из двух элементов. Задача о минимальном линейном разложении (MinLinDecomp). Дано натуральное число M и векторы B,A^1,...,A^s в пространстве F^d. Вопрос: существует ли такой вектор u из F^s, что u имеет неавтор egor - Высшая математика
Если нули чаще, то при n\to\infty предел тот же - 20 лет назад
Недавно расспросил людей, которые об этом читали. Оказывается, кем-то доказан следующий результат (не уверен в формулировке). Рассмотрим случайные квадратные матрицы порядка n над полем из двух элементов {0,1}. Элемент 0 выбирается с вероятностью p, элемент 1 - с вероятностью 1-p. Обозначим через X(p,n) вероятность, что такая случайная матрица невырожденная. Если фиксировать p, то при n\to\inftавтор egor - Высшая математика
Насчёт эквивалентности - погорячился - 20 лет назад
Цитата maxal писал(а): Как доказывается полиномиальная эквивалентность? Да, тут я загнул. Подразумевал лишь следующее: если задачу нахождения лз подсистемы мощности M можно решить за время T(d*n), то задачу нахождения минимальной подсистемы можно решить за время n*T(d*n). В другую сторону, к сожалению, не подумал. Получается, что я подменил задачу и не доказал NP-полноту исходной задачи. Названавтор egor - Высшая математика
Похоже, что это NP-полная задача - 20 лет назад
Видимо, тот приём, который предлагает maxal в сообщении SVP через LLL, легко приспособить для сведения NP-полной задачи X3C к задаче FindLinDep (см. далее). Этим будет доказано, что задача FindLinDep является NP-полной. Похожая задача есть у Гэри и Джонсона (МП5 - минимальное по весу решение системы линейных уравнений). Заменю исходную задачу на очень близкую (полиномиально эквивалентную):автор egor - Высшая математика
Вопрос по терминологии: "коэф-ты Безу" - 20 лет назад
Цитата maxal писал(а) : Пусть u и v - коэффициенты Безу для A и B, т.е. такие целые числа что НОД(A,B) = 1 = uA + vB. Интересно, а насколько принято выражение "коэффициенты Безу"? В каких учебниках так говорится? Я чаще слышал "линейное представление НОД", но это нехорошо.автор egor - Высшая математика
Спасибо; пока что не разобрался с LLL - 20 лет назад
Большое спасибо! Ваша идея (сведение к SVP) понятная и очень красивая, особенно построение векторов b. А вот с LLL ещё не разобрался. Первое впечатление такое (поправьте, пожалуйста). 1) Для произвольных решёток с целочисленным базисом задача SVP является NP-полной, и алгоритм LLL даёт лишь приближённое решение, которое не превосходит оптимальное * (1+eps). 2) В нашем случае кратчайшие векторавтор egor - Высшая математика
Решение исходной задачи (сложность m*n) - 20 лет назад
Всё-таки напишу полностью программку с оценкой времени O(m*n). // Исходные данные: int m, n; a - массив размера n; // Вспомогательные переменные: ls - массив размера m+1 (индекс может быть от 0 до m); int i, k; // счётчики в a и ls, соответственно // Роль массива ls ("last summand"): // в каждый момент ls есть последнее слагаемое в разложении k // либо 0, если для k не нашавтор egor - Высшая математика
Найти минимальную лин. зависимую подсистему - 20 лет назад
Даны векторы a_1,...,a_n в d-мерном векторном пространстве над полем из двух элементов, причём n>d (поэтому векторы образуют линейно зависимую систему). Нужно выделить из них минимальную (по числу элементов) линейно зависимую подсистему. P. S. Под рукой нет книги Гэри и Джонсона.автор egor - Высшая математика
Удобно через векторы - 20 лет назад
Обозначим через M центр окружности. Основную идею см. в четвёртом шаге. 1-й шаг. Пусть a1 и a2 - единичные векторы, направленные по лучам BA и BC: a1=BA/|BA|, a2=BC/|BC| (здесь BA - вектор, |BA| - его длина). 2-й шаг. Найдём угол ABC и его половину - угол ABM: угол ABC=arccos(a1*a2), угол ABM=угол ABC/2. 3-й шаг. Найти |BM| как R / sin(угла ABM). (Рассмотреть треугольник MHB, где H - павтор egor - Высшая математика
Сумма из одного слагаемого допускается? - 20 лет назад
Сначала я почему-то подумал, что запрещено раскладывать m в сумму, состоящую из одного слагаемого. Если сумма из одного слагаемого допускается, то решение совсем простое: либо вспомогательный массив размера m и двойной цикл (сложность n*m), либо рекурсия (сложность 2^n). Для минимизации числа слагаемых достаточно отсортировать исходный массив.автор egor - Высшая математика
Есть алгоритмы сложности m*n и 2^n - 20 лет назад
Похоже, для небольших m напрашивается алгоритм сложности m*n. Завести массивы s и last_summand: s - число слагаемых, которыми можно представить число k. last_summand - последнее слагаемое в разложении k. Устроить большой цикл по исходным числам и "добавлять возможные суммы". Внутри большого цикла - вложенный цикл по массиву s, отсюда сложность m*n. После завершения работы большогавтор egor - Высшая математика
3 разные ситуации - 20 лет назад
Цитата Nickolay2 писал: Так, дайте я еще разок спрошу. Значит все согласны, что из 5 испытаний вероятность того, что хоть где-то(кроме первого испытания) окажется 0 больше чем вероятность того, что все испытания будут равны 1??? Итак, монета бросается 5 раз. 1. Если оценивать вероятность перед всеми бросками, то больше. 2. Если же рассматривается ситуация, когда уже 4 раза выпали орлы, тавтор egor - Высшая математика
Условная вероятность - 20 лет назад
Цитата Nickolay2 писал: Значит если не считать первы бросок, так как мы решили, что выпало 1, то чем дальше будут выпадать 1 тем больше вероятность, что выпадет 0. Разве не так??? Ну вы же сами это сказали, вероятность что шесть раз подряд выпадет 1 крайне не велика. Отсюда и получается, что чем больше раз подряд выпала 1 тем больше вероятность выпадения 0. Или нет. Или я что-то путаю. Где-то изъавтор egor - Высшая математика
Другая задача: 100 шариков и генератор. - 20 лет назад
Цитата Nickolay2 писал: Предположим мы вытаскиваем из бездонного мешка шарики различного цвета, предположим, что цветов может быть только 6. Встречаются все 6 цветов с равной вероятностью. Если фраза "бездонный мешок" означает, что несколько первых вытаскиваний не меняют распределения шариков, то ответ 1/6 сидит в постановке задачи. Но можно рассмотреть и такую задачку: В меавтор egor - Высшая математика
Действительно, легко. А если нули встречаются чаще? - 20 лет назад
Цитата maxal писал: первый множитель - это количество вариантов первой строки матрицы (годятся все ненулевые), второй множитель - это количество вариантов второй строки (годятся все не лежащие в лин. простанстве натянутом на первую строку), третий множитель - это количество вариантов третьей строки и т.д. Да, теперь понятно. И всё же интересно, как Вы так быстро нашли ссылку в энциклопедии.автор egor - Высшая математика
Спасибо - 20 лет назад
Цитата maxal писал: Количество невырожденных матриц равно (2^n - 1)*(2^n-2)*(2^n-4)*...*(2^n-2^(n-1)) Интересно, как Вы так быстро нашли ответ . Можно, конечно, посчитать для небольших n и посмотреть в указанной Вами энциклопедии...автор egor - Высшая математика
Определитель случайной матрицы над конечным полем - 20 лет назад
Рассмотрим квадратные матрицы порядка n над полем из двух элементов. Найти число таких матриц, у которых определитель равен 0. Другая формулировка: найти вероятность того, что матрица вырожденная. Понятно, что для малых n задача хорошо решается перебором. Известно ли общее решение или хотя бы асимптотика при n\to\infty? P. S. Естественно, эту задачу можно поставить для любого конечного поля.автор egor - Высшая математика
О звезде Спасской башни и ответе Б - 20 лет назад
Цитата Lyova писал: Объсни разницу между твоим софизмом и "первое число - 5, а второе написано на звезде Спасской башни. Время пошло". Спасибо за интересную идею. Разница, очевидно, в том, что в исходном диалоге второе число определено математически. Кстати, какое число написано на звезде Спасской башни? Цитата Lyova писал: Нехорошо вкладывать дополнительное время туда, куда савтор egor - Высшая математика
Спасибо, меня это сейчас устраивает - 20 лет назад
Цитата Sonte писал: Какой смысл Вы вкладываете слово "невозможно", когда говорите "найти r (или сравнить r с 1/2) невозможно"? ... Наиболее нейтральный вариант - "невозможно доказать, что r>1/2 (или <1/2)", но тут вроде и парадокса нет, мы ж и так знали, что теория неполна. Смысл вкладываю такой: "найти r", "сравнить r с 1/2" и "выясавтор egor - Высшая математика
Идея: Card(2A)=Card(A) для бесконечного A - 20 лет назад
Насколько я помню, в учебниках по теории множеств доказывается, что если A бесконечно и Card(D)<Card(A), то Card(D\times A)=Card(A). Отсюда легко следует требуемое утверждение. Пусть A и B - кусочки исходного множества C. Среди них существует наибольшее по мощности. Будем считать, что это A. Тогда Card(A)\le Card(C)=Card(A\cup B)\le Card(2\times A)=Card(A). Здесь 2\times A понимаетсяавтор egor - Высшая математика