Cập nhật thông tin chi tiết về Hình Học Của Số Phức mới nhất trên website Sansangdethanhcong.com. Hy vọng nội dung bài viết sẽ đáp ứng được nhu cầu của bạn, chúng tôi sẽ thường xuyên cập nhật mới nội dung để bạn nhận được thông tin nhanh chóng và chính xác nhất.
Trần Hải Cát Bộ môn Vật lý, khoa Khoa học ứng dụng Trường Đại học Sư phạm Kỹ thuật Tp. Hồ Chí Minh
Có lẽ trong chúng ta, khi đọc bài này, hầu như ai cũng từng học qua số phức. Và cũng có lẽ số phức phần nào để lại những bí ẩn khó hiểu. Bài viết này ra đời với mong muốn góp phần làm sáng tỏ vấn đề số phức, giúp sinh viên các ngành kĩ thuật vận dụng tốt hơn, thấu hiểu hơn về bản chất của các biểu diễn phức.
j – “đơn vị ảo”
Số phức theo định nghĩa thông thường được biểu diễn dưới dạng z = a+jb gồm hai thành phần: phần thực a và phần ảo b. “Phức” ở đây có nghĩa là sự pha trộn giữa “thực” và “ảo”. j được gọi là và có tính chất vô cùng độc đáo:
Và mọi chuyện trở nên khó hiểu từ đó. Suy nghĩ thông thường của chúng ta đấu tranh rằng, số gì bình phương lên lại bằng -1, một số âm. Lẽ ra bình phương một số bất kì phải ra số dương chứ! Chúng ta đã chấp nhận nó như một tiên đề. Số phức đi vào tâm tưởng sinh viên như một kẻ nhiễu loạn, phá phách.
Số phức trong toán học thuần tuý được xây dựng hết sức công phu, chặt chẽ và sâu sắc. Ở đây chúng ta chỉ bàn đến một vài khía cạnh thường xuất hiện trong kỹ thuật: chuyển động quay.
j – toán tử quay
Trong bài viết này chúng ta có thể tiếp cận số phức theo hướng hình học, giúp các ứng dụng kĩ thuật có cái nhìn dễ hình dung hơn. Hãy bắt đầu từ ý nghĩa hình học của kí hiệu j và xem như một tiên đề:
Cho vector (1,0), tức số 1 trên trục hoành, quay một góc 90^circ bằng toán tử j, ta viết j1, và thu được vector (0,1), chính là số 1 trên trục tung. Giả sử cho toán tử j tác dụng hai lần lên số 1, tức j^21, bằng cách quay vector (1,0) theo góc 90^circ hai lần, chúng ta thu được vector (-1,0), tức số -1 trên trục hoành. Đó là lý do tại sao j^2 lại bằng -1.
Bản chất của j không khác gì chính là phép quay quanh một trục. Nếu muốn quay một góc bất kì, ví dụ 30^circ, ta đưa 30/90 = 1/3 vào tầm tác dụng của toán tử j và thu được j^{1/3} – chính là phép quay 30 độ. Để kiểm tra lại, ta làm phép quay 30^circ ba lần:
left(j^{1/3}right)^3=j,
cho ra đúng phép quay 90 độ, phù hợp logic.
Từ đây khi biểu diễn vector z = a+jb, ta hiểu rằng vector này được cấu thành từ hai thành phần hình chiếu: thành phần a theo trục hoành, còn thành phần b bị quay 90 độ và hướng theo trục tung. Toán tử j phải là phép quay 90 độ chứ không phải góc nào khác, bởi vì có như thế ta mới làm việc với hệ trực giao (cắt nhau vuông góc), rất thuận tiện khi tính toán. Giả như j là phép quay 60 độ, ta vẫn biểu diễn được mọi số, nhưng các thành phần vector không phải trực giao nên các định lý sẽ có dạng phức tạp không cần thiết, đôi khi không thể biểu diễn. Điển hình như định lý Pythagor không thể biểu diễn một cách đơn giản r^2 = a^2+b^2 như hệ trực giao (r – chiều dài của vector z).
Toán tử j và chuyển động tròn đều
Xét một chất điểm chuyển động tròn đều với vận tốc góc omega theo ngược chiều kim đồng hồ trên quỹ đạo tròn có tâm ở gốc toạ độ và bán kính R như hình dưới.
Ta có thể biểu diễn toạ độ của chất điểm theo hệ trục toạ độ Descartes:
begin{aligned}x&=Rcosomega t,\y&=Rsinomega t,end{aligned}
hay
begin{aligned}vec{r}&=x+jy\&=Rcosomega t+jRsinomega t.end{aligned}tag{1}
vec{v}=jomegavec{r}.
Bởi vận tốc là đạo hàm của toạ độ theo thời gian:
frac{dvec{r}}{dt}=jomegavec{r}.tag{2}
Phương trình (2) có nghiệm là hàm mũ:
vec{r}=Re^{jomega t},tag{3}
miêu tả chuyển động tròn đều dưới dạng số phức.
So sánh (1) và (3), ta rút ra được hệ thức:
e^{jvarphi}=cosvarphi+jsinvarphi,tag{4}
trong đó varphi=omega t. Hệ thức (4) còn gọi là công thức Euler, vừa được chứng minh bằng phương pháp hình học. Nếu thay varphi=pi ta có được đẳng thức Euler nổi tiếng
có tính chất hết sức đặc biệt: nó chứa số 0, đơn vị số thực 1, đơn vị “số ảo” j, số pi, số e và dấu đẳng thức.
Công thức (3) cho chúng ta một công cụ biểu diễn số phức theo một cách thuận tiện khác:
z=Re^{jvarphi},
với R – độ dài của vector z, varphi – góc hợp bởi vector z với trục Ox.
Lưu ý rằng bản thân toán tử j cũng có thể biểu diễn thành hàm mũ với góc quay varphi=pi/2:
j=e^{jdfrac{pi}{2}}.
j – toán tử tuyến tính
Phép quay j là một toán tử tuyến tính, có nghĩa nó mang đầy đủ các tính chất kết hợp và tính chất phân phối. Thực vậy, việc kéo dài vector z lên k lần rồi cho quay một góc 90 độ cũng tương đương với việc cho vector z quay 90 độ trước rồi sau đó mới kéo giãn ra k lần:
Mặt khác, việc cho hai vector cộng lại rồi cho vector tổng quay 90 độ cũng cho ra cùng một kết quả với việc cho mỗi vector quay riêng rẽ 90 độ rồi mới cộng chúng lại với nhau:
j(z_1+z_2)=jz_1+jz_2.
Do mang bản chất tuyến tính, toán tử j hành xử không khác gì một phép nhân. Cho nên trong các tình huống bắt gặp số phức, ta thấy j như một thành tố được nhân vào mà ta hay quen gọi một cách không có lợi là “đơn vị ảo”. Chúng ta cùng kiểm tra lại toán tử quay 90 độ j khi nó tác dụng lên vector z=a+jb:
jz=j(a+jb)=-b+ja=z’.
Rõ ràng toán tử j đã quay vector z thành z’, một vector có cùng độ dài nhưng lệch một góc 90 độ theo ngược chiều kim đồng hồ. Ta cũng thấy rõ điều đó khi biểu diễn tác dụng này theo hàm mũ:
jz=jRe^{jvarphi}=Re^{j(varphi+pi/2)}.
Nhờ tính chất tuyến tính, ta thấy phép cộng trừ hai số phức không khác gì cộng trừ hai vector:
(a_1+jb_1)pm(a_2+jb_2)=(a_1pm a_2)+j(b_1pm b_2).
Trong khi đó phép nhân hai số phức chính là sự chồng chập của phép quay:
z_1z_2 = R_1e^{jvarphi_1}R_2e^{jvarphi_2}=R_1R_2e^{j(varphi_1+varphi_2)},
có nghĩa: tích của hai số phức có modul bằng tích các modul và có góc quay bằng tổng các góc quay. Từ đây có thể khái quát lên phép tính luỹ thừa cho số phức, theo De Moivre:
z^n=left(Re^{jvarphi}right)^n=R^ne^{jnvarphi},
cũng như phép khai căn:
z^{1/n}=left(Re^{jvarphi}right)^{1/n}=R^{1/n}e^{jvarphi/n}.
Phép khai căn của số phức mang lại vẻ đẹp thuận tiện về tính đối xứng. Căn bậc hai luôn có 2 nghiệm, căn bậc 3 luôn có 3 nghiệm, căn bậc n luôn có n nghiệm… Ví dụ ta muốn lấy căn bậc hai của 4, tức căn của vector (4,0), chỉ cần chia quỹ đạo quay của vector thành 2 nửa, một nghiệm sẽ cho vector (2,0)) tức số 2, còn nghiệm kia cho ra vector (-2,0)) tức -2. Thử lại, xét theo vector, (2,0) khi bình phương lên sẽ cho ra vector (4,0), vì góc quay của nó vốn bằng 0, quay thêm lần nữa cũng trùng hướng đó. Vector (-2,0) khi bình phương lên cũng vẫn cho ra vector (4,0), bởi vì (-2,0) có hướng 180 độ, bình phương lên sẽ thành 360^circ, tức 0 độ. Nếu thử lại theo thành phần trục hoành, ta vẫn có được 2^2 = 4 và (-2)^2 = 4.
Nhớ lại rằng trong toán học thông thường, căn bậc hai của 4 chỉ bằng 2, trong khi đó theo định nghĩa căn của 4 phải là số nào đó bình phương lên bằng 4, lúc này cả 2 lẫn -2 đều thoả mãn. Hai nghiệm dành cho căn bậc hai là kết quả hợp lý.
Moment quay của một vector
Xét hai số phức
begin{aligned}z_1&=a_1+jb_1,\z_2&=a_2+jb_2.end{aligned}
Phép nhân liên hợp của hai số phức z_1 và z_2 được định nghĩa như sau:
begin{aligned}z_1^*z_2&=(a_1-jb_1)(a_2+jb_2)\&=(a_1a_2+b_1b_2)+j(a_1b_2-b_1a_2),end{aligned}tag{5}
trong đó z_1^*=a_1-jb_1 – số phức liên hợp của z_1. Phần thực của phép nhân liên hợp (5) được gọi là tích vô hướng của hai vector:
z_1cdot z_2=Re(z_1^*z_2)=a_1a_2+b_1b_2.
Phần “ảo” của phép nhân liên hợp (5) có trị số bằng độ lớn của vector tích có hướng:
Chiều của vector tích có hướng z_1times z_2 được quy ước theo trục vuông góc với mặt phẳng chứa z_1 và z_2 theo quy tắc xoắn ốc.
Xét vector vec{F} nằm trên mặt phẳng xOy với các thành phần hình chiếu F_x và F_y:
Moment của vector vec{F} là một vector hướng theo trục Oz, biểu diễn qua tích có hướng của cánh tay đòn vec{r} và vec{F}:
trong đó vec{r}=x+jy – toạ độ của điểm đặt vector vec{F}. Nếu vec{F} là lực tác dụng, công thức (6) miêu tả moment lực, nếu vec{F} là động lượng, công thức (6) miêu tả moment động lượng… Trong vật lý, moment của một vector gắn liền với vận động quay, do đó sự có mặt của toán tử j không có gì lạ.
Toán tử j trong dao động và sóng
Trong lĩnh vực dao động và sóng, bao gồm cả dòng điện xoay chiều cũng như xử lý tín hiệu, toán tử j được áp dụng rất thành công nhờ quy sự dao động điều hoà thành hình chiếu của một chuyển động tròn. Không có gì khó hiểu khi trong các lĩnh vực này, số phức được áp dụng rộng rãi do tính chất quay của nó. Trong khi đó mọi đại lượng vật lý đều phải là số thực, thì quả thật số phức không hề đưa vào một thành phần “ảo” nào ở đây cả. Số phức lúc này chẳng qua là một vector quay đều quay trục với vận tốc mà ta gọi là tần số. Làm việc với toán tử quay thuận tiện hơn nhiều so với các phép toán đầy sin, cos của lượng giác, bởi vì phép cộng vector đơn giản hơn nhiều so với phép cộng lượng giác.
Dòng điện biến thiên điều hoà có thể diễn tả thông qua hình chiếu của chuyển động tròn đều:
I=I_0cosomega t=Releft(I_0e^{jomega t}right).
Trong nhiều trường hợp, người ta quy luôn đại lượng biến thiên điều hoà tương đương với phép quay đều. Khi ấy dòng điện xoay chiều nói trên viết hẳn thành:
I=I_0e^{jomega t}.
Khi dòng này đi qua điện trở thuần R, nó tạo ra một điện áp theo định luật Ohm:
U_R=RI=RI_0e^{jomega t}.
Khi dòng này tạo tác dụng tích điện lên tụ có điện dung C:
I=frac{dq}{dt}=Cfrac{dU_C}{dt}
và tạo nên một điện áp tức thời giữa hai bản tụ:
U_C=frac{1}{C}int{I,dt}=frac{1}{jomega C}I_0e^{jomega t}=-jfrac{1}{omega C}cdot I.
Khi dòng I nói trên đi qua một ống dây có độ tự cảm L, điện áp tức thời xuất hiện trên cuộn dây tuân theo định luật Faraday:
U_L=frac{dPhi}{dt}=Lfrac{dI}{dt}=jomega LI_0e^{jomega t}=jomega Lcdot I.
Từ trên ta thấy rằng, điện áp giữa hai đầu điện trở thuần luôn cùng pha với dòng điện. Với tụ, điện áp chậm pha hơn dòng điện 1/4 chu kỳ. Còn điện áp hai đầu cuộn cảm lại nhanh pha hơn dòng điện 1/4 chu kỳ.
Công suất tức thời là tích vô hướng của điện áp với cường độ dòng điện:
P=Ucdot I=Re(U^*I),
trong đó U^* – số phức liên hợp của U. Áp dụng lần lượt cho các trường hợp điện trở, tụ điện và cuộn cảm:
P_R=Re(U_R^*I)=Re(RI_0e^{-jomega t}I_0e^{jomega t})=I_0^2R. P_C=Re(U_C^*I)=Re(frac{1}{jomega C}I_0e^{-jomega t}I_0e^{jomega t})=0. P_L=Re(U_L^*I)=Re(jomega LI_0e^{-jomega t}I_0e^{jomega t})=0.
Tụ điện và cuộn cảm lý tưởng không gây hao phí công suất trên chúng.
Toán tử j trong cơ học lượng tử
Phương trình Newton đóng vai trò trọng tâm trong cơ học cổ điển:
frac{partial^2 x}{partial t^2}=frac{F_x}{m}.
Theo đó, trạng thái (gồm toạ độ và vận tốc) của hạt trong tương lai rất gần t+dt phụ thuộc hoàn toàn vào trạng thái lúc thời điểm hiện tại t. Biết trạng thái của hiện tại, có thể suy ra trạng thái của tương lai rất gần. Rồi trạng thái của tương lai rất gần sau đó cũng lại được suy ra từ trạng thái trước đó. Cứ thế, nhờ vào phương trình Newton, ta có thể suy ra trạng thái của hạt tại bất kì thời điểm nào trong tương lai.
Trong cơ học lượng tử, trạng thái của hạt được miêu tả qua hàm sóng psi(x,t) luôn biến chuyển theo thời gian. Để tiên đoán trạng thái tương lai, ta cũng cần một phương trình cơ bản, tương tự như phương trình Newton trong cơ học cổ điển.
Theo Louis de Broglie, một hạt tự do có xung lượng p và năng lượng E xác định sẽ tương ứng với một sóng hình sin có số sóng k=p/hbar và tần số omega=E/hbar:
psi(x,t)=Acos(kx-omega t),tag{7}
với hbar – hằng số Planck. Nói ngược lại một sóng vật chất hình sin có số sóng k và tần số omega sẽ tương ứng với một hạt tự do có xung lượng và năng lượng:
p=hbar k,qquad E=hbaromega.
Mặt khác, giữa xung lượng và năng lượng lại có mối liên hệ:
hay:
hbaromega=frac{hbar^2k^2}{2m}.tag{8}
Để làm xuất hiện những biểu thức trong (8), chỉ cần lấy đạo hàm của hàm sóng (7) theo thời gian và theo toạ độ:
begin{aligned}hbarfrac{partialpsi}{partial t}&=hbaromegasin(kx-omega t),\-frac{hbar^2}{2m}frac{partial^2psi}{partial x^2}&=frac{hbar^2k^2}{2m}cos(kx-omega t).end{aligned}tag{9}
Hệ thức (8) sẽ được thoả mãn nếu trong hệ (9) hàm sin biến thành hàm cos:
hbarfrac{partialpsi}{partial t}=-frac{hbar^2}{2m}frac{partial^2psi}{partial x^2}.
Thực tế ta có thể biến đổi hàm sin thành hàm cos thông qua phép dịch pha 1/4 chu kì, tức xoay pha lên 90^circ:
sin(alpha+pi/2)=cosalpha.
Từ đây ta có được phương trình:
{mathrm{xoay pha} 90^circ}left(hbarfrac{partialpsi}{partial t}right)=-frac{hbar^2}{2m}frac{partial^2psi}{partial x^2}.tag{10}
Tuy nhiên toán tử {mathrm{xoay pha} 90^circ} nói trên không thuận tiện trong biểu diễn và tính toán. Do đó trong cơ học lượng tử, người ta đề xuất sử dụng các hàm sóng dưới dạng phức. Trường hợp sóng sin tương ứng với hạt tự do hàm sóng (7) viết thành:
psi(x,t)=Ae^{j(kx-omega t)}.
Khi ấy toán tử {mathrm{xoay pha} 90^circ} có thể thay bằng toán tử quay j, và phương trình (10) được viết lại:
jhbarfrac{partialpsi}{partial t}=-frac{hbar^2}{2m}frac{partial^2psi}{partial x^2}.
Trong trường hợp tổng quát khi hạt chuyển động trong trường thế U(x):
jhbarfrac{partialpsi}{partial t}=-frac{hbar^2}{2m}frac{partial^2psi}{partial x^2}+U(x)psi.tag{11}
Phương trình (11) do Schrodinger đề xuất vào năm 1926, đóng vai trò chủ đạo trong cơ học lượng tử. Với sóng sin cho hạt tự do, toán tử j đứng trước phương trình trên đơn giản chỉ là sự đảo pha với ý nghĩa rằng: trạng thái của hạt trong hiện tại có thể suy ra từ trạng thái của quá khứ 1/4 chu kì trước đó. Với hạt trong trường thế bất kì, tính thuần nhất của phương trình Schrodinger cho phép trạng thái của hạt là sự chồng chập từ những sóng sin, và sự đảo pha 90^circ vẫn mang ý nghĩa.
Toán tử j và các hệ đối xứng
Định lý Cauchy dành cho hàm số phức nói rằng: nếu hàm f(z) khả vi thì tích phân của hàm đó theo một đường cong khép kín bất kì luôn bằng 0:
Cụm câu “theo một đường khép kín” đã nói lên bản chất vận động quay của vector. Định lý này tương đồng với định lý bảo toàn cơ năng trong vật lý: công của một trường lực xuyên tâm theo một đường cong khép kín bất kì luôn bằng 0. Thực vậy, trường lực xuyên tâm thoả mãn điều kiện khả vi Cauchy-Riemann:
begin{aligned}frac{partial F_x}{partial x}&=frac{partial F_y}{partial y},\frac{partial F_x}{partial y}&=-frac{partial F_y}{partial x}.end{aligned}
Cũng có nghĩa rằng, công của một trường lực xuyên tâm không phụ thuộc vào đường đi, chỉ phụ thuộc vào điểm đầu và điểm cuối. Do vậy ta nói trường vector xuyên tâm là một trường bảo toàn. Bảo toàn cơ năng là một định lý, không phải định luật vì được chứng minh hoàn toàn toán học. Chỉ có bảo toàn năng lượng mới gọi là định luật.
Phải nói rằng ở đâu có tính đối xứng tâm, đối xứng trục, hay tính tuần hoàn, ở đó có tính chất của hàm số phức. Các hàm số siêu việt xuất thân từ số phức như hàm Bessel, hàm Hankel, các hàm cầu… đều là hệ quả của tính chất quay của vector thông qua toán tử j, cho nên Bessel, Hankel, hàm cầu… ứng dụng rộng rãi trong việc giải các bài toán dao động của màng tròn, truyền nhiệt của thanh trụ tròn, lý thuyết nguyên tử khi làm việc với các moment quay… và dành cho các hệ đối xứng trục khác nữa.
Ngôn ngữ toán học của vector và số phức có sự tương hỗ trong các mô hình vật lý. Toán tử tịnh tiến làm nên vector, còn toán tử quay làm nên số phức. Do đó vector tương ứng với chuyển động tịnh tiến, còn số phức tương ứng với chuyển động quay.
Sách: Phương Pháp Số Phức Và Hình Học Phẳng
1. Lời nói đầu
Do nhu cầu phát triển của toán học, số phức đã ra đời từ thế kỷ trước. đến lượt nó số phức lại thúc đẩy phát triển không những Toán học mà còn các ngành khoa học khác. Ngày nay, số phức không thể thiếu được trong các ngành khoa học lý thuyết cũng như kỹ thuật. Thế mà số phức được học trong các trường phổ thông ở những năm cuối cùng, mang tính chất giới thiệu. Chúng tôi biên soạn cuốn sách này không phải để phổ biến số phức, mà chỉ dùng số phức như là công cụ giải những bài toán hình học điển hình ở phổ thông. Do vậy, chúng tôi trình bầy sơ lược về số phức mà ta sẽ dùng chứ không đi sâu nghiên cứu số phức, phần quan trọng là dùng số phức để giải bài toán hình học, chúng tôi cố gắng phân loại những bài toán hình học theo một dạng nào đấy để thấy mặt mạnh của phương pháp số phức. Ngoài ra những bài tập trong cuốn sách này là chọn lọc những bài toán hay trong hình học.
Để đọc tài liệu này, không cần yêu cầu bạn đọc biết trước về số phức, chúng tôi sẽ giới thiệu ngắn gọn và các tính chất của số phức để dùng sau này. Nếu bạn đọc còn bỡ ngỡ và tìm hiểu theo một hướng khác, thì nên xem:
A.I. Markusevits, Số phức và ánh xạ bảo giác, NXB KHKT, 1987 N.C. Toàn, Tập cho học sinh giỏi toán làm quen dần với nghiên cứu toán học, NXB GD, 1992.
Ngày nay số phức cũng là khởi đầu một ngành nghiên cứu mới trong toán học đó là hình học Fractal của thời đại vi tính. Hy vọng chúng tôi sẽ giới thiệu loại hình học mới này trong một cuốn sách khác tiếp theo.
Hà nội, 1998
2. Nội dung
Lời nói đầu iNội dung iii 1. Khái niệm về số phức 1 1.1. Định nghĩa số phức 1 1.2. Biểu diễn đại số của số phức 2 1.3. Dạng lượng giác của số phức 4 1.4. Công thức Moavrơ 7 2. Độ đo góc của hai tia 10 2.1. Góc định hướng 10 2.2. Ví dụ 12 2.3. Bài tập 15 3. Phương trình đường thẳng 18 3.1. Đường thẳng qua hai điểm 18 3.2. Phương trình tham số 19 3.3. Ví dụ 19 3.4. Bài tập 25 4. Phương trình đường tròn 27 4.1. Phương trình tổng quát 27 4.2. Đường tròn đơn vị 30 4.3. Giao điểm hai cát tuyến 31 4.4. Giao điểm hai tiếp tuyến 33 4.5. Chân đường vuông góc ở dây cung 34 4.6. Bài tập 36 5. Đường thẳng và đường tròn Euler 38 5.1. Nhãn của những điểm đặc biệt trong tam giác 38 5.2. Ví dụ 40 5.3. Bài tập 42 6. Đường thẳng Simson 45 6.1. Ba điểm trên đường thẳng Simson 45 6.2. Ví dụ 46 6.3. Bài tập 49 7. Tứ giác nội tiếp đường tròn 52 7.1. Những điểm đặc biệt của tứ giác nội tiếp 52 7.2. Ví dụ 53 7.3. Bài tập 56 8. Đường tròn đơn vị nội tiếp 59 8.1. Hệ tọa độ đơn vị mớ i 59 8.2. Ví dụ 60 8.3. Bài tập 67 9. Tam giác đồng dạng 69 9.1. Quan hệ đồng dạng của hai tam giác 69 9.2. Ví dụ 70 9.3. Bài tập 72 10. Đa giác đều 75 10.1. Nhãn của đỉnh các đa giác đều 75 10.2. Ví dụ 76 10.3. Bài tập 80 11. Diện tích đa giác 82 11.1. Công thức tính diện tích 82 11.2. Ví dụ 83 11.3. Bài tập 87 12. Lời giải và hướng dẫn bài tập 89 13. Vấn đề tiếp tục và bài tập tự giải 139 13.1. Vai trò như nhau của các nhãn điểm 139 13.2. Những định lý nổi tiếng trong hình học phẳng 141 13.3. Lời cuối cùng 149 13.4. Bài tập tự giải 150Tài liệu tham khảo 154
Một Số Phương Pháp Dạy Học Toán Học 6 Theo Mô Hình Trường Học Mới
ên đề: Một số phương pháp dạy học Toán 6 theo mô hình trường học mới Thực hiện: Nguyễn Tấn Phong Trang 10 Ví dụ 2: Đối với môn hình học 6 thì hoạt động trải nghiệm thường dễ nhận biết thông qua các yêu cầu "Thực hiện các hoạt động sau" như: Quan sát và nhận xét, Đọc và làm theo, em vẽ, em viết, hoạt động . Ở bước này giáo viên cố gắng nêu ra các câu hỏi từ bước 2 để học sinh có nhu cầu về tìm hiểu kiến thức mới và tìm hiểu nó. Đặc trưng để nhận biết ở bước 3 này chính là hoạt động "đọc kĩ nội dung sau" và các bài tập ngay sau đó. Ví dụ 1: Trong "§1: Tập hợp. Phần tử của tập hợp" - Sách HDH 6/Tr3 Chuyên đề: Một số phương pháp dạy học Toán 6 theo mô hình trường học mới Thực hiện: Nguyễn Tấn Phong Trang 11 Chú ý: - Nên soạn những câu hỏi thích hợp giúp học sinh đi vào tiến trình phân tích thuận lợi và hiệu quả. - Vì học sinh học theo tiến độ cá nhân nên giáo viên không phải lo "chạy" giáo án, do đó cần giành một ít thời gian thích hợp để các em trong nhóm kiểm tra chéo nhau phần kiến thức mới. - Khuyến khích học sinh đặt câu hỏi tình huống đối với giáo viên hoặc với bạn để nâng cao khả năng tìm tòi, khám phá và nắm sâu kiến thức mới hơn. Chuyên đề: Một số phương pháp dạy học Toán 6 theo mô hình trường học mới Thực hiện: Nguyễn Tấn Phong Trang 12 Trong một bài học Toán 6 theo mô hình trường học mới, bước này là hoạt động . Ở bước này giáo viên yêu cầu học sinh hoạt động cá nhân rồi đến hoạt động nhóm để các em học tập lẫn nhau, tự sửa lỗi cho nhau, giúp cho quá trình học tập hiệu quả hơn. Ví dụ: Trong "§9: Quy tắc dấu ngoặc" - Sách HDH 6/Tr129 Chú ý: - Có thể giao bài tập áp dụng cho cả lớp, cho từng cá nhân, hoặc theo nhóm, theo cặp đôi, theo bàn, theo tổ HS. - Các bài tập trong hoạt động luyện tập thường được thiết kế theo theo 3 mức: Thấp, trung bình, nâng cao. Tùy đối tượng học sinh mà giáo viên yêu cầu mức độ cần đạt được ngay tại lớp hoặc ra thêm bài tập để nâng cao hơn. 1.1.5. Bước 5: Vận dung Vận dụng điều đã học để giải quyết các tình huống trong thực hành, giải thích các hiện tượng trong cuộc sống hoặc thay đổi cách làm cũ. Kết quả cần đạt được ở bước 5: - Học sinh củng cố, nắm vững các nội dung kiến thức trong bài đã học. - Học sinh biết vận dụng kiến thức đã học trong hoàn cảnh mới, đặc biệt trong những tình huống gắn với thực tế đời sống hàng ngày. - Cảm thấy tự tin khi lĩnh hội và vận dụng kiến thức mới . Cách làm: - Học sinh thực hành, vận dụng từng phần, từng đơn vị kiến thức cơ bản của nội dung bài đã học. - Giáo viên giúp học sinh thấy được ý nghĩa thực tế của các tri thức toán học, từ đó khắc sâu kiến thức đã học. - Khuyến khích học sinh diễn đạt theo ngôn ngữ, cách hiểu của chính các em, tập phát biểu, tập diễn đạt bước đầu có lí lẽ, có lập luận. Bước này là hoạt động và . Ở bước này giáo viên yêu cầu học sinh hoạt động với sự trợ giúp của cộng đồng, cha mẹ, bạn bè, ... tất cả các nguồn học liệu mà các em có thể tìm được như sách báo, internet, .. Kết quả của bước này sẽ được các em chia sẻ với nhau và báo cáo với thầy cô của mình. Ví dụ: Trong "§2: Ba điểm thẳng hàng" - Sách HDH 6/T1/Tr165 Chuyên đề: Một số phương pháp dạy học Toán 6 theo mô hình trường học mới Thực hiện: Nguyễn Tấn Phong Trang 13 Chú ý: - Tuy không yêu cầu các em phải hoàn thành hết tất cả các hoạt động này, nhưng giáo viên nên khuyến khích và động viên các em để nhằm mục đích rèn luyện và hình thành dần kĩ năng sống. 1.1.6. Một số lưu ý khi giảng dạy - Có thể hiểu "Quy trình 5 bước lên lớp" chính là phương pháp dạy học "bàn tay nặn bột" được áp dụng vào trường hợp giảng dạy cụ thể là môn Toán. Quy trình dạy học 5 bước và 5 hoạt động trong sách chỉ mang tính tương đối, cho nên kế hoạch bài dạy cần phải được thiết kế linh hoạt và thực hiện mềm dẻo trong quá trình dạy học. Ở bước 4 và bước 5 xét trong phạm vi tổ chức một tiết/bài dạy, cũng có thể chia hai bước này cùng lúc với 3 hoạt động C, D, E. - Các hoạt động có thể kết hợp với nhau hoặc bớt đi một, hai hoạt động tùy đặc trưng của bài dạy, nhưng hoạt động có tính chất vui chơi, vận động không nên bớt đi mà cần sắp xếp thời gian thêm vào trong mỗi tiết dạy. Nếu bài dạy có 2 tiết dạy liền nhau thì nên có thời gian vui chơi giữa 2 tiết. - Trong tài liệu hướng dẫn học, ở mỗi bài học, các hoạt động học tập đều được chỉ dẫn cụ thể và chi tiết, nên cần rèn luyện kĩ năng cho mỗi học sinh, luôn ý thức được mình phải bắt đầu và kết thúc hoạt động học tập như thế nào, không cần chờ đến sự nhắc nhở của giáo viên. 1.2. Quy trình 10 bước học tập của học sinh theo mô hình trường học mới Bước 1. Chúng em làm việc nhóm (nhóm trưởng lấy tài liệu và đồ dùng). Bước 2. Em đọc tên bài học và viết vào vở. Bước 3. Em đọc mục tiêu bài học. Bước 4. Em thực hiện hoạt động cơ bản ( nhớ xem làm việc cá nhân hay theo nhóm theo lôgô trong tài liệu). Bước 5. Kết thúc HĐ cơ bản, em tự đánh giá rồi báo cáo những việc đã làm được với thầy, cô giáo để thầy, cô xác nhận. Bước 6. Em thực hiện hoạt động thực hành (Làm việc cá nhân rồi chia sẻ với bạn kề bên, với cả nhóm). Bước 7. Chúng em đánh giá cùng thầy, cô giáo. Chuyên đề: Một số phương pháp dạy học Toán 6 theo mô hình trường học mới Thực hiện: Nguyễn Tấn Phong Trang 14 Bước 8. Em thực hiện Hoạt động ứng dụng (với sự giúp đỡ của gia đình, người lớn). Bước 9. Kết thúc bài, em viết vào Bảng đánh giá. Bước 10. Em đã học xong bài mới em phải ôn lại phần nào? Sơ đồ quy trình 10 bước học tập Chuyên đề: Một số phương pháp dạy học Toán 6 theo mô hình trường học mới Thực hiện: Nguyễn Tấn Phong Trang 15 2. Phương pháp dạy học theo nhóm 2.1. Các cách chia nhóm Trong thực tế thì có nhiều kiểu nhóm khác, tôi nêu ra 11 kiểu điển hình, cách chia và các hình thức chia các nhóm này. Cách chia như sau: 2.1.1. Nhóm đếm số: Muốn chia lớp thành n nhóm thì chia tổng số học sinh của lớp cho n để xác định số học sinh trong một nhóm. Ví dụ: Lớp có 30 học sinh, muốn chia thành 5 nhóm thì yêu cầu học sinh đếm 1,2,3,4;5;6. Yêu cầu những học sinh có số đếm là 1 thì về nhóm 1, những học sinh có số 2 về nhóm 2 Ưu điểm:Tốn ít thời gian, tạo cho học sinh có không khí học tập thoải mái, phong cách nhanh nhẹn, áp dụng được cho tất cả các môn học. 2.1.2. Nhóm biểu tượng: Biểu tượng có thể là: (con vật, cây cối, hình ảnh, các bông hoa ) Muốn chia lớp thành n nhóm thì bạn phải chuẩn bị n biểu tượng . Ví dụ: Lớp có 30 học sinh, muốn chia thành 5 nhóm theo biểu tượng là con vật, bạn phải chuẩn bị các con vật như: Chào mào, Vành khuyên, Thỏ ngọc, Sơn ca, Hoàng yến, Sóc nâu chẳng hạn. Mỗi con vật phải có 5 biểu tượng. Cho học sinh chọn các biểu tượng đó, rồi chia nhóm theo biểu tượng từng con vật hoặc nhóm có đủ 6 con vật. Ưu điểm: Tốn ít thời gian, tạo cho học sinh có không khí học tập thoải mái, lớp học sinh động, tạo cơ hội thể hiện sở thích của các em. Lớp học sôi nổi hứng thú cho tất cả học sinh. Nhược điểm: GV phải chuẩn bị nhiều, gây tốn kém. 2.1.3. Nhóm mã màu: Hình thức chia như nhóm biểu tượng. 2.1.4. Nhóm cặp đôi: Xếp 2 học sinh vào một cặp . 2.1.5. Nhóm sở thích: Những học sinh có cùng sở thích ngồi cùng một nhóm. "Những người cùng sở thích thì sự thống nhất sẽ cao hơn." 2.1.6. Nhóm tương trợ: Xếp những học sinh có trình độ và năng lực khác nhau (khá giỏi và trung bình- yếu) vào một nhóm, để học sinh khá giỏi có thể hỗ trợ cho học sinh yếu. Chuyên đề: Một số phương pháp dạy học Toán 6 theo mô hình trường học mới Thực hiện: Nguyễn Tấn Phong Trang 16 Chuyên đề: Một số phương pháp dạy học Toán 6 theo mô hình trường học mới Thực hiện: Nguyễn Tấn Phong Trang 17 + Hình thức tổ chức trò chơi phải đa dạng, phong phú. + Trò chơi phải được chuẩn bị chu đáo + Trò chơi phải gây được hứng thú đối với học sinh 3.2. Cấu trúc của Trò chơi học tập: + Tên trò chơi + Mục đích: Xác định rõ mục đích của trò chơi nhằm ôn luyện, củng cố kiến thức, kỹ năng nào. + Đồ dùng, đồ chơi: Mô tả đồ dùng, đồ chơi được sử dụng trong Trò chơi học tập. + Luật chơi: Chỉ rõ quy tắc của hành động chơi quy định đối với người chơi, quy định thắng thua của trò chơi. + Số người tham gia chơi: Cần chỉ rõ số người tham gia trò chơi + Nêu cách chơi. 3.3. Cách tổ chức trò chơi Thời gian tiến hành: thường từ 5 - 7 phút - Đầu tiên là giới thiệu trò chơi : + Nêu tên trò chơi. + Hướng dẫn cách chơi bằng cách vừa mô tả vừa thực hành, nêu rõ quy định chơi. - Chơi thử và qua đó nhấn mạnh luật chơi - Chơi thật - Nhận xét kết quả chơi, thái độ của người tham dự, giáo viên có thể nêu thêm những tri thức được học tập qua trò chơi, những sai lầm cần tránh. - Thưởng - phạt: Phân minh, đúng luật chơi, sao cho người chơi chấp nhận thoải mái và tự giác làm trò chơi thêm hấp dẫn, kích thích học tập của học sinh. Phạt những học sinh phạm luật chơi bằng những hình thức đơn giản, vui (như chào các bạn thắng cuộc, hát một bài, nhảy lò cò...) 3.4. Một vài trò chơi điển hình Trò chơi: Hái hoa dân chủ (Áp dụng trong những tiết luyện ôn tập) - Mục đích : Rèn các kỹ năng tính toán, ôn tập kiến thức, kỹ năng giải toán. - Chuẩn bị : + Một cây cảnh, trên có đính các bông hoa bằng giấy màu trong có các đề toán. + Phần thưởng + Đồng hồ - Cách chơi: + Cho các em chơi trong lớp. Lần lượt từng em lên hái hoa. Em nào hái được hoa thì đọc to yêu cầu cho cả lớp cùng nghe. Sau đó suy nghĩ trong vòng 30 giây rồi trình bày câu trả lời trước lớp. Em nào trả lời đúng thì được khen và được một phần thưởng. + Tổng kết chung khen những em chơi tốt . Trò chơi : Rồng cuốn lên mây - Mục đích: Kiểm tra kỹ năng tính nhẩm của học sinh. - Chuẩn bị: Một tờ giấy viết sẵn các bài toán đã học. - Cách chơi : Một em được chỉ định làm đầu rồng lên bảng. + Em cất tiếng hát : Chuyên đề: Một số phương pháp dạy học Toán 6 theo mô hình trường học mới Thực hiện: Nguyễn Tấn Phong Trang 18 "Rồng cuốn lên mây Rồng cuốn lên mây Ai mà tính giỏi về đây với mình" + Sau đó em hỏi : "Người tính giỏi có nhà hay không ?" - Một em học sinh bất kỳ trả lời : "Có tôi ! Có tôi !" - Em làm đầu rồng ra phép tính đó, ví dụ : "- 2 + 3 - 5 bằng bao nhiêu ?" - Em tính giỏi trả lời (nếu trả lời đúng thì được đi tiếp theo em đầu rồng). Cứ như thế em làm đầu rồng cứ ra câu hỏi và cuốn đàn lên mây. 4. Các phương pháp thường dùng khi dạy học 4.1. Phương pháp trực quan Phương pháp trực quan trong dạy học Toán nói chung và dạy học Toán 6 mô hình trường học mới nói riêng là phương pháp đặc biệt quan trọng, phương pháp này đòi hỏi nhóm trưởng tổ chức hướng dẫn các bạn hoạt động trực tiếp theo yêu cầu trong mỗi hoạt động, dựa vào đó nắm bắt được kiến thức kĩ năng. 4.2. Phương pháp gợi mở - vấn đáp Phương pháp gợi mở vấn đáp là phương pháp dạy học không trực tiếp đưa ra những kiến thức hoàn chỉnh mà sử dụng một hệ thống câu hỏi để hướng dẫn giúp đỡ học sinh khi các nhóm không thể hoàn thành được kiến thức cho riêng mình. Giáo viên giúp học sinh suy nghĩ và lần lượt trả lời từng câu hỏi, từng bước tiến dần đến kết luận cần thiết, giúp học tìm ra những kiến thức mới. 4.3. Phương pháp giảng giải minh hoạ Phương pháp giảng giải minh hoạ trong dạy học Toán là phương pháp dùng lời nói để giải thích tài liệu Toán, kết hợp các phương tiện trực quan để hỗ trợ cho việc giải thích. Tuy nhiên với phương pháp này giáo viên cần điều hành nhóm trưởng rút ra kiến thức trong nhóm, nói ngắn gọn, rõ ràng, dễ hiểu. 4.4. Phương pháp thực hành luyện tập: Phương pháp thực hành luyện tập là phương pháp giáo viên tổ chức cho học sinh luyện tập các kiến thức kĩ năng của học sinh thông qua các hoạt động thực hành luyện tập. Hoạt động thực hành luyện tập chiếm hơn 50% tổng thời lượng dạy học ở lớp 6. Vì vậy phương pháp này được sử dụng thường xuyên trong các tiết dạy như học kiến thức mới, trong các tiết ôn tập, luyện tập. Nhiệm vụ chủ yếu của dạy học thực hành luyện tập là củng cố kiến thức và kĩ năng cơ bản của chương trình, rèn luyện các năng lực thực hành, giúp học sinh nhận ra rằng: học không chỉ để biết mà học còn để làm, để vận dụng. Tóm lại: Trong dạy học Toán 6 mô hình trường học mới, người giáo viên cần biết vận dụng linh hoạt và lựa chọn các phương pháp phù hợp từng hoạt động bài học phù hợp với từng đối tượng học sinh, để hướng dẫn học sinh tự tìm tòi chiếm lĩnh kiến thức mới, hướng dẫn học sinh thực hành hình thành và rèn luyện kĩ năng, hướng dẫn học sinh giải Toán, kết hợp việc vận dụng phương pháp dạy học hợp tác theo nhóm nhỏ, dạy học dự án, hay trò chơi Toán học, nhằm đáp ứng nhu cầu đổi mới trong dạy học Toán 6 theo mô hình trường học mới. Chuyên đề: Một số phương pháp dạy học Toán 6 theo mô hình trường học mới Thực hiện: Nguyễn Tấn Phong Trang 19 5. Một số kĩ thuật tổ chức hoạt động học và tiến trình các bước lên lớp 5.1. Kĩ thuật tổ chức hoạt động học theo kí hiệu Sách hướng dẫn học Toán 6 được thiết kế theo một cấu trúc trình tự, mỗi hoạt động học đều được kí hiệu cách học: Trước khi bước vào một tiết học giáo viên yêu cầu nhóm trưởng kiểm tra các dụng cụ hỗ trợ học tập của các thành viên như giấy nháp, bút, thước kẻ, ... c. Hoạt động chung cả lớp : Thông thường đến hoạt động này giáo viên nên ngừng lớp học lại, yêu cầu tất cả học sinh chú ý vào nội dung hoạt động. Cách tổ chức hoạt động: - Giáo viên hoặc Chủ tịch HĐTQ mời 1 hoặc 2 bạn đọc nội dung hoạt động (thường đây là phần kiến thức mới cần ghi nhớ), tất cả học sinh phải chú ý vào nội dung không làm việc riêng. - Giáo viên giải thích thêm hoặc đặt thêm câu hỏi để làm rõ nội dung kiến thức. Chuyên đề: Một số phương pháp dạy học Toán 6 theo mô hình trường học mới Thực hiện: Nguyễn Tấn Phong Trang 20 - Vì học sinh học theo tiến độ, có nghĩa sẽ có nhóm chưa hoàn thành để đến hoạt động chung tiếp theo. Do đó giáo viên cần tìm cách đảm bảo tiến độ chung cho cả lớp để tránh phải trình bày cùng một nội dung kiến thức ở từng nhóm riêng lẻ. Thực tế, sách thiết kế hoạt động tiếp theo 1b, 1c, 2b, 2c, như hình: Thường thì đây là hoạt động cặp đôi hoặc nhóm với những bài tập không khó như phần luyện tập mà rất đơn giản bám sát kiến thức mới, nên rất dễ để đảm bảo tiến độ chung các nhóm. d. Hoạt động cá nhân : Cá nhân tự làm các bài tập rồi báo cáo kết quả với thầy/cô giáo. Sự phân hóa khả năng học sinh thể hiện rõ nhất trong hoạt động này. Lúc này là lúc mà giáo viên phải chú ý đến hai đối tượng là học sinh yếu và khá giỏi. Chú ý: - Mặc dù là hoạt động cá nhân để làm các bài tập nhưng giáo viên nên yêu cầu nhóm cùng tham gia vào bài tập và đảm bảo tiến độ chung theo cả nhóm. Hiểu "nôm na" là gắn tiến độ cá nhân là trách nhiệm chung của nhóm. - Phải rèn được ý thức "Cá nhân tự giác yêu cầu trợ giúp từ bạn, thầy cô". - Vì thời gian tiết học hạn chế nên giáo viên không thể trợ giúp hết tất cả học sinh yếu, nên cần áp dụng chia các cặp hỗ trợ học tập để những em học lực khá giỏi hướng dẫn cho các bạn yếu hơn hoàn thành bài tập. - Cũng có thể bỏ qua thiết kế bài tập của sách mà chỉ chọn một vài bài đặc trưng nhất cho những bạn học yếu hoàn thành, phần còn lại về nhà các em hoàn thành tiếp. Chuyên đề: Một số phương pháp dạy học Toán 6 theo mô hình trường học mới Thực hiện: Nguyễn Tấn Phong Trang 21 - Chuẩn bị các bài tập khó hơn cho các em học sinh khá giỏi (nếu thật sự cần). e. Hoạt động báo cáo: Có 3 lần báo cáo kết quả trong một bài học như sau: Sau hoạt động sẽ có: Lúc này là lúc giáo viên chốt lại phần lý thuyết là những kiến thức chính của bài học. Cần rèn cho học sinh cách trả lời và kiểm tra bằng cách bám vào mục tiêu bài học. Có nghĩa mục tiêu có bao nhiêu ý thì trả lời bấy nhiêu ý. Để khắc sâu hơn giáo viên có thể chuẩn bị nội dung này trên máy chiếu để chiếu cho học sinh nắm lại một lần nữa những vấn đề chính. Phần chốt kiến thứ
Độ Phức Tạp Tính Toán
Nguồn bài: Topcoder
…đọc phần 1
Giới thiệu
Trong phần này của bài viết chúng ta sẽ tập trung vào việc ước lượng độ phức tạp cho các chương trình đệ quy. Về mặt bản chất việc này sẽ dẫn tới khảo sát độ tăng của các hàm độ phức tạp thời gian thỏa mãn các công thức truy hồi. Nếu bạn chưa hiểu chính xác thế nào là một thuật giải đệ quy thì không cần lo lắng vì nó sẽ được giải thích trong các phần sau. Trước mắt chúng ta sẽ xem xét trường hợp đơn giản hơn – các chương trình không sử dụng đệ quy.
Vòng lặp lồng nhau
Để mở đầu, ta xét các chương trình đơn giản không sử dụng các lời gọi đệ quy. Với các chương trình như vậy, ba quy tắc phổ biến dễ áp dụng để tìm cận trên của độ phức tạp là:
Tính số lần lặp tối đa của một vòng lặp
Nếu các vòng lặp nối tiếp nhau thì cộng các cận đó với nhau
Nếu các vòng lặp lồng nhau thì nhân các cận với nhau
Ví dụ 1
Ước lượng độ phức tạp của đoạn mã sau:
int
result
=
0
;
// 1
for
(
int
i
=
0
;
i
<
N
;
i
++
)
// 2
for
(
int
j
=
i
;
j
<
N
;
j
++
)
{
// 3
for
(
int
k
=
0
;
k
<
M
;
k
++
)
{
// 4
int
x
=
0
;
// 5
while
(
x
<
N
)
{
result
++
;
x
+=
3
;
}
// 6
}
// 7
for
(
int
k
=
0
;
k
<
2
*
M
;
k
++
)
// 8
if
(
k
%
7
==
4
)
result
++
;
// 9
}
// 10
Rõ ràng độ phức tạp của vòng lặp while ở dòng 6 là $O(N)$ – số lần lặp không vượt quá $N/3+1$ lần.
Xét vòng lặp for ở các dòng 4 – 7. Dễ thấy biến $k$ được tăng lên $M$ lần. Mỗi lần như vậy thì toàn bộ vòng lặp while ở dòng 6 lại được thực thi. Như vậy tổng số độ phức tạp của đoạn lệnh từ dòng 4 tới 7 là $O(MN)$ (áp dụng quy tắc 3)
Độ phức tạp của vòng for ở các dòng 8 – 9 là $O(M)$. Như vậy tổng độ phức tạp của dòng từ 4 tới 9 là $O(MN + M) = O(MN)$ (áp dụng quy tắc 2 và loại đại lượng không đáng kể)
Toàn bộ phần mã bên trong này được thực thi $O(N^2)$ lần – mỗi lần tương ứng với một tổ hợp của biến $i$ và $j$ (dòng 2 và 3) (chú ý là chỉ có $N(N + 1)/2$ giá trị khác nhau cho bộ số $[i,j]$. Mặc dù vậy $O(N^2)$ vẫn là cận trên đúng).
Từ nhận xét trên ta có tổng độ phức tạp của thuật toán trong Ví dụ 1 là $O(N^2 MN) = O(MN^3)$.
Từ ví dụ trên người đọc đã có khả năng phân tích độ phức tạp của các phần mã đơn giản sử dụng phương pháp như đã trình bày. Chúng ta sẽ đi tới xem xét các chương trình có sử dụng đệ quy (tức là một hàm số mà trong thân hàm của nó sẽ gọi tới chính nó với tham số khác) và phân tích ảnh hưởng của những lời gọi đệ quy này tới độ phức tạp của chúng.
Sử dụng đệ quy để sinh các cấu hình tổ hợp
Một ứng dụng phổ biến của đệ quy là cài đặt thuật toán quay lui để sinh ra tất cả các nghiệm của một bài toán. Ý tưởng chung là đào sâu vào từng nhánh nghiệm đến khi nhánh nghiệm này được thử hết thì quay lại bước trước đó để thử các nhánh nghiệm khác.
Cách tiếp cận này không phải lúc nào cũng áp dụng được, có những bài toán mà ta không thể sinh ra tất cả các nghiệm để thử từng nghiệm một như vậy. Tuy nhiên, trường hợp thường xảy ra là tập nghiệm của một bài toán trùng với một loại cấu hình tổ hợp nào đó. Thông thường đó là tập các hoán vị (với số phần tử cho trước), nhưng đôi lúc cũng có thể là các cấu hình khác (tổ hợp, số cách phân chia một tập hợp, …)
Lưu ý là ta luôn luôn có thể sinh ra tất cả các chuỗi của 0 và 1, kiểm tra từng chuỗi một (kiểm tra xem chuỗi đó có tương ứng với một nghiệm hợp lệ hay không) và lưu lại nghiệm tốt nhất. Nếu ta có thể tìm một cận trên của kích cỡ nghiệm tốt nhất, số nghiệm phải kiểm tra là hữu hạn. Tuy nhiên cách làm này không đủ nhanh và không nên dùng nó nếu có cách làm khác.
Ví dụ 2
Một thuật toán quay lui đơn giản để sinh ra tất cả các hoán vị của các số tự nhiên từ 0 tới $N-1$
void
try
(
int
which
,
int
what
)
{
// try taking the number “what” as the “which”-th element
permutation
[
which
]
=
what
;
used
[
what
]
=
1
;
if
(
which
==
N
–
1
)
outputPermutation
();
else
// try all possibilities for the next element
for
(
int
next
=
0
;
next
<
N
;
next
++
)
if
(
!
used
[
next
])
try
(
which
+
1
,
next
);
used
[
what
]
=
0
;
}
int
main
()
{
// try all possibilities for the first element
for
(
int
first
=
0
;
first
<
N
;
first
++
)
try
(
0
,
first
);
}
Trong trường hợp này, dễ thấy cận dưới chính là số lượng nghiệm khả dĩ của bài toán. Thuật toán quay lui thường được sử dụng để giải các bài toán khó – khi ta không tìm được thuật toán nào tối ưu hơn. Thường thì không gian nghiệm khá lớn và phân bố đồng đều, thuật toán có thể được cài đặt sao cho độ phức tạp gần với đánh giá cận dưới. Để tìm cận trên ta chỉ việc cộng thêm số lượng phép tính cần thiết trong thực tế.
Tuy vậy cách làm này thường là không khả thi do nó phải khảo sát một số lượng lớn các nghiệm – thường là hàm mũ hoặc lớn hơn thế.
Chia để trị sử dụng đệ quy
Từ ví dụ 2 chúng ta có thể nhầm tưởng rằng đệ quy chạy không hiệu quả và làm cho tốc độ thực thi rất chậm. Không phải lúc nào điều này cũng đúng. Ngược lại, đệ quy có thể là một công cụ rất mạnh để thiết kế những thuật toán hiệu quả. Cách thông thường để thiết kệ một giải thuật đệ quy hiệu quả là áp dụng tư tưởng Chia để Trị – chia bài toán thành nhiều phần, xử lý các phần nhỏ tách biệt nhau và cuối cùng ghép các kết quả con lại để được kết quả cho bài toán lớn. Dễ thấy rằng, phần “xử lý các phần nhỏ tách biệt nhau” thường được cài đặt bằng đệ quy – tiếp tục chia phần nhỏ thành phần nhỏ hơn cho tới khi đủ nhỏ để giải trực tiếp bằng các thuật toán đơn giản.
Ví dụ 3
Mã giả mô tả thuật toán sắp xếp trộn MergeSort
MergeSort(mảng S) { if (số phần tử của S <= 1) return S; chia đôi S thành hai mảng con S1 và S2 với số phần tử gần bằng nhau; MergeSort(S1); MergeSort(S2); trộn S1 và S2 đã sắp xếp để thu được S mới đã sắp xếp; return S mới; }Ta thấy là chỉ cần $O(N)$ (hoặc $O(1)$, tùy vào cách cài đặt) để chia một mảng $N$ phần tử thành hai mảng con. Trộn hai mảng con ngắn hơn đã sắp xếp này có thể làm trong $ Theta(N)$: khởi tạo mảng $S$ rỗng. Tại mỗi bước phần tử nhỏ nhất mà chưa có trong $S$ là phần tử đầu của $S1$ hoặc $S2$. Lấy phần tử này cho vào cuối của $S$ và cứ thế tiếp tục.
Như vậy tổng độ phức tạp cần để $MergeSort$ một mảng với $N$ phần tử là $Theta(N)$ cộng với thời gian thực hiện hai lệnh gọi đệ quy.
Gọi $f(N)$ là độ phức tạp của thuật toán MergeSort ở trên. Theo suy luận ở trên ta có:
$$ f(N) = f(lfloor N/2 rfloor) + f(lceil N/2 rceil) + p(N) $$
Với $p$ là hàm tuyến tính biểu thị tổng chi phí tính toán dành cho việc chia đôi mảng ban đầu và trộn hai mảng con vào kết quả cuối.
Công thức trên được gọi là công thức truy hồi. Nếu bạn không biết thuật ngữ này thì cũng không cần lo lắng. Từ “truy hồi” (recurrence) trong tiếng Latin có nghĩa là “chạy về phía sau”. Vì vậy “công thức truy hồi” có nghĩa là giá trị của hàm $f$ được tính theo giá trị trước đó (đầu vào nhỏ hơn) của $f$.
Để định nghĩa hoàn chỉnh một công thức truy hồi, ta cần chỉ ra giá trị của một vài trường hợp khởi tạo cơ bản – trong trường hợp này là $f(1)$. Các giá trị này (và hàm $p$) sẽ cho phép ta tính toán chính xác giá trị của hàm $f$.
Tuy nhiên, như ta đã thấy ở phần 1, giá trị chính xác của hàm $f$ không phải là mục tiêu cần tính. Mặc dù về mặt lý thuyết ta có thể tính cụ thể biểu thức của hàm $f(N)$ theo dạng đóng, biểu thức đó có thể rất phức tạp và không thật sự cần thiết. Trong thực tế, ta chỉ quan tâm tới đánh giá $Theta$ (hoặc cận trên $O-lớn$) của độ tăng của hàm $f$. Thông thường các đánh giá này có thể tính được một cách khá thuận lợi nếu ta nắm được các phương pháp tính thông dụng.
Vì lý do trên, ta sẽ không cần tới dạng chính xác của hàm $p$ mà chỉ cần biết rằng $p(N) = Theta(N)$. Thêm vào đó, ta không cần giá trị khởi tạo của $p$. Ta chỉ cần biết rằng với $N$ nhỏ thì giá trị của $p$ sẽ dễ dàng tính được với độ phức tạp là hằng số.
Lý do đằng sau việc đơn giản hóa $p$ như trên là do một nhận xét: việc thay đổi các giá trị khởi tạo chỉ thay đổi nghiệm của công thức truy hồi chứ không thay đổi cận trên tiệm cận của hàm số. (Bạn có thể thử bằng cách tìm một hàm $p$ bất kỳ và tính $f(8)$, $f(16)$ và $f(32)$ với các giá trị $f(1)$ khác nhau).
Bên cạnh đó, vì đây chỉ là bài viết mang tính giới thiệu nên chúng ta sẽ không bàn đến các lý thuyết để xử lý các phép lấy phần nguyên, làm tròn lên và làm tròn xuống. Ta sẽ đơn giản bỏ qua các phép toán đó (ví dụ ta sẽ coi các phép chia luôn là chia lấy nguyên và làm tròn xuống).
Các bạn có kỹ năng toán tốt nên thử tự chứng minh mệnh đề sau đây: nếu $p$ là hàm đa thức (với $N$ không âm) và $q(n) = p(n+1)$ thì $q(n) = Theta(p(n))$. Mệnh đề trên cho phép ta chứng minh (với $f$ bị chặn trên bởi một hàm đa thức) rằng vế phải của công thức truy hồi có độ tăng tiệm cận không thay đổi khi ta thay phép làm tròn xuống bởi phép làm tròn lên.
Nhận định trên cho phép ta viết lại công thức truy hồi ở trên theo cách đơn giản hơn:
$$ f(N) = 2f(N/2) + Theta(N) spacespacespace(1) $$
Lưu ý rằng đây không phải là một “phương trình” theo nghĩa truyền thống. Ở phần 1 ta đã thấy rằng dấu bằng ở đây có nghĩa là “tiệm cận bằng”. Thông thường có rất nhiều hàm số khác nhau thỏa mãn phương trình trên. Tuy nhiên tất cả các hàm số đó sẽ có cùng độ tăng – và đây chính là điều mà ta hướng tới. Tổng quát hơn, ta muốn tìm cận trên nhỏ nhất của độ tăng của tất cả các hàm số thỏa mãn phương trình trên.
Trong các phần cuối cùng của bài viết này, ta sẽ bàn luận một vài phương pháp giải các “phương trình” trên. Tuy nhiên trước đó ta sẽ tìm hiểu thêm một chút về các hàm logarit.
Lưu ý về hàm logarit
Tới đây bạn có thể đặt câu hỏi: tác giả viết một vài thuật toán có độ phức tạp là hàm logarit ví dụ $O(NlogN)$, vậy cơ số của hàm logarit này là bao nhiêu? Tại sao ta không sử dụng cơ số 2 để có $O(Nlog_2N)$?
Câu trả lời: cơ số của hàm logarit không quan trọng, tất cả cac hàm logarit (với cơ số lớn hơn 1) đều tiệm cận bằng nhau. Lý do là hai hàm logarit khác nhau tỷ lệ với nhau:
$$ log_aN = frac{log_bN}{log_ba} spacespacespace(2) $$
Nhằm mục đích viết rõ ràng và dễ đọc, ta luôn sử dụng ký hiệu chung $logN$ bên trong hàm $O-lớn$, kể cả khi các hàm logarit khác nhau được sử dụng khi tính cận của độ phức tạp.
Bên cạnh đó, ý nghĩa của cách viết $logN$ khác nhau giữa các quốc gia khác nhau. Để tránh nhầm lẫn ta quy ước như sau: $logN$ để chỉ cơ số $10$, $lnN$ để chỉ cơ số tự nhiên, $lgN$ cho cơ số $2$ và $log_bN$ cho các trường hợp chung khác.
Từ (2) ta có:
$$ log_ab = frac{log_bb}{log_ba} = frac{1}{log_ba} $$
Sử dụng tính chất trên để biến đổi $a^{log_bN}$ ta được: $a^{log_bN} = a^{log_aN/log_ab} = (a^{log_aN})^{1/log_ab} = N^{log_ba} spacespacespace(3)$
Phương pháp Thay Thế
Phương pháp này có thể được tổng kết trong một câu: dự đoán cận trên (tiệm cận) của $f$ và (cố gắng) chứng minh bằng quy nạp.
Để minh họa, ta sẽ chứng minh rằng hàm $f$ thỏa mãn phương trình (1) là $O(NlogN)$ Từ (1) ta có:
$$ forall N; f(N) leq 2f(N/2) + cN $$
với một hằng số $c$ nào đó. Ta sẽ chứng minh rằng tồn tại một hằng số $d$ đủ lớn nào đó mà với mọi $N$ lớn ta có $f (N) leq dN lg N$. Ta sẽ chứng minh bằng quy nạp.
Giả sử $f (N/2) leq d (N/2)lg(N/2)$. Ta có:
Để hoàn thiện ta cần chứng minh rằng bất đẳng thức trên đúng với một vài giá trị đầu tiên của $N$. Phép chứng minh khá phức tạp. Ý tưởng chính là nếu giá trị $d$ ta tìm được chưa đủ lớn, ta luôn có thể tăng $d$ sao cho các trường hợp đầu tiên của $N$ thỏa mãn bất đẳng thức.
Lưu ý rằng trong ví dụ trên ta không thể chứng minh khi $N = 1$ với vì $lg1 = 0$. Tuy nhiên, điều này không ảnh hưởng tới tính đúng đắn của phép chứng minh trên. Kết luận: từ (1) ta có $f (N) = O(N lg N)$.
Phương pháp Cây Đệ Quy
Với một người mới bắt đầu thì phương pháp trên không hữu dụng lắm. Để sử dụng phương pháp Thay Thế ta cần phải có một dự đoán tốt về cận trên của độ phức tạp, và để có dự đoán tốt đó ta cần có một vài thông tin, hiểu biết về hàm độ phức tạp trước. Câu hỏi là, làm thế nào để thu thập các hiểu biết này? Trước tiên ta sẽ xem xét kỹ hơn về cơ chế chạy đệ quy của nó của hàm số trên (bằng việc chạy thử từng bước đệ quy của nó).
Ta có thể biểu diễn các bước thực thi của một chương trình đệ quy trên một bộ đầu vào cho trước bằng một cây có gốc xác định. Mỗi đỉnh trên cây sẽ tương ứng với một bài toán con mà chương trình đang giải. Xét một đỉnh bất kỳ trên cây. Nếu giải bài toán thuộc đỉnh đó cần phải gọi đệ quy, đỉnh đó sẽ có các đỉnh con tương ứng với các bài toán nhỏ hơn nữa. Gốc của cây là bộ đầu vào, các lá tương ứng với các bài toán cơ bản có thể giải trực tiếp bằng các thuật toán thông thường (không đệ quy).
Giả sử ta đánh dấu mỗi đỉnh bằng một nhãn biểu thị độ phức tạp nội tại cần có trên đỉnh đó (không tính tới độ phức tạp của lệnh gọi đệ quy). Rõ ràng là độ phức tạp của bài toán gốc bằng tổng tất cả các nhãn của các đỉnh.
Tương tự như các phần trên, ta chỉ quan tâm tới cận trên tiệm cận. Để tìm giá trị này ta có thể “làm tròn” mỗi nhãn để việc tính tổng dễ dàng hơn. Ta minh họa cách làm trên bằng một vài ví dụ sau:
Ví dụ 4
Cây đệ quy cho thuật toán MergeSort ở Ví dụ 3 với 5 phần tử.
Cây đệ quy cho công thức truy hồi tương ứng của MergeSort. Số trong mỗi đỉnh biểu thị số bước mà thuật toán thực thi tại đỉnh đó.
Ví dụ 5
Cây đệ quy trong trường hợp xấu nhất của phương trình (1):
Một cách xử lý phổ biến trong toán tổ hợp là tính tổng các cấu hình theo thứ tự mới khác với thứ tự mà các tổ hợp được tạo ra. Trong trường hợp này ta tính tổng theo từng mức trên cây (các đỉnh có cùng độ sâu). Không khó để nhận ra rằng tổng độ phức tạp ở mỗi mức là $cN$.
Câu hỏi thứ hai là: cây trên có bao nhiêu mức? Rõ ràng là lớp lá tương ứng với trường hợp cơ bản của thuật toán. Chú ý là kích cỡ mảng cần xử lý giảm một nửa khi đi từ mức trên xuống mức dưới. Vì sau $lgN$ bước ta có bài toán cơ bản với mảng có $1$ phần tử, chiều cao của cây (tổng số mức) sẽ là $Theta(logN)$.
Từ hai nhận xét trên ta thu được kết quả cuối cùng: tổng độ phức tạp cần thực hiện là $ Theta(cN log N) = Theta(N log N)$.
Nếu bạn chưa hoàn toàn tin tưởng vào kết quả vừa thu được thì có thể áp dụng phương pháp Thay Thế ở trên để kiểm tra lại. Trong phần sau ta sẽ thấy là tồn tại những định lý cụ thể để có thể chứng minh chặt chẽ kết quả thu được ở trên.
Cây Đệ Quy mở rộng
Ví dụ 5 ở trên cho ta một câu hỏi: việc tổng độ phức tạp ở mỗi mức của cây bằng nhau có phải là trùng hợp hay không?
Trả lời: Không và Có. Không, vì một lý do đơn giản mà ta sẽ xem ở phần sau. Có, vì không phải lúc nào tổng các mức cũng bằng nhau như vậy – hai ví dụ sau đây sẽ minh họa cho điều đó.
Ví dụ 6
Ta thử áp dụng phương pháp Cây Đệ Quy để giải cho phương trình sau: $f(N) = 3f(N/2) + Theta(N^3)$
Cây đệ quy sẽ có dạng sau:
Thử tính toán độ phức tạp tại vài mức đầu tiên, ta có:
level 1 2 3 …
work $cN$ $ {3over 8}cN^3 $ $ {3^2 over 8^2}cN^3 $ …
Rõ ràng là ta càng đi sâu xuống cây thì tổng độ phức tạp càng giảm. Vậy tốc độ giảm là bao nhiêu? Khi ta đi xuống một mức thì sẽ phải giải số bài toán con gấp ba lần số bài toán ở mức hiện tại. Tuy nhiên, vì mỗi bài toán con chỉ phải giải có kích cỡ giảm một nửa, nên thời gian cần để giải bài toán con giảm còn bằng $1 over 8$ bài toán cha. Như vậy tổng độ phức tạp giảm theo hệ số $3 over 8$.
Điều này có nghĩa là toàn bộ bảng số ở trên sẽ hình thành một dãy cấp số nhân. Giả sử rằng dãy cấp số nhân đó tăng tới vô cùng. Tổng của dãy sẽ là:
$$ S = frac{cN^3}{1 – frac{3}{8}} = frac{8}{5}cN^3 = Theta(N^3) $$
Như vậy tổng độ phức tạp trên cây đệ quy là $O(N^3)$ (tổng tới vô cùng cho ta cận trên). Ta cũng thấy là ngay phần từ đầu tiên của dãy cấp số nhân đã là $ Theta(N^3)$. Vậy ta kết luận tổng độ phức tạp của cây đệ quy trên là $ Theta(N^3)$.
Một nguyên lý tổng quát quan trọng ta có thể rút ra từ ví dụ này là: nếu tổng độ phức tạp của các mức của cây tạo nên một dãy cấp số nhân giảm, thì tổng độ phức tạp trên cả cây sẽ tiệm cận bằng với độ phức tạp ở gốc của cây.
Từ kết quả trên ta có một nhận xét quan trọng về thuật toán đệ quy biểu diễn bằng công thức truy hồi có tính chất trên: lệnh gọi đệ quy giải bài toán con không tốn thời gian thực thi bằng việc chuẩn bị lời gọi và xử lý sau lời gọi đệ quy. (Nói cách khác, nếu ta cần cải tiến thuật toán thì phải tập trung tối hưu hóa hai việc đó).
Ví dụ 7
Giờ chúng ta cùng thử áp dụng phương pháp Cây Đệ Quy để giải phương trình sau: $f(N) = 5f(N/3) + Theta(N)$ Cây đệ quy sẽ có dạng sau
Như trên, thử tính số lệnh cần thực thi ở vài mức đầu tiên. Ta có:
level 1 2 3 …
work $cN$ ${5over 3}cN$ ${5^2 over 3^2}cN$ …
Ta có kết quả ngược với ví dụ 6: khi ta càng đi sâu xuống dưới thì tổng độ phức tạp lại càng tăng lên. Khi ta đi xuống một mức, sẽ có gấp $5$ lần số bài toán con, mỗi bài toán con sẽ có kích cỡ bằng $1 over 3$ bài toán cha. Vì thời gian xử lý là tuyến tính với kích cỡ bài toán nên ta có tổng độ phức tạp ở mức sau tăng gấp $5 over 3 $ mức trước.
Vẫn như trên ta hướng tới việc tính tổng độ phức tạp trên cả cây. Lần này việc tính toán sẽ khó hơn vì lượng công việc phải tính nằm ở mức sâu nhất. Ta cần biết độ sâu của cây.
Mức thấp nhất tương ứng bài toán kích cỡ bằng $1$. Tổng quát, kích cỡ bài toán con ở mức $k$ là $N over 3^k$. Giải phương trình $1 = N over 3^k$ ta được $k = log_3N$. Lưu ý là ở đây ta viết rõ chỉ cơ số của hàm logarit vì cơ số này quan trọng trong việc phản ánh cấu trúc cây.
Như vậy cây đệ quy có $log_3N$ mức. Mỗi mức có $5$ lần số đỉnh so với mức trên nó, nên mức cuối cùng có $5^{log_3N}$ đỉnh. Tổng độ phức tạp ở mức cuối tương ứng là $c5^{log_3N}$.
Sử dụng phương trình (3) ta viết lại giá trị này là $cN^{log_35}$.
Để tính tổng độ phức tạp trên toàn cây ta đảo ngược cây, tạo thành một dãy cấp số nhân giảm và như vậy ta có thể áp dụng cách tính ở trên. Xử lý tương tự ví dụ trước đó ta thu được tổng độ phức tạp là một giá trị tiệm cận bằng với phần tử lớn nhất trong dãy cấp số nhân.
Ta kết luận rằng tổng độ phức tạp của thuật toán biểu diễn bởi phương trình trên là xấp xỉ $Theta(N^{log_35}) approx Theta(N^{1.465}) $.
Lưu ý là cơ số 3 trong hàm logarit cho ta kết quả mũ chính xác, vì vậy cơ số này rất quan trọng. Nếu là cơ số khác thì giá trị tiệm cận cũng sẽ thay đổi.
Định lý Tổng Quát
Từ các ví dụ trên chúng ta đã thấy một quy luật giải các công thức truy hồi. Cho một công thức truy hồi, lập cây đệ quy tương ứng và tính tổng độ phức tạp trên mỗi mức. Kết quả thu được sẽ là một dãy cấp số nhân. Nếu đó là dãy giảm, tổng độ phức tạp trên toàn cây sẽ tỷ lệ với độ phức tạp của đỉnh gốc. Nếu là dãy tăng, tổng độ phức tạp sẽ tỷ lệ với tổng độ phức tạp ở các lá. Nếu là dãy không đổi thì tổng độ phức tạp sẽ là (độ phức tạp trên một mức) nhân với (chiều cao cây).
Trong thực tế sẽ có một vài trường hợp mà quy luật trên gặp khó khăn, tuy nhiên hầu hết sẽ chỉ có một trong ba trường hợp trên xảy ra. Thêm vào đó, ta có cơ sở để chứng minh quy luật trên một cách chặt chẽ. Cơ sở chính thống của quy luật trên được biết đến với cái tên Định lý Tổng Quát.
Để thuận tiện bài viết này sẽ trình bày đầy đủ về định lý này. (Lưu ý là ta không cần biết chứng minh của nó để có thể áp dụng vào giải công thức truy hồi).
$f(N) = af(N/b) + p(N)$ Ta có kết quả sau:
Nếu $p(N) = O(N^{(log_ba) – varepsilon})$ thì $f (N) = Theta(p(N)log N)$.
Trường hợp $1$ tương với Ví dụ 7. Hầu hết thời gian thực thi được dành cho việc gọi lệnh đệ quy và số lần gọi đệ quy là đáng kể.
Trường hợp $2$ tương ứng với Ví dụ 5. Thời gian dành cho việc gọi đệ quy xấp xỉ bằng thời gian để chuẩn bị cho lệnh gọi đệ quy và xử lý sau đó. Trên tất cả các mức của cây ta có độ phức tạp xấp xỉ bằng nhau, chiều cao cây luôn là một hàm logarit của kích cỡ tập đầu vào.
Trường hợp $3$ tương ứng với Ví dụ 6. Hầu hết thời gian thực thi được dành cho việc chuẩn bị để gọi lệnh đệ quy và xử lý kết quả sau đó. Thông thường thì tổng độ phức tạp sẽ tiệm cận bằng với thời gian thực thi ở đỉnh gốc của cây.
Lưu ý điều kiện thêm vào ở trường hợp $3$. Để trường hợp $3$ đúng ta cần có điều kiện của hàm $p$ phải thỏa mãn thời gian thực thi hàm $p$ lớn hơn tổng thời gian thực thi ở các đỉnh con cháu. Thật ra đây không phải là một vấn đề cần phải chú tâm quá nhiều bởi trong các kỳ thi các hàm $p$ mà bạn có thể gặp hầu như sẽ thỏa mãn điều kiện trên (nếu rơi vào trườn hợp $3$).
Ví dụ 8
Gọi $f(N)$ là thời gian mà thuật toán nhân ma trận Strassen cần để nhân hai ma trận vuông kích cỡ $N$ x $N$. Đây là một thuật toán đệ quy, thực hiện $7$ lời gọi hàm đệ quy, mỗi hàm nhân hai ma trận có kích cỡ $N/2$ x $N/2$ và sau đó tổng hợp kết quả trong $Theta(N^2)$.
Ta có công thức truy hồi sau:
$$ f(N) = 7f(N/2) + Theta(N^2) $$
Sử dụng định lý Tổng Quát, ta thấy Trường hợp $1$ có thể áp dụng được. Vì vậy độ phức tạp của thuật toán Strassen là $Theta(N^{log_27}) approx Theta({N^{2.807}})$. Lưu ý là thuật toán cổ điển nhân ma trận theo định nghĩa có độ phức tạp $ Theta(N^3)$.
Ví dụ 9
Thỉnh thoảng ta có thể gặp trường hợp mà kích cỡ các bài toán con không bằng nhau. Một ví dụ là thuật toán Trung vị của 5 để tìm phần tử lớn thứ k của một mảng số. Thuật toán trên được chứng minh là có độ phức tạp thỏa mãn công thức
$$ f(N) = f(N/5) + f(7N/10 + 6) + Theta(N) $$
Công thức trên giải như thế nào? Phương pháp cây Đệ Quy có thể được áp dụng trong trường hợp bất đối xứng như vậy không? Có một phiên bản tổng quát hơn của Định lý Tổng Quát áp dụng cho trường hợp như vậy hay không? Và trong các trường hợp mà định lý Tổng Quát không áp dụng được, điển hình là với công thức $f (N) = 4f (N/4) + Theta(N log N)$, ta cần xử lý thế nào?
Lời người dịch
Bạn đang xem bài viết Hình Học Của Số Phức trên website Sansangdethanhcong.com. Hy vọng những thông tin mà chúng tôi đã chia sẻ là hữu ích với bạn. Nếu nội dung hay, ý nghĩa bạn hãy chia sẻ với bạn bè của mình và luôn theo dõi, ủng hộ chúng tôi để cập nhật những thông tin mới nhất. Chúc bạn một ngày tốt lành!