Bài giảng Tin học đại cương: Phần 2 (Chương 1) - TS.Nguyễn Bá Ngọc

Nối tiếp phần 1 bộ bài giảng Tin học đại cương mời các bạn cùng tìm hiểu phần 2 (Chương 1) với các nội dung chính như: Giải quyết bài toán bằng máy tính: Khái niệm về bài toán; quá trình giải quyết bài toán bằng máy tính; các phương pháp giải quyết bài toán bằng máy tính; phân loại bài toán;...
Nội dung trích xuất từ tài liệu:
Bài giảng Tin học đại cương: Phần 2 (Chương 1) - TS.Nguyễn Bá NgọcIT1110Tinhọcđạicương PhầnIIGiảiquyếtbàitoán NguyễnBáNgọc 1 ÔntậpnộidungphầnI PhầnI:TINHỌCCĂNBẢN  Thôngtin  Biểudiễndữliệutrongmáytính  Máytínhvàmạngmáytính  Hệđiềuhànhvàcáchệthốngứngdụng NộidungphầnII Chương1:Giảiquyếtbàitoánbằngmáytính  Kháiniệmvềbàitoán  Quátrìnhgiảiquyếtbàitoánbằngmáytính  Cácphươngphápgiảiquyếtbàitoánbằngmáytính  Phânloạibàitoán Chương2:Thuậttoán  Địnhnghĩathuậttoán  Biểudiễnthuậttoán  Mộtsốthuậttoánthôngdụng  Thuậttoánđệquy  Thuậtgiảiheuristic 3 NộidungphầnII Chương1:Giảiquyếtbàitoánbằngmáytính  Kháiniệmvềbàitoán  Quátrìnhgiảiquyếtbàitoánbằngmáytính  Cácphươngphápgiảiquyếtbàitoánbằngmáytính  Phânloạibàitoán Chương2:Thuậttoán  Địnhnghĩathuậttoán  Biểudiễnthuậttoán  Mộtsốthuậttoánthôngdụng  Thuậttoánđệquy  Thuậtgiảiheuristic 4 1.1.Kháiniệmvềvấnđềvàbàitoán Vấnđềrộnghơnbàitoán? Pitagochiavấnđềra:  Theoremalàvấnđềcầnđượckhẳngđịnhđúngsai  Problemalàvấnđềcầntìmgiảiphápđểđạtđượcmột mụctiêuxácđịnhtừnhữngđiềukiệnbanđầu. Diễnđạtbằngsơđồ:A B  Alàgiảthiết,điềukiệnbanđầu  Blàkếtluận,mụctiêucầnđạt  làsuyluận,giảiphápcầnxácđịnh 5 1.2.Cácbướcgiảiquyếtbàitoánbằng máytính Bước1:Xácđịnhvấnđềbàitoán Bước2:Lựachọnphươngphápgiải Bước3:Xâydựngthuậttoánhoặcthuật giải Bước4:Càiđặtchươngtrình Bước5:Hiệuchỉnhchươngtrình Bước6:Thựchiệnchươngtrình 6 1.3.Cácphươngphápgiảiquyếtvấnđề bằngmáytính Giảiquyếtvấnđềtheohướngxácđịnhtrựctiếp lờigiải  xácđịnhtrựctiếplờigiảiquathủtụctínhtoánhoặcthủ tụcbaogồmmộtsốhữuhạncácthaotácsơcấp. Giảiquyếtvấnđềtheohướngtìmkiếmlờigiải  nguyênlýthửvàsai  cácphươngpháp  liệtkêhayvétcạn  thửngẫunhiên  quaylui  chiađểtrị 7 1.4.Phânloạibàitoán Bàitoánđathức Bàitoánkhôngđathức NPProblems 8 NộidungphầnII Chương1:Giảiquyếtbàitoánbằngmáytính  Kháiniệmvềbàitoán  Quátrìnhgiảiquyếtbàitoánbằngmáytính  Cácphươngphápgiảiquyếtbàitoánbằngmáytính  Phânloạibàitoán Chương2:Thuậttoán  Địnhnghĩathuậttoán  Biểudiễnthuậttoán  Mộtsốthuậttoánthôngdụng  Thuậttoánđệquy  Thuậtgiảiheuristic 9 2.1.Địnhnghĩathuậttoán Làmộtkháiniệmcơsởcủatoánhọcvàtin học. Baogồmmộtdãyhữuhạncáclệnh/chỉthị rõràngvàcóthểthihànhđượcđểhướng dẫnthựchiệnmộthànhđộngnhằmđạt đượcmụctiêuđềra. Thuậttoánlàsựthểhiệncủamộtphương phápđểgiảiquyếtmộtvấnđề. 10 Vídụ1:Thuậttoántìmphầntửlớnnhất củamộtdãyhữuhạncácsốnguyên Cácbước:  1.Đặtgiátrịlớnnhấttạmthờilàsốnguyênđầutiên.  2.Sosánhsốnguyênkếtiếptrongdãyvớigiátrịlớn nhấttạmthời,nếusốnguyênnàylớnhơngiátrịlớn nhấttạmthờithìđặtgiátrịlớnnhấttạmthờibằngsố nguyênnày.  3.Lặplạibước2nếucònsốnguyêntrongdãychưa đượcxét.  4.Dừngnếukhôngcònsốnguyênnàotrongdãychưa đượcxét.Giátrịlớnnhấttạmthờilúcnàychínhlàgiá trịlớnnhấttrongdãysố. 11 Vídụ2:Thuậttoángiảiphươngtrìnhbậc hai:ax2+bx+c=0(a 0) 1.Nhập3hệsốa,b,c 2.TínhgiátrịΔ=b24*a*c 3.XétdấuΔ.NếuΔ>0thìthựchiệncácthaotác sauđây:  3.1.Tínhcácnghiệmtheocáccôngthức:  x1=(bsqrt(Δ))/(2*a)  x2=(b+sqrt(Δ))/(2*a)  3.2.Xuấtkếtquả:phươngtrìnhcóhainghiệmx1vàx2. 4.NếuΔlà0thìxuấtkếtquả:phươngtrìnhcó nghiệmképlàb/(2*a) 5.NếuΔ ...