Discrete Math

Ялгаатай 15 гийгүүлэгч болон 5 эгшгээс 4 гийгүүлэгч ба 3 эгшигтэй хэдэн үг бүтээж болох вэ?

Газарзүйн 2ш, байгалийн шинжлэх ухааны 5ш, түүхийн 3ш, математикийн 4ш өөр өөр номууд тавиур дээр байгаа бол ижил сэдвийн номууд нэг дор байхаар хэдэн янзаар байрлуулж болох вэ?

Өгөгдсөн 11 элементээс 4-ийг нь сонгох боломжийн тоо хэд вэ?

Хуваагаад эзлэх алгоритм нь эхлээд бодлогыг нэг буюу хэд хэдэн бодлогуудад хувааж, аль нэг бодлогын шийдийг ашиглан анхны бодлогын шийдийг олно.

Оновчлолын бодлогыг greedy алгоритмаар шийдвэрлэж болох бөгөөд энэ нь алхам бүрт “хамгийн сайн“ шийдлийг өгөх албагүй.

n урттай, дараалсан гурван 0 агуулаагүй бит тэмдэгт мөрийн тоог илэрхийлэх рекурент харьцаа аль нь вэ?

{an} дарааллын нэг эсвэл хэд хэдэн өмнөх гишүүдийг ашиглан түүнээс хойших дурын гишүүдийг олох дүрмийг рекурент харьцаа гэнэ.

n гишүүн бүхий шатаар гарахдаа хүн нэг алхмаар нэг, эсвэл хоёр шат ахидаг бол уг шатыг хэд хэдэн янзаар гарч болох илэрхийлэх рекурент харьцаа аль вэ?

Графын нэг оройгоос нөгөөд хүрэх ирмэгүүдийн дарааллыг цикл гэнэ.

A нь G графын холболтын матриц бол vi оройгоос vj оройд очих r урттай замын тоо A матрицын (i,j) элементийн утгатай тэнцүү байна.

Эхлэл ба төгсгөл нь давхцсан замыг цикл гэнэ.

Графын бүх ирмэгийг агуулсан циклийг Эйлерийн цикл, бүх ирмэгийг агуулсан замын Эйлерийн зам гэнэ.

Хоёр оройг зөвхөн нэгээс олон ирмэг холбож байвал Мультиграф гэнэ.

A нь G графын холболтын матриц бол vi оройгоос vj-1 оройд очих r урттай замын тоо A матрицын (i,j) элементийн утгатай тэнцүү байна.

G нь n (n>3) оройтой энгийн граф бөгөөд бүх оройн зэрэг нь n/2-оос багагүй бол G хамилтоны граф байна.

Графын бүх оройг нэг удаа дайрч гарсан замыг хамилтоны цикл, бүх ирмэгийг нэг удаа дайрч гарсан циклийг хамилтоны зам гэнэ.

Эйлерийн зам олдох зайлшгүй бөгөөд хүрэлцээтэй нөхцөл нь яг хоёр оройн зэрэг нь тэгш байх явдал юм.

A нь G графын холболтын матриц бол vi оройгоос vj-1 оройд очих r урттай замын тоо A матрицын (i-1,j-1) элементийн утгатай тэнцүү байна.

Графыг v оройгоос гарч байгаа ирмэгийн тоог уг оройн зэрэг гээд deg(v) гэж тэмдэглэнэ.

Чиглэлгүй графт дурын хоёр оройг холбож байгаа ирмэг олдож байвал тэдгээр оройнуудыг хөрш оройнууд гэнэ

Чиглэлтэй графт дурын хоёр оройг холбож байгаа ирмэг олдож байвал тэдгээр оройнуудыг хөрш оройнууд гэнэ

Циклгүй, чиглэлгүй холбоост графыг мод гэнэ

Орой бүр яг m хүүтэй бол бүрэн m-ary мод гэж нэрлэнэ.

Мод тойрох inorder үндсэн арга:

Left, Right, Root

Чиглэлгүй граф мод байх зайлшгүй бөгөөд хүрэлцээтэй нөхцөл нь дурын хоёр оройн хооронд олон зам оршино

G нь энгийн граф байг. G-н бүх оройг агуулсан модыг үнэлгээт мод (spanning tree) гэнэ.

Төгсгөлөг төлөвт машин нь төлөвүүдийн олонлог, эхлэлийн төлөв болон төлөвийн шилжилтийн функцээс тогтоно.

Циклгүй, чиглэлтэй графыг мод гэнэ

