CÂU HỎI MÔN PHÂN TÍCH THIẾT KẾ THUẬT TOÁN - Page 2


Diễn đàn chia sẻ kiến thức, kinh nghiệm về IT và cuộc sống!
 
Trang ChínhGalleryTrợ giúpTìm kiếmThành viênNhómĐăng kýĐăng Nhập
Top posters
Sakura (1124)
 
hotboy (705)
 
Già Làng (373)
 
con_ca_nho90 (289)
 
that_true (154)
 
theanhkkt (143)
 
phamay (137)
 
lovelonelyman (134)
 
o0ovioletstaro0o (128)
 
stevenhung (122)
 
Âm - Dương lịch
Clock
Logo
11TH02 Pro!
Liên kết
Tin tức 60s
Tin công nghệ
Thời sự 24h
Game Moblie

Share | 
 

 CÂU HỎI MÔN PHÂN TÍCH THIẾT KẾ THUẬT TOÁN

Xem chủ đề cũ hơn Xem chủ đề mới hơn Go down 
Chuyển đến trang : Previous  1, 2, 3  Next
Tác giảThông điệp
Già Làng


avatar

Thú CƯng :
Nam Libra

Số bài viết : 373
Điểm : 2200708
Được cảm ơn : 53
Ngày sinh : 20/10/1987
Tham gia ngày : 16/03/2010
Tuổi : 31
Đến từ : Bình Dương
Ngề nghiệp : Sinh Viên
Chăm ngôn : Cơm Cha - Áo Mẹ!

Bài gửiTiêu đề: CÂU HỎI MÔN PHÂN TÍCH THIẾT KẾ THUẬT TOÁN   22/6/2010, 22:30

First topic message reminder :

Tổng hợp tất cả câu hỏi trên lớp của Thầy Lân về môn PTTKTT đây:

1. Hệ thức truy hồi là gì? Cách giải htth
2. Phương pháp brainstorming
3. Giải thích từ prolem
4. Hệ thức truy hồi tuyến tính thuần nhất bậc một với hệ số hằng. cho vd
5. Hệ thức truy hồi tuyến tính không thuần nhất bậc k. cho vd
6. Vẽ máy tính turing chạy đồng hồ cơ
7. Tiên đề là gì? Luận đề là gì? Cho vd
8. Cho 3 vd trong trường hợp các phần tử mảng có sự trùng lặp(cách tiếp cận big o)
9. Cơ chế gọi hàm trong máy tính
10. Vì sao Pascal bỏ dòng lệnh tăng i lên

11. CM : n<2n
12. Cho 3 vd ngôn ngữ lập trình C thuật toán không vi phạm 5 tiêu chuẩn và 3 vd vi phạm 5 tiêu chuẩn (thuật giải)
13. Phân tích độ phức tạp thuật toán BFS và DFS

_________________________________________________
Khách viếng thăm đọc rồi thì thanks đi chứ!!
Về Đầu Trang Go down
Xem lý lịch thành viên http://itworld.4rumer.com

Tác giảThông điệp
tkhking

Member Năng Động


Member Năng Động
avatar

Thú CƯng :
Nam Pisces

Số bài viết : 114
Điểm : 135
Được cảm ơn : 1
Ngày sinh : 18/03/1990
Tham gia ngày : 01/07/2010
Tuổi : 28
Đến từ : Óc Trâu Lấy Ra
Ngề nghiệp : Student
Chăm ngôn : King

Bài gửiTiêu đề: Re: CÂU HỎI MÔN PHÂN TÍCH THIẾT KẾ THUẬT TOÁN   15/7/2010, 02:13

10. Vì sao Pascal bỏ dòng lệnh tăng i lên
Vì vòng lập For trong Pascal thì nó truy cập dựa trên cơ sở đúng trong đó có thể tăng hoặc giảm mổi lần 1 đơn vị khi vòng lập được thực thi. Vì thế nó ít linh hoạt hơn so với các ngôn ngữ khác( vì không thể xác định được số lần tăng hoặc giảm khác 1)
Về Đầu Trang Go down
Xem lý lịch thành viên trungkienho90@yahoo.com
p0p0.vL




Nam Cancer

Số bài viết : 4
Điểm : 4
Được cảm ơn : 0
Ngày sinh : 27/06/1990
Tham gia ngày : 14/07/2010
Tuổi : 28
Đến từ : 11TH02

Bài gửiTiêu đề: Re: CÂU HỎI MÔN PHÂN TÍCH THIẾT KẾ THUẬT TOÁN   15/7/2010, 04:37

thì tui nói !!! đọc tham khảo chứ nói mấy người copy hết vô đâu
chán chít mẹ.........!!!!!!!!! không đọc rõ cứ ghi lun tung.........
Về Đầu Trang Go down
Xem lý lịch thành viên
binhduong




Nam Pisces

