Các loại thuật toán trong Python

Thiết kế và phân tích các thuật toán là một chủ đề cơ bản trong khoa học máy tính và giáo dục kỹ thuật. Nhiều khóa học thuật toán bao gồm các bài tập lập trình để giúp sinh viên hiểu rõ hơn về các thuật toán. Thật không may, việc sử dụng các ngôn ngữ lập trình truyền thống buộc sinh viên phải xử lý các chi tiết về cấu trúc dữ liệu và các thủ tục hỗ trợ, thay vì thiết kế thuật toán. Python đại diện cho một ngôn ngữ định hướng thuật toán cực kỳ cần thiết trong giáo dục. Ưu điểm của Python bao gồm cú pháp giống sách giáo khoa và tính tương tác khuyến khích thử nghiệm. Quan trọng hơn, chúng tôi báo cáo việc sử dụng Python mới của mình để biểu diễn các cấu trúc dữ liệu tổng hợp như biểu đồ và mạng luồng ở dạng văn bản ngắn gọn, điều này không chỉ khuyến khích sinh viên thử nghiệm các thuật toán mà còn cắt giảm đáng kể thời gian phát triển. Các tính năng này đã được triển khai trong một khóa học thuật toán cấp độ sau đại học với kết quả thành công

1. Giới thiệu

Thuật toán là hộp công cụ quan trọng nhất cho bất kỳ ai phải giải quyết vấn đề bằng cách viết chương trình máy tính. Các thuật toán không chỉ được sử dụng bởi các nhà khoa học máy tính và kỹ sư máy tính mà còn bởi nhiều người trong các ngành khoa học và kỹ thuật khác. Kết quả là, các khóa học về thuật toán được yêu cầu không chỉ bởi các chuyên ngành máy tính mà còn bởi các sinh viên từ các chuyên ngành khác.

Mặc dù có thể nghiên cứu các thuật toán chỉ bằng cách đọc sách giáo khoa và thực hiện các bài toán, nhưng học sinh thường không thực sự học các thuật toán cho đến khi họ thực sự thử triển khai chúng. Do đó, không có gì lạ khi các khóa học thuật toán bao gồm các bài tập lập trình. Các sách giáo khoa bao gồm lập trình như một phần không thể thiếu trong giáo dục thuật toán cũng đã được biên soạn để đáp ứng nhu cầu này []. Hầu như tất cả các khóa học và sách giáo khoa cho đến nay đều yêu cầu sinh viên lập trình bằng ngôn ngữ truyền thống như C hoặc C++, và gần đây Java đã trở nên phổ biến []. Đối số cho việc sử dụng các ngôn ngữ này chủ yếu là một đối số thực tế. học sinh có thể đã thành thạo các ngôn ngữ này;

1. 1 Lập trình vs. thiết kế thuật toán

Thật không may, kinh nghiệm đã chỉ ra rằng các bài tập lập trình trong các lớp thuật toán có thể không phải lúc nào cũng có lợi về mặt sư phạm. Mặc dù hầu hết các thuật toán dài từ vài dòng đến nửa trang trong sách giáo khoa, nhưng việc triển khai chúng thường yêu cầu hàng trăm dòng trong C hoặc Java. Một lý do là các ngôn ngữ này yêu cầu khai báo biến toàn cục, biến cục bộ và tham số trước khi chúng có thể được sử dụng. Một lý do khác, quan trọng hơn, là nhiều cấu trúc dữ liệu như danh sách, cấu trúc dữ liệu được liên kết và mảng chuyên biệt phải được thiết kế và triển khai để hỗ trợ thuật toán và độ phức tạp của các bài tập này tăng lên nhanh chóng khi tổng hợp các cấu trúc dữ liệu như biểu đồ hoặc mạng luồng. . Trên thực tế, hầu hết các lập trình viên hướng đối tượng dành phần lớn nỗ lực của họ trong việc thiết kế các lớp và giao diện, và dành tương đối ít thời gian để điền mã cho các phương thức. Do đó, các bài tập lập trình này sẽ buộc sinh viên dành nhiều thời gian để thực hành các vấn đề về lập trình hơn là các vấn đề về thuật toán. Những sinh viên không phải chuyên ngành máy tính có xu hướng gặp bất lợi nghiêm trọng

