5-6-mavzu: Algoritmik yechilmaydigan muammolar. Mayxil teoremasi. Algoritmik darjalar

5-6-MAVZU: Algoritmik yechilmaydigan muammolar. Mayxil teoremasi. Algoritmik darjalar

• REJA:
• 1. Algoritmik yechilmaydigan muammolar.
• 2. Mayxil teoremasi.
• 3. Algoritmik darajalar.

Foydalanilgan adabiyotlar.

• 1. Горбатов В.А., Останков Б.Л., Фролов С.А . Регулярные структуры автоматного управления / Под ред. В .А .Горбатова . М., «Машиностроение», 1980.
• 2. Горбатов В.А., Павлов П .Г ., Четвериков В.Н. Логическое управление информационными процессами. М., « Энергоатомиздат », 1984.
• 3. Гроссман И., Магнус В. Группы и графы. М ., «Мир», 1971.
• 4. Дорофеев Г. В., П о тап о в М . К., Розов Н. X. Пособие по математики для поступаю щ их в вузы. М., «Наука», 1976.
• 5. Евстигнеев В. А. Применение теории графов в программировании. М., «Наука», 1985.
• 6. Ерусалимски й Я. М. Дискретная математика: теория, задачи, приложения. М., «Вузовская книга», 2000

Mur-Myhillning Adan bog'i teoremasi. F to'plamlardan Y to'plamga (F: X Y) xaritalash, agar X to'plamning turli elementlari Y to'plamining turli elementlariga moslashtirilgan bo'lsa, in'ektiv deyiladi. Agar to'plamning har bir elementi bo'lsa, F: X Y xaritalash sur'ektiv deyiladi. Y - to'plamlarning kamida bitta elementining tasviri, ya'ni har qanday y Y uchun x X mavjud bo'lib, y = F(x). Agar u in'ektiv va sur'ektiv bo'lsa, xaritalash ikkilamchi hisoblanadi. In'ektiv va sur'ektiv xaritalash misollari keltirilgan

1-rasm In’ektiv va sur'ektiv xaritalarga misollar.

Shundan so'ng, DFA uchun minimallashtirilgan D < Q', S, q0, d', F' > tuzilishi mumkin. L tili sifatida: 

• 1-qadam: Q (holatlar to'plami)ni ikkita to'plamga ajratamiz. Bitta to'plam barcha yakuniy holatlarni, ikkinchisi esa yakuniy bo'lmagan holatlarni o'z ichiga oladi. Ushbu bo’lim P0 deb ataladi. 2-qadam: k = 1-ni ishga tushiring. 3-qadam: P k-1 ning turli to'plamlarini bo'lish orqaliP k niтопинг . Har bir P k-1 to'plamida biz barcha mumkin bo'lgan holatlar juftligini olamiz.Agar to'plamning ikkita holati farqlanadigan bo'lsa, biz to'plamlarni Pk da turli to'plamlarga ajratamiz . 4-qadam: Pk = Pk -1 bo'lganda to'xtating (bo'limda o'zgarish yo'q) 5-qadam: Bitta to'plamning barcha holatlari birlashtiriladi. Yiqilgan DFAdagi shtatlar soni no bo'ladi. P kda to'plalar.