Số bài viết : 5
Điểm : 6
Được cảm ơn : 0
Ngày sinh : 26/02/1990
Tham gia ngày : 08/07/2010
Tuổi : 28
Đến từ : binh duong

Bài gửiTiêu đề: Re: CÂU HỎI MÔN PHÂN TÍCH THIẾT KẾ THUẬT TOÁN   15/7/2010, 08:48

Phân tích thiết kế và đánh giá thut toán

[You must be registered and logged in to see this link.] Đ bài
Câu 1.
a) Th
ế nào là bài toán tìm kiếm. Trình bày các bước, đánh giá đ phc tp và viết sơ đ thut toán tìm kiếm tuyến tính.
b) Cài đt thut toán sp xếp ni bt tăng dn trên mng cu trúc công nhân.
Câu 2.
a) Thu
t toán sinh xâu s t các s 1,2,3 vi đ dài n nhp t bàn phím.
b) S
p xếp trn áp dng trên mng s nguyên: 3 8 10 9 82 4 78 28 9 10 13 11.
Câu 3.
a) Bài toán nhân dãy các ma tr
n áp dng vi dãy các ma trn: 5x50; 50x10; 10x20; 20x15.
b) Bài toán tìm dãy con g
m các phn t liên tiếp có tng ln nht áp dng vi dãy s nguyên:
-9 8 -3 18 4 -2 8 -13 20 -4 8 9 3

Về Đầu Trang Go down
Xem lý lịch thành viên
binhduong




Nam Pisces

Số bài viết : 5
Điểm : 6
Được cảm ơn : 0
Ngày sinh : 26/02/1990
Tham gia ngày : 08/07/2010
Tuổi : 28
Đến từ : binh duong

Bài gửiTiêu đề: Re: CÂU HỎI MÔN PHÂN TÍCH THIẾT KẾ THUẬT TOÁN   15/7/2010, 08:54

Trẻ sơ sinh là sau?
chung ta là sinh viên.
vậy =>> diễn đàn có tôn trọng thàh viên không.
nếu muốn đánh giá thành viên dùng thang điểm hay j đó.
Về Đầu Trang Go down
Xem lý lịch thành viên
lovelonelyman

Member Năng Động


Member Năng Động
avatar

Nam Cancer

Số bài viết : 134
Điểm : 180
Được cảm ơn : 9
Ngày sinh : 15/07/1990
Tham gia ngày : 30/04/2010
Tuổi : 28
Đến từ : Thai Binh

Bài gửiTiêu đề: Re: CÂU HỎI MÔN PHÂN TÍCH THIẾT KẾ THUẬT TOÁN   15/7/2010, 10:52

Anh em quên đề thi này của thầy cho hôm học môn LTDT thầy cho à.
Tính độ phưc tạp của thuật toán Dịkstra?
Tính độ phưc tạp của thuật toán Ford_bellman?
Cho bết sự khác biệt về độ phức tạp của 2 thuật toán đó?
(viết trên 1 trang giấy)
Về Đầu Trang Go down
Xem lý lịch thành viên
hotboy


avatar

Thú CƯng :
Nam Aries

Số bài viết : 705
Điểm : 1043
Được cảm ơn : 9
Ngày sinh : 21/03/1990
Tham gia ngày : 13/05/2010
Tuổi : 28
Đến từ : BDU

Bài gửiTiêu đề: Re: CÂU HỎI MÔN PHÂN TÍCH THIẾT KẾ THUẬT TOÁN   15/7/2010, 11:31

tkhking đã viết:
10. Vì sao Pascal bỏ dòng lệnh tăng i lên
Vì vòng lập For trong Pascal thì nó truy cập dựa trên cơ sở đúng trong đó có thể tăng hoặc giảm mổi lần 1 đơn vị khi vòng lập được thực thi. Vì thế nó ít linh hoạt hơn so với các ngôn ngữ khác( vì không thể xác định được số lần tăng hoặc giảm khác 1)

nói rõ hơn ý này nha:

là do vòng lặp for của pascal ý nghĩa rất rõ ràng : cho i chạy từ 1 đến n;

còn for của C gồm 3 biểu thức : for ( bt1; bt2 ; bt3) { khối lệnh }
1 trong 3 biểu thưc này có thể khuyết ;

ở dạng đầy đủ, bt1 là biểu thức khởi gán của for ; vd : i =1 tưc là gán
gia trị i = 1 ; là giá trị đầu tiên của vòng lặp để vòng lặp thực hiện.

bt2 là biểu thức quan trọng nhất, là biểu thưc điều kiện tiwwps tục lặp,
VD i<n ;bt này trả về trị hoặc true hoặc false; nếu true thì tiếp
tục thực hiện khối lệnh, và sau khi thực hiện khối lệnh rồi; phải tăng i lên để lặp, do đó mới có câu lệnh i++ ; i++ mang ý nghĩa là cập nhật lại i để lặp tiếp; còn nếu bt2 nhận giá trị false thì sẽ dừng vòng lặp.

