На главную

3. Какие разделы математики наиболее полезны? И что они делают?

 

Поскольку, вышли мы все из анализа, то этот предмет оставим без комментариев. Из остальных разделов, прежде всего, понадобится алгебра. Теория чисел, несомненно, пригодится,  так как «все есть число».

Сами эти науки ничего не делают, это их делают числовики и алгебраисты, да и все кому не лень.

Алгебраисты придумывают знаки и гордо называют их символами. Символ должен помещаться в формат А4. Главный символ 0. Потом они изобретают знаки для операций с символами. Пустой операции пока не придумали. Затем они двигают символами, с помощью операций, вокруг нуля. Некоторые операции позволяют символам обвести себя, они называются коммутативными. Другие операции, ассоциативные, не всегда это позволяют. Тогда алгебраисты все равно это делают и получают новый символ. Шевеля символами, они ищут группы, что, по сути, есть операция. Найдя группу, приобретают новую операцию. Некоторые группы распознать очень трудно, но они по-прежнему упорно ищут. Так была доказана велика теорема Ферма. Некоторые группы распознать принципиально невозможно, это им сказал великий числовик Гедель, тогда они стали искать полугруппы. И еще, алгебраисты воруют числа у числовиков, загоняют их в клетки – матрицы и разводят свои, но уже комплексные.

Числовики крепкие ребята, почти как мы программисты. Чем они занимаются, вот уже лет двести, не знает никто. Это они придумали числа. После того, как у них остались одни натуральные, они никому не дают разложить их на простые. Иногда они пудрят мозги алгебраистам квадратичными невычетами и четными простыми числами. Я попробовал найти, хотя бы одно, четное простое число после двойки, написал программу, по сей день работает.

Что означает аббревиатура TCS?

Теоретическая Компьютерная Наука [3].

Направления - сложностные аспекты вычислительных процессов и все, что с этим связано.

Главное достижение – выделение класса эффективных алгоритмов. Это такие алгоритмы, вычислительная сложность которых полиноминально зависит от длины входных данных [4].

Наивно полагается,  что требование полиноминальности достаточно для практической значимости алгоритма. Тем не менее, замечательно то, что от абстрактной проблемы существования алгоритма для некоторой задачи, перешли к абстрактной проблеме эффективности ее решения.

Этапы становления.

Первый. В ходе испытаний компьютера выяснилось, что алгоритм от входных данных объема n, имеет вычислительную сложность O( n x ) , где x натуральное число.

Второй. Область применения x была расширена до поля целых и рациональных чисел.

В настоящее время активно включают внутрь О( ) логарифмы и экспоненты.

Перспективы развития – расширить зону х до поля действительных и гиперкомплексных чисел, а внутрь О( ) добавить обобщенные функции.

А как все хорошо начиналось.

Первоначально, проблема сложности возникла в работах Андрея Николаевича Колмогорова [5]. Здесь, данная проблема сводилась к измерению информационной емкости конструктивных объектов.

Термин конструктивные объекты обозначает натуральные числа или какие-то объекты, вычислимым образом закодированные натуральными числами, например двоичные слова.

Позже стали изучаться сложностные проблемы вычислительных процессов. В этой области больших успехов добились наши американские коллеги –  R.Karp, S.Cook, Л.Левин, Ю.Гуревич и другие.

Потом, когда у большинства народонаселения появились писюки, математики в тему пошли валом.

На сегодняшний день все рогом уперлись в проблему P ?= NP, а именно, существуют или нет чисто переборные алгоритмы (B1).

Немного теории.

По Колмогорову, сложность двоичной последовательности х определяется так - это длина в битах самой короткой программы  ps( x), способной заставить машину напечатать эту последовательность:

                                                      K( x ) = min l( ps( x )) ,

где минимум берется по всем способам программирования s .

Таким образом, получается, что некоторые числа проще набрать вручную, чем пытаться придумать всеми способами программы, которые смогут их напечатать. Такие числа можно назвать сильно случайными. Например, это числа от 0 до 7, а ноль, тот и вовсе абсолютно случаен.

Теперь помечтаем.

Хорошо бы знать K( x ) для  любого конечного двоичного слова. В этом случае можно было бы сжимать файлы до самого предела. Далее, нетрудно будет решить задачу распознавания образов, полностью изъять случайность из бирже…, то есть, временных рядов. Конечно, потом захочется иметь шестисотый пентиум, трубопровод с пивного завода...

Но строгие дяди доказали [6], что не существует способа точно вычислить функцию Колмогорова.

Ну и что с этого? Синус тоже теоретически не вычислим. Мы его в ряд раскладываем и понемногу выгребаем.

Оказывается, выделить линейный член K( x ) несложно, например, с помощью комбинаторных методов [7], квадратичный труднее, а далее как повезет. Но об этом позже.

 

              

 


The Programs And Source Codes Rambler's Top100 Rambler's Top100