Bài giảng Thuật toán và tư duy thuật toán

Bài giảng Thuật toán và tư duy thuật toán với mục tiêu củng cố khái niệm và những đặc trưng cơ bản về thuật toán; củng cố và phân tích thêm về thiết kế thuật toán; nâng cao hiệu quả giảng dạy thuật toán và cài đặt thuật toán ở PT.
Nội dung trích xuất từ tài liệu:
Bài giảng Thuật toán và tư duy thuật toánRÈNLUYỆNTƯDUYVÀKHẢNĂNGCÀIĐẶT THUẬTTOÁNỞTRƯỜNGPT MụctiêuCủngcốkháiniệmvànhữngđặctrưngcơbản vềthuậttoán.Củngcốvàphântíchthêmvềthiếtkếthuật toánNângcaohiệuquảgiảngdạythuật toánvàcài đặtthuậttoánởPT HồCẩmHàĐHSPHN 1.THUẬTTOÁN• Kháiniệmthuậttoán• Máytínhvàthuậttoán• Đánhgiáthuậttoán 3 1.1KHÁINIỆMTHUẬTTOÁN(1)• Khôngđềcậpđếnkháiniệmhìnhthứcchínhxáccủathuật toán(địnhnghĩathôngquamôhìnhmáyTuring). Xemxétmộtsốđịnhnghĩa(khônghìnhthức)ítnhiềukhác nhau• Bảnchấtmôtảmộtcáchthứcmàmộtnhiệmvụhaymột tiếntrìnhđượcthựchiệnnhưthếnàocủathuậttoán. 4 1.1KHÁINIỆMTHUẬTTOÁN(2) Địnhnghĩa1(K.Rosen):Mộtthuậttoánlàmộtthủtụcxácđịnhđểgiảimộtbàitoán(vấnđề),sửdụngmộtsốhữuhạnbước.Mỗibướccóthểgồmmộthoặcmộtsốthaotác/phéptoán. 5 1.1KHÁINIỆMTHUẬTTOÁN(3) Địnhnghĩa2.(G.Brookshear)Mộtthuậttoánlàmộttậphợpcóthứtựcácbứớckhôngnhậpnhằng,thựchiệnđược,xácđịnhmộttiếntrìnhcókếtthúc,(tứcviệcthựchiệnthuậttoánphảidẫntớimộtkếtthúc). 6 1.1KHÁINIỆMTHUẬTTOÁN(4) Địnhnghĩa3.(A.V.Aho,J.E.Hopcroft,J.D.Ullman)Thuậttoánlàmộtdãyhữuhạncáccâulệnh,mỗicâulệnhđềucómộtýnghĩarõràngvàcóthểđượcthựchiệnvớimộtlượngcôngsứchữuhạntrongmộtthờigianhữuhạn. 7 1.1KHÁINIỆMTHUẬTTOÁN(5) Địnhnghĩa4.(C.A.Shaffer)Mộtthuậttoánlàmộtbảngchỉdẫnđểgiảimộtbàitoán,trongđócácbướclàcụthểvàkhôngnhậpnhằng.Thuậttoánphảiđúngđắntheonghĩanóphảitínhđúnghàmmongmuốn,chuyểnđổimỗiđầuvào(dữliệuvào)thànhđầura(dữliệura)đúng,cóđộdàihữuhạnvàphảikếtthúcvớimọidữliệuvàohợplệ. 8 1.1KHÁINIỆMTHUẬTTOÁN(6) Cáctínhchất:Đầuvào(dữliệuvào) cócácgiátrịđầuvàođượclấytừmộttậpxácđịnh.Đầura(kếtquảra) Từmộttậpcácgiátrịđầuvào,thuậttoánsảnsinhracácgiátrịđầurathuộcmộttậpxácđịnh.Cácgiátrịđầurachứalờigiảicủabàitoán.Tínhxácđịnh Cácbướctrongmộtthuậttoánphảiđượcđịnhnghĩachính 9xác(khôngnhậpnhằng). 1.1KHÁINIỆMTHUẬTTOÁN(7) Cáctínhchất(tiếp)Tínhhữuhạn Phảichokếtquả(đầura)mongđợisaumộtsốhữuhạnbước (cóthểrấtlớn)vớimọiđầuvàothuộctậpcácdữliệuvàohợp lệ.Tínhhiệuquả Phảicókhảnăngthựchiệnmỗibướccủathuậttoánmộtcách đúngđắn(chínhxác)vàtrongmộtthờigianchấpnhậnđược.Tínhtổngquát(phổdụng) phảiđượcápdụngchomọibàitoáncóchungmộtdạng,mà khôngphảichỉchoriêngmộttậpcácdữliệuvàođặcbiệt. 10 1.1KHÁINIỆMTHUẬTTOÁN(8)Khôngchỉcótrongtinhọc,cónhiềuthuậttoánmôtảnhiềuloạitiếntrìnhcủađờisốnghàngngàynhưđanáolen,làmmộtloạibánh,chơimộtbảnnhạc,phamộttáchcàphê,...Nóichung,mộttácnhânthựchiệnmộttiếntrìnhđượcgọilàmộtbộxửlý.Mộtbộxửlýcóthểlàmộtngười,mộtmáytínhhaymộtthiếtbịcơhoặcđiệnnàođó. 11 1.2Máytínhvàthuậttoán(1)MTlàmộtbộxửlýđặcbiệtvớicácđặctrưngvề• Tốcđộ• Tínhtincậy• Bộnhớ• Chiphí 12 1.2Máytínhvàthuậttoán(2)Đểbộxửlýcóthểthựcthimộttiếntrình:NóphảiđượccungcấpmộtthuậttoánthíchhợpNóphảicókhảnănglýgiải(cũnggọilàthôngdịch)thuậttoán,tứcphảicókhảnăng: – hiểuđượcýnghĩamỗibướccủathuậttoán; – thựchiệnđượcthaotác(phéptoán)tươngứng.VD 13 1.2Máytínhvàthuậttoán(3)TrườnghợpbộxửlýlàmộtmáytínhthìthuậttoánphảiđượcbiểuthịdướidạngmộtchươngtrìnhĐểthựcthimộttiếntrìnhtrênmộtmáytính,cầnphải:Thiếtkếmộtthuậttoán(đưaramộtmôtảtiếntrìnhphảiđượcthựchiệnnhưthếnào);Biểuthịthuậttoánthànhmộtchươngtr ...