Nếu xet về mặt ý nghĩa, vòng for của pascal tường minh hơn ; có nghĩa
nếu bạn viết for i := 1 to n do .... thì bạn sẽ biết chắc đc nó sẽ lặp n
lần;

còn trong vòng lặp for của C nếu bạn viết for ( i=0 ; i<n; bt3 )
thì bạn chưa biết chắc nó sẽ lặp bao nhiêu lần ; vì số lần lặp này còn
phụ thuộc vào biểu thức thứ 3 : VD nếu là i ++ thì sau 1 vòng lặp, giá
trị của i tăng 1; vì vậy sẽ lặp n lần; nhưng nếu i = i+2 thì mọi chuyện
sẽ khác.

nói vậy có nghĩa : pascal là bạn lặp từ 1 đến n, còn C là : đầu tiên bạn
cho i là gia trị nào đó, kiểm tra xem i có thỏa mãn đk hay ko ( i<n )
; nếu đúng thì thực hiện khối lệnh rồi tăng i lên 1 đơn vị, rồi lại
kiểm tra xem i có thỏa mãn đk hay ko, rồi tiếp tục công việc như trên .


cái này tui tham khảo ý kiến của mấy pro bên congdongCviet nên tui nghĩ chắc là không sai đâu [You must be registered and logged in to see this image.]
Về Đầu Trang Go down
Xem lý lịch thành viên
hotboy


avatar

Thú CƯng :
Nam Aries

Số bài viết : 705
Điểm : 1043
Được cảm ơn : 9
Ngày sinh : 21/03/1990
Tham gia ngày : 13/05/2010
Tuổi : 28
Đến từ : BDU

Bài gửiTiêu đề: Re: CÂU HỎI MÔN PHÂN TÍCH THIẾT KẾ THUẬT TOÁN   15/7/2010, 11:34

không có EDIT được nên tui post bổ sung thêm ý này

Trong Pascal nếu muốn có bước nhảy chỉ có cách dùng While..Do hoặc Repeat..Until
Vì Pascal có cấu trúc mạnh, chặt chẽ, ko tự do như 1 số ngôn ngữ khác (C/C++, VB...)
Trong Pascal vòng biến điều khiển vòng for tăng lần lượt từ chỉ số đầu
đến chỉ sô cuối, bước nhảy là 1 đơn vị. Nếu trong vòng for có lệnh làm
thay đổi giá trị biến điều kiển thì sẽ phá vỡ tính cấu trúc,đặc biệt lưu
ý không được thay đổi giá trị của biến điều khiển vòng for.
Về Đầu Trang Go down
Xem lý lịch thành viên
con_ca_nho90

Member Nhiệt Tình


Member Nhiệt Tình
avatar

Thú CƯng :
Nam Aquarius

Số bài viết : 289
Điểm : 329
Được cảm ơn : 4
Ngày sinh : 17/02/1990
Tham gia ngày : 05/05/2010
Tuổi : 28
Đến từ : Nhà hàng xóm
Ngề nghiệp : click chuột định giang sơn :D
Chăm ngôn : Giang hồ hiểm ác không bằng mạng lag thất thường

Bài gửiTiêu đề: Re: CÂU HỎI MÔN PHÂN TÍCH THIẾT KẾ THUẬT TOÁN   15/7/2010, 17:30

mình thấy mấy pạn giải mấy câu đó vậy là ổn rồi có ai giải được câu 13 ko? cho mình hỏi cái lệnh gọi đệ qui trong hàm đó vậy tính big O sao?
Về Đầu Trang Go down
Xem lý lịch thành viên https://plus.google.com/u/0/?hl=vi jeennguyen@ymail.com
hotboy


avatar

Thú CƯng :
Nam Aries

Số bài viết : 705
Điểm : 1043
Được cảm ơn : 9
Ngày sinh : 21/03/1990
Tham gia ngày : 13/05/2010
Tuổi : 28
Đến từ : BDU

Bài gửiTiêu đề: Re: CÂU HỎI MÔN PHÂN TÍCH THIẾT KẾ THUẬT TOÁN   15/7/2010, 18:41

Code:

Void DFS(int
s)  [b][/b]


{


                [b][color=red]1[/color][/b] Int u;                                                                                                 


                [b][color=red]2[/color][/b] daxet[s]=1;


                [b][color=red]3[/color][/b] for(u=1;u<=n;u++)


                {


                                [b][color=red]4[/color][/b] If(a[s][u]
&&!daxet[u])


                                {


                                                [b][color=red]5[/color][/b] Truoc[u]=s;


                                                [b][color=red]6[/color][/b] If(u==t) // khi đã đến được đỉnh T



                                                                [b][color=red]7[/color][/b] Xuat();//hàm
xuất đường đi 


                                                [b][color=red]8 [/color][/b]Else


                                                                [b][color=red]9[/color][/b] DFS(u);


}


}


}



