Chương I: Giải thuật

I. Khái niệm: Giải thuật là một hệ thống các thao tác, các phép toán một cách chính xác, sao cho sau một số hữu hạn các bước thực hiện ta đạt được kết quả mong muốn.

* Giải thuật phản ánh các phép sử lí, đối tượng xử lí là dữ liệu.

II. Dữ liệu là các phần tử biểu diễn các thông tin cần thiết cho bài toán.

Có ba loại dữ liệu cho bài toán: DL vào, DL trung gian, DL ra.

-> Giải thuật là việc thực hiện các phép biến đổi DL vào thành DL ra với kết quả mong muốn.

DL nguyên tử là loại DL cơ sở không thể chia nhỏ ra được nữa, DLNT có thể là một chữ số, một kí tự,... Trong bài toán DL bao gồm một tập thể các DLNT.

Trên cơ sở các DLNT, các cách thức liên kết chúng lại tạo thành các cấu trúc DL.

Trước đây CTDL rất đơn giản như xâu kí tự, mảng, bản ghi,... Nay có thêm nhiều kiểu mới phức tạp hơn như: cây, đồ thị ....

Lựa chọn cấu trúc DL thích hợp, trên đó XD một giải thuật hợp lí, hữu hiệu là công việc quan trọng trong lập trình. Chọ CTDL là xét tới tác động của các phép toán tới CTDL ấy và ngược lại, xét tác động của phép toán thì nó tác động nên được những cấu trúc DL nào.

Cấu trúc lưu trữ là cách biểu diễn một cấu trúc DL trong bộ nhớ của máy tính, đó chính là cách cài đặt cấu trúc DL trên máy tính.

Có thể có nhiều cấu trúc lưu trữ cho một cấu trúc DL. VD: Với một CTDL kiểu chuỗi ta có thể lưu trữ theo cấu trúc ô nhớ liền nhau, liên tiếp; cũng có thể lưu trữ bằng các ô nhớ không kế tiếp nhau trong bộ nhớ.

Mỗi ngôn ngữ lập trình đều có các cấu trúc sẵn có ( cấu trúc tiền định ). Chọn ngôn ngữ nào để lập trình là ta đã chấp nhận cấu trúc tiền định đó của nó, ta phải vận dụng linh hoạt nó vào bài toán của ta.

II. Mối quan hệ giữa giải thuật và cấu trúc DL.

+ Xét tới giải thuật thì phải xét giải thuật đó tác động đến cấu trúc DL nào.

+ Xét tới cấu trúc DL thì phải hiểu cấu trúc DL đó cần tác động bằng giải thuật gì để có kết quả mong muốn.

+ Lựa chọn cấu trúc DL hợp lí và một giải thuật xử lí hiệu quả là đã thành công trong việc lập trình.

+ Cấu trúc DL thay đổi thì giải thuật cũng thay đổi theo. Cần lựa chọn cấu trrúc DL thật hợp lí.

III. Thiết kế và phân tích giải thuật.

1. Thiết kế giải thuật.

Mô hình hóa công việc giải quyết bài toán bằng phương pháp mô-dul hóa bài toán: Chúng ta coi cả chương trình cần viết là một mô-dul chính. Sau đó chia chương tình ra theo các mô-dul nhỏ là các yêu cầu của bài toán cần giải quyết. Các mô-dul con này lại được phân chia tiếp cho tới khi mà bài toán có thể được giải quyết đơn giản nhất. Đây là cách mô hình hóa bài toán theo hình cây:

Đây còn được gọi là chiến thuật "chia để trị" hay phương pháp thết kế "TOP-DOWN". Tức là đi từ cái tổng thể rồi chia ra dần dần đi vầo từng chi tiết của bài toán.

2. Tinh chỉnh từng bước.

Đây là phương pháp gắn liền với quá trình lập trình, nó phản ánh tinh thần của quá trình mô-dul hóa bài toán và thiết kế kiểu "TOP-DOWN".

+ Phương pháp tinh chỉnh từng bước thể hiện như sau: Thoạt đầu bài toán được diễn tả bằng ngôn ngữ tự nhiên, phản ánh ý chính của bài toán. Các bước sau sẽ tinh chỉnh dần dần, tương ứng với các công việc nhỏ hơn, ta gọi là các bước tinh chỉnh. Càng ở các bước sau càng mô tả rõ các lệnh lập trình.

+ Quá trình đó diễn tả như sau: NN tự nhiện-> giả NN -> NN lập trình.

Trong quá trình trên dữ liệu cũng được tinh chế dần dần từ dạng cấu trúc sang dạng cài đặt.

3. Phân tích giải thuật

