Thuật toán là một thủ tục từng bước, trong đó xác định một tập hợp các hướng dẫn được thực thi theo một thứ tự nhất định để có được đầu ra mong muốn. Các thuật toán thường được tạo ra độc lập với các ngôn ngữ cơ bản, tức là một thuật toán có thể được thực hiện bằng nhiều ngôn ngữ lập trình. Show
Từ quan điểm cấu trúc dữ liệu, sau đây là một số loại thuật toán quan trọng -
Đặc điểm của thuật toánKhông phải tất cả các thủ tục có thể được gọi là thuật toán. Một thuật toán phải có các đặc điểm sau -
Làm thế nào để viết một thuật toán?Không có tiêu chuẩn được xác định rõ để viết thuật toán. Thay vào đó, đó là vấn đề và phụ thuộc vào tài nguyên. Các thuật toán không bao giờ được viết để hỗ trợ một mã lập trình cụ thể. Như chúng ta biết rằng tất cả các ngôn ngữ lập trình đều chia sẻ các cấu trúc mã cơ bản như các vòng lặp (làm, vì, while), kiểm soát dòng chảy (if-else), v.v ... Các cấu trúc phổ biến này có thể được sử dụng để viết một thuật toán. Chúng tôi viết các thuật toán theo cách từng bước, nhưng nó không phải lúc nào cũng đúng. Viết thuật toán là một quá trình và được thực thi sau khi miền vấn đề được xác định rõ. Đó là, chúng ta nên biết miền vấn đề, mà chúng ta đang thiết kế một giải pháp. Thí dụChúng ta hãy cố gắng học thuật toán viết bằng cách sử dụng một ví dụ.
Bước 1 - Bắt đầu − START Bước 2 - Khai báo ba số nguyên A, B & C − declare three integers a, b & c Bước 3 - Xác định các giá trị của A & B − define values of a & b Bước 4 - Thêm các giá trị của A & B − add values of a & b Bước 5 - Lưu trữ đầu ra của Bước 4 đến C − store output of step 4 to c Bước 6 - In C − print c Bước 7 - Dừng − STOP Các thuật toán cho các lập trình viên biết cách viết mã chương trình. Ngoài ra, thuật toán có thể được viết là - Bước 1 - Bắt đầu Thêm − START ADD Bước 2 - Nhận các giá trị của A & B − get values of a & b Bước 3 - C ← A + B − c ← a + b Bước 4 - Hiển thị C − display c Bước 5 - Dừng − STOP Trong thiết kế và phân tích các thuật toán, thông thường phương pháp thứ hai được sử dụng để mô tả một thuật toán. Nó giúp nhà phân tích dễ dàng phân tích thuật toán bỏ qua tất cả các định nghĩa không mong muốn. Anh ta có thể quan sát những gì hoạt động đang được sử dụng và cách thức quá trình chảy. Viết số bước, là tùy chọn.step numbers, is optional. Chúng tôi thiết kế một thuật toán để có được một giải pháp cho một vấn đề nhất định. Một vấn đề có thể được giải quyết theo nhiều cách.  Do đó, nhiều thuật toán giải pháp có thể được lấy cho một vấn đề nhất định. Bước tiếp theo là phân tích các thuật toán giải pháp được đề xuất đó và thực hiện giải pháp phù hợp nhất. Pai H. Chou Bộ Kỹ thuật Điện và Máy tính của California, Irvine, CA 92697-2625 Hoa KỳKhoa Điện và Kỹ thuật Máy tính đa dạng của California, Irvine, CA 92697-2625 Hoa Kỳ University of California, Irvine, CA 92697-2625 USA trừu tượngThiết kế và phân tích các thuật toán là một chủ đề cơ bản trong giáo dục khoa học và kỹ thuật máy tính. 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 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 đối phó với các chi tiết về cấu trúc dữ liệu và thói quen 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 đã rất cần thiết trong giáo dục. Những lợi thế của Python bao gồm cú pháp giống như 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 lạ của chúng tôi để thể hiện các cấu trúc dữ liệu tổng hợp như đồ thị và mạng lưu lượng ở dạng văn bản ngắn gọn, 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 thực hiện 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ệuThuậ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 các chương trình máy tính. Các thuật toán được sử dụng không chỉ 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 kỹ thuật và khoa học khác. Do đó, các khóa học thuật toán được thực hiện bởi không chỉ các chuyên ngành máy tính như một yêu cầu, 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 vấn đề, sinh viên thường không thực sự học các thuật toán cho đến khi chúng thực sự thử thực hiện chúng. Do đó, không có gì lạ đối với các khóa học thuật toán để bao gồm các bài tập lập trình. 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 tác giả để đáp ứng nhu cầu này [4]. Hầu như tất cả các khóa học và sách giáo khoa cho đến nay đã yêu cầu sinh viên lập trình bằng một ngôn ngữ truyền thống như C hoặc C ++, và gần đây Java đã trở nên phổ biến [5]. Lập luận cho việc sử dụng các ngôn ngữ này chủ yếu là một ngôn ngữ thực tế: sinh viên có lẽ đã thành thạo các ngôn ngữ này; Ngay cả khi chúng không, học các ngôn ngữ này sẽ cung cấp cho họ một kỹ năng thực tế. 1.1 Lập trình so với thiết kế thuật toánThậ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 là một vài dòng đến nửa trang trong sách giáo khoa, việc triển khai của 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 các biến toàn cầu, biến cục bộ và tham số trước khi chúng có thể được sử dụng. Một lý do 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à các mảng chuyên dụng 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 phát triển nhanh chóng khi các cấu trúc dữ liệu tổng hợp như đồ thị hoặc mạng lưu lượng có liên quan. 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 vào 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 phần lớn thời gian thực hành các vấn đề lập trình, thay vì các vấn đề thuật toán. Những sinh viên không phải là chuyên ngành máy tính có xu hướng bị bất lợi nghiêm trọng. Một số giảng viên đã cố gắng giảm bớt gánh nặng này bằng cách cung cấp cho sinh viên các 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 đề vốn có đối với các ngôn ngữ truyền thống này, bao gồm đầu vào/đầu ra và tái sử dụng. 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ứng trường hợp kiểm tra của mình, thực hiện các cuộc gọi liên tiếp để thêm một nút tại một thời điểm 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ể gây khó xử, bởi 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 để thể hiện biểu đồ, có thể súc tích hơn, nhưng nó đòi hỏi các thói quen phân tích cú pháp, có thể làm giảm khả năng tái sử dụng và 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 trọng số nhưng sau đó muốn một biểu đồ có trọng số. Có thể dễ dàng tạo ra 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 các trọng số một lần nữa 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 PythonPython 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 vết lõm của nó rất giống với hầu hết các sách giáo khoa đến nỗi ngay cả sinh viên không có nhiều nền lập trình cũng không gặp khó khăn gì trong việc mã hóa các thuật toán chỉ bằng cách theo dõi cuốn sách. Do đó, đối số phổ biến với các ngôn ngữ khác là moot, đặc biệt là thực tế là chế độ tương tác của nó khuyến khích sinh viên thử nghiệm nó mà không cần chu kỳ 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ả các cấu trúc dữ liệu phức tạp hơn như cây và đồ thị cũng có thể được biểu thị bằng python ở dạng con người, ngắn gọn có thể đọc được, mà không phải phát minh lại các cấu trúc dữ liệu đó. Ví dụ, Phần 5 sẽ hiển thị một cách mới lạ thể hiện một biểu đồ có trọng số như một từ điển các đỉnh có danh sách kề được thể hiện bằng từ điển của trọng lượng 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 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ó thể mở rộng vô hạn đối với các loại dữ liệu tùy ý, vì Python chỉ cần truyền chúng theo và không giải thích kiểu dữ liệu cho đến khi cần thiết. 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 có thể đọc được cho con người và bởi Python. Phần còn lại của bài viết này báo cáo kinh nghiệm thành công của chúng tôi với việc triển khai Python trong một lớp thuật toán cấp sau đại học. Học sinh của chúng tôi không chỉ tiếp nhận 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 riêng họ. 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 cùng một chuỗi như được trình bày trong lớp. Chúng tôi bắt đầu với việc sắp xếp các thuật toán và Heapsort với hàng đợi ưu tiên để làm nổi bật các vấn đề 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à thực hiện 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ếpHầu hết các sách giáo khoa bắt đầu với việc 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 để cũng giới thiệu Python 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 cạnh nhau với mã Python để hiển thị sự tương đồng của chúng. Chúng tôi bắt đầu với INSERTIONORT, phát triển mảng được sắp xếp một phần tử tại một thời điểm từ đầu mảng. Ban đầu, A [1] (trong văn bản; A [0] trong Python) là yếu tố duy nhất trong subarray này và được sắp xếp tầm thường. Mỗi lần lặp của vòng lặp chèn phần tử mới tiếp theo vào subarray được sắp xếp để các phần tử được sắp xếp so với nhau; Điều này trái ngược với bongbbledort, đặt một yếu tố mới ở vị trí được sắp xếp tuyệt đối của nó trên mỗi lần lặp. Thuật toán từ sách giáo khoa [1] Một khi sinh viên nhìn thấy sự tương đồng, hầu hết nỗi sợ lập trình của họ chỉ đơn giản là 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 máy tính 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 gõ trong trường hợp thử nghiệm dưới dạng danh sách: >>> x = [2,7,3,8,1] & nbsp; & nbsp;# Tạo trường hợp kiểm tra >>> actionSort (x) & nbsp; & nbsp;# gọi thói quen >>> x & nbsp; & nbsp; & nbsp; & nbsp; & nbsp; # Nhìn vào kết quả [1, 2, 3, 7, 8] Theo một nghĩa nào đó, Python cung cấp cho sách giáo khoa liên quan vì các thuật toán được trình bày trong sách giáo khoa không còn chỉ là mã giả hoặc các bước quan tâm lý thuyết; Họ có thể thấy mức độ dễ dàng của việc thực hiện các thuật toán bằng cách sử dụng dữ liệu mà chúng tạo ra. 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 cả chuỗi, bộ dữ liệu, v.v. sẽ được thảo luận sau), nhưng ngữ nghĩa tham số cũng phù hợp: vô hướng được truyền theo giá trị, trong khi các mảng được truyền qua tham chiếu. 3. Hàng xếp hàng và hàng đợi ưu tiênGiới thiệu của chúng tôi tiếp tục với hàng hóa và hàng đợi ưu tiên. Một đống là 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 bằng cách sử dụng một mảng A [1..n], trong đó trẻ em trái và phải của một nguyên tố A [i] được đặt tại [2i], A [2i+1 ], tương ứng và a [i]> = a [2i], a [2i+1]. Heapsort xây dựng subarray được sắp xếp từ phía sau của mảng về phía một phần tử phía trước tại một thời điểm bằng cách trích xuất phần tử lớn nhất từ phía trước của đống. Ban đầu, phần được sắp xếp trống, và một cuộc gọi để xây dựng biến một [1..n] thành một đống. Vì phần Heap đặt phần tử lớn nhất ở [1], trong lần lặp đầu tiên, chúng tôi trích xuất nó và đặt nó vào [n], đó 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 [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 trao đổ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ư" một đống-nghĩa là, tất cả ngoại trừ Vị trí gốc vẫn là những người phụ - nó có thể được cố định hiệu quả trong thời gian O (LG H) bằng cách gọi Heapify mà không phải xây dựng lại đống trong thời gian O (H). 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 các lỗi do điều chỉnh chỉ số, chúng tôi yêu cầu các sinh viên chỉ cần đệm A [0] của họ và sử dụng một mảng có kích thước N+1 thay thế. Mã Python là
Heaps and priority queues are closely related, since heaps can implement priority queues efficiently with O(lg n)-time insertion and extraction. One difference, though, is dynamic memory management: in heap sort, the size of the array remains the same, whereas in priority queues, the size of the queue grows and shrinks. We use this opportunity to introduce two constructs. First, we show that A.append() and A.pop() can be used to grow and shrink the list A, while len(A) returns the current length of the list. Second, in case of underflow (and overflow if desired), we show the students how to raise and catch an exception. These constructs might not be unique to Python, but Python makes it easy to experiment. 4. Binary Trees and Huffman EncodingOnce we have the priority queue, we enable students to quickly implement interesting algorithms, including Dijkstra's single-source shortest paths and Prim's min-spanning tree. Our next topic is greedy algorithms, and we ask the students to implement Huffman encoding in Python. To recall, the Huffman algorithm produces prefix-free, variable-length code words based on the frequency of each character. A frequently used letter will be encoded using a shorter bit string, whereas a less frequently used letter will be encoded using a longer bit string. The greedy algorithm uses a priority queue to extract two nodes (leaf or internal) with the lowest frequencies, allocates a new node whose weight is the sum of the two, and inserts the new node back into the priority queue. The algorithm terminates when the priority queue removes the last node, which becomes the root of the Huffman tree. The bit string for each letter can be produced by traversing the Huffman binary tree, where taking a left branch results in a `0', and a right branch results in a `1'. For example, suppose our input character set with the associated frequencies is
The Huffman algorithm constructs a tree by repeatedly dequeuing two elements with the least frequencies, creating a new internal node whose frequency is equal to their sum, and enqueuing it in the priority queue. The result is a tree (Fig. 1) that defines the variable-length code for each character. The left branches are labeled 0, and right branches are labeled 1, and the Huffman code for a character is simply the string of path labels from the root to the leaf. For example, the encodings are
Fig.1 Example of Huffman tree Since we already have the priority queue, what we are missing is a specialized binary tree. The requirements are
If we were to implement this with a traditional language like C or Java, we would have to teach students how to define a structure or a class with a field named weight; leaf nodes need a character field, while internal nodes require leftchild and rightchild fields. Because the priority queue must be able to compare them, it will be necessary to modify the priority queue to call the appropriate comparison method instead of using the built-in comparison operators, and both the leaves and internal nodes must either be in the same class or be subclasses of the same base class that implements the comparison method. Once defined, the student will want to able to check if they construct the Huffman tree correctly. However, no existing debugger has the knowledge to be able to automatically print the nodes together as a tree, and therefore the student has the burden of having to write the print routine, which may actually be rather tricky and be another major source of bugs. Similarly, for the students to specify the different test cases, they will either have to modify the hardwired data and recompile each time, or they will need to write additional parsing routines, which will be yet another source of errors. Việc triển khai Python có thể được thực hiện một cách thanh lịch mà không phải viết thêm các thói quen hoặc xác định một lớp mới hoặc một cấu trúc cho các nút cây. Chúng tôi yêu cầu học sinh đại diện cho cây nhị phân bằng cách sử dụng các bộ dữ liệu trong Python, với tinh thần tương tự như Lisp:
Cây được xây dựng về mặt chức năng với việc tạo ra tuple, 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 điều khiển các con trỏ trẻ em trái/phải. Hơn nữa, nó có thể sử dụng được với cấu trúc dữ liệu hàng đợi ưu tiên hiện có, mà không có bất kỳ sửa đổi nào! Điều này là do các bộ dữ liệu có thể được so sánh theo thứ tự từ vựng bằng cách sử dụng các toán tử so sánh tương tự. 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 các thông tin khác nhau. Sự khác biệt giữa chúng là Len () = 2 cho một lá và = 3 cho một nút bên trong. Để tóm tắt lại, với một cách hơi sáng tạo để sử dụng Python, chúng ta đạt được sự tái sử dụng cuối cùng của các thuật toán và cấu trúc dữ liệu. Nó cũng cho phép các sinh viên mô tả về mặt văn bản một cây trong cú pháp Python có thể súc tích và có thể mở rộng nhất có thể, mà không 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 biểu đồ là G (V, E), trong đó V là một tập hợp các đỉnh và E, như một tập hợp con của sản phẩm chéo của V Cross V, là một tập hợp các cạnh. Một biểu đồ có nhiều biểu diễn và hầu hết các thuật toán đều có danh sách kề hoặc biểu diễn ma trận kề. Cái trước là tốt cho đồ thị thưa thớt trong đó | e | gần với | v |, trong khi cái sau là tốt cho các biểu đồ dày đặc có | e | gần hơn với | v | 2. Để thực hiện biểu đồ bằng 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 sẽ phải xác định các cấu trúc dữ liệu cho các đỉnh, cho các cạnh và cho biểu đồ, đóng vai trò là mặt trận để tạo và xóa Các đỉnh và cạnh của nó. Thiết kế của các cấu trúc dữ liệu như vậy có thể dễ dàng thống trị thời gian mã hóa và không dễ dàng tái sử dụng, chủ yếu là vì các loại dữ liệu này phải được thiết kế dưới dạng container. Mặc dù các gói như Leda [3] 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 ++, họ vẫn yêu cầu các sinh viên áp dụng toàn bộ gói trước khi chúng có thể bắt đầu làm bất cứ điều gì hữu ích. Các container thường được thiết kế để phá vỡ các vấn đề với việc gõ mạnh, tĩnh, nhưng làm như vậy đòi hỏi phải thực hiện lại kiểm tra loại độ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 tham chiếu Java làm cho nó khó xử khi xem các đối tượng này. Mặc dù một trình gỡ lỗi có thể hiển thị các đối tượng này ở một số dạng văn bản, nhưng nó có thể 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 tô sáng bởi cấu trúc dữ liệu đồ thị. Chúng tôi sử dụng một triển khai từ điển rất nhỏ gọn (DD) của 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 từ điển Python, có các phím là tên chuỗi của các đỉnh và mỗi tên đỉnh được ánh xạ vào danh sách kề của nó. Ví dụ, hãy xem xét biểu đồ được hiển thị trong Hình 2: Hình 2: Ví dụ về biểu đồ được định hướng Nó có thể được biểu diễn bằng mã python sau đây
Trên đây đại diện cho một biểu đồ đơn giản, được định hướng, không trọng số. Nếu một biểu đồ có trọng số như Hình 3 là bắt buộc, thì chúng ta chỉ có thể thay thế các danh sách các đỉnh liền kề bằng các từ điển ánh xạ các đỉnh liền kề với trọng số của chúng: Hình 3: Ví dụ về đồ thị có trọng số L = {'a': {'c': 2, 'd': 6}, 'b': {'d': 8, 'a': 3}, & nbsp; & nbsp; & nbsp; & nbsp; & nbsp; & nbsp ; 'C': {'d': 7, 'e': 5}, 'd': {'e':-2}, 'e': {}} Danh sách các đỉnh V chỉ đơn giản là h.keys () hoặc l.keys (). Danh sách kề là H [v] cho các biểu đồ không trọng số và L [v] .KEY () cho các biểu đồ có trọng số. Trọng lượng cạnh w (u, v) là l [u] [v]. Để tạo điều kiện cho lập trình, chúng ta có thể bao bọc các chi tiết triển khai bên trong một đối tượng. Biểu đồ lớp: & nbsp; & nbsp; & nbsp; def __init __ (self, g): & nbsp; & nbsp; & nbsp; & nbsp; & nbsp; & nbsp; self.g = g & nbsp; & nbsp; & nbsp; & nbsp; & nbsp; return g.keys () & nbsp; ) & nbsp; Chúng ta có thể tạo một đối tượng đồ thị với g = đồ thị (l). Những lợi thế với 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 thực thi. 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 soạn thảo đồ thị đặc biệt nào. Cấu trúc dữ liệu có thể được kiểm tra chỉ bằng cách nhập tên của nó. Sau đó, nó có thể được cắt/dán vào một cửa sổ phiên dịch Python khác hoặc vào một chương trình Python khác, mà không cần sửa đổi cú pháp. 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ụ, các thuật toán đường dẫn ngắn nhất nguồn đơn hoặc các đường truyền đầu tiên/chiều sâu đầu tiên yêu cầu các thuộc tính bổ sung như con trỏ tiền thân. 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 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 vào 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 thói quen mới. 6. Đánh giá của sinh viênTheo văn bản 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 tích cực, mặc dù vẫn còn chỗ để 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ề mặt thành công của câu chuyện, hầu hết các sinh viên xuất hiện tiếp nhận Python và hầu hết các sinh viên 35-40 từ mỗi lớp đã có thể hoàn thành thành công 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 một 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 ta không chỉ sử dụng các tiện ích giao diện người dùng Jython và Tkinter để tập lệnh mà còn sử dụng Python để lập trình ổ cắm, đa luồng và mã C mã C gốc. Điều đáng khích lệ hơn là một số sinh viên không có kinh nghiệm lập trình viên đã trở nên khá giỏi ở Python vào cuối quý. Họ đã thực hiện thành công thuật toán dòng chảy tối đa của Edmonds-Karp, không được đưa ra đầy đủ trong sách giáo khoa và thử nghiệm nó với một số ví dụ trong ít nhất 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 một phần cuối tuần của mình cho cùng một nhiệm vụ, nhưng cuối cùng đã thành công sau một số gợi ý từ người hướng dẫn. Anh ta nhận xét rằng một phần của khó khăn là với bản sao và tham số truyền qua ngữ nghĩa trong Python, nhưng vấn đề chính là anh ta đã không 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à hơn một vài sinh viên muốn thực hiện các thuật toán không được chỉ định làm vấn đề 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ọ. Những giai thoại này đều phục vụ để xác nhận dự đoán của chúng tôi và xác nhận lý do chúng tôi kết hợp Python trong khóa học ngay từ đầu. Không phải tất cả các sinh viên đã có một trải nghiệm suôn sẻ với Python, mặc dù. Một khiếu nại phổ biến là thiếu một trình gỡ 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ó sẽ hoạt động trong lần thử đầu tiên. Tuy nhiên, không phải tất cả các sinh viên đã bị thuyết phục. Bản sao ngữ nghĩa của các cấu trúc dữ liệu tổng hợp như danh sách, từ điển và các đối tượng cũng gây ra một số nhầm lẫn, mặc dù chúng tôi có kế hoạch khắc phục vấn đề này bằng cách bao gồm lời giải thích của chúng như là một phần của 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 điều chỉnh theo 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 phím băm cho các từ điển thuộc tính khác nhau; Thay vào đó, họ muốn nghĩ về các đỉnh như là đối tượng. Một vài sinh viên đã không làm theo hướng dẫn cho biểu đồ hoặc cấu trúc dữ liệu cây Huffman như được trình bày ở trên và họ đã viết một cách hiệu quả mã kiểu Java hoặc C ++ trong cú pháp Python bằng cách xác định nhiều lớp và các 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 nó trong khoảng một trang. Theo dự đoán, hầu hết trong số 12 trang mã xử lý các cấu trúc dữ liệu thao tác và in các cấu trúc dữ liệu được kết nối con trỏ theo cách có ý nghĩa về mặt văn bản. Đây không thực sự là một 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 trước đó 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 laiBài viết 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 thuật toán, Python cho phép học sinh 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ì đấu tranh với các tính năng bình dị, cấp thấp 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 một kết hợp hoàn hảo với cách các thuật toán trình bày 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ữ. Điều quan trọng không kém là việc sử dụng các cấu trúc dữ liệu mới lạ của chúng tôi cho cây và đồ thị, nhỏ gọn nhất có thể và người có thể đọc được và được người phiên dịch Python chấp nhận dễ dàng. Sinh viên 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 độ dự định của sách giáo khoa, 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 trong không chỉ các lớp học mà còn cả các dự án nghiên cứu, vì nghiên cứu cũng có thể được hưởng lợi từ cùng một lợi thế. 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 tạo loạt chương trình giới thiệu đại học của chúng tôi để bao gồm Python theo một cách chính. Theo văn bản này, bộ phận này vừa nhận được sự chấp thuận của trường đại học để thay thế C bằng Python trong lớp lập trình giới thiệu đầu tiên (ECE 12), bắt đầu từ mùa thu năm 2002. Chúng tôi đã phải vượt qua một số sự phản đối mạnh mẽ từ một số giảng viên kỹ thuật phi máy tính, những người đã có 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 lập trình "quá mềm" cho sinh viên kỹ thuật, và chúng tôi đã được hỏi "nếu c không bị phá vỡ, tại sao lại sửa chữa nó?" Phản hồi của chúng tôi là chúng tôi muốn dạy các kỹ năng giải quyết vấn đề, không chỉ là lập trình và chúng tôi tự tin rằng Python sẽ là một cách hiệu quả hơn nhiều để giới thiệu các khái niệm cơ bản hơn là C. Sự sẵn có của các gói CGI và đồ họa trong 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 sinh viên hơn C hoặc Java. Người giới thiệu
Tại sao Python được sử dụng cho các thuật toán?Cú pháp đơn giản của Python đơn giản có nghĩa là nó cũng là ứng dụng nhanh hơn trong phát triển so với nhiều ngôn ngữ lập trình và cho phép nhà phát triển nhanh chóng kiểm tra các thuật toán mà không phải thực hiện chúng.allows the developer to quickly test algorithms without having to implement them.
Ngôn ngữ nào là tốt nhất cho thuật toán?Ngôn ngữ tốt nhất để viết thuật toán.. Python và Ruby. Đầu tiên và quan trọng nhất, tôi muốn giới thiệu các ngôn ngữ cấp cao. .... Ngôn ngữ C. C chính xác là trái ngược với Python ở đây. .... Chương trình Java. Rất nhiều người thực sự ghét Java vì quá dài dòng và nghiêm khắc. .... C# và C ++ C# gần như giống với Java .. |
