Презентации, доклады, проекты по математике

Теория графов. Основные понятия
Теория графов. Основные понятия
Введение В математике и информатике существует класс задач, которые наиболее просто и понятно решаются с применением теории графов. Это замечательные математические объекты, применяя которые можно решать математические и логические задачи, а также упрощать условия задач. История возникновения теории графов Математические графы с дворянским титулом "граф" связывает общее происхождение от лат. слова "графио" - пишу. Впервые основы теории графов появились в работе члена Петербургской академии наук, выдающегося математика Леонардо Эйлера, где он описывал решение головоломок и математических развлекательных задач. Среди них знаменитая задача о Кенигсбергских мостах. Философ Иммануил Кант, гуляя по городу Кенигсбергу, поставил задачу: можно ли пройти по всем семи мостам и при этом вернуться в исходную точку так, чтобы по каждому мосту пройти только один раз. В 1736 году задача о семи мостах заинтересовала Леонарда Эйлера. Он смог найти правило, пользуясь которым легко определить, можно ли пройти по всем мостам, не проходя дважды ни по одному из них.
Продолжить чтение
Лекции 19. Алгоритмы Маркова
Лекции 19. Алгоритмы Маркова
Ассоциативные исчисления. Пусть имеется алфавит (конечный набор различных символов). Составляющие его символы будем называть буквами. Любая конечная последовательность букв алфавита (линейный их ряд) называется словом в этом алфавите. Рассмотрим два слова N и М в некотором алфавите А. Если N является частью М, то говорят, что N входит в М. Зададим в некотором алфавите конечную систему подстановок N - М, S - Т,..., где N, М, S, Т,... - слова в этом алфавите. Любую подстановку N-M можно применить к некоторому слову К следующим способом: если в К имеется одно или несколько вхождений слова N, то любое из них может быть заменено словом М, и, наоборот, если имеется вхождение М, то его можно заменить словом N. Пример. Пусть в алфавите А = {а, b, с} имеются слова N = ab, М = bcb, К = abcbcbab, Заменив в слове К слово N на М, получим bcbcbcbab или abcbcbbcb, и, наоборот, заменив М на N, получим aabcbab или аbсаbаb. Подстановка ab - bcb недопустима к слову bacb, так как ни ab, ни bcb не входит в это слово. К полученным с помощью допустимых подстановок словам можно снова применить допустимые подстановки и т.д. Совокупность всех слов в данном алфавите вместе с системой допустимых подстановок называют ассоциативным исчислением. Чтобы задать ассоциативное исчисление, достаточно задать алфавит и систему подстановок. Слова P1 и Р2 в некотором ассоциативном исчислении называются смежными, если одно из них может быть преобразовано в другое однократным применением допустимой подстановки. Последовательность слов Р, P1, Р2, ..., М называется дедуктивной цепочкой, ведущей от слова Р к слову М, если каждое из двух рядом стоящих слов этой цепочки - смежное. Если можно построить цепочку, ведущую от слова R к слову S, то в силу симметричности подстановок можно построить и цепочку, ведущую от S к R. Слова R и S будут эквивалентными в данном ассоциативном исчислении (R~S). Пример. Алфавит {а, b, с, d, е}.  Подстановки: ас – сa; abac - abace ad - da; eca - ae bc - cb; eda - be bd - db; edb - be Слова abcde и acbde - смежные (подстановка bc - cb). Слова  abcde  и  cadbe  -эквивалентны.
Продолжить чтение