Các lệnh 1,2,7
có độ phúc tạp là O(1)


Vòng for ở
hàng 3 có độ phức tạp là O(n+1)


Hàng 4 có độ phức tạp là O(n)


Hàng 5,6,8,9 có độ phức tạp là O(m) do không xác định
được sẽ có bao nhiêu đỉnh thỏa điều kiện ở hàng 4


èT(n)=3x1+n+1+n+4xm=4+2n+4m,
áp dụng luật tổng ta suy ra độ phức tạp của DFS là O(n+m)
Về Đầu Trang Go down
Xem lý lịch thành viên
hotboy


avatar

Thú CƯng :
Nam Aries

Số bài viết : 705
Điểm : 1043
Được cảm ơn : 9
Ngày sinh : 21/03/1990
Tham gia ngày : 13/05/2010
Tuổi : 28
Đến từ : BDU

Bài gửiTiêu đề: Re: CÂU HỎI MÔN PHÂN TÍCH THIẾT KẾ THUẬT TOÁN   15/7/2010, 18:42

Void DFS(int
s)


{


1 Int u;


2 daxet[s]=1;


3 for(u=1;u<=n;u++)


{


4 If(a[s][u]
&&!daxet[u])


{


5 Truoc[u]=s;


6 If(u==t) // khi đã đến được đỉnh T



7 Xuat();//hàm
xuất đường đi


8 Else


9 DFS(u);


}


}


}





Các lệnh 1,2,7
có độ phúc tạp là O(1)


Vòng for ở
hàng 3 có độ phức tạp là O(n+1)


Hàng 4 có độ phức tạp là O(n)


Hàng 5,6,8,9 có độ phức tạp là O(m) do không xác định
được sẽ có bao nhiêu đỉnh thỏa điều kiện ở hàng 4


èT(n)=3x1+n+1+n+4xm=4+2n+4m,
áp dụng luật tổng ta suy ra độ phức tạp của DFS là O(n+m)
Về Đầu Trang Go down
Xem lý lịch thành viên
tkhking

Member Năng Động


Member Năng Động
avatar

Thú CƯng :
Nam Pisces

Số bài viết : 114
Điểm : 135
Được cảm ơn : 1
Ngày sinh : 18/03/1990
Tham gia ngày : 01/07/2010
Tuổi : 28
Đến từ : Óc Trâu Lấy Ra
Ngề nghiệp : Student
Chăm ngôn : King

Bài gửiTiêu đề: Re: CÂU HỎI MÔN PHÂN TÍCH THIẾT KẾ THUẬT TOÁN   15/7/2010, 22:08

hotboy đã viết:
Void DFS(int
s)


{


1 Int u;


2 daxet[s]=1;


3 for(u=1;u<=n;u++)


{


4 If(a[s][u]
&&!daxet[u])


{


5 Truoc[u]=s;


6 If(u==t) // khi đã đến được đỉnh T



7 Xuat();//hàm
xuất đường đi


8 Else


9 DFS(u);


}


}


}





Các lệnh 1,2,7
có độ phúc tạp là O(1)


Vòng for ở
hàng 3 có độ phức tạp là O(n+1)


Hàng 4 có độ phức tạp là O(n)


Hàng 5,6,8,9 có độ phức tạp là O(m) do không xác định
được sẽ có bao nhiêu đỉnh thỏa điều kiện ở hàng 4


èT(n)=3x1+n+1+n+4xm=4+2n+4m,
áp dụng luật tổng ta suy ra độ phức tạp của DFS là O(n+m)
theo tui nghĩ thì kết quả là đúng nhưng mà cách làm thì sai đó để tui nghiên cứu tí nếu được thì post lên anh em tham khảo nha..ai tìm được thì post lên cho anh em luôn nha
Về Đầu Trang Go down
Xem lý lịch thành viên trungkienho90@yahoo.com
binhduong




Nam Pisces

Số bài viết : 5
Điểm : 6
Được cảm ơn : 0
Ngày sinh : 26/02/1990
Tham gia ngày : 08/07/2010
Tuổi : 28
Đến từ : binh duong

Bài gửiTiêu đề: Re: CÂU HỎI MÔN PHÂN TÍCH THIẾT KẾ THUẬT TOÁN   15/7/2010, 22:13

DFS
Để đánh giá độ phức tạp tính toán của thủ tục, trước hết nhận thấy rằng số phép toán cần thực hiện trong hai chu trình của thuật toán (hai vòng for ở chương trình chính) là cỡ n. Thủ tục DFS phải thực hiện không quá n lần. Tổng số phép toán cần phaỉ thực hiện trong các thủ tục này là O(n+m), do trong các thủ tục này ta phải xét qua tất cả các cạnh và các đỉnh của đồ thị. Vậy độ phức tạp tính toán của thuật toán là O(n+m).
Về Đầu Trang Go down
Xem lý lịch thành viên
con_ca_nho90