Khi xây dựng giải thuật và chương trình tương ứng cần có các nhu cầu sau:

Phân tích tính đúng đắn:

+ Chạy thử chương trình trên bộ dữ liệu, so snahs kết quả với kết quả đã biết.

+ Dùng các công cụ toán học để chứng minh tính đúng đắn của giải thuật.

+ Tính đơn giản, để dễ hiễu, dễ viết, dễ chỉnh lí.

+ Phân tíhc thời gian: Thời gian để thực hiện giải thuật là tiêu chuẩn đánh giá hiệu lực của giải thuật. Đây là yêu cầu của thực tế. Một bài toán cần được giải nhanh và chíng xác. Thời gian thực hiện hiện giải thuật phụ thuộc vào rất nhiều yếu tố: kích thước dữ liệu, các kiểu lệnh, tốc đọ xử lí của máy tính, ngôn ngữ viết chương trình...

Các yếu tố trên là không giống nhau trên mỗi loại máy tính, do vậy người ta không dùng cách đnahs giá thời gian chạy cho giải thuật. Người ta thường dùng công cụ " Độ phức tạp tính toán của giải thuật." để đánh giá thời gian chạy của chương trình.

Chương II: Đệ quy và giải thuật đệ quy

I. Khái niệm: Ta nói một đối tượng là đệ quy nếu nó được định nghĩa dưới chính nó.

II. Giải thuật đệ quy và thủ tục đệ quy.

Nếu lời giải của bài toán T được thực hiện bằng lời giải của một bài toán T' có dạng giống như bài toán T thì đó là một lời giải đệ quy.

Giải thuật tương ứng với lời giải đệ quy thì được gọi là giải thuật đệ quy.

Thủ tục viết cho bài toán đệ quy được gọi là thủ tục đệ quy.

Trong thủ tục đệ quy có lời gọi tới chính nó thì bài toán ngày càng thu nhỏ và dần dần tiến tới trường hợp suy biến.

Chương III: Các kiểu dữ liệu

I. Khái niệm các kiểu DL:

Kiểu DL xác định tập hợp mà các giá trị mà hằng, biến, biểu thức, hàm có thể có.

Kiểu của một đại lượng được chỉ ra trong khi khai báo hoặc được suy ra từu dạng của nó.

Mỗi toán tử, hàm thuộc kiểu định sẵn thì tạo kết quả từ kiểu đình sẵn.Nếu mỗi toán tử có đối thuộc một vài kiểu khác nhau thì kiểu của kết quả theo quy tắc riêng của ngôn ngữ lập trình đang viết.

II. Các loại kiểu DL.

1. Kiểu DL cơ bản.

Kiểu dữ liệu cơ bản là kiểu dữ liệu được khai báo từ những kiểu DL đã được định sẵn.

a. Kiểu nguyên ( Integer).

Bao gồm các giá trị là sô nguyên và các phép tính thực hiện với kiểu số nguyên là: +, -, *, /, MOD , DIV.

b. Kiểu số thực ( Real ).

Kiểu thực bao gồm các số thực.Các phép tính : +, -, *, /

c. Kiểu logic ( Boolean ).

Là kiểu chỉ nhận giá trị True hoặc False. Các phép tính: NOT, AND, OR, NOTOR.

d. Kiểu kí tự ( Char ).

Là kiểu chỉ nhận các giá trị là một kí tự trong bẳng mã ASCII.

e. Kiểu liệt kê.

Là kiểu giá trị nhận các giá trị trong danh sách liệt kê. Khai báo bằng một tập các giá trị có thứ tự.

f. Kiểu miền con ( đoạn con).

Kiểu đoạn con nhận giá trị vô hướng đếm được. Kiểu đoạn con được khai báo bằng cách chỉ ra khoảng cách: Min..Max.

2. Dữ liệu có cấu trúc.

Mảng và danh sách:

KN: + Mảng là một tập hợp có thứ tự gồm một số cố định các phần tử cùng kiểu.

Một phần tử mảng được chỉ ra bởi chỉ số, chỉ số này thể hiện thứ tự phần tử trong mảng. Vectơ là mảng có một chiều với chỉ số (i).Ma trận là mảng hahi chiều với chỉ số (I,j).Không gian n chiều là mảng có chỉ số (x,y,z,...n).Có các phép tạo mảng, tìm kiếm phần tử của mảng,lưu trữ phần tử của mảng.

+ Danh sách là một tập hợp có thứ tự gồm một số biến động các phần tử cùng kiểu.Phép loại bỏ, bổ xung một phần tử là phép thường xuyên tác động lên danh sách.

