Bài giảng Nguyên lý và phương pháp lập trình

ðại học Quốc gia TP.HCM Trường ðại học Công nghệ thông tin Nguyên lý và phương pháp lập trình SuivantPrécédent TS. Nguyễn Tuấn ðăng Phần 1. Tổng quan các ngôn ngữ lập trình 1. Các ngôn ngữ lập trình thủ tục 2. Các ngôn ngữ lập trình hướng ñối tượng 3. Các ngôn ngữ lập trình hàm 4. Các ngôn ngữ lập trình logic Phần 2. Các nguyên lý căn bản của lập trình 1. Chương trình và cú pháp chương trình Nguyên lý và phương pháp lập trình Nội dung môn học SuivantPrécédent 2 2. Các phẩm chất cần có của chương trình 3. Tính dừng của chương trình 4. Tính ñúng ñắn của chương trình 5. Một số kỹ thuật tối ưu hóa chương trình Phần 3. Khảo sát một số ngôn ngữ lập trình (option) 1. C, Pascal 2. C++, Java, Smalltalk 3. Lisp 4. Prolog Bài thu hoạch : 40% Thi viết : 60% Bài giảng tham khảo chính: Nguyên lý và phương pháp lập trình, GS. TSKH. Hoàng Văn Kiếm. Nguyên lý và phương pháp lập trình ðánh giá môn học SuivantPrécédent 3 Lưu ý: - Học viên phải nắm vững các nội dung trong bài giảng chính ñược nêu ở trên (ñã ñược sử dụng từ các khóa 1, 2). - Các bài giảng mới bổ sung thêm cho khóa 3 chỉ dùng ñể tham khảo thêm. Hai yếu tố ảnh hưởng ñến thiết kế của các ngôn ngữ lập trình: • Kiến trúc máy tính ða số các ngôn ngữ lập trình ñược thiết kế trên cơ sở nguyên lý kiến trúc máy tính của von Nguyên lý và phương pháp lập trìnhPhần 1 : Tổng quan các ngôn ngữ lập trình Thiết kế của các ngôn ngữ lập trình SuivantPrécédent 4 Neumann. • Các phương pháp lập trình Mỗi phương pháp lập trình ñặt ra yêu cầu phải thiết kế các ngôn ngữ lập trình thích hợp. Nguyên lý kiến trúc máy tính của von Neumann: - Dữ liệu và chương trình ñược lưu trong bộ nhớ máy tính. - Bộ nhớ ñược tách biệt với CPU. - Các chỉ thị và dữ liệu ñược chuyển từ bộ nhớ ñến CPU theo cơ chế ống dẫn. Nguyên lý và phương pháp lập trìnhPhần 1 : Tổng quan các ngôn ngữ lập trình Yếu tố : kiến trúc máy tính SuivantPrécédent 5 Nguyên lý và phương pháp lập trìnhPhần 1 : Tổng quan các ngôn ngữ lập trình Yếu tố : kiến trúc máy tính SuivantPrécédent 6 • Thập niên 1950 và ñầu thập niên 1960: các chương trình máy tính còn ñơn giản. • Cuối thập niên 1960: - Lập trình có cấu trúc. - Thiết kế top-down. • Cuối thập niên 1970: Lập trình hướng dữ liệu. Nguyên lý và phương pháp lập trìnhPhần 1 : Tổng quan các ngôn ngữ lập trình Yếu tố : các phương pháp lập trình SuivantPrécédent 7 - Trừu tượng hóa dữ liệu • Giữa thập niên 1980: Lập trình hướng ñối tượng Trừu tượng hóa dữ liệu + kế thừa + ña hình • Các ngôn ngữ lập trình thủ tục/mệnh lệnh Biến, phát biểu, cấu trúc ñiều khiển. Ví dụ: C, Pascal • Các ngôn ngữ lập trình hướng ñối tượng Trừu tượng hóa dữ liệu, kế thừa, liên kết trễ. Ví dụ: Java, C++ • Các ngôn ngữ lập trình hàm Nguyên lý và phương pháp lập trìnhPhần 1 : Tổng quan các ngôn ngữ lập trình Phân loại các ngôn ngữ lập trình SuivantPrécédent 8 Áp dụng các hàm vào những ñối số. Ví dụ: LISP, Scheme • Các ngôn ngữ lập trình logic Dựa trên các luật. Ví dụ: Prolog Các ngôn ngữ lập trình thủ tục (procedural) còn ñược gọi là các ngôn ngữ lập trình mệnh lệnh (imperative). Nguyên lý chung: • Dữ liệu và khai báo dữ liệu Nguyên lý và phương pháp lập trìnhPhần 1 : Tổng quan các ngôn ngữ lập trình Các ngôn ngữ lập trình thủ tục Các ngôn ngữ lập trình thủ tục Các ngôn ngữ lập trình hướng ñối tượng Các ngôn ngữ lập SuivantPrécédent 9 • Các lệnh (phát biểu) làm thay ñổi các trạng thái của chương trình • Luồng ñiều khiển Các vấn ñề cần nghiên cứu: • Cấu trúc chương trình • Lập trình thủ tục trình hàm Các ngôn ngữ lập trình logic Dữ liệu và khai báo dữ liệu Khai báo hằng Bí danh Kiểu Kiểu liệt kê Mảng Nguyên lý và phương pháp lập trìnhPhần 1 : Tổng quan các ngôn ngữ lập trình Các ngôn ngữ lập trình thủ tục Dữ liệu và khai báo dữ liệu Các ngôn ngữ lập trình hướng ñối tượng Các ngôn ngữ lập SuivantPrécédent 10 Chuỗi Tập hợp và gói Cấu trúc Con trỏ Hợp Thủ tục như là kiểu dữ liệu Ép kiểu và chuyển kiểu trình hàm Các ngôn ngữ lập trình logic • Mọi dữ liệu trên máy tính ñều phải ñược biểu diễn theo một hình thức nào ñó, gắn liền với những thuộc tính xác ñịnh – ñược hiểu là kiểu dữ liệu. • Hầu hết các ñối tượng dữ liệu ñều có tên, trừ một Nguyên lý và phương pháp lập trìnhPhần 1 : Tổng quan các ngôn ngữ lập trình Các ngôn ngữ lập trình thủ tục Dữ liệu Các ngôn ngữ lập trình hướng ñối tượng Các ngôn ngữ lập SuivantPrécédent 11 số ñối tượng dữ liệu vô danh. • Mối liên hệ giữa các ñối tượng dữ liệu, tên, kiểu và sự biểu diễn ñược lập trình viên ñặc tả thông qua sự khai báo dữ liệu. trình hàm Các ngôn ngữ lập trình logic • Mỗi mục dữ liệu bao gồm một số lượng các bit trong bộ nhớ. • Cần có các cấu trúc ñể biết ñược cách diễn giải ý nghĩa các bit của mọi mục dữ liệu một cách chính xác. Nguyên lý và phương pháp lập trìnhPhần 1 : Tổng quan các ngôn ngữ lập trình Các ngôn ngữ lập trình thủ tục Khai báo dữ liệu Các ngôn ngữ lập trình hướng ñối tượng Các ngôn ngữ lập SuivantPrécédent 12 • Thường mỗi mục dữ liệu ñều có một tên ñể tham chiếu ñến nó. • Dữ liệu tồn tại trên máy tính nhưng tên và cấu trúc của dữ liệu thì chỉ tồn tại trong chương trình. • Khai báo dữ liệu nhằm thực hiện hai việc: - Cấp phát bộ nhớ cho mục dữ liệu, - Kết hợp một tên với mục dữ liệu ñó. trình hàm Các ngôn ngữ lập trình logic Nguyên lý và phương pháp lập trìnhPhần 1 : Tổng quan các ngôn ngữ lập trình Các ngôn ngữ lập trình thủ tục Khai báo dữ liệu Các ngôn ngữ lập trình hướng ñối tượng Các ngôn ngữ lập SuivantPrécédent 13 Mối liên hệ giữa tên, cấu trúc và giá trị của dữ liệu trình hàm Các ngôn ngữ lập trình logic • Một số ngôn ngữ cho phép kết hợp khai báo với khởi tạo dữ liệu. Ví dụ: trong ngôn ngữ C int i=5, j=5; (C cho phép trong một phát biểu khai báo nhiều Nguyên lý và phương pháp lập trìnhPhần 1 : Tổng quan các ngôn ngữ lập trình Các ngôn ngữ lập trình thủ tục Khởi tạo dữ liệu Các ngôn ngữ lập trình hướng ñối tượng Các ngôn ngữ lập SuivantPrécédent 14 biến và khởi tạo cho mỗi biến một giá trị khác nhau). trình hàm Các ngôn ngữ lập trình logic • Một số ngôn ngữ có các khai báo hằng. Ví dụ : trong ngôn ngữ C const int i = 10; • Các hằng (biến) không thể bị thay ñổi giá trị. Tuy nhiên, nếu có các lỗi con trỏ trỏ ñến vùng nhớ của Nguyên lý và phương pháp lập trìnhPhần 1 : Tổng quan các ngôn ngữ lập trình Các ngôn ngữ lập trình thủ tục Khai báo hằng Các ngôn ngữ lập trình hướng ñối tượng Các ngôn ngữ lập SuivantPrécédent 15 các hằng (biến) thì giá trị của các hằng (biến) ñó có thể bị thay ñổi ngoài mong muốn. trình hàm Các ngôn ngữ lập trình logic • Các tên khác ñược dùng ñể chỉ ñến cùng một biến. Ví dụ: trong C++, int &k = I; Nguyên lý và phương pháp lập trìnhPhần 1 : Tổng quan các ngôn ngữ lập trình Các ngôn ngữ lập trình thủ tục Bí danh (alias) Các ngôn ngữ lập trình hướng ñối tượng Các ngôn ngữ lập SuivantPrécédent 16 trình hàm Các ngôn ngữ lập trình logic • ðối với dữ liệu trên máy tính: kiểu là cách thức ñể diễn giải các bit dữ liệu. • Trong lập trình: kiểu dữ liệu ñặc tả một tập các giá trị và một tập các thao tác ñược ñịnh nghĩa trên các giá trị ñó. Nguyên lý và phương pháp lập trìnhPhần 1 : Tổng quan các ngôn ngữ lập trình Các ngôn ngữ lập trình thủ tục Kiểu dữ liệu Các ngôn ngữ lập trình hướng ñối tượng Các ngôn ngữ lập SuivantPrécédent 17 • ðịnh nghĩa kiểu: cho phép lập trình viên ñịnh nghĩa kiểu dữ liệu riêng. trình hàm Các ngôn ngữ lập trình logic • Kết hợp các tên với một tập các giá trị của một kiểu. • Phần lớn các ngôn ngữ cài ñặt kiểu liệt kê như là các số nguyên và cho phép thực hiện các phép so sánh (lớn hơn/nhỏ hơn) hay tăng (lấy phần tử kế Nguyên lý và phương pháp lập trìnhPhần 1 : Tổng quan các ngôn ngữ lập trình Các ngôn ngữ lập trình thủ tục Kiểu liệt kê Các ngôn ngữ lập trình hướng ñối tượng Các ngôn ngữ lập SuivantPrécédent 18 tiếp).trình hàm Các ngôn ngữ lập trình logic • Mảng là một dãy với số lượng hữu hạn các mục có cùng kiểu dữ liệu. • Mỗi mục là một phần tử. • Các phần tử ñược truy cập theo một trật tự thông qua chỉ số. Nguyên lý và phương pháp lập trìnhPhần 1 : Tổng quan các ngôn ngữ lập trình Các ngôn ngữ lập trình thủ tục Mảng Các ngôn ngữ lập trình hướng ñối tượng Các ngôn ngữ lập SuivantPrécédent 19 •Associative arrays: kết hợp một giá trị của một kiểu với một phần tử của một mảng. Ví dụ: C và Ada cho phép dùng kiểu liệt kê và ký tự ñể làm chỉ mục cho mảng. Perl cho phép dùng một chuỗi ký tự ñể làm chỉ mục cho một mảng. trình hàm Các ngôn ngữ lập trình logic •Array slicing: truy cập một mảng con thay vì là một phần tử của mảng. Ví dụ: trong Ada các phẩn tử A(3) ñến A(6) của một mảng có thể ñược truy cập A(3..6). Trong Fortran90, A(4:10:2) cho phép truy Nguyên lý và phương pháp lập trìnhPhần 1 : Tổng quan các ngôn ngữ lập trình Các ngôn ngữ lập trình thủ tục Mảng Các ngôn ngữ lập trình hướng ñối tượng Các ngôn ngữ lập SuivantPrécédent 20 cập các phần tử A(4), A(6), A(8) vàA(10).trình hàm Các ngôn ngữ lập trình logic • Một số ngôn ngữ như Pascal cung cấp sẵn kiểu chuỗi ký tự. Một số ngôn ngữ khác như C không cung cấp kiểu này. Nguyên lý và phương pháp lập trìnhPhần 1 : Tổng quan các ngôn ngữ lập trình Các ngôn ngữ lập trình thủ tục Chuỗi ký tự Các ngôn ngữ lập trình hướng ñối tượng Các ngôn ngữ lập SuivantPrécédent 21 trình hàm Các ngôn ngữ lập trình logic • Các thao tác cơ bản trên tập hợp: - Giao, - Hợp, - Hiệu. • C và Ada không cung cấp kiểu tập hợp. • Modula-2 cung cấp kiểu tập hợp. Nguyên lý và phương pháp lập trìnhPhần 1 : Tổng quan các ngôn ngữ lập trình Các ngôn ngữ lập trình thủ tục Tập hợp Các ngôn ngữ lập trình hướng ñối tượng Các ngôn ngữ lập SuivantPrécédent 22 • C++ và Java cung cấp các thư viện cho kiểu tập hợp. trình hàm Các ngôn ngữ lập trình logic • Kiểu gói là một biến thể của tập hợp, trong ñó mỗi giá trị có thể xuất hiện nhiều hơn một lần. • Các thao tác cơ bản trên kiểu gói : - chèn một giá trị, - xóa một giá trị. • Kiểu gói có thể ñược xem là multiset. Nguyên lý và phương pháp lập trìnhPhần 1 : Tổng quan các ngôn ngữ lập trình Các ngôn ngữ lập trình thủ tục Gói (bag) Các ngôn ngữ lập trình hướng ñối tượng Các ngôn ngữ lập SuivantPrécédent 23 • C và Ada không cung cấp kiểu gói. • C++ và Java cung cấp các thư viện cho multiset. trình hàm Các ngôn ngữ lập trình logic • Các cấu trúc cho phép kết hợp một số lượng xác ñịnh các mục dữ liệu có kiểu khác nhau. Ví dụ: record trong Pascal và struct trong C. • Các mục dữ liệu trong một cấu trúc ñược gọi là các trường (fields) hay các thành phần (components). Nguyên lý và phương pháp lập trìnhPhần 1 : Tổng quan các ngôn ngữ lập trình Các ngôn ngữ lập trình thủ tục Cấu trúc Các ngôn ngữ lập trình hướng ñối tượng Các ngôn ngữ lập SuivantPrécédent 24 • Một cấu trúc không thể có trường nào có kiểu là chính nó, trong trường hợp này phải dùng con trỏ trỏ ñến kiểu của chính nó. trình hàm Các ngôn ngữ lập trình logic • Một số ngôn ngữ lập trình cho phép các hàm/thủ tục ñược dùng như một kiểu. • Có thể ñịnh nghĩa một mảng các hàm/thủ tục. • C cho phép sử dụng con trỏ hàm. Ví dụ: trong C int (*convert_to_int) (float); Nguyên lý và phương pháp lập trìnhPhần 1 : Tổng quan các ngôn ngữ lập trình Các ngôn ngữ lập trình thủ tục Kiểu hàm/thủ tục Các ngôn ngữ lập trình hướng ñối tượng Các ngôn ngữ lập SuivantPrécédent 25 Khai báo một biến convert_to_int có kiểu “con trỏ ñến một hàm – hàm này trả về một số kiểu int và có một tham số kiểu float”. i = (*convert_to_int)(3.14); trình hàm Các ngôn ngữ lập trình logic Luồng ñiều khiển: - Sequencing - Selection - Routine Invocation - Repetition - Loops & Exits - Run Time Error Handling Nguyên lý và phương pháp lập trìnhPhần 1 : Tổng quan các ngôn ngữ lập trình Các ngôn ngữ lập trình thủ tục Luồng ñiều khiển Các ngôn ngữ lập trình hướng ñối tượng Các ngôn ngữ lập SuivantPrécédent 26 - Exceptionstrình hàm Các ngôn ngữ lập trình logic • Luồng ñiều khiển: Các ngôn ngữ lập trình thủ tục cho phép ñiều khiển trật tự các phát biểu ñược thực hiện (hoặc bỏ qua). • Các cơ chế : Sequencing (khối lệnh tuần tự, goto) Nguyên lý và phương pháp lập trìnhPhần 1 : Tổng quan các ngôn ngữ lập trình Các ngôn ngữ lập trình thủ tục Luồng ñiều khiển Các ngôn ngữ lập trình hướng ñối tượng Các ngôn ngữ lập SuivantPrécédent 27 Selection (if-then-else hay switch-case, ) Repetition (for-loops, while-loops, repeat- until, ) Routine invocation (gọi hàm và thủ tục) trình hàm Các ngôn ngữ lập trình logic Ba nguyên nhân chính gây ra các lỗi run-time: Lỗi dữ liệu Thiếu tài nguyên hệ thống Các sự cố hay lỗi của hệ thống Nguyên lý và phương pháp lập trìnhPhần 1 : Tổng quan các ngôn ngữ lập trình Các ngôn ngữ lập trình thủ tục Xử lý các lỗi run-time Các ngôn ngữ lập trình hướng ñối tượng Các ngôn ngữ lập SuivantPrécédent 28 trình hàm Các ngôn ngữ lập trình logic • Các ngoại lệ : cung cấp một hay nhiều cơ chế tích hợp ñể xử lý các ñiều kiện lỗi. • Một bộ xử lý lỗi bao gồm một ñiều kiện lỗi và một tập các phát biểu ñể lý lỗi. Nguyên lý và phương pháp lập trìnhPhần 1 : Tổng quan các ngôn ngữ lập trình Các ngôn ngữ lập trình thủ tục Các ngoại lệ Các ngôn ngữ lập trình hướng ñối tượng Các ngôn ngữ lập SuivantPrécédent 29 trình hàm Các ngôn ngữ lập trình logic Nguyên lý và phương pháp lập trìnhPhần 1 : Tổng quan các ngôn ngữ lập trình Các ngôn ngữ lập trình thủ tục Các ngoại lệ Các ngôn ngữ lập trình hướng ñối tượng Các ngôn ngữ lập Statement m has caused the error condition SuivantPrécédent 30 trình hàm Các ngôn ngữ lập trình logic Arrows show the flow of control Các khối lệnh với cơ chế xử lý lỗi