| Chillugy | Математика. Мои результаты. |
| Небольшой список сделанного |
13. Пошёл август 2012.Предыдущий абзац был написан уж не помню в каком году, я работал в стол без отчёта. Полагаю, последний абзац с характерным номером. Finita ля. Меня выгоняют из квартиры, а это значит, что работу я не закончил и не закончу. Фактически построены только алгоритмы, а вот непосредственное программирование не завершено. Быть разработчиком в моём возрасте и с моим здоровьем весьма и весьма...TSP или Задача Коммивояжера. Тема мне давно перестала быть интересной, так как ответ для меня очевиден. Существует эффективный алгоритм. Несколько работающих вариантов проверки оптимальности. На который решение выйдет, тот и применяется.
Линейное программирование. Я придумал термин, объединяющий линейное программирование, целочисленное линейное программирование, и частично целочисленное линейное программирование, но ещё не использую его, просто по причине неготовности компьютерной программы. Вместо симплекс-алгоритма я пользуюсь другим, собственным, который называю "школьным", потому что применил его ещё будучи школьником, не имеющим понятия даже о линейной алгебре и матрицах.
Если из общей задачи линейного программирования удалить все неравенства, преобразовав их в равенства, то можно использовать симплекс-алгоритм, получая и все его проблемы. Я применил иной подход, избавился от равенств, разрешив их одно за другим. Полученная задача в некоторых источниках именуется канонической.Факторизация нечётного числа N. Первый алгоритм использует двоичное представление числа N и совсем не использует деления. Для чисел N>=15 можно написать уравнение
В полученной системе неравенств я строю конус из гиперплоскостей. Вместо линейной функции цели я использую невырожденную линейную матрицу целей. Если решаемая задача оптимизации имеет несколько решений, то стартует следующая задача минимизации, выбираемая из следующей строки матрицы целей. Каждая переменная имеет тип, или грануляцию - целый либо рациональный. Алгоритм фактически не зависит от грануляции переменной, так как любое неравенство всегда имеет решение, в отличие от равенства.
4A^2+4AB+16A+6B+15=NЭто то же самое, что иКвантовая механика. Ещё в универе зачитывался сборниками Фейнмана. Теперь той серии у меня нет, но есть некоторые другие книги. Специалистом по теме я не стал, но пришло некоторое понимание.
(2A+3)(2A+2B+5)=N
Если найдены целые числа A>=0 и B>=0, удовлетворяющие данному уравнению, то это значит, что найдена пара неравных нечётных сомножителя числа N, т.е. квадратные числа опускаются. Теперь последовательно вычитая младший бит из числа N и деля уравнение на 2 (для двоичной машины это не деление, а просто сдвиг на 1 разряд), можно привести первичное уравнение к некоторой системе уравнений, в которой участвуют как целые неотрицательные числа, так и отдельные биты. При этом важно не допускать ветвления и не раскрывать скобки. Последним уравнением системы будет примерно такое, (пишу без индексов, чтоб понятнее)
a+b+...+z=1
Все малые буквы в финальном уравнении - биты. Как решать уравнение, очевидно. Решением будет битовая строка, где ровно одна битовая переменная равна 1, а все остальные равны 0. Программировать алгоритм легко, но я даже не начинал работу. Если число уравнений вполне приемлемо и равно примерно log2(N), то число переменных в финальном уравнении равно
const*(log2(N))^2.
Его также можно считать приемлемым (нет экспоненты!), но не для моего слабенького компьютера. Подозреваю, что может начаться соревнование между создателями памяти для компьютеров, и разработчиками систем шифрования. Если компьютерщики будут выигрывать, создателя алгоритма не зазорно и пришибить. Кстати, необязательно последовательно перебирать все биты.
Второй алгоритм является результатом применения некоторой общей методики, впервые использованной мною в задаче TSP. Чтобы разделить, нужно сначала подобрать подходящий множитель факторизации. Вдруг новое число окажется менее прочным? Действительно, пусть M=m*N; Если окажется, что M=T^2+T, то задача решена, находится T так: T=sqrt(M). Вычислив p=(T,N), получаем через шаг p*q=N.
Второй алгоритм не требует чрезмерной памяти, но чувствителен к скорости процессора (работа с очень большими числами). Формул, подобных M=T^2+T, довольно много. Как находить множители m, задача непростая, но, по-видимому, вполне решаемая. Уже пытаюсь создать интерактивный алгоритм с применением графики и плавающей арифметики (это не та компьютерная плавающая арифметика) и думаю о полной автоматизации. Вернее, думал, до известных последних событий.Если ряды, которые должны сходиться, почему-то расходятся, а сами создатели метода перенормировки сомневаются в его математической правильности, то, возможно, мёд лежит совсем на другой полке? Используя уже упомянутую методику, я обнаружил, что формулы Ньютона-Тейлора-Маклорена о разложении функций в ряды - неполны. Остаточный член имеет частный, фактически единственный вид. У меня есть Справочник дифференциальных уравнений Камке. Я попробовал построить приближённые решения по-новому, естественно выбирая самые сложные нерешучие уравнения. Результат положительный во всех случаях. А на квантовой механике - застрял. У меня нет вузовских учебников по квантовой механике. Скачать из интернета - не получилось. Мне нужны сами оригинальные уравнения и постановки математических задач.Игра на бирже. Я давно понимал, что компьютерная программа может играть на бирже самостоятельно, а недавно в интернете попались материалы об автоматах, которые то помогают разбогатеть, то разориться.
Ксли какой-либо ряд расходится, потому что некий параметр по абсолютной величине больше 1, проблема решабельна. Нужно использовать другую формулу записи остаточного члена, коих множество обильно есть. Их математическая достоверность легко доказуема.Есть у меня некоторая идея, как это правильно организовать. Пока что термин этот мне не встретился, но я понимаю, что скоро об этом догадаются. Может, кто и применил, да помалкивает - можно и пулю схлопотать.
Итоги. Они таковы - больше не осталось интересных для меня математических задач, которые я не сумел куснуть, а некоторые просто решить.
12.
Тугодум я, признаюсь. За 5 лет (наконец-то!) научился из файлов .tex создавать файлы в формате .pdf (Adobe Reader) и файлы в формате .ps (PostScript). Привожу ссылки:
laplas.pdf 172Kb laplas.ps 438Kb TSP.pdf 125Kb TSP.ps 366Kb
11.
Выполняю разработку ранее начатых алгоритмов. Если позволят ресурсы и здоровье, сделаю всё. Пару файлов, полученных от Jonny, можно прочитать либо скачать:
read or download Combinatorial-Optimization.pdf 1.03Mb Lower-Bounds.pdf 379Kb
download Combinatorial-Optimization.zip 622Kb Lower-Bounds.zip 341Kb
Вы можете увидеть в статьях множество детальных графиков. У меня графиков всего 2, но они настолько просты, что их легче описать словами, чем пытаться нарисовать.
График 1. Линейный MST G1, построенный на подграфе графа G, у которого изъята вершина V1. Алгоритм пытается замкнуть обход двумя пунктирными линиями от V1 к концам графа G1.
График 2. MST строится на полном графе G, но недостраивается - осталось одно недобавленное ребро. График состоит из двух линейных графов Ga и Gb, необязательно равных по длине. Алгоритм пытается замкнуть обход двумя парами пунктирных линий. Рисунок чаще всего похож на трапецию, а замыкающие рёбра - либо её боковые стороны, либо диагонали.
Несложно видеть, что график 1 является частным случаем графика 2, если один из подграфов вырождается в изолированную точку.
В обоих случаях правило одно и то же - если в замкнутом обходе, полученном замыканием линейного MST, два максимальных ребра являются равными: то обход - ОПТИМАЛЕН!
Так решать TSP куда легче, а результат легко проверить. Ответ получается точный. Мною доказана теорема о достижимости обхода, для которого выполнен (ДПО) - Достаточный Признак Оптимальности.
Не могу удержаться: чтоб не повторить: "Гениальное всегда просто!"
10.
Здесь статья о том, как я справился с Задачей Коммивояжёра. Основы решения. TSP solution
I KILL TSP - другое её название. Получен первый отклик на статью от Jonny, пространный и проблемный. Я скопировал из гостевой отклик от Jonny и свой ответ на него сюда.
Выводы: моя уверенность в том, что мною получен верный результат, весьма окрепла. В науке правильные результаты имеют признак простоты. Еще в 1970 году Хэлд и Карп HK1 и HK2 получили нижнюю границу для стоимости оптимального обхода TSP и заодно проблему, как её вычислить и достичь, поскольку она в общем случае оказалась неточной. Полученный мною достаточный признак оптимальности (ДПО) обхода даёт точное значение стоимости оптимального обхода и тем самым точную нижнюю границу, в частности. ДПО в известной степени закрывает данную проблеиу. Подсказка математикам: если нужно во что бы то ни стало найти точное решение TSP, применяйте мой метод. Но приближённые решения задачи TSP, возможно, могут быть получены быстрее, в том числе и методом Хэлда и Карпа. Ссылки на работы HK1 и HK2 взяты из [1], где приведено краткое описание результатов упомянутых авторов. Самих работ HK1 и HK2 я, к сожалению, не читал..
9.
Построен новый формат сжатия звуковых файлов. Файлы .wav и .au сжимает БЕЗ ПОТЕРЬ, кажется, сильнее, чем .mp3. Но .mp3 - это всё-таки сжатие с потерей качества. Слово кажется означает, что результат не окончательный, пытаюсь набрать статистику и учусь сжимать с некоторой управляемой потерей качества. Воспроизводить пока не умею, процессор не успевает за звуком. Звуковые файлы нового формата предполагается поначалу использовать для хранения и для передачи по интернету (без немедленного воспроизведения). Качество ассемблерной программы для воспроизведения должно быть очень высоким, надеюсь справиться.
8.
Под Linux Fedora с применением LaTeX и LaTex2html для интернета в кодировке UTF-8 подготовлена статья Метод цепных пропорций. Источник статьи в кодировке UTF-8 в формате .tex - файл propor.tex
7.
Под Linux Fedora с применением LaTeX и LaTex2html для интернета в кодировке UTF-8 подготовлена статья Собственные функции и собственные числа оператора Лапласа для треугольников .
Вот список использованых .tex файлов, в кодировке UTF-8
- start.tex
- intro.tex
- deftask.tex
- baricentriccoords.tex
- baricentricHelmholz.tex
- solutionview.tex
- boundaryrole.tex
- partresultview.tex
- makestrategy.tex
- makemap.tex
- example1.tex
- example2.tex
- need.tex
6.
Стихов почти не пишу, уже давно. Время трачу на математику. Компьютер сдыхал, сдыхал, и наконец сдох. На этот раз всё успел сохранить. Подарили списанный, барахлит, но выручает. Голова гудит. Долго так продолжаться не может.
Предварительный отчёт:
- Построен быстрый алгоритм для задачи ОГК - "Оптимальный гамильтоновый контур". Так что ЗК - "Задача коммивояжёра" более не актуальна, так как является частным случаем ОГК. 28 вершин - за считанные секунды, даже неинтересно стало.
9 месяцев, идиот, не мог понять, почему для ЗК иногда не срабатывает критерий остановки. Клинч алгоритма. Оказалось, и не должен, так как этот критерий на самом деле для задачи ОГК. ЗК не всегда даёт наилучшие решения! Кто бы мог подумать! С ОГК этих проблем, кажется, нет, так как всегда есть возможность модифицировать задачу. Но процесс ещё не автоматизирован, в состоянии клинча расчёт останавливается, выход из мёртвой точки выполняется вручную, волевым решением. Пока застыло всё, отвлёкся на другое.
- Построен быстрый алгоритм для задачи ЦЛП - "Целочисленное линейное программирование". Как полезны поломки компьютера! Ни в жисть не думал, что я с этой задачей справлюсь. Оставшись без компа, листал подряд все книжки. Обнаружил во французской переводной книженции традиционное изложение методов отсечения, методов ветвей и границ и как-то сразу догадался, что все их примеры можно решить гораздо проще. И быстрее.
Отсечения - побоку. Ветвление - побоку. Перебор, возможно, остаётся, но очень-очень маленький в большинстве задач. К программированию, к сожалению, ещё не приступал, пока всё на бумаге. Вот восстановлю ранее утраченную библиотеку рациональной арифметики, возьмусь всерьёз. Если что-нибудь иное не отвлечёт.
- С малой достоверностью, сомнительно, но что-то есть. Обнаружен почти логарифмический(!) алгоритм для задачи ПЧ - "Простота числа". Бьюсь над ним. Понимаю, что так нельзя, но приказать мозгу не могу, он у меня искажён. Сосредоточиться - никак не может, постоянны токмо перескоки. Устал до чёртиков, заснуть бы - и не проснуться.
5.
Построил несколько быстрых и даже весьма быстрых алгоритмов решений некоторых задач, принадлежащих NP. Как-то вдруг прорвало плотину. Пишу программу для тестирования этих алгоритмов. Н-ну, тут проблем почти нет, правда, возможности компьютера ограничены. Пытаюсь доказать оптимальность хотя бы некоторых из этих алгоритмов.
Попытался применить иты в одном из алгоритмов. Если просто считать число операций, то оно уменьшается примерно в 4 раза (нужно ещё проверять). Это для обычных вычислений, но скорее всего иты потребуют модификации всей вычислительной математики. К сожалению, эмуляция железа съедает весь эффект. Понимаю, что не увижу процессоров, работающих на итах. Может, когда они будут, кто-нить вспомнит обо мне.
Мирона Тельпиза и его P versus NP я проштудировал. Признаюсь, что решения там так и не нашёл. Взыграл у меня кураж, взялся за задачу всерьёз. Что-то, кажется, получилось.
Буду жить, будет компьютер, будет продолжение работы.
4.
Быстрые числа - иты.
Были обнаружены в результате общения на математическом форуме. Впрочем, вряд ли я первый их придумал. Смысл в том, что двоичные разряды могут принимать не два, а три значения: 0, 1(бит), и -1(нит). Не путать с троичной арифметикой! Каждый разряд стоит ровно в 2 раза больше левого и ровно в 2 раза меньше правого. Тогда каждое число имеет несколько эквивалентных представлений, в том числе и такое, в котором любые значащие разряды 1, -1 отделены друг друга хотя бы одним незначащим 0. Такое представление чисел, при котором между значащими цифрами всегда стоит незначащая, называется приведённым.
Оказывается, что сложение двоичных итных чисел длиною в несколько машинных слов можно выполнять "почти" параллельно. Скорость работы увечивается почти во столько раз, сколько имеется параллельных процессоров (их необязательно делать мощными).
Слово "почти" указывает на вероятностный коэффициент, который зависит от частоты присутствия двух смежных 0 в машинном слове.
Будущие свехмощные компьютеры должны уметь выполнять операции над двоичными итными числами!
3.
Собственные числа и собственные функции оператора Лапласа для треугольных областей на плоскости.
Этой задаче, наверное, 200 лет. Уравнение Гельмгольца имеет вид: Δf = λf. Нужно найти собственные функции f и собственные числа λ для треугольника Γ на плоскости.
Если углы треугольника α, β, γ относятся друг к другу как целые числа α: β: γ = m: n: p, то задача имеет точное решение. Если же пропорция иррациональна, можно получить приближённые значения собственной функции, соответствующей экстремальному собственному числу.
Точные решения ищутся в виде суммы синусов ∑sin(kuu + kvv + kww), где u, v, w - барицентрические координаты в треугольнике, т.е. u + v + w = 1..
Число слагаемых является делителем числа M - удвоенного наименьшего общего кратного чисел m, n, p. Собственные функции объединяются в серии, в каждой серии своё число слагаемых, эти числа не обязательно совпадают. Серии возникают из-за того, что собственные числа выражаются формулами, в которых переменные могут принимать лишь целочисленные значения.
Начато составление карты собственных чисел и собственных функций треугольников для малых значений m: n: p.
Равностороннему треугольнику соответствует вектор 1: 1: 1. Собственные функции одной из серий можно записать в виде
sin kπu*sin kπv*sin kπw - формула трёх синусов. (k - целое число, отличное 0)
Это единственный случай, когда собственная функция представляется в виде произведения. Впрочем, несложно переписать её и в виде суммы трёх слагаемых.
2.
Алгоритм и программа GrateSort "Сортировка данных в оперативной памяти".
Работа была сделана аж в 1979 году, опубликовать так и не удалось. Впервые применена совсем недавно в 2004-м году, в проекте BestRoutes ("Оптимальная развозка пива автотранспортом по городу Омску") для фирмы "Sun Interbrew". Вот ссылка.
Свойства: Работает несколько медленнее быстрой сортировки Хоара, но никакой другой первенства по скорости не уступит. Надёжна на 100% - асимптотика всегда n*ln n. ( У Быстрой сортировки при плохом раскладе n^2). Не требует памяти. Монотонна по инверсиям: не переставляет данные, если они уже расположены в нужном порядке, поэтому всегда опережает Пирамидальную сортировку. На полностью отсортированном массиве число перестановок равно 0.
Алгоритм несложен: две пирамиды строятся одновременно внутри массива навстречу друг друга, соприкасаясь или совпадая вершинами. Применяются несложные ускоряющие операции. После того, как пирамиды достроены каждая до своей вершины, массив оказывается разделённым. Чаще всего точно пополам, тогда процесс продолжается для каждого подмассива. Этот же алгоритм может применяться, когда нужно отделить, к примеру, 5% самых больших значений или самых маленьких, объявляя их незначащими, БЕЗ сортировки всего массива. Для этой задачи моя сортировка GrateSort пока является наилучшей.
Бинарные пирамиды необязательны, годится любой граф, который приводил бы к разделению массива, но эти пирамиды оказались самыми эффективными.
Если подмассив мал размером, применяется сортировка его простыми вставками либо методом Шелла. Этот приём заимствован у сортировки Хоара.
Вышел на эту задачу, читая книгу Кнута "Искусство программирования". Там он поставил задачу: найти лучшую сортировку, обладающую наперёд заданными характеристиками. При попытке решить задачу Кнута и возник алгоритм GrateSort. Исходный модуль GrateSort.html
1.
Перечисляю то немногое, что у меня есть. Все три работы из нижнего списка уже были опубликованы в интернете, но раздел непонятно как грохнулся, а немного погодя сдох и комп. Впрочем, черновики на бумаге сохранились, будет компьютер, буду жить - всё восстановлю.
В 2002-м году, кажется, я сделал попытку опубликовать кое-что из этого списка "на бумаге", общаясь через интернет-форум. Даже Кнутовский ТеХ выучил! Но так ничего и не вышло. Сначала мне объявили, что нужно срочно приехать куда-то в Псков, не помню уж, на какой сбор. Потом объяснили, что я неправильно оформил документы - нет или мало ссылок. Я был тогда буквально прикован к кровати и не имел никакого доступа к научным библиотекам. Да и что толку? Одна из решённых мной задач уже 200 лет лежала без движения!