Đ I H Ạ C QUỐỐC GIA TP Ọ . HỐỒ CHÍ MINH TRƯ NG Đ Ờ I H Ạ C CỐNG NGH Ọ THỐNG TIN Ệ Ch ng T ươ rình Đào T o CNTT ạ BÀI BÁO CÁO MÔN H C Ọ PHƯ N Ơ G PHÁP NGHIÊN C U Ứ KHOA H C Ọ TRONG TIN H C Ọ H c ọ viên: Trầần Văn ABC Mã sốố: 1234567890 TP. HCM, 05/2010 Tóm Tắt1 Các Ph ng Pháp Khoa H ươ c ọ
Trong Khoa Học Máy Tính Gordana DODIG-CRNKOVIC
Khoa Khoa h c máy tính, Đ ọ i h ạ c Malardalen ọ Vasteras, Th y Đi ụ ển
Bài báo này phân tích nh ng ữ khía c nh ạ khoa h c ọ c a
ủ KHMT. Đâầu tiên nó đ nh ị nghĩa khoa h c ọ và ph ng ươ pháp khoa h c
ọ nói chung. Bàn vêầ mốối quan hệ gi a ữ khoa h c, nghiên c ọ u, phát tri ứ n và c ể ống ngh . ệ
Các lý thuyêốt hi n có ệ vêầ khoa h c (theo P ọ
oper, Carnap, Kuhn, Chalmers) có tính châốt nh m ư t lý ộ t ng. Khống ưở
nhiêầu ngành khoa h c ọ tiêốp c n ậ đ c ượ v i ớ quan ni m ệ này. Triêốt h c ọ vêầ khoa h c
ọ (Lý thuyêốt vêầ khoa h c)
ọ ngày nay khống giúp đ c ượ gì nhiêầu
khi cốố gắống phân tích ngành Khoa h c Máy tính. ọ Khoa h c Máy ọ tính là m t lĩnh ộ v c m ự i và ớ đốối t ng
ượ nghiên c u (thêố ứ gi i) ớ c a ủ nó
là máy tính. Máy tính là cống cụ phát tri n ể khống ng ng,
ừ là sự hi n ệ th c ự hóa ý t ng đ ưở cốố gắ
ể ống bi u diêễn câ ể
ốu trúc tri th c và thống tin ứ
vêầ thêố gi i, bao ớ gốầm luốn
chính bản thân máy tính. Tuy nhiên có s khác bi ự t, Khoa h ệ
c Máy tính có nêần t ọ ng ả c s ơ c ở a ủ nó là logic h c, ọ toán h c, ọ c nh ả ng ữ ph ng
ươ pháp nghiên c uứ lý thuyêốt và th c ự nghi m đêầu ệ đi theo nh ng chu ữ n m ẩ c ự c a ủ khoa h c c ọ ổ đi n. Mố ph ể ng ỏ và
mố hình hóa máy tính nh ư m t ộ ph ng ươ pháp c th ụ ể cho ngành h c, ọ seễ phát tri n ể h n ơ n a ữ trong t ng
ươ lai, khống chỉ áp d ng
ụ cho máy tính mà còn cho nh ng ữ ngành khoa h c khác c ọ ũng nh trong lĩnh v ư c th ự ng m ươ i và ngh ạ thu ệ t ậ .
1 Phâần trích yêốu (abstract) ii Mục Lục1
Tóm Tắốt......................................................................................................................................................... ii M c L ụ c
ụ ...................................................................................................................................................... iii L i Cám ờ n
Ơ ................................................................................................................................................ iv Danh M c B
ụ ảng & Hình nh
Ả ...............................................................................................................v M Đâầu ở
.......................................................................................................................................................... 1 1. Khoa h c là gì ọ
.................................................................................................................................... 3
1.1. Các ngành khoa h c kinh đi ọ n (
ể Classical Sciences).................................................3
1.2. Các ngành khoa h c thu ọ
c vêầ nhiêầu lĩnh v ộ c khác nhau ự
.......................................5
2. Phương pháp khoa h c
ọ .................................................................................................................6 3. Khoa h c, Nghiên c ọ u, Cống ngh ứ
ệ...........................................................................................9 3.1. Khoa h c c ọ a Aristot ủ le v i Cống ngh ớ
ệ..........................................................................9 3.2. Khoa h c hi ọ n đ ệ i v
ạ ới Cống nghệ...................................................................................9
4. Khoa h c Máy tính là gì? ọ
............................................................................................................11
4.1. Các lĩnh v c con c ự a KHMT ủ
..............................................................................................13
5. Phương pháp khoa h c c ọ a KHMT ủ
.......................................................................................15
5.1. Mố hình hóa (modeling).....................................................................................................15
5.2. KHMT lý thuyêốt (Theoretical Computer Science)....................................................17 5.3. KHMT th c nghi ự m (Experimental C ệ
omputer Science).......................................19
5.4. Mố ph ng máy tính ỏ
.............................................................................................................. 20
Kêốt lu n vêầ các ph ậ ương pháp khoa h c c ọ a KHMT ủ
...............................................................24 Tài li u tham kh ệ o
ả ................................................................................................................................ 25 Ph L ụ c
ụ ....................................................................................................................................................... vi 1 Mục l c t ụ đ ự ng (T ộ able of Contents) iii Lời Cám Ơn
Trong quá trình tìm tài li u cho ệ mốn h c Ph ọ ng pháp ươ nghiên c u ứ khoa h c trong ọ tin h c,
ọ tối tiêốp cận với hai bài báo khoa h c
ọ Scientific Methods in Computer Science c a Gordana D ủ .C thu c
ộ khoa Khoa h c máy tính, Đ ọ i h ạ c M ọ alardalen, Th y ụ Đi n
ể . Và Should Computer Scientists Experiment More? c a
ủ Walter F. Tichy, Đ i ạ h c ọ Karlsruhe, Đ c.
ứ Trong khuốn khổ bài thu ho ch ạ mốn h c
ọ này, tối xin đ c ượ
phép trình bày l i bài ạ báo khoa h c c ọ a Gordan ủ v i sớ hi ự u biêốt ể h n ạ chêố c a ủ tối,
trong quá trình chuy n ng ể vâễn còn m ữ t sốố thu ộ t ng ậ ch ữ a chu ư n xác. ẩ
Cuốối cùng tối xin c m ả n thâầy XYZ, ng ơ i đã h ườ ng dâễn c ướ húng tối mốn h c ọ này (và m t ộsốố mốn ở nh ng ữ nắm đ i ạ h c ọ c a
ủ tối), và các b n
ạ bè, đốầng nghi p ệ v i ớ nh ng ữ trao đ i thú v ổ
ị và sự giúp đ chân thà ỡ nh. iv
Danh Mục Bảng & Hình Ảnh B ng 1 - Các ng ả ành khoa h c,
ọ đốối t ng và ph ượ ng pháp ươ
...................................................4 B ng 2 - Các k ả hác bi t tiêu chu ệ n ẩ gi a khoa h ữ c v ọ i c
ớ ống nghệ......................................9
Hình 1 - Khoa h c là gì? ọ
......................................................................................................................... 3
Hình 2 - S đốầ mố t ơ tính châốt l ả p c ặ a ph ủ ng pháp gi ươ thuyê ả ốt-suy lu n ậ
(hypothetico-deductive method)........................................................................................................6
Hình 3 - Mốối quan h gi ệ a Khoa h ữ c, Nghiên c ọ u, Phát tri ứ n và C ể
ống nghệ. . . . . . 10
Hình 4 - KHMT trong câốu trúc c a lĩnh v ủ c Đi ự n toán ệ
.........................................................11
Hình 5 - Mố hình hóa............................................................................................................................ 15
Hình 6 - Quan ni m 3 chiêầu tro ệ
ng thu t toán Heapsort [21] ậ
.............................................18
Hình 7 - Khoa h c tính toán ọ
.............................................................................................................. 21
Hình 8 - Mố ph ng so sánh các biê ỏ ốn th mố hì ể nh v t châốt đen l ậ nh N-body trong ạ v t lý thiên th ậ
ể........................................................................................................................................ 22 v Mở Đầu1
Khoa học Máy tính (KHMT) là m t ộ lĩnh v c ự m i ớ nh ng
ư có đóng góp to l n ớ vào xã h i
ộ loài người. KHMT vâễn trên con đ ng ườ phát tri n, ể mang l i ạ nhiêầu ng ứ d ng ụ hi u ệ qu , đốầng ả th i ờtiêốp t c ụ hoàn thi n ệ các ph ng ươ pháp lu n ậ khoa h c ọ c a ủ nó.
KHMT vâễn kêố th a ừ nh ng ữ ph ng ươ pháp lu n
ậ từ các ngành khoa h c ọ kinh đi n ể
hàng ngàn nắm qua, mà nêần t ng ả c a ủ nó là Logic h c ọ và Toán h c ọ . Tuy nhiên, nó có ph i
ả là ngành khoa h c
ọ như bao ngành khoa h c ọ t
ự nhiên khác hay khống? Là khoa h c th ọ c nghi ự m hay khoa h ệ c lý thuyêốt? ọ
Theo Brooks (trong Allen Newell Award Lecture) nghi ng rắầng ờ th c ự têố các hi n ệ t ng/đốối ượ t ng ượ đ c ượ nghiên c u ứ b i
ở các nhà khoa h c
ọ máy tính là máy tính và ch ng ươ trình là nh ng ữ th do ứ con ng i
ườt oạ ra, vì v y
ậ chúng ta có th kêốt ể lu n ậ
rắầng KHMT khống ph i ảlà m t ộngành khoa h c ọ t nhiên ự
theo nghĩa truyêần thốống c a nó. ủ V y thì ậ ch đêầ ủ chính c a
ủ KHMT khống ph i là máy tính, mà ả
là thống tin và các quá
trình xử lý thống tin. Nh ng
ư các mố hình máy tính th t
ậ nghèo nàn khi so sánh v i ớ
quá trình xử lý thống tin trong t nhiên, ự ch ng ẳ h n ạ nh ư h
ệ thâần kinh, quá trình di truyêần…
Vâốn đêầ vâễn còn nhiêầu tranh cãi.
Khống rõ ràng nh tên ư g i, Khoa ọ h c Máy ọ
tính khống mang tiêu chu n ẩ “khoa h c” ọ
theo cách lý thuyêốt truyêần thốống vêầ khoa h c ọ [3-6] đ nh ị nghĩa c m ụ t ừ này. Khoa h c
ọ Máy tính (KHMT) là m t ộ ngành h c ọ trẻ kh i
ở đâầu từ Toán h c ọ và V t ậ lý h c, ọ t ng ươ t nh ự các ư ngành khoa h c c ọ đi ổ n khác, ể tâốt c đêầu ả
có nguốần gốốc trong triêốt h c c ọ a Hy L ủ p c ạ đ ổ i. ạ N i
ổlên trong giai đo nạ hi nệ đ i (máy ạ tính đi n ệ t kyễ ử thu t
ậsốố đâầu tiên đ c ượ xây d ng
ự vào th pậ niên 1940), KHMT đã lâốy nh ng ữ ngành khoa h c ọ hi n ệ có làm nêần
tảng, tạo ra cơ sở cho mình từ nhiêầu mốn h c
ọ khác [11], [14], [16]. Do đó nghiên c u
ứ KHMT đòi h i ỏph i ảs d ử ng ụ ý t ng ưở t nhiêầu ừ lĩnh v c. ự KHMT kêốt h p ợ cả lý
thuyêốt v i thớ c nghi ự m, tr ệ u từ ng (t ượ ng qua ổ
n) v i thiêốt kêố (c ớ hi tiêốt). S phát ự tri n ể mang tính l ch ị s dâễn ử đêốn vi c
ệ bùng nổ nhiêầu ngành khoa h c ọ trao
đổi thống tin nhiêầu và nhiêầu h n ơ b i
ở vì khống chỉ ph ng ươ ti n
ệ truyêần thốầng trở nên râốt thu n ti ậ n ệ và hi u ệ qu , mà ả
còn nhu câầu đ nhìn nh ể n ậ thêố gi i ớ d i góc đ ướ ộ
1 Phâần nh p đêầ (Introduction) ậ 1 t ng
ổ th ngày càng tắng, đó ể là cách gi n th ả hóa thêố gi ể i đang ớ
thốống tr ịm nh meễ ạ hi n ệ nay. 2 1.Khoa học là gì
“Tổng thể sự vậ t nhiêầu hơ n tổ ng các phâần củ a nó”
Aristotle, Siêu hình học (Metaphysica)
Nói vêầ “khoa h c” ọ chúng ta th ng
ườ có nhiêầu đ nh
ị nghĩa vêầ các ngành khoa h c ọ khác nhau. Và gi a
ữ các ngành khoa h c
ọ này l i ạkhác bi t
ệ nhau râốt nhiêầu. Đ nh ị nghĩa vêầ khoa h c ọ khống đ n ơ gi n
ả và do đó cũng khống rõ ràng. Xem thêm m t ộsốố phân lo i
ạ có thể trong [1] và [2]. Ví d , ụ l ch
ị sử và ngốn ng ữ h c ọ th ng ườ là khoa h c nh ọ n
ưg khống ph i lúc nào cũng đ ả c xêốp lo ượ i nh ạ là các ngành ư khoa h c. ọ 1.1.
Các ngành khoa học kinh điển (Classical Sciences)
Hình 1 - Khoa học là gì?
Hình trên cho thâốy rắầng khoa h c ọ có các lĩnh v c ự phân bi t
ệ rõ ràng. Logic và toán h c (tr ọ u t ừ
ng nhâốt và đốầng th ượ i là khoa h ờ c
ọchính xác nhâốt) là phâần quan tr ng ọ nhiêầu ho c ít ặ h n so ơ v i các
ớ ngành khoa h c khác. ọ
Nó râốt câần thiêốt cho v t ậ lý, ít 3 quan tr ng h ọ n đốối v ơ i hóa ớ h c và sinh h ọ c. V
ọ à ý nghĩa c a nó tiêốp t ủ c ụ gi m so v ả i ớ
các lĩnh v c khác ngoài ự l c đốầ trên. ượ
Dĩ nhiên cho đêốn ngày nay, cách lý lu n
ậ logic vâễn là nêần t ng ả cho tâốt c ả tri th c ứ nhân lo i trong m ạ i lĩnh v ọ c khoa h ự c cũng nh ọ triêốt h ư c. ọ Câốu trúc c a
ủ Hình 1 cho ta thâốy sự t ng
ươ tự như khi nhìn vào m t ộ kính hi n ể vi. V i đ ớ phân ộ gi i cao
ả nhâốt chúng ta có th nhìn ể thâốu vào khu v c ự gâần trung tâm
nhâốt. Bên trong khu v c
ự trung tâm logic h c ọ khống ch là ỉ cống c đ
ụ aư ra quyêốt đ nh, đối ị
lúc nó còn là đốối t ng
ượ để nghiên c u ứ . M c
ặ dù phâần l n các b ớ ph ộ n ậ c a ủ toán h c
ọ có thể gi m ả g n
ọ lại thành logic h c
ọ (theo Freg, Rusell và Whitehead), nh ng vi ư c rút g ệ n
ọ hoàn toàn thành logic h c là điêầu khống th ọ . ể Trong t ng ừ b c
ướ thu nhỏ lại, các lĩnh v c ự bên trong đ c
ượ xem như là điêầu ki n ệ
tiên quyêốt cho các lĩnh v c ự bên ngoài. V t ậ lý s ử d ng ụ toán h c ọ và logic h c ọ nh ư là các cống c mà
ụ khống câần ph i biêốt ả
rõ vêầ câốu trúc bên trong toán h c ọ hay logic.
Nghĩa là các thống tin vêầ câốu trúc sâu bên trong toán h c ọ và logic đ c ượ che giâốu khi nhìn t bên ừ ngoài. T ng ươ t nh ự vư y, v ậ t lý
ậ là điêầu ki n tiên ệ
quyêốt (câần thiêốt) cho hóa h c và t ọ i l ớ t hóa h ượ c đ ọ c che giâốu bên tro ượ ng lĩnh v c sinh h ự c ọ … Ý t ng ưở cơ b n
ả trên Hình 1 là trình bày m t
ộcách gi nả l c
ượ mốối liên hệ gi a ữ ba nhóm ngành khoa h c
ọ (Logic & Toán h c, ọ Khoa h c
ọ Tự nhiên và Khoa h c ọ Xã h i) ộ
cũng nh kêốt nốối v ư i các h ớ thốống t ệ t ư ng c ưở a nhân lo ủ i. ạ
Cuốối cùng toàn b h ộ thốống ệ lý lu n, ậ khoa h c ọ và tri th c ứ c a ủ nhân lo i ạ đ c ượ
nhúng vào trong mối tr ng vắn hóa. ườ
Bả ng 1 - Các ngành khoa h c, đốối t ọ
ượng và phươ ng pháp KHOA H C Ọ ĐỐỐI T NG ƯỢ PH NG ƯƠ PHÁP THỐỐNG TRỊ Đ n gi ơ n ả Gi n hóa lu ả n (phân tích) ậ Logic & Toán h c ọ Các đốối t ng
ượ trừu t ng: ượ Suy lu n (Deduction) ậ
m nh đêầ, sốố… ệ Khoa h c T ọ ự Các đốối t ng
ượ tự nhiên: các Ph ng
ươ pháp gi thuyêốt ả -suy nhiên câốu trúc v t ậ lý, tr ng ườ & lu n
ậ (Hypothetico-deductive
tương tác, các cơ thể method) sốống… Khoa h c Xã h ọ i ộ Các đốối t ng
ượ xã hội: cá Ph ng
ươ pháp gi thuyêốt ả -suy
nhân con người, nhóm, xã lu n
ậ (Hypothetico-deductive h i… ộ
method) + chú thích, gi i ả thích (Hermeneutics) Nhân văn Các đốối t ng
ượ vắn hóa: ý Chú thích, gi i ả thích 4 tưởng c a ủ con ng i,
ườ hành (Hermeneutics) đ ng
ộ và mốối quan h , ệ ngốn ng , ữ nh ng ữ t o ạ tác c a ủ nhân lo i… ạ Ph c t ứ p ạ
Chính thể lu n, ậ t ng ổ h p ợ (Synthesis) 1.2.
Các ngành khoa học thuộc về nhiều lĩnh vực khác nhau
Sự phát tri n ể c a ủ t t ư ng ưở con ng i ườ song song v i s ớ phát ự tri n ể c a ủ xã h i loài ộ ng i đã
ườ dâễn đêốn s xuâốt ự hi n
ệ các ngành khoa h c
ọ m i ớkhống thu c ộ vào bâốt kỳ m t ộ trong nh n ữ g ngành kinh đi n
ể trên, mà nó là các phâần chung chia s gi ẻ a ữ các
ngành khoa h c kinh đi ọ n. ể
Nhiêầu ngành khoa h c
ọ hi nệ đ i ạlà các liên ngành, hay thu c
ộ lo i ạ“chiêốt trung”. Đó là m t ộ xu h ng
ướ cho các ngành khoa h c
ọ m i ớđ tìm ể kiêốm các ph ng ươ pháp nghiên c u
ứ c aủ riêng nó và th m
ậ chí các vâốn đêầ trong nh ng ữ lĩnh v c ự r ng ộ l n. ớ
Ngày nay, nó có th để c xem ượ nh là ư m t kêốt ộ qu c ả aủ vi c
ệ giao tiêốp xuyên qua biên gi i các lĩnh v ớ c khoa h ự
c khác nhau dêễ dàng h ọ n và m ơ nh meễ h ạ n tr ơ c. ướ KHMT là ví d bao ụ gốầm lĩnh v c ự Trí tu nhân ệ t o
ạ có nguốần gốốc t ừ logic toán h c ọ và toán h c nh ọ ng ư dùng v t lý
ậ , hóa h c và sinh h ọ c ọ và th m ậ chí có nh ng ph ữ âần mà đó y h ở c và tâm lý h ọ c râốt quan tr ọ ng. ọ đây chúng ta có th Ở tìm thâốy m ể t
ộtiêầm nắng c a thêố gi ủ i ớ quan t ng th ổ m ể i trốễi ớ d y trong t ậ ng lai. ươ 5
2.Phương pháp khoa học Ph ng pháp khoa ươ h c là h ọ
thốống các nguyên tắốc logic đ ệ c
ượ các nhà khoa h c s ọ ử d ng đ ụ tìm
ể kiêốm các câu tr lải cho ờ nh ng
ữ thắốc mắốc, câu h i ỏ đ c ượ đ t ặ ra trong khoa h c. ọ Ph ng ươ pháp khoa h c ọ đ c ượ dùng đ s
ể nả sinh ra nh ng
ữ lý thuyêốt khoa h c, bao ọ gốầm c các
ả siêu lý thuyêốt khoa h c
ọ - meta-theories (lý thuyêốt vêầ các lý
thuyêốt), cũng nh các
ư lý thuyêốt đ c dùn ượ g đ thiêốt ể
kêố ra các cống c ụ đ ể s n ả sinh
các lý thuyêốt (các d ng ụ c , ph ụ ng ươ ti n, ệ các thu t
ậtoán…). Đ nơ gi nả trống giốống hình sau (Hình 2)
Hình 2 - S đốầ mố t ơ tính châốt l ả p c ặ a ph ủ ng pháp gi ươ ả thuyêốt-suy lu ậ n
(hypothetico-deductive method) 1. Đ t ra
ặ các câu h i trong ỏ bốối c nh
ả c aủ tri th c
ứ hi nệ t i ạ(lý thuyêốt & quan sát). Nó có th là ể m t
ộcâu h i ỏm i ớmà các lý thuyêốt cũ có kh ả nắng tr ả l i ờ (th ng ườ là tr ng ườ
hợp này), hay câu h i ỏ m i
ớ câần kêu g i đ ọ ể xây d ng ự m t ộ lý thuyêốt m i. ớ 2. Xây d ng m ự t gi ộ thuyêốt nh ả là câu tr ư l ả i d ờ kiêốn . ự 6