Долоон тэмдгийн урттай, англи цагаан толгойн эгшгээр эхлээд А-аар дуусах хэдэн үг бүтээж болох вэ?

5 оронтой бөгөөд 1-7 хүртэл цифрээс бүрдэх тоо хэд байгаа вэ?

Зөв найман өнцөгт хэдэн диагональтай вэ?

Оновчлолын бодлогыг greedy алгоритмаар шийдвэрлэж болох бөгөөд энэ нь алхам бүрт “хамгийн сайн“ шийдлийг олдог.

Хуваагаад эзлэх алгоритм нь эхлээд бодлогыг нэг буюу хэд хэдэн бодлогуудад хувааж, жижиг бодлогын шийдийг ашиглан анхны бодлогын шийдийг олно.

{an} дарааллын нэг эсвэл хэд хэдэн өмнөх гишүүдийг ашиглан дурын гишүүдийг олох дүрмийг рекурент харьцаа гэнэ.

7 урттай, дараалсан хоёр агуулсан бит тэмдэгт мөрийн тоог аль нь вэ?

n урттай, дараалсан хоёр 0 агуулсан бит тэмдэгт мөрийн тоог илэрхийлэх рекуррент харьцаа аль нь вэ?

Нэг оройг эхлэл гэж үзвэл эхлэл ба төгсгөл нь давхцсан графыг цикл гэнэ

Цэгүүдийн хоосон биш олонлог V, тэдгээрийг хооронд нь холбосон хэрчмүүдийн олонлог E хоёрын G=(V,E) хосыг граф гэнэ.

Холбоост граф Эйлерийн граф байх зайлшгүй бөгөөд хүрэлцээтэй нөхцөл нь бүх оройн зэрэг нь тэгш байх явдал юм.

Зам нь ирмэгийг нэгээс олон удаа агуулсан бол энгийн зам гэнэ.

Графын бүх оройг нэг удаа дайрч гарсан замыг хамилтоны зам, графын бүх ирмэгийг нэг удаа дайрч гарсан циклийг хамилтоны цикл гэнэ.

G нь энгийн граф бөгөөд хөрш биш v ба u хоёр оройн хувьд deg(u) = deg(v) бол хамилтоны граф байна.

Ирмэг нь оройг нь өөрийг нь өөрт нь холбодог бол түүнийг уг оройн гогцоо гэнэ.

Хоёр оройг зөвхөн нэг ирмэг холбож байвал мультиграф гэнэ

Чиглэлгүй графт сондгой зэрэгтэй оройн тоо сондгой байна.

Чиглэлгүй графт дурын хоёр оройг холбож байгаа ирмэг олдож байвал тэдгээр оройнуудыг хөрш оройнууд гэнэ.

Төгсгөлөг төлөвт машин нь төлөв шилжилтийн функцээс тогтоно.

Модны орой бүр m-ээс олонгүй хүүтэй бол m-ary мод гэнэ

Чиглэлгүй граф мод байх зайлшгүй бөгөөд хүрэлцээтэй нөхцөл нь дурын хоёр оройн хооронд цор ганц зам оршино.

Орой бүр яг m хүүтэй бол хоёртын мод гэнэ

m=2 байх модыг хоёртын мод гэнэ

Төгсгөлөг төлөвт машин нь эхлэлийн төлөв болон төлөв шилжилтийн функцээс тогтоно.

Циклтэй, чиглэлгүй холбоост графыг мод гэнэ

(A v F) v (A v T) нь үргэлж

Логикийн хувьд зөв оюун дүгнэлтийг үндэслэлтэй оюун дүгнэлт гэж хэлэхгүй.

P: Бид шударга байх ёстой

Q: Бид үнэнч байх ёстой

R: Бид бардам байх ёстой

бол “Бид шударга эсвэл үнэнч гэхдээ бардам биш байх ёстой“ нь

“4+3=7“ эсвэл “5 бол анхны тоо“-ийн үнэний утга нь

“Үүлэрхэг шиврээ бороотой байна. Тиймээс үүлэрхэг байна“ аргументад гаргалгааны ямар дүрэм ашигласан бэ?

Бодит тооны муж дахь ∀n(n+1>n)-н утга юу вэ?

P,Q,R-ууд тус тус T,F,F бол дараахийн аль нь үнэн бэ?

Хэрвээ A нь дурын хэллэг бол аль нь тавтологи вэ?

“Бүгд сансар судлалд суралцдаг“ гэсэн хэллэг нь ямар мужид үнэн бэ?

