ЗНАЙ ИНТУИТ, Лекция, Комбинаторни изчисления

Комбинаторната математика е стара дисциплина. Името си получава през 1666 г. от Лайбниц в неговата Дисертация на Arte Combinatori. Комбинаторните алгоритми, с акцент върху разработването, анализирането и прилагането на практически алгоритми, са продукт на компютърната ера.

Предметът на теорията на комбинаторните алгоритми е изчисляването на дискретни математически структури. Това е нова линия на изследване. Само през последните няколко години система от знания за проектирането, внедряването и анализа на алгоритми се формира от набор от интелигентни техники и различни алгоритми.

Комбинаторното изчисление е в същото отношение към комбинаторната математика (дискретна, крайна математика), както и числените методи за анализ - към анализа. Комбинаторните изчисления се развиват в следната посока:

интензивно се измислят нови алгоритми;
има бърз напредък (главно в математически план) в разбирането на алгоритмите, тяхното проектиране и анализ;
има преход от изучаване на отделни алгоритми към изследване на свойства, присъщи на класовете алгоритми.

За разлика от някои други клонове на математиката, комбинаторните изчисления нямат „ядро“, тоест определен брой „фундаментални теореми“, които съставляват същността на предмета, от който се извеждат повечето резултати. Отначало може да изглежда, че цялата област се състои от куп специални методи и трикове. След като обаче бяха изследвани много комбинаторни алгоритми, започнаха да се появяват някои общи принципи. Именно тези принципи правят комбинаторното изчисление свързана област на знанието и позволяват то да бъде представено в систематизирана форма.

Задача за представяне: кодове, които запазват разликите

Изключително важен проблем при комбинаторните изчисления е проблемът за ефективното представяне на обектите, които трябва да бъдат обработени. Възниква, защото обикновено има много възможни начини за представяне на сложни обекти с по-опростени структури, които могат да бъдат вградени в езици за програмиране, но не всички такива представяния са еднакво ефективни по отношение на времето и паметта. Освен това идеалното представяне зависи от вида на извършените операции.

Ето примери, в които са посочени много специфични операции с цели числа. Целите числа се определят като данни от най-простия тип в почти всички изчислителни устройства и езици за програмиране. По този начин проблемът с представянето обикновено не възниква. Наличното представяне е почти винаги най-доброто. Има обаче някои забележителни изключения, при които е полезно или дори необходимо да се използва представянето на цели числа в изчислително устройство по различен начин. Тези изключения се появяват в следните случаи:

Необходими са цели, по-достъпни директно в хардуера.
Необходими са само малки цели числа и искате да спестите памет, като опаковате кратни числа в една клетка.
Операциите с цели числа се извършват не чрез конвенционални аритметични операции.
Целите числа се използват за представяне на други видове обекти и трябва да можете лесно да конвертирате цяло число към и от съответния му обект.

Проблемите с кодовете за запазване на разликите се отнасят до случаи 2 и 3. При проблемите с разпознаването и класификацията на шаблони, следната процедура е стандартна, за да се реши дали два обекта са еквивалентни. са представени съответно от вектори на характеристики, където всеки компонент означава характеристика на обект, изразена като цяло число. Смята се, че еквиваленти тогава и само ако

Класове по алгоритъм

Една от причините за бързия напредък на комбинаторните изчисления е повишеният фокус върху изучаването на класове алгоритми, за разлика от изучаването на отделни. За да се твърди например, че „всички алгоритми, предназначени да изпълняват това и което трябва да имат такива и такива свойства“ или „няма алгоритъм, който да удовлетворява това и това“, е необходимо да се работи с добре дефиниран клас на алгоритми. С тази дефиниция става възможно да се каже, че даден алгоритъм е оптимален по отношение на някакво свойство, ако работи поне толкова добре (по отношение на това свойство), колкото всеки друг алгоритъм от разглеждания клас.