Discrete Math

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

(15 4)*(5 3)*7!

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

829440

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

330

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

False, хамгийн жижиг бодлогын шийдийг ашиглана

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

False

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

an=an-1+an-2+an-3

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

True

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

an=an-1+an-2

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

False

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

True

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

True

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

True

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

True

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

False

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

True

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

False

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

False

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

False

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

True

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

True

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

False

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

True

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

True

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

Left, Right, Root

False

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

False

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

True

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

True

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

False

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

59406880

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

16807

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

20

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

True

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

True

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

False

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

94

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

an=an-1+an-2+2n-2

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

True

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

True

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

True

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

False

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

True

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

False

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

True

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

False

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

False

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

True

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

False

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

True?

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

True

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

False

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

True

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

False

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

False

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

True

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

False

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

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

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

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

P v Q ^ ~R

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

True

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

Simplification

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

True

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

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

A v ~A

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

Сансар судлалын ангийн бүх оюутан, Дэлхий дээрх сансар судлалд суралцаж буй бүх оюутан

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

False

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

5

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

{1/2, 2/3, 3/4, 4/5, 5/6, 6/7}

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

O(n^2)

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

True

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

False

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

820

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

0001 0011 0101 1010 1011

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

21

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

Хоёрын 3 зэрэг нь 8-тай тэнцүү байна

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

7,14,21,28,35

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

True

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

True

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

2545 2757 1211

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

True

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

False

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

1,3

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

False

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

4500

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

~p v q

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

False

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

∀n(~Q((n))→~P(n)))

A→(A v q) бол

Tautology

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

∀x(C(x)→F(x))

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

A v F

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

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

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

P(9)

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

{1,3,5,7,9}

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

10

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

O(n^2)

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

O(2^n)

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

O(x^3)

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

False

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

True

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

2^1 ** 3^1 * 5^0*

(3^4 mod 17)^2 mod 11

4