Seriese and Recurrence Relations

ເປັນຫຍັງການເຂົ້າໃຈ Recurrence Relations ຈຶ່ງມີປະໂຫຍດຕໍ່ນັກພັດທະນາເວັບ?

• ເພື່ອອອກແບບຖານຂໍ້ມູນທີ່ມີປະສິດທິພາບ.

• ເພື່ອຂຽນ CSS selectors ທີ່ຊັບຊ້ອນ.

• ເພື່ອວິເຄາະປະສິດທິພາບ (ເຊັ່ນ: Time Complexity) ຂອງຟັງຊັນ ຫຼື ຂັ້ນຕອນວິທີແບບ Recursive ທີ່ໃຊ້ໃນການປະມວນຜົນຂໍ້ມູນ ຫຼື ການສະແດງຜົນ.

• ເພື່ອຕັ້ງຄ່າ Web Server.

Recurrence Relation ແມ່ນຫຍັງ?

• ສູດທີ່ກຳນົດພົດໃດໜຶ່ງຂອງລຳດັບໂດຍກົງຈາກດັດຊະນີ `n`.

• ສົມຜົນທີ່ກຳນົດພົດໃດໜຶ່ງຂອງລຳດັບໂດຍອີງໃສ່ພົດກ່ອນໜ້າໜຶ່ງ ຫຼື ຫຼາຍພົດໃນລຳດັບນັ້ນ.

• ສົມຜົນທີ່ໃຊ້ສະເພາະໃນການຄິດໄລ່ດອກເບ້ຍ.

• ລຳດັບຂອງຕົວເລກທີ່ບໍ່ມີແບບແຜນ.

ອົງປະກອບສຳຄັນທີ່ຕ້ອງມີຄູ່ກັບ Recurrence Relations ເພື່ອໃຫ້ສາມາດກຳນົດລຳດັບໄດ້ຢ່າງສົມບູນແມ່ນຫຍັງ?

• ສົມຜົນລັກສະນະ (Characteristic Equation)

• ຄ່າຄົງທີ່ (Constants)

• ເງື່ອນໄຂເບື້ອງຕົ້ນ (Initial Conditions) ຫຼື ກໍລະນີພື້ນຖານ (Base Cases)

• ຕົວປ່ຽນ`n`

Recurence Relations `F(n) = F(n-1) + F(n-2)` ໂດຍມີ `F(0)=0` ແລະ `F(1)=1` ອະທິບາຍລຳດັບໃດ?

• ລຳດັບເລຂາຄະນິດ (Geometric Sequence)

• ລຳດັບ Factorial

• ລຳດັບ Fibonacci

• ລຳດັບເລກຄະນິດ (Arithmetic Sequence)

ໃຫ້ Recurrence Relations `a_n = 3 a_{n-1}` ແລະ ເງື່ອນໄຂເບື້ອງຕົ້ນ `a_0 = 2`. ຄ່າຂອງ `a_2` ແມ່ນເທົ່າໃດ?

• 6

• 9

• 12

• 18

ວິທີການແທນຄ່າຊ້ຳໆ (Iteration/Substitution Method) ໃຊ້ເພື່ອເຮັດຫຍັງກັບRecurrence Relations?

• ເພື່ອຊອກຫາເງື່ອນໄຂເບື້ອງຕົ້ນ.

• ເພື່ອພິສູດວ່າRecurrence Relations ຖືກຕ້ອງ.

• ເພື່ອປ່ຽນRecurrence Relationsໃຫ້ເປັນສູດ Closed-form (Explicit formula) ໂດຍການສັງເກດຮູບແບບ.

• ເພື່ອແຕ້ມກຣາຟຂອງລຳດັບ.

ສົມຜົນລັກສະນະ (Characteristic Equation) ຂອງ Recurrence Relations ລີເນແອເອກະພັນ `a_n = 4a_{n-1} - 3a_{n-2}` ແມ່ນຫຍັງ?

• `r - 4 = 0`

• `r^2 - 4r + 3 = 0`

• r^2 + 4r - 3 = 0`

• 4r - 3 = 0`

ການວິເຄາະ Time Complexity ຂອງຂັ້ນຕອນວິທີ Binary Search ມັກຈະນຳໄປສູ່ Recurrence Relations ໃນຮູບແບບໃດ (ໂດຍ `c` ເປັນຄ່າຄົງທີ່)?

• T(n) = T(n-1) + c`

• T(n) = 2T(n/2) + cn`

• T(n) = T(n/2) + c`

• `T(n) = n T(n-1) + c`

ຖ້າຟັງຊັນ Recursive ທີ່ຖືກສ້າງຂຶ້ນຕາມ Recurrence Relations ຂາດກໍລະນີພື້ນຖານ (Base Case) ທີ່ເໝາະສົມ, ຈະເກີດຫຍັງຂຶ້ນເມື່ອເອີ້ນໃຊ້ຟັງຊັນ?

• ຟັງຊັນຈະສົ່ງຄ່າ 0 ຫຼື null ກັບຄືນທັນທີ.

• ຟັງຊັນຈະເຮັດວຽກໄດ້ໄວຂຶ້ນ ເພາະບໍ່ຕ້ອງກວດສອບເງື່ອນໄຂ.

• ຟັງຊັນຈະຄິດໄລ່ຄຳຕອບທີ່ຜິດພາດ.

• ຟັງຊັນຈະເກີດ Infinite Recursion (ເອີ້ນຕົວເອງຊ້ຳໆ ບໍ່ສິ້ນສຸດ) ແລະ ສຸດທ້າຍອາດເຮັດໃຫ້ເກີດ Stack Overflow error.

Recurrence Relations `T(n) = T(n-1) + n` ດ້ວຍ `T(0) = 0` ຈະມີຄ່າ `T(3)` ເທົ່າໃດ?

• 3

• 4

• 5

• 6