Member Nhiệt Tình


Member Nhiệt Tình
avatar

Thú CƯng :
Nam Aquarius

Số bài viết : 289
Điểm : 329
Được cảm ơn : 4
Ngày sinh : 17/02/1990
Tham gia ngày : 05/05/2010
Tuổi : 28
Đến từ : Nhà hàng xóm
Ngề nghiệp : click chuột định giang sơn :D
Chăm ngôn : Giang hồ hiểm ác không bằng mạng lag thất thường

Bài gửiTiêu đề: ý nhầm pạn ơi   15/7/2010, 22:21

binhduong đã viết:
DFS
Để đánh giá độ phức tạp tính toán của thủ tục, trước hết nhận thấy rằng số phép toán cần thực hiện trong hai chu trình của thuật toán (hai vòng for ở chương trình chính) là cỡ n. Thủ tục DFS phải thực hiện không quá n lần. Tổng số phép toán cần phaỉ thực hiện trong các thủ tục này là O(n+m), do trong các thủ tục này ta phải xét qua tất cả các cạnh và các đỉnh của đồ thị. Vậy độ phức tạp tính toán của thuật toán là O(n+m).

pài ở trên mình thấy như vậy là tạm ổn rồi=> vì đề thầy kêu là phân tích độ phức tạp(tức ta phải mổ xẽ vấn đề ra ->đi đến kết luận 1 cách cụ thể) chứ ko phải là đánh giá như pạn làm.ai có cách làm hay hơn xin post cho anh em nhe.
Về Đầu Trang Go down
Xem lý lịch thành viên https://plus.google.com/u/0/?hl=vi jeennguyen@ymail.com
tkhking

Member Năng Động


Member Năng Động
avatar

Thú CƯng :
Nam Pisces

Số bài viết : 114
Điểm : 135
Được cảm ơn : 1
Ngày sinh : 18/03/1990
Tham gia ngày : 01/07/2010
Tuổi : 28
Đến từ : Óc Trâu Lấy Ra
Ngề nghiệp : Student
Chăm ngôn : King

Bài gửiTiêu đề: Re: CÂU HỎI MÔN PHÂN TÍCH THIẾT KẾ THUẬT TOÁN   15/7/2010, 23:15

4. Hệ thức truy hồi tuyến tính thuần nhất bậc một với hệ số hằng. cho vd
Hệ thức truy hồi tuyến tính bậc 1 có dạng: an=c.an-1 với c#0
Ví dụ: Đếm số lần chuyển đĩa của bài toán tháp Hanoi.
Về Đầu Trang Go down
Xem lý lịch thành viên trungkienho90@yahoo.com
tkhking

Member Năng Động


Member Năng Động
avatar

Thú CƯng :
Nam Pisces

Số bài viết : 114
Điểm : 135
Được cảm ơn : 1
Ngày sinh : 18/03/1990
Tham gia ngày : 01/07/2010
Tuổi : 28
Đến từ : Óc Trâu Lấy Ra
Ngề nghiệp : Student
Chăm ngôn : King

Bài gửiTiêu đề: Re: CÂU HỎI MÔN PHÂN TÍCH THIẾT KẾ THUẬT TOÁN   15/7/2010, 23:16

5. Hệ thức truy hồi tuyến tính không thuần nhất bậc k. cho vd
Trích dẫn :
Hệ thức truy hồi tuyến tính không thuần nhất bậc k là hệ thức truy hồi có dạng :
an = c1an-1 +… + ckan-k + fn
Trong đó c1, c2, …,ck là những số thực và c*k ≠ 0
Ví dụ Hệ thức truy hồi an= 2an-2 + 2n là hệt thức truy hồi tuyến tính không thuần nhất bậc 2 với hệ số hằng

Về Đầu Trang Go down
Xem lý lịch thành viên trungkienho90@yahoo.com
tkhking

Member Năng Động


Member Năng Động
avatar

Thú CƯng :
Nam Pisces

Số bài viết : 114
Điểm : 135
Được cảm ơn : 1
Ngày sinh : 18/03/1990
Tham gia ngày : 01/07/2010
Tuổi : 28
Đến từ : Óc Trâu Lấy Ra
Ngề nghiệp : Student
Chăm ngôn : King

Bài gửiTiêu đề: Re: CÂU HỎI MÔN PHÂN TÍCH THIẾT KẾ THUẬT TOÁN   15/7/2010, 23:19

Câu 6 thì tôi po hand rồi có anh em nào biết không sposst lên nha
Về Đầu Trang Go down
Xem lý lịch thành viên trungkienho90@yahoo.com
tkhking

Member Năng Động


Member Năng Động
avatar

Thú CƯng :
Nam Pisces

