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(k_uu + k_vv + k_ww), где 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 лет лежала без движения!