Một số người hướng dẫn đã cố gắng giảm bớt gánh nặng này bằng cách cho sinh viên thói quen thư viện cho các cấu trúc dữ liệu. Tuy nhiên, vẫn còn nhiều vấn đề cố hữu đối với các ngôn ngữ truyền thống này, bao gồm cả đầu vào/đầu ra và sử dụng lại. Ví dụ: thư viện có thể cung cấp API để xây dựng cây hoặc biểu đồ trước khi gọi thuật toán với cấu trúc dữ liệu. Học sinh phải cài đặt sẵn trường hợp thử nghiệm của mình, thực hiện các lệnh gọi liên tiếp để thêm từng nút vào biểu đồ hoặc đọc mô tả về biểu đồ từ một tệp. Cách tiếp cận trước đây có thể khó xử vì mã nguồn không giống với cấu trúc dữ liệu, nhưng ý nghĩa được gắn với API. Cách tiếp cận thứ hai, sử dụng ngôn ngữ tùy chỉnh để biểu diễn biểu đồ, có thể ngắn gọn hơn, nhưng nó yêu cầu các quy trình phân tích cú pháp, điều này có thể làm giảm khả năng sử dụng lại và khả năng mở rộng. Ví dụ, hãy xem xét trường hợp ban đầu chúng tôi xác định một biểu đồ không có trọng số nhưng sau đó muốn có một biểu đồ có trọng số. Có thể dễ dàng tạo một lớp con cho phần mở rộng có trọng số, nhưng chúng ta cũng cần thay đổi trình phân tích cú pháp để xử lý trường hợp có trọng số hoặc không có trọng số. Nhưng giả sử chúng ta muốn mở rộng lại các trọng số thành một bộ, một chuỗi hoặc một tập hợp tùy ý. trình phân tích cú pháp phải được thay đổi mỗi lần

1. 2 Cạnh Python

Python giải quyết những vấn đề này và tạo ra một ngôn ngữ hấp dẫn cho giáo dục thuật toán. Đầu tiên, cú pháp dựa trên dấu đầu dòng của nó giống với hầu hết các sách giáo khoa đến mức ngay cả những sinh viên không có nhiều nền tảng về lập trình cũng không gặp khó khăn gì khi mã hóa các thuật toán chỉ bằng cách làm theo cuốn sách. Do đó, tranh luận về mức độ phổ biến với các ngôn ngữ khác là không cần thiết, đặc biệt là khi chế độ tương tác của nó khuyến khích sinh viên thử nghiệm với nó mà không cần chu trình biên dịch dài. Thứ hai, Python cung cấp các cấu trúc dữ liệu cơ bản như danh sách, bộ dữ liệu và từ điển có thể được sử dụng trực tiếp bởi các thuật toán. Ngay cả những cấu trúc dữ liệu phức tạp hơn như cây và đồ thị cũng có thể được thể hiện bằng Python ở dạng ngắn gọn, con người có thể đọc được mà không cần phải phát minh lại các cấu trúc dữ liệu đó. Ví dụ: Phần sẽ hiển thị một cách mới để biểu diễn đồ thị có trọng số dưới dạng từ điển các đỉnh có danh sách kề được biểu thị bằng từ điển trọng số cạnh. Có một số lợi thế. các trường hợp thử nghiệm cho các thuật toán có thể được viết trực tiếp bằng Python mà không cần phải gọi bất kỳ API xây dựng cấu trúc dữ liệu nào và không phải dựa vào bất kỳ trình phân tích cú pháp tùy chỉnh nào. Hơn nữa, nó có khả năng mở rộng vô hạn đối với các kiểu dữ liệu tùy ý, vì Python chỉ đơn giản chuyển chúng theo và không diễn giải kiểu dữ liệu cho đến khi cần. Bất cứ lúc nào, cấu trúc dữ liệu cũng có thể được hiển thị ở dạng văn bản mà con người và Python có thể đọc được

Phần còn lại của bài báo này báo cáo kinh nghiệm thành công của chúng tôi khi triển khai Python trong lớp thuật toán cấp độ sau đại học. Sinh viên của chúng tôi không chỉ tiếp thu mà còn có được một công cụ có giá trị để giúp họ giải quyết các vấn đề trong lĩnh vực nghiên cứu của mình. Các phần sau đây minh họa cách chúng tôi dạy các thuật toán trong Python, theo trình tự tương tự như được trình bày trên lớp. Chúng tôi bắt đầu với thuật toán sắp xếp và heapsort với hàng đợi ưu tiên để làm nổi bật các vấn đề về quản lý bộ nhớ. Sau đó, chúng tôi sử dụng chúng để xây dựng cây nhị phân và triển khai thuật toán nén Huffman. Cuối cùng, chúng tôi chỉ ra cách Python có thể được sử dụng hiệu quả cho các thuật toán đồ thị

2. bài học giới thiệu. Sắp xếp

