Дискретна математика

Дискретна математика (от лат. discretus — прекъснат,
който се състои от отделни части, и математика).

Дискретната математика е раздел на математиката, в който се изучават някои дискретни структури с особено значение за информатиката. Нарича се още математически основи на информатиката. Основни направления на дискретната математика са теория на двоичните функции, теория на кодирането, теория на графите, теория на формалните езици и граматики, теория на алгоритмите и изчислимостта.

Джордж Бул
Джордж Бул (1815—1864). Английски математик и логик.

В теорията на двоичните функции се изучават свойствата на функции, чиито аргументи са двоични вектори и имат стойност 0 или 1. Основа на тази теория са работите на Дж. Бул, изследвал наречената на негово име булева алгебра. Основните резултати в теорията на двоичните функции са в областта на т. нар. минимални представяния на двоичните функции (представяния, които съдържат най-малък брой знакове).

Теорията на кодирането е пряко свързана с представянето на информацията. Кодът задава изображение на множеството от думи, съставени от знаковете на дадена азбука, върху множеството от думи на друга азбука. Изучават се свойствата на кодовете и проблемите на кодирането и декодирането (възстановяване на кодираните съобщения). Особено полезни са т. нар. шумозащитни кодове. Те позволяват автоматично откриване и дори поправяне на ограничен брой грешки в кодираните съобщения.

Азбуката на Морз
Азбуката на Морз.

Теорията на графите води началото си от работите на А. Ойлер (1707—1783). Графите са удобно средство за описание на системи. В информатиката се използват за описание на сложни информационни структури (напр. семантични мрежи) или на управляващи структури (напр. блоксхеми). Интересни задачи в теорията на графите са намиране на най-къс път, намиране на цикли, декомпозиция, проверка за планарност (възможност графът да бъде разположен в равнината, без ребрата му да се пресичат).

Теорията на формалните езици и граматики, създава необходимите математически структури, с които се изучава такова сложно явление като езика. В основата й стои определянето на понятията формална граматика и формален език. Едно от най-съществените теоретични постижения в тази област е класификацията на Н. Чомски (САЩ), създадена през 50-те години на XX в., която разделя формалните езици на четири класа в зависимост от вида на продукционните правила в пораждащите ги формални граматики. Теорията на формалните езици и граматики е с голяма приложна стойност за теорията на алгоритмичните езици и методите за транслация.

Наименованието алгоритъм произлиза от името на арабския
математик ал-Хорезми — Algo-rizmy (787 — ок. 850 г.)

Теорията на алгоритмите и изчислимостта изучава математическите свойства на алгоритмите. Възникнал на интуитивно равнище още в древната математика (напр. алгоритъма на Евклид за намиране на най-голям общ делител на две цели числа), алгоритъмът става точно математическо понятие едва през 30-те години на XX в. В основата на този резултат са работите на А. Тюринг, А. Чърч, С. Клини и Е. Пост, които независимо един от друг (следвайки различни подходи) през 1936 г. дават формално определение на понятието алгоритъм, като го обвързват с конкретен изпълнител на алгоритми и конкретен език за описание на алгоритмите. Тези резултати дават необходимия инструмент за изследване на възникналите още преди това проблеми, свързани с конструирането на алгоритми, които дават отговори на определен въпрос (от такъв характер напр. е знаменитият десети проблем на Хилберт за разрешимостта на диофантовите уравнения в цели числа).

Вж. Изкуствен интелект и Теория на графите.

Няма коментари - Остави коментар

Вашият коментар

Вашият имейл адрес няма да бъде публикуван. Задължителните полета са отбелязани с *

*

Можете да използвате тези HTML тагове и атрибути: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>