Số bài viết : 114
Điểm : 135
Được cảm ơn : 1
Ngày sinh : 18/03/1990
Tham gia ngày : 01/07/2010
Tuổi : 28
Đến từ : Óc Trâu Lấy Ra
Ngề nghiệp : Student
Chăm ngôn : King

Bài gửiTiêu đề: Re: CÂU HỎI MÔN PHÂN TÍCH THIẾT KẾ THUẬT TOÁN   15/7/2010, 23:23

Chứng minh bằng phương pháp quy nạp
Bước cơ sở: 1  21 (hiển nhiên đúng)

n  2n
2n  2n .2
n+1  2n  2n+1
n+1  2n+1
Về Đầu Trang Go down
Xem lý lịch thành viên trungkienho90@yahoo.com
tkhking

Member Năng Động


Member Năng Động
avatar

Thú CƯng :
Nam Pisces

Số bài viết : 114
Điểm : 135
Được cảm ơn : 1
Ngày sinh : 18/03/1990
Tham gia ngày : 01/07/2010
Tuổi : 28
Đến từ : Óc Trâu Lấy Ra
Ngề nghiệp : Student
Chăm ngôn : King

Bài gửiTiêu đề: Re: CÂU HỎI MÔN PHÂN TÍCH THIẾT KẾ THUẬT TOÁN   15/7/2010, 23:25

tkhking đã viết:
Chứng minh bằng phương pháp quy nạp
Bước cơ sở: 1  21 (hiển nhiên đúng)

n  2n
2n  2n .2
n+1  2n  2n+1
n+1  2n+1
sao cái bài này post lên bị lỗi thế này diển đàn bị sao zậy mong admin sửa dùm nha... afro affraid pale
Về Đầu Trang Go down
Xem lý lịch thành viên trungkienho90@yahoo.com
tkhking

Member Năng Động


Member Năng Động
avatar

Thú CƯng :
Nam Pisces

Số bài viết : 114
Điểm : 135
Được cảm ơn : 1
Ngày sinh : 18/03/1990
Tham gia ngày : 01/07/2010
Tuổi : 28
Đến từ : Óc Trâu Lấy Ra
Ngề nghiệp : Student
Chăm ngôn : King

Bài gửiTiêu đề: Re: CÂU HỎI MÔN PHÂN TÍCH THIẾT KẾ THUẬT TOÁN   15/7/2010, 23:26

