đề thi mẫu PTTKTT


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 | 
 

 đề thi mẫu PTTKTT

Xem chủ đề cũ hơn Xem chủ đề mới hơn Go down 
Tác giảThông điệp
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 đề: đề thi mẫu PTTKTT   15/7/2010, 12:29

link down:
[You must be registered and logged in to see this link.]
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: đề thi mẫu PTTKTT   15/7/2010, 23:34

hotboy đã viết:
link down:
[You must be registered and logged in to see this link.]
sao phân tích thiết kế thuật toán mà sao giống lý thuyết đồ thị quá...thanks hotboy cái nha.. không có nút thanks nên nói thôi... santa
Về Đầu Trang Go down
Xem lý lịch thành viên trungkienho90@yahoo.com
bubupro.gdty

Member Năng Động


Member Năng Động
avatar

Thú CƯng :
Nữ Aries

Số bài viết : 118
Điểm : 123
Được cảm ơn : 0
Ngày sinh : 01/04/1990
Tham gia ngày : 02/04/2010
Tuổi : 28
Đến từ : Gia Lai
Ngề nghiệp : student
Chăm ngôn : to be or not to be

Bài gửiTiêu đề: do phuc tap cua thuat toan   16/7/2010, 00:20

Đặt vấn đề
Thời gian mà máy tính khi thực hiện một thuật toán không chỉ phụ thuộc vào bản thân thuật toán đó, ngoài ra còn tùy thuộc từng máy tính. Để đánh giá hiệu quả của một thuật toán, có thể xét số các phép tính phải thực hiện khi thực hiện thuật toán này. Thông thường số các phép tính được thực hiện phụ thuộc vào cỡ của bài toán, tức là độ lớn của đầu vào. Vì thếđộ phức tạp thuật toán là một hàm phụ thuộc đầu vào. Tuy nhiên trong những ứng dụng thực tiễn, chúng ta không cần biết chính xác hàm này mà chỉ cần biết một ước lượng đủ tốt của chúng.
Để ước lượng độ phức tạp của một thuật toán ta thường dùng khái niệm bậc O-lớn
Bậc O-lớn
Gọi n là độ lớn đầu vào. Tùy thuộc từng bài toán mà n có thể nhận những giá trị khác nhau. Chẳng hạn, bài toán tính giai thừa thì n chính là số cần tính giai thừa. Nhiều bài toán số trị, chẳng hạn tính sai phân thì n là số chữ số có nghĩa cần đạt được. Trong các phép tính đối với ma trận thì n là số hàng hoặc cột của ma trận.
Độ phức tạp của bài toán phụ thuộc vào n. Ở đây ta không chỉ đặc trưng độ phức tạp bởi số lượng phép tính, mà dùng một đại lượng tổng quát là tài nguyên cần dùng R(n). Đó có thể là số lượng phép tính (có thể tính cả số lần truy nhập bộ nhớ, hoặc ghi vào bộ nhớ); nhưng cũng có thể là thời gian thực hiện chương trình (độ phức tạp về thời gian) hoặc dung lượng bộ nhớ cần phải cấp để chạy chương trình (độ phức tạp về không gian).
Xét quan hệ giữa tài nguyên và độ lớn đầu vào, nếu như tìm được hằng số C > 0, C không phụ thuộc vào n, sao cho với n đủ lớn, các hàm R(n),g(n) đều dương và

thì ta nói thuật toán có độ phức tạp cỡ O(g(n)).
Diễn giải
Độ phức tạp không phải là độ đo chính xác lượng tài nguyên máy cần dùng, mà đặc trưng cho động thái của hệ thống khi kích thước đầu vào tăng lên. Chẳng hạn với thuật toán có độ phức tạp tuyến tính O(n) (xem phần dưới), nếu kích thước đầu vào tăng gấp đôi thì có thể ước tính rằng tài nguyên cần dùng cũng tăng khoảng gấp đôi. Nhưng với thuật toán có độ phức tạp bình phương O(n2) thì tài nguyên sẽ tăng gấp bốn. Mặt khác, với thuật toán có độ phức tạp hàm mũ O(2n) thì chỉ cần công thêm 2 đơn vị vào độ lớn đầu vào cũng đã làm tài nguyên tăng gấp 4 lần (tức là theo cấp số nhân) rồi.
Các độ phức tạp thường gặp đối với các thuật toán thông thường gồm có:
 Độ phức tạp hằng số, O(1). Số phép tính/thời gian chạy/dung lượng bộ nhớ không phụ thuộc vào độ lớn đầu vào. Chẳng hạn như các thao tác hệ thống: đóng, mở file.
 Độ phức tạp tuyến tính, O(n). Số phép tính/thời gian chạy/dung lượng bộ nhớ có xu hướng tỉ lệ thuận với độ lớn đầu vào. Chẳng hạn như tính tổng các phần tử của một mảng một chiều.
 Độ phức tạp đa thức, O(P(n)), với P là đa thức bậc cao (từ 2 trở lên). Chẳng hạn như các thao tác tính toán với mảng nhiều chiều (tính định thức ma trận).
 Độ phức tạp logarit, O(logn) (chú ý: bậc của nó thấp hơn so với O(n)) . Chẳng hạn thuật toán Euclid để tìm ước số chung lớn nhất.
 Độ phức tạp hàm mũ, O(2n). Trường hợp này bất lợi nhất và sẽ rất phi thực tế nếu thực hiện thuật toán với độ phức tạp này.
Lưu ý
Định nghĩa trên mang tính "an toàn" theo nghĩa nó chỉ xét sự tiêu tốn tài nguyên không vượt quá một ngưỡng g(n) nào đó, chứ không nhất thiết đúng bằng g(n) (chú ý dấu bất đẳng thức). Theo đó, một thuật toán có độ phức tạp cỡ n thì đồng thời sẽ có độ phức tạp cỡ n2; với hàm ý rằng thuật toán này không bao giờ có động thái phức tạp hóa vượt qua ngưỡng đa thức bậc hai.
Về Đầu Trang Go down
Xem lý lịch thành viên
bubupro.gdty

Member Năng Động


Member Năng Động
avatar

Thú CƯng :
Nữ Aries

Số bài viết : 118
Điểm : 123
Được cảm ơn : 0
Ngày sinh : 01/04/1990
Tham gia ngày : 02/04/2010
Tuổi : 28
Đến từ : Gia Lai
Ngề nghiệp : student
Chăm ngôn : to be or not to be

Bài gửiTiêu đề: Re: đề thi mẫu PTTKTT   16/7/2010, 00:22

đáng nhẽ ra ko nên post ở đây nhưng bên kia nhìu chữ quá tui mà post thêm cái này nữa e mọi người thôi mien nên để qua bên này vậy
Về Đầu Trang Go down
Xem lý lịch thành viên
Sponsored content




Bài gửiTiêu đề: Re: đề thi mẫu PTTKTT   

Về Đầu Trang Go down
 

đề thi mẫu PTTKTT

Xem chủ đề cũ hơn Xem chủ đề mới hơn Về Đầu Trang 
Trang 1 trong tổng số 1 trang

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-