Danh sách tuyến tính là một danh sách mà mối quan hệ lân cận giữa các phần tử được hiển thị ra thì được gọi là danh sách tuyến tính. Vectơ là một hình ảnh của một danh sách tuyến tính tại một thời điểm nào đó, như vậy danh sách tuyến tính hoặc là rỗng hoặc là có dạng (a1,a2,a3,a4...,an).

Các phép toán trên danh sách: + Phép bổ xung: Có thể bổ xung phần tử vào cuối danh sách.

+ Phép loại bỏ: Có thể loại bỏ một phẩn tử ra khỏi danh sách.

+ Phép ghép: Có thể ghép 2 hay nhiều danh sách vào một danh sách.

+ Phép cập nhật: Cập nhật các giá trị cho các phần tử của danh sách.

+ Phép sao chép: Có thể sao chép một danh sách.

+ Phép sắp xếp: Có thể sắp xếp các phần tử của danh sách theo một trật tự nhất định.

+ Phép tìm kiếm: Tìm kiếm một phần tử trong danh sách mà có một trường ấn định.

3. Cấu trúc lưu trữ của mảng.

+ Cách biểu diễn một cấu trúc dữ liệu trên bộ nhớ của máy tính gọi là cấu trúc lưu trữ.

+ Cấu trúc lưu trữ đơn giản nhất là dùng địa chỉ tính được để lưu trữ và tìm kiếm phần tử và được gọi là lưu trữ kế tiếp.Lưu trữ kế tiếp được thể hiện như sau: Một số từ máy kế tiếp nhau sẽ được dành ra để lưu trữ các phần tử của mảng. Với mảng một chiều.

+ Cấu trúc ngăn xếp (stack ) là một kiểu danh sách tuyến tính đặc biệt mà cho phép bổ xung và phép loại bỏ luôn luôn thực hiện ở một đỉnh.

+ Cấu trúc hàng đợi ( Queue) là kiểu danh sách tuyến tính mà phép bổ xung được thực hiện trên một đầu, đây là lối sau và phép loại bỏ được thực hiện trên một đầu, lối đỉnh.

Danh sách móc nối.

Danh sách nối đơn: Mỗi phần tử trong danh sách được lưu trữ trong một phần tử nhớ mà ta gọi là nút, mỗi nút bao gồm nhiều từ nhớ liên tiếp của máy tính, các nút này có thể nằm cạnh nhau hoặc riêng biệt. Trong nút có các từ nhớ dùng để ghi dữ liệu, các từ nhớ còn lại dùng để chỉ đến các nút đứng sau nó trong danh sách.

Trường thông tin chứa thông tin cần lưu trữ.

Trường Link chứa địa chỉ của nút kế tiếp.

Riêng nút cuối cùng phần Link không trỏ tới đâu nên là Null.

Để truy cập vào danh sách tâ cần có con trỏ của nút đầu tiên.Do đó cần phải có con trỏ L trỏ tới nút đầu tiên.Nếu danh sách rỗng thì L= Null.

CÂY

Cây là một tập hợp hữu hạn các nút, trong đó các nút có một quan hệ đặc biệt gọi là gốc. Giữa các nút có quan hệ phân cấp gọi là quan hệ cha con.Một cây không có nút nào gọi là rỗng.

Các khái niệm: + Gốc là nút đặc biệt không có nút cha.

+ Cấp: Số con của một nút được gọi là cấp của nút đó.

+ Lá: Nút không có con là nút lá, tức la nút có cấp là không.

+ Nút nhánh: Là nút có cấp thấp nhất là một. Tức là có ít nhất một con ( chứa ít nhất một lá ).

+ Mức: Gốc cây có mức là một, nếu nút cha có mức là I thì nút con có mức là i+1.

+ Chiều cao của cây: Là số mức lớn nhất của cây có thể đạt được.

+ Đường đi: Nếu từ n1 cho tới nk mà có i là cha và i+1 là con ( 1 <= I <= n) thì đoạn từ n¬1->nk được gọi là đường dẫn.

Cây nhị phân: Là dạng đặc biệt của cấu trúc cây, trong đó mỗi nút chỉ có tối đa là hai nút con hoặc hai nút lá. Đối với các nút con của một nút người ta phân biệt là nút trái và nút phải ( nhánh trái và nhánh phải ).Như vậy cây nhị phân là cây có cấu trúc, có thứ tự.

Cây nhị phân hoàn chỉnh là cây nhị phân có các mức (trừ các mức cuối hay các nút lá ) đều đạt tối đa là hai con.

Cây nhị phân đầy đủ là cây nhị phân đều đạt mức tối đa mọi mức.