Hầu hết các sách giáo khoa bắt đầu với sắp xếp như một cách để giới thiệu các thuật toán và phân tích độ phức tạp. Chúng tôi sử dụng các thuật toán sắp xếp để giới thiệu Python ngay từ bài học đầu tiên. Chiến lược của chúng tôi là hiển thị thuật toán song song với mã Python để thể hiện sự giống nhau của chúng. Chúng ta bắt đầu với InsertionSort, nó tăng từng phần tử của mảng đã sắp xếp từ đầu mảng. Ban đầu, A[1] (trong văn bản; A[0] trong Python) là phần tử duy nhất trong mảng con này và được sắp xếp tầm thường. Mỗi lần lặp của vòng lặp for sẽ chèn phần tử mới tiếp theo vào mảng con đã sắp xếp sao cho các phần tử được sắp xếp tương đối với nhau;

Thuật toán từ sách giáo khoa []

Chèn-Sắp xếp(A)
1 cho j <- 2 đến độ dài[A]
2      phím do <- A[j]
3            i <- j - 1
4          trong khi i > 0 và phím A[i] >
5                   làm A[i+1] <- A[i]
6                     i <- i - 1
7           A[i + 1] <- phím

Mã Python

def InsertionSort(A)
cho j trong khoảng(1, len(A))
phím = A[j]
tôi = j - 1
while (i >=0) and (A[i] > key)
A[i+1] = A[i]
tôi = tôi - 1
A[i+1] = phím

Một khi sinh viên nhìn thấy sự giống nhau, hầu hết nỗi sợ lập trình của họ sẽ biến mất. Nó cũng giúp chứng minh bản chất tương tác của Python. Chúng tôi sử dụng máy chiếu và thực sự nhập chương trình, chỉ dài 8 dòng. Phần tốt nhất là, chúng ta có thể kiểm tra thuật toán bằng cách chỉ cần nhập trường hợp thử nghiệm ở dạng danh sách

>>> x = [2,7,3,8,1]   # tạo trường hợp thử nghiệm
>>> InsertionSort(x)   # lệnh gọi
>>> x        # xem kết quả
[1, 2, 3, 7, 8]

Theo một nghĩa nào đó, Python mang lại sự phù hợp cho sách giáo khoa vì các thuật toán được trình bày trong sách không còn chỉ là mã giả hoặc các bước quan tâm lý thuyết mà thôi; . Trên thực tế, chúng tôi cũng chỉ ra rằng cùng một mã, không thay đổi, chỉ hoạt động tốt với các loại dữ liệu khác, bao gồm chuỗi, bộ dữ liệu, v.v. Sắp xếp là một ví dụ khởi đầu tốt bởi vì không chỉ cấu trúc ánh xạ trực tiếp mà không có sự phức tạp với quản lý bộ nhớ (sẽ được thảo luận sau), mà ngữ nghĩa tham số cũng phù hợp. vô hướng được truyền theo giá trị, trong khi mảng được truyền theo tham chiếu

3. Sắp xếp đống và hàng đợi ưu tiên