Mấy câu kia thì pó tay rồi sao không có ai thức hổ trợ hết vậy trời...Sad(
mai không biết mình sẽ ra sao nữa
Về Đầu Trang Go down
Xem lý lịch thành viên trungkienho90@yahoo.com
nonamebdu




Thú CƯng : Khung Long
Nam Leo

Số bài viết : 4
Điểm : 4
Được cảm ơn : 0
Ngày sinh : 28/07/1990
Tham gia ngày : 02/07/2010
Tuổi : 28
Đến từ : ả rập cê út
Ngề nghiệp : thiepngat
Chăm ngôn : knmom

Bài gửiTiêu đề: Re: CÂU HỎI MÔN PHÂN TÍCH THIẾT KẾ THUẬT TOÁN   15/7/2010, 23:33

ĐỀ 1:
Câu 1:
Đánh giá và chứng minh độ phức tạp của thuật toán sắp xếp Insert Sort(chèn).
{1}for i:=2 to n do
Begin
{2}x:=a[i];

{3}j:=i-1;
{4}While xbegin
{5}a[j+1]:=a[j];
{6}dec(j);
end;

{7}a[j+1]:=x;
end;
Ta có lệnh {2},{3},{5},{6},{7} có độ
phức O(1)

Dòng {1} có độ phức tạp O(n-1)
Dòng {4} có độ phức tạp O(n)
Vậy thuật toán có độ phức tạp O(n2) theo nguyên tắc cộng và nhân
Câu 2:
Anh/chị cho một ví dụ (chương trình).Để tính toán độ phức tạp của chương trình
vừa cho có sử dụng định lý tổng của các hàm tính độ phức tạp.
** Qui tắc cộng:
Nếu T1(n) và T2(n) là thời gian thực hiện của hai đoạn chương trình P1 và P2;
và T1(n)=O(f(n)), T2(n)=O(g(n) thì thời gian thực hiện của đoạn hai chương
trình đó nối tiếp nhau là T(n)=O(max(f(n),g(n)))

Ví dụ 1-6: Lệnh gán x:=15 tốn một hằng thời gian hay O(1)

Lệnh đọc dữ liệu READ(x) tốn một hằng thời gian hay O(1)

Vậy thời gian thực hiện cả hai lệnh trên nối tiếp nhau là O(max(1,1))=O(1)
Câu 3:
Cho biết độ phức tạp của chương trình sau, Tổng 2 số tự nhiên a và b
m:=a;
n:=b;
While m>0 do begin m:=m-1;
n:=n+1;
return(n);
Giải :
{1}m:=a;
{2}n:=b;
{3}While m>0 do
begin
{4}m:=m-1;
{5}n:=n+b;
end;
return(n);
Dòng 1 2 4 5 có độ phức tạp là O(1)
vậy trong While có độ phức tạp là O(1)
Ta thấy while chạy theo m giảm dần khi m còn >0
Cũng khi đó độ phức tạp thuật toán là O(m)

Đề 2: MÔN PHÂN TÍCH THIẾT KẾ THUẬT TOÁN
Câu 1:
Đánh giá và chứng minh độ phức tạp của thuật toán sắp xếp Buble Sort(nổi bọt)
procedure Swap (var x, y: integer);
var temp: integer;
begin
temp := x;
x := y;
y := temp;
end;

procedure Bubble (var a: array[1..n] of integer);
var i,j :integer;
begin
{1} for i:=1 to n-1 do
{2} for j:=n downto i+1 do
{3} if a[j-1]>a[j] then Swap(a[j-1], a[j]);
end;

Trong cách viết trên, chương trình Bubble gọi chương trình con Swap, do đó để
tính thời gian thực hiện của Bubble, trước hết ta cần tính thời gian thực hiện
của Swap. Dễ thấy thời gian thực hiện của Swap là O(1) vì nó chỉ bao gồm 3 lệnh
gán.
Câu 2:
Anh/chị cho một ví dụ (chương trình).Để tính toán độ phức tạp của chương trình
vừa cho có sử dụng định lý tích của các hàm tính độ phức tạp.
** Qui tắc nhân:
Nếu T1(n) và T2(n) là thời gian thực hiện của hai đoạn chương trình P1và P2 và
T1(n) = O(f(n)), T2(n) = O(g(n) thì thời gian thực hiện của đoạn hai đoạn
chương trình đó lồng nhau là T(n) = O(f(n).g(n))
for (int i=0;iFor(int j=0;jSum++;
Lệnh Sum++; có độ phức tạp thuật toán là O(1)
Hai vòng for có độ phực tạp O(n2)
Câu 3:
Cho biết độ phức tạp của chương trình sau, Tích 2 số tự nhiên a và b
m:=a;
n:=b;
While m>0 do begin m:=m-1;
n:=n+b;
return(n);
Giải :
{1}m:=a;
{2}n:=b;
{3}While m>0 do
begin
{4}m:=m-1;
{5}n:=n+b;
end;
return(n);
Dòng 1 2 4 5 có độ phức tạp là O(1)
vậy trong While có độ phức tạp là O(1)
Ta thấy while chạy theo m giảm dần khi m còn >0
Cũng khi đó độ phức tạp thuật toán là O(m)

Giải phần lý thuyết

1. Hệ thức truy hồi là gì? Cách giải htth
Hệ thức truy hồi(hay công thức truy hồi) đối với dãy số {an} là công thức biểu
diễn an qua một hay nhiều số hạng đi trước của dãy. Dãy số được gọi là lời giải
hay nghiệm của hệ thức truy hồi nếu các số hạng của nó thỏa mãn hệ thức truy hồi
này
Ví dụ :
Ví dụ: Cho {an} là dãy thỏa mãn hệ thức truy hồi an = an-1 – an-2 với
n=2,3,4,... Và giả sử a0 = 5,
a1 = 9. Tìm a2, a3?
Giải : Từ hệ thức truy hồi ta có
a2 = a1 - a0 = 9 - 5 = 4.
a3 = a2 – a1 = 4 – 9 = -5.
Về Đầu Trang Go down
Xem lý lịch thành viên
tkhking

Member Năng Động


Member Năng Động
avatar

Thú CƯng :
Nam Pisces

Số bài viết : 114
Điểm : 135
Được cảm ơn : 1
Ngày sinh : 18/03/1990
Tham gia ngày : 01/07/2010
Tuổi : 28
Đến từ : Óc Trâu Lấy Ra
Ngề nghiệp : Student
Chăm ngôn : King

Bài gửiTiêu đề: Re: CÂU HỎI MÔN PHÂN TÍCH THIẾT KẾ THUẬT TOÁN   16/7/2010, 01:29

Code:
DFS:
Procedure DFS(v);
1Begin
2   Thamdinh(v);
3            Chuaxet[v]:=false;
 4                For u thuoc ke(v) do
 5                         If chuaxet[u] then DFS(u);
6End;
Có chương trình DFS thì thực hiện không quá n lần
 2 3 có độ phức tạp là O(1)
4  có độ phức tạp là O(n)
5 theo định lý cộng thì dòng if và đệ quy có độ phức tạp là max(O(1, m)) => O(m)
=> Theo định lý cộng xét cho nguyên thuật toán DFS có độ phức tạp là O(n+m)
Về Đầu Trang Go down
Xem lý lịch thành viên trungkienho90@yahoo.com
tkhking

Member Năng Động


Member Năng Động
avatar

Thú CƯng :
Nam Pisces

Số bài viết : 114
Điểm : 135
Được cảm ơn : 1
Ngày sinh : 18/03/1990
Tham gia ngày : 01/07/2010
Tuổi : 28
Đến từ : Óc Trâu Lấy Ra
Ngề nghiệp : Student
Chăm ngôn : King

Bài gửiTiêu đề: Re: CÂU HỎI MÔN PHÂN TÍCH THIẾT KẾ THUẬT TOÁN   16/7/2010, 01:30

Code:
BFS
produce BFS(v)
1 begin 2   Queue:=rổng; 3 Queue<= v; 4 chuaxet[v]:=false; 5 while Queue #rổng do 6 begin 7   p<=Queue; 8 thamdinh(p); 9 for u thuoc ke[p] do 10 if chuaxet then 11 begin 12   Queue<= u; 13 chuaxet[u]:=false; 14 end; 15 end; 16 end;   
2,3,4,7,8,13,14 có độ phức tạp là O(1)
5 dòng lặp While có độ phức tạp là O(n)
10,11 vì chỉ chạy không quá số đỉnh nên O(m)
=>Thuật toán BFS có độ phức tạp là O(m+n)
Về Đầu Trang Go down
Xem lý lịch thành viên trungkienho90@yahoo.com
tkhking

Member Năng Động


Member Năng Động
avatar

Thú CƯng :
Nam Pisces

Số bài viết : 114
Điểm : 135
Được cảm ơn : 1
Ngày sinh : 18/03/1990
Tham gia ngày : 01/07/2010
Tuổi : 28
Đến từ : Óc Trâu Lấy Ra
Ngề nghiệp : Student
Chăm ngôn : King

Bài gửiTiêu đề: Re: CÂU HỎI MÔN PHÂN TÍCH THIẾT KẾ THUẬT TOÁN   16/7/2010, 01:31

đã hoàn thành nhiệm vụ đã hứa với anh em chỉ còn việc ngày mai lên thi nữa là ok ah
Về Đầu Trang Go down
Xem lý lịch thành viên trungkienho90@yahoo.com
Sakura


avatar

Thú CƯng :
Nam Scorpio

Số bài viết : 1124
Điểm : 1688
Được cảm ơn : 35
Ngày sinh : 03/11/1990
Tham gia ngày : 16/03/2010
Tuổi : 27
Đến từ : Bình Dương
Ngề nghiệp : IT Student

Bài gửiTiêu đề: Re: CÂU HỎI MÔN PHÂN TÍCH THIẾT KẾ THUẬT TOÁN   16/7/2010, 08:59

Dẹp hết đi, thảo luận cho đã, cuối cùng được gì nào? 70k à? kakak! tốt nhất là nên đi cúng để các môn sau không gặp ổng thì tốt hơn! hehe!
Ikariam nào anh em!
[You must be registered and logged in to see this link.]

_________________________________________________
Khách viếng thăm muốn liên hệ với mình thì xem thông tin phía dưới nha:
Email: [You must be registered and logged in to see this link.]
Nick Yahoo: Edward_Thien
Về Đầu Trang Go down
Xem lý lịch thành viên
con_ca_nho90

Member Nhiệt Tình


Member Nhiệt Tình
avatar

Thú CƯng :
Nam Aquarius

Số bài viết : 289
Điểm : 329
Được cảm ơn : 4
Ngày sinh : 17/02/1990
Tham gia ngày : 05/05/2010
Tuổi : 28
Đến từ : Nhà hàng xóm
Ngề nghiệp : click chuột định giang sơn :D
Chăm ngôn : Giang hồ hiểm ác không bằng mạng lag thất thường

Bài gửiTiêu đề: Re: CÂU HỎI MÔN PHÂN TÍCH THIẾT KẾ THUẬT TOÁN   16/7/2010, 09:44

thế là được 70k rồi.hehe
Về Đầu Trang Go down
Xem lý lịch thành viên https://plus.google.com/u/0/?hl=vi jeennguyen@ymail.com
Sponsored content




Bài gửiTiêu đề: Re: CÂU HỎI MÔN PHÂN TÍCH THIẾT KẾ THUẬT TOÁN   

Về Đầu Trang Go down
 

CÂU HỎI MÔN PHÂN TÍCH THIẾT KẾ THUẬT TOÁN

Xem chủ đề cũ hơn Xem chủ đề mới hơn Về Đầu Trang 
Trang 2 trong tổng số 3 trangChuyển đến trang : Previous  1, 2, 3  Next

Permissions in this forum:Bạn không có quyền trả lời bài viết
IT World! :: HỌC TẬP :: Học Kỳ IV :: Phân Tích Thiết Kế Thuật Toán-