Бүх бүхэл тооны мужид Q(x,y) нь “x+y=x-y“ бол ∃xQ(x,4) кванторын утга нь

10-аас бага эерэг бүхэл тооноос тогтох олонлогийн хэмжээ нь

{x: x=n/(n+1)}, n нь 7-оос бага анхны тоо олонлогийн элементүүд нь

Insertion sort алгоримтын worst case хүндрэл нь

Аливаа асуудлыг шийдвэрлэх, тооцоолол хийхэд чиглэсэн үйлдлүүдийг төгсгөлөг дарааллыг алгоритм гэнэ.

Tractable Problem: There doesn’t exist a polynomial time algorithm to solve this problem

41-д хуваагддаг, 39-д хуваахад 1 үлдэгдэл өгөх хамгийн бага натурал тоог ол

Дараах арван зургаатын тоог хоёртын тоо болон хувирга (135AB)

2 оронтой анхны тоо хэд байдаг вэ?

Хоёртын тооллын системд бичигдсэн эерэг бүхэл тоог наймтын тооллын систем рүү шилжүүлэхийн тулд яагаад хоёртын цифрүүдийг гурав гурваар нь бүлэглэж, шаардагатай бол эхний бүлгийн өмнө тэгүүдийг нэмж гурван цифртэй болгоод бүлэг бүрийг нэг наймтын цифр болгоход хангалттай байдгийг товч тайлбарла.

6-д хуваагдахад ногдвор нь үлдэгдэлтэйгээ тэнцүү байх бүх натурал тоог ол. Тайлбар багаас нь эхэлж 101,102,103 хэлбэртэй бичнэ

Хэрэв ab(mod m) бол c*ac**b(mod m) байна

Хаш функц нь k түлхүүр бүхий бичлэгт санах ойн ялгаатай хаягийг хуваарилдаг

UPLOAD гэсэн текстийг n=53*61 e=17 үед RSA аргаар нууцал

Санамсаргүй тоо нь компьютерийн симуляцид өргөн ашиглагддаг

Recursive algorithm зогсон нөхцөл бол шийд нь мэдэгдэхгүй байгаа жижиг бодлого юм

Доорх хариултуудын алийг нь 2-тын болон 5-тын зоосыг ашиглан өгөх боломжгүй вэ

Зүй тогтлын цөөн тооны тухай тохиолдлоос ерөнхий дүгнэлт хийх аргыг гүйцэд индукцийн арга гэнэ

4 оронтой тэгш тоо хэд байгаа вэ

p → q логик эквивалент нь

p,q хэллэгүүд “буюу“ холбоос хэрэглэхэд гарах “p буюу q“ гэсэн нийлмэл хэллэгийг p,q хэллэгүүдийн үржвэр буюу конъюкц гэнэ.

“Хэрэв n нь сондгой бүхэл тоо биш бол ямар нэг сондгой биш тоо болон n-Ийн нийлбэр сондгой биш байна“ гэсэн хэллэг байг, энд P(n) Нь сондгой бүхэл тоо биш …………..

A→(A v q) бол

Бүх хүмүүсийн мужид C(x) нь “x нь хошин шогийн жүжигчин“ болон F(x) нь “x нь хөгжилтэй“ бол “Бүх хошин шогийн жижүгчин хөгжилтэй“ гэсэн хэллэгийн квантор нь

Хэрвээ A нь дурын хэллэг бол аль нь эсрэгцэл биш вэ?

“Хоёр сөрөг тооны үржвэр нь сөрөг биш“ квантор нь

… нь тавтологи бол нийлмэл хэллэг p болон q-г логик эквивалент гэнэ

P(x) нь x>7 бол аль нь үнэн бэ

O Нь 10 бага сондгой эерэг бүхэл тооноос бүрдэх олонлогийн элементүүд нь ---- байна

Хэрэв n(A)=20 ба n(B)=30 ба n(A U B)=40 бол n(A ~U B) нь

Bubble sort алгоритмын хүндрэл нь

Фибоначчи цувааны хүндрэл нь

Хэрвээ f(x)=3x^2+x^3logx бол f(x) нь

Цифрүүдийнхээ үржвэрээс 5 дахин их байх 4 оронтой тоо олдох уу

7,8,9,11 тоонууд хос хосоороо харилцан анхны тоонууд уу

a тоо нь 2^2 ** 3^1 * 5^0 ба b тоо нь 2^2 * 3^1 * 5^1 бол ХИЕХ нь*

(3^4 mod 17)^2 mod 11