Phần giới thiệu của chúng tôi tiếp tục với sắp xếp theo đống và hàng đợi ưu tiên. Heap là một cấu trúc dữ liệu đại diện cho một cây nhị phân gần như cân bằng sử dụng một mảng A[1. n], trong đó các phần tử con bên trái và bên phải của phần tử A[i] lần lượt nằm ở A[2i], A[2i+1] và A[i] >= A[2i], A[2i+1 . HeapSort xây dựng mảng con được sắp xếp từ phía sau của mảng về phía trước từng phần tử một bằng cách trích xuất phần tử lớn nhất từ ​​phía trước của heap. Ban đầu, phần được sắp xếp trống và lệnh gọi BuildHeap biến A[1. n] thành một đống. Vì phần heap đặt phần tử lớn nhất tại A[1] nên trong lần lặp đầu tiên, chúng tôi trích xuất nó và đặt nó vào A[n], đây là vị trí được sắp xếp chính xác của nó. Lần lặp tiếp theo trích xuất phần tử lớn thứ hai (từ A[1] một lần nữa) và đặt nó vào A[n-1], v.v., và nó tiếp tục cho đến khi tất cả A được sắp xếp. Lưu ý rằng Heapify được gọi là một phần của mỗi bước trích xuất. Điều này là do nếu chúng ta hoán đổi A[1] và A[h], thì A[1. h-1] không còn thỏa mãn thuộc tính heap, nhưng vì nó vẫn "gần như" là một đống -- nghĩa là, tất cả ngoại trừ vị trí gốc vẫn là các nhóm con -- nó có thể được sửa một cách hiệu quả trong thời gian O(lg h) bằng cách gọi

Một điểm khác biệt là thuật toán trong sách giáo khoa giả định các chỉ số mảng dựa trên 1, trong khi Python giả định các mảng dựa trên 0. Để tránh lỗi do điều chỉnh chỉ mục, chúng tôi yêu cầu sinh viên chỉ cần điền A[0] của họ bằng Không và thay vào đó sử dụng một mảng có kích thước n+1. Mã Python là

def Parent(i). trả lại tôi/2
def Left(i). trả lại 2 * tôi
def Right(i). trả về 2*i+1

def Heapify(A, i, n). # A là "gần như một đống" (ngoại trừ gốc);
l = Trái(i)
r = Đúng(i)
    if l <= n and A[l] > A[i]: largest = l
khác. lớn nhất = tôi
    if r <= n and A[r] > A[largest]:
lớn nhất = r
nếu lớn nhất. = tôi
A[i], A[lớn nhất] = A[lớn nhất], A[i]
Heapify(A, lớn nhất, n)

def HeapLength(A). quay lại len(A)-1
def BuildHeap(A). # tạo một đống A từ một mảng chưa sắp xếp
n = HeapLength(A)
cho tôi trong phạm vi (n/2,0,-1)
Heapify(A,i,n)

def HeapSort(A). # sử dụng một đống để tạo mảng được sắp xếp từ cuối
BuildHeap(A)
HeapSize=HeapLength(A)
cho tôi trong phạm vi (HeapSize,1,-1)
A[1],A[i]=A[i],A[1] # phần tử lớn nhất là gốc của heap, đặt nó ở cuối mảng
HeapSize=HeapSize-1 # thu nhỏ kích thước heap xuống 1 để lấy phần tử lớn nhất tiếp theo
Heapify(A,1,HeapSize)

Heaps và hàng đợi ưu tiên có liên quan chặt chẽ với nhau, vì heaps có thể triển khai hàng đợi ưu tiên một cách hiệu quả với việc chèn và trích xuất thời gian O(lg n). Tuy nhiên, một điểm khác biệt là quản lý bộ nhớ động. trong sắp xếp heap, kích thước của mảng vẫn giữ nguyên, trong khi trong hàng đợi ưu tiên, kích thước của hàng đợi tăng lên và thu hẹp lại. Chúng tôi sử dụng cơ hội này để giới thiệu hai cấu trúc. Đầu tiên, chúng tôi chỉ ra rằng A. nối thêm () và A. pop() có thể được sử dụng để tăng và thu nhỏ danh sách A, trong khi len(A) trả về độ dài hiện tại của danh sách. Thứ hai, trong trường hợp tràn (và tràn nếu muốn), chúng tôi chỉ cho học sinh cách nâng cao và bắt một ngoại lệ. Các cấu trúc này có thể không phải là duy nhất đối với Python, nhưng Python giúp bạn dễ dàng thử nghiệm

4. Cây nhị phân và mã hóa Huffman

Khi chúng tôi có hàng đợi ưu tiên, chúng tôi cho phép sinh viên nhanh chóng triển khai các thuật toán thú vị, bao gồm các đường đi ngắn nhất nguồn đơn của Dijkstra và cây bao trùm tối thiểu của Prim. Chủ đề tiếp theo của chúng tôi là thuật toán tham lam và chúng tôi yêu cầu sinh viên triển khai mã hóa Huffman bằng Python. Để nhớ lại, thuật toán Huffman tạo ra các từ mã có độ dài thay đổi, không có tiền tố dựa trên tần suất của mỗi ký tự. Một chữ cái được sử dụng thường xuyên sẽ được mã hóa bằng chuỗi bit ngắn hơn, trong khi một chữ cái ít được sử dụng hơn sẽ được mã hóa bằng chuỗi bit dài hơn. Thuật toán tham lam sử dụng hàng đợi ưu tiên để trích xuất hai nút (lá hoặc bên trong) có tần số thấp nhất, phân bổ một nút mới có trọng số bằng tổng của hai nút và chèn nút mới trở lại hàng đợi ưu tiên. Thuật toán kết thúc khi hàng đợi ưu tiên loại bỏ nút cuối cùng, nút này trở thành gốc của cây Huffman. Chuỗi bit cho mỗi chữ cái có thể được tạo ra bằng cách duyệt cây nhị phân Huffman, trong đó nhánh bên trái dẫn đến `0' và nhánh bên phải dẫn đến `1'

Ví dụ: giả sử bộ ký tự đầu vào của chúng tôi có tần số liên quan là

• 'Một'. 45%
• 'b'. 13%
• 'c'. 12%
• 'd'. 16%
• 'e'. 9%
• 'f'. 5%

Thuật toán Huffman xây dựng một cây bằng cách liên tục loại bỏ hai phần tử có tần số nhỏ nhất, tạo một nút bên trong mới có tần số bằng tổng của chúng và đưa nó vào hàng đợi ưu tiên. Kết quả là một cây () xác định mã có độ dài thay đổi cho mỗi ký tự. Các nhánh bên trái được gắn nhãn 0 và các nhánh bên phải được gắn nhãn 1 và mã Huffman cho một ký tự chỉ đơn giản là chuỗi các nhãn đường dẫn từ gốc đến lá. Ví dụ, các mã hóa là

• 'Một'. 0
• 'b'. 1 0 0
• 'c'. 1 0 1
• 'd'. 1 1 0
• 'e'. 1 1 1 0
• 'f'. 1 1 1 1

Vì chúng tôi đã có hàng đợi ưu tiên, thứ chúng tôi thiếu là một cây nhị phân chuyên dụng. Các yêu cầu là

• Một nút lá phải có khả năng đại diện cho chữ cái được mã hóa và tần số của nó
• Một nút bên trong phải có hai nút con và nó cũng phải có trọng số bằng tổng các nút con của nó
• Hàng đợi ưu tiên phải có khả năng liệt kê và loại bỏ cả nút lá và nút bên trong và so sánh chúng dựa trên trọng số

Nếu chúng ta thực hiện điều này với một ngôn ngữ truyền thống như C hoặc Java, chúng ta sẽ phải dạy học sinh cách định nghĩa một cấu trúc hoặc một lớp với một trường có tên là trọng số; . Vì hàng đợi ưu tiên phải có khả năng so sánh chúng, nên cần phải sửa đổi hàng đợi ưu tiên để gọi phương thức so sánh phù hợp thay vì sử dụng các toán tử so sánh tích hợp và cả nút lá và nút bên trong phải cùng lớp . Sau khi được xác định, học sinh sẽ muốn kiểm tra xem họ đã xây dựng cây Huffman đúng chưa. Tuy nhiên, không có trình gỡ lỗi hiện tại nào có kiến ​​thức để có thể tự động in các nút lại với nhau dưới dạng cây và do đó, học sinh có gánh nặng phải viết quy trình in, điều này thực sự có thể khá phức tạp và là một nguồn lỗi chính khác. Tương tự, để sinh viên chỉ định các trường hợp kiểm tra khác nhau, họ sẽ phải sửa đổi dữ liệu được kết nối cứng và biên dịch lại mỗi lần, hoặc họ sẽ cần phải viết các quy trình phân tích cú pháp bổ sung, đây sẽ là một nguồn lỗi khác

Việc triển khai Python có thể được thực hiện một cách tinh tế mà không cần phải viết thêm các thủ tục hoặc xác định một lớp mới hoặc cấu trúc cho các nút cây. Chúng tôi yêu cầu học sinh biểu diễn cây nhị phân bằng cách sử dụng các bộ dữ liệu trong Python, theo tinh thần tương tự như Lisp

• Các nút lá được biểu diễn dưới dạng các bộ dữ liệu (tần số, ký tự)
  [(45, 'a'), (13, 'b'), (12, 'c'), (16, 'd'), (9, 'e'), (5, 'f')]
• Các nút bên trong được biểu diễn dưới dạng 3 bộ theo thứ tự. (tần số, trái, phải). Ví dụ, cây con phía dưới bên phải trong có thể được biểu diễn dưới dạng
  (14, (5, 'f'), (9, 'e'))
  đại diện cho một nút bên trong có trọng số là 14%, nút con bên trái là (5, 'f') và nút con bên phải là (9, 'e')

Cây được xây dựng theo chức năng với việc tạo bộ, mà không phải sử dụng bất kỳ cấu trúc dữ liệu nút cây nào và không cần phải thao tác con trỏ con trái/phải. Hơn nữa, nó có thể dễ dàng sử dụng với cấu trúc dữ liệu hàng đợi ưu tiên hiện có mà không cần sửa đổi. Điều này là do các bộ dữ liệu có thể được so sánh theo thứ tự từ điển bằng cách sử dụng cùng các toán tử so sánh. Bằng cách này, các nút và lá bên trong có thể được so sánh, mặc dù chúng mã hóa thông tin khác nhau. Sự khác biệt giữa chúng là len() = 2 cho lá và = 3 cho nút bên trong

Tóm lại, với cách sử dụng Python hơi sáng tạo, chúng tôi đạt được khả năng tái sử dụng tối đa các thuật toán và cấu trúc dữ liệu. Nó cũng cho phép sinh viên mô tả bằng văn bản một cây theo cú pháp Python ngắn gọn và có thể mở rộng nhất có thể mà không cần phải sử dụng trình phân tích cú pháp chuyên dụng

5. thuật toán đồ thị

Một đồ thị là G(V,E), trong đó V là một tập hợp các đỉnh và E, là một tập hợp con của tích chéo của V chéo với V, là một tập hợp các cạnh. Một biểu đồ có nhiều cách biểu diễn và hầu hết các thuật toán giả sử một danh sách kề hoặc một biểu diễn ma trận kề. Cái trước là tốt cho các biểu đồ thưa thớt trong đó. E. gần gũi hơn nhiều. V. , trong khi cái sau tốt cho các đồ thị dày đặc có. E. gần hơn với. V. 2

Để triển khai biểu đồ trong ngôn ngữ lập trình hệ thống truyền thống như C hoặc Java, trước tiên người ta phải xác định cấu trúc dữ liệu cho các đỉnh, cho các cạnh và cho biểu đồ, đóng vai trò là giao diện người dùng để tạo và xóa biểu đồ. . Thiết kế của các cấu trúc dữ liệu như vậy có thể dễ dàng chi phối thời gian viết mã và không dễ sử dụng lại, chủ yếu là do các loại dữ liệu này phải được thiết kế dưới dạng các thùng chứa. Mặc dù các gói như LEDA [] cố gắng tăng cường tái sử dụng mã nguồn hướng đối tượng với các mẫu C++, chúng vẫn yêu cầu sinh viên sử dụng toàn bộ gói trước khi họ có thể bắt đầu làm bất cứ điều gì hữu ích. Các vùng chứa thường được thiết kế để tránh các vấn đề với kiểu gõ tĩnh, mạnh, nhưng làm như vậy yêu cầu triển khai lại kiểm tra kiểu động trong mã người dùng cuối. Một nhược điểm thậm chí còn tồi tệ hơn là việc sử dụng các con trỏ C hoặc các tham chiếu Java khiến việc xem các đối tượng này trở nên khó khăn. Mặc dù trình gỡ lỗi có thể hiển thị các đối tượng này ở dạng văn bản nào đó, nhưng nó sẽ hiển thị quá nhiều thông tin hoặc không thể sử dụng trực tiếp trong chương trình

Python cung cấp nhiều lợi thế như được làm nổi bật bởi cấu trúc dữ liệu đồ thị. Chúng tôi sử dụng triển khai từ điển của từ điển (DD) rất nhỏ gọn để biểu diễn danh sách kề của biểu đồ. Về cơ bản, một biểu đồ được biểu diễn dưới dạng một từ điển Python, có khóa là tên chuỗi của các đỉnh và mỗi tên đỉnh được ánh xạ tới danh sách kề của nó. Ví dụ, hãy xem xét biểu đồ hiển thị trong

Nó có thể được biểu diễn bằng mã Python sau

H = {'A'. ['C', 'D'], 'B'. ['D', 'A'], 'C'. ['D', 'E'],
'D'. ['E'], 'E'. [] }

Ở trên đại diện cho một đồ thị đơn giản, có hướng, không trọng số. Nếu cần có một đồ thị có trọng số, chẳng hạn như, thì chúng ta chỉ cần thay thế danh sách các đỉnh kề nhau bằng các từ điển ánh xạ các đỉnh liền kề với trọng số của chúng

L = {'A'. {'C'. 2, 'D'. 6}, 'B'. {'D'. 8, 'A'. 3},
'C'. {'D'. 7, 'Ê'. 5}, 'D'. {'E'. -2}, 'Ê'. {}}

Danh sách các đỉnh V đơn giản là H. phím () hoặc L. phím(). Danh sách kề là H[v] đối với đồ thị không trọng số, và L[v]. keys() cho đồ thị có trọng số. Trọng lượng cạnh w(u,v) là L[u][v]. Để thuận tiện cho việc lập trình, chúng ta có thể bọc các chi tiết triển khai bên trong một đối tượng

lớp đồ thị
def __init__(bản thân, g)
bản thân. g = g
def V (tự)
trả lại g. phím()
def Adj(tự, v)
tự trở về. g[v]. phím()
def w(tự,u,v)
tự trở về. g[u][v]

Chúng ta có thể tạo một đối tượng đồ thị với G = Graph(L). Ưu điểm của phương pháp này bao gồm định dạng văn bản nhỏ gọn và khả năng mở rộng. Đầu tiên, thực sự không có cấu trúc dữ liệu để thiết kế. Biểu diễn văn bản của biểu đồ là Python có thể thực thi được. Học sinh có thể nhập cấu trúc này một cách tương tác hoặc trong một tệp văn bản mà không cần sử dụng bất kỳ trình chỉnh sửa biểu đồ đặc biệt nào. Cấu trúc dữ liệu có thể được kiểm tra chỉ bằng cách gõ tên của nó. Sau đó, nó có thể được cắt/dán sang một cửa sổ trình thông dịch Python khác hoặc sang một chương trình Python khác mà không cần bất kỳ sửa đổi cú pháp nào

Quan trọng hơn, đại diện này là cực kỳ mở rộng. Các thuật toán khác nhau sử dụng các thuộc tính bổ sung, nhưng chúng có thể được thêm vào khi cần thiết. Ví dụ: thuật toán đường dẫn ngắn nhất nguồn đơn hoặc duyệt theo chiều rộng/chiều sâu trước yêu cầu các thuộc tính bổ sung như con trỏ tiền nhiệm. Trong Python, thuật toán có thể chỉ cần thêm thuộc tính tiền thân vào đối tượng đồ thị (như G. pred[v]), mà không cần phải xác định một lớp con cho mỗi thuật toán. Các thuộc tính mới được thêm này cũng có thể được kiểm tra và sửa đổi trực tiếp mà không yêu cầu các quy trình mới

6. Đánh giá sinh viên

Khi viết bài này, chúng tôi đã cung cấp lớp thuật toán hai lần với Python. Nhìn chung, kết quả rất khả quan, mặc dù vẫn còn chỗ cần cải thiện. Phần này thảo luận về cả hai khía cạnh với giai thoại

Về khía cạnh thành công của câu chuyện, hầu hết học sinh đều tỏ ra dễ tiếp thu Python và hầu hết trong số 35-40 học sinh của mỗi lớp đều có thể hoàn thành xuất sắc các bài tập lập trình mà không gặp nhiều khó khăn. Ít nhất một sinh viên đã trở thành người hâm mộ Python và chuyển từ C++ sang Python cho công việc nghiên cứu của riêng mình sau khóa học này. Hiện tại, anh ấy không chỉ sử dụng Jython và TkInter để tạo tập lệnh cho các tiện ích giao diện người dùng mà còn sử dụng Python để lập trình ổ cắm, đa luồng và viết tập lệnh mã C gốc. Điều đáng khích lệ hơn là một số sinh viên chưa có kinh nghiệm lập trình đã trở nên khá giỏi Python vào cuối quý. Họ đã triển khai thành công thuật toán luồng tối đa của Edmonds-Karp, thuật toán này không được cung cấp đầy đủ trong sách giáo khoa và đã thử nghiệm thuật toán này với một số ví dụ chỉ trong vòng một giờ. Một sinh viên khác, cũng không có nhiều nền tảng lập trình trước đó, đã dành phần lớn thời gian cuối tuần của mình cho cùng một bài tập, nhưng cuối cùng đã thành công sau một số gợi ý từ người hướng dẫn. Anh ấy nhận xét rằng một phần khó khăn là do ngữ nghĩa sao chép và truyền tham số trong Python, nhưng vấn đề chính là anh ấy chưa thực sự hiểu thuật toán E-K. Một khi anh ấy thực sự hiểu nó, thì việc mã hóa nó thực sự rất đơn giản. Phần đáng khích lệ nhất là nhiều học sinh muốn thực hiện các thuật toán không được giao làm bài tập về nhà. Các sinh viên cho biết họ muốn xem các thuật toán chạy và kiểm tra sự hiểu biết của chính họ. Tất cả những giai thoại này đều phục vụ để xác thực dự đoán của chúng tôi và xác nhận lý do chúng tôi đưa Python vào khóa học ngay từ đầu

Tuy nhiên, không phải tất cả sinh viên đều có trải nghiệm suôn sẻ với Python. Một khiếu nại phổ biến là thiếu trình sửa lỗi tốt. Tác giả đã trả lời các sinh viên bằng cách yêu cầu họ viết các thói quen nhỏ và kiểm tra chúng kỹ lưỡng trước khi viết thêm mã, thay vì viết một chương trình lớn và mong đợi nó hoạt động trong lần thử đầu tiên. Tuy nhiên, không phải tất cả học sinh đều bị thuyết phục. Ngữ nghĩa sao chép của các cấu trúc dữ liệu tổng hợp như danh sách, từ điển và đối tượng cũng gây ra một số nhầm lẫn, mặc dù chúng tôi dự định khắc phục sự cố này bằng cách đưa phần giải thích của chúng vào phần bài tập đọc. Trong một số trường hợp, hóa ra một số sinh viên có nhiều kinh nghiệm hơn với C++ hoặc Java gặp nhiều khó khăn hơn khi thích nghi với Python. Một số cảm thấy khó chịu với ý tưởng gõ lỏng lẻo, trong khi những người khác gặp khó khăn khi nghĩ về các đỉnh chỉ là một chuỗi có thể được sử dụng làm khóa băm cho các từ điển thuộc tính khác nhau; . Một số sinh viên đã không làm theo hướng dẫn về biểu đồ hoặc cấu trúc dữ liệu cây Huffman như đã trình bày ở trên và họ đã viết mã kiểu Java hoặc C++ theo cú pháp Python một cách hiệu quả bằng cách định nghĩa nhiều lớp và lớp con. Một danh sách chương trình như vậy cho Huffman dài hơn 12 trang, mặc dù hầu hết các sinh viên khác đã làm điều đó trong khoảng một trang. Đúng như dự đoán, hầu hết trong số 12 trang mã xử lý thao tác với cấu trúc dữ liệu và in cấu trúc dữ liệu được kết nối với con trỏ theo cách có ý nghĩa về mặt văn bản. Đây thực sự không phải là vấn đề với Python và trên thực tế, nó đang thúc đẩy chúng tôi giới thiệu Python sớm hơn trong chương trình giảng dạy

7. Kết luận và kế hoạch giáo dục trong tương lai

Bài báo này báo cáo việc chúng tôi sử dụng Python trong một khóa học thuật toán trong hai năm qua. Là một ngôn ngữ định hướng theo thuật toán, Python cho phép sinh viên của chúng tôi học các khái niệm chính trong thiết kế thuật toán, thay vì phải vật lộn với các tính năng cấp thấp, mang phong cách riêng của các ngôn ngữ lập trình thông thường. Cách Python xử lý các loại dữ liệu thể hiện sự phù hợp hoàn hảo với cách trình bày các thuật toán trong sách giáo khoa và bản chất diễn giải của nó khuyến khích sinh viên thử nghiệm ngôn ngữ này. Điều quan trọng không kém là việc chúng tôi sử dụng các cấu trúc dữ liệu mới cho cây và đồ thị, càng nhỏ gọn càng tốt và vẫn có thể đọc được bằng con người và được trình thông dịch Python chấp nhận dễ dàng. Những sinh viên mới tốt nghiệp có ít hoặc không có kinh nghiệm lập trình đã có thể thử nghiệm các thuật toán ở cấp độ mà sách giáo khoa dự định mà không bị sa lầy bởi nhiều vấn đề lập trình cấp thấp

Chúng tôi đã áp dụng Python không chỉ trong lớp học mà còn trong các dự án nghiên cứu, vì nghiên cứu cũng có thể hưởng lợi từ những lợi thế tương tự. Chúng tôi cũng được khuyến khích bởi phản hồi từ các sinh viên cũ của chúng tôi, những người đã áp dụng Python trong công việc hiện tại của họ. Chúng tôi hiện đang cải tiến loạt chương trình giới thiệu đại học của mình để đưa Python vào một cách chủ yếu. Khi viết bài này, bộ phận này vừa nhận được sự chấp thuận của Đại học để thay thế C bằng Python trong lớp lập trình nhập môn đầu tiên (ECE 12), bắt đầu từ quý mùa thu năm 2002. Chúng tôi đã phải vượt qua sự phản đối mạnh mẽ từ một số thành viên khoa kỹ thuật máy tính, những người chưa bao giờ nghe nói về Python và nghi ngờ về cách tiếp cận của chúng tôi. Chúng tôi bị chỉ trích vì cố gắng làm cho chương trình trở nên "quá mềm" đối với sinh viên kỹ thuật và chúng tôi được hỏi "nếu C không hỏng thì tại sao phải sửa nó?" . Sự sẵn có của CGI và các gói đồ họa bằng Python thông qua Jython và TkInter cũng sẽ cung cấp nhiều ý tưởng hấp dẫn hơn cho các dự án của sinh viên so với C hoặc Java

Có bao nhiêu loại thuật toán trong Python?

4 loại thuật toán là gì?

Các loại thuật toán khác nhau là gì?

Thuật toán nào được sử dụng trong Python?