Lập trình cấu trúc dữ liệu và thuật toán bằng python là gì?

Khóa học này giới thiệu về lập trình và giải quyết vấn đề bằng Python. Nó không thừa nhận bất kỳ kiến ​​thức lập trình trước đó. Sử dụng một số ví dụ thúc đẩy, khóa học nhanh chóng xây dựng các khái niệm cơ bản như điều kiện, vòng lặp, hàm, danh sách, chuỗi và bộ dữ liệu. Nó tiếp tục bao gồm các thuật toán tìm kiếm và sắp xếp, lập trình động và quay lui, cũng như các chủ đề như xử lý ngoại lệ và sử dụng tệp. Về cấu trúc dữ liệu, khóa học bao gồm các từ điển Python cũng như các lớp và đối tượng để xác định các kiểu dữ liệu do người dùng xác định, chẳng hạn như danh sách được liên kết và cây tìm kiếm nhị phân

ĐỐI TƯỢNG DỰ ĐỊNH. Học sinh trong bất kỳ ngành toán học/khoa học/kỹ thuật nào, năm thứ nhất

điều kiện tiên quyết. Toán cấp trường

CÔNG NGHIỆP HỖ TRỢ. Khóa học này nên có giá trị đối với bất kỳ công ty nào yêu cầu kỹ năng lập trình

GIỚI THIỆU. Bấm vào đây

Chúng tôi vừa phát hành một khóa học trên kênh YouTube freeCodeCamp, đây là phần giới thiệu thân thiện với người mới bắt đầu về các cấu trúc dữ liệu phổ biến [danh sách được liên kết, ngăn xếp, hàng đợi, biểu đồ] và thuật toán [tìm kiếm, sắp xếp, đệ quy, lập trình động] trong Python

Khóa học này sẽ giúp bạn chuẩn bị cho các cuộc phỏng vấn và đánh giá mã hóa. Trong khóa học này, bạn sẽ

• Xem trực tiếp các video hướng dẫn tập trung vào mã hóa
• Thực hành mã hóa với sổ ghi chép đám mây Jupyter
• Giải quyết các câu hỏi từ các cuộc phỏng vấn lập trình thực tế

Aakash N S dạy khóa học này. Ông là người đồng sáng lập kiêm CEO của Jovian và đã tạo ra nhiều khóa học nổi tiếng về học máy và lập trình

Khóa học được chia thành một loạt các bài học, bài tập và dự án. Có các tệp Jupyter Notebook đi cùng với từng phần

Đây là những gì được đề cập trong khóa học

Bài 1 - Tìm kiếm nhị phân, Danh sách liên kết và Độ phức tạp

• Tìm kiếm tuyến tính và nhị phân
• Độ phức tạp và ký hiệu Big O
• Danh sách được liên kết sử dụng các lớp Python

Bài tập 1 - Thực hành tìm kiếm nhị phân

• Hiểu và giải quyết vấn đề một cách có hệ thống
• Thực hiện tìm kiếm tuyến tính và phân tích nó
• Tối ưu hóa giải pháp bằng tìm kiếm nhị phân

Bài 2 - Cây tìm kiếm nhị phân, duyệt và đệ quy

• Cây nhị phân, duyệt và đệ quy
• Cây tìm kiếm nhị phân & các hoạt động phổ biến
• Cây nhị phân cân bằng và tối ưu hóa

Bài tập 2 - Bảng băm và Từ điển Python

• Bảng băm từ đầu trong Python
• Xử lý va chạm bằng thăm dò tuyến tính
• Sao chép từ điển Python

Bài 3 - Thuật toán Sắp xếp và Chia để trị

• Sắp xếp bong bóng và Sắp xếp chèn
• Hợp nhất sắp xếp bằng cách sử dụng Chia & Chinh phục
• Quicksort và độ phức tạp trung bình

Bài tập 3 - Thực hành chia để trị

• Thực hiện phép nhân đa thức
• Tối ưu hóa bằng cách sử dụng chia để trị
• Phân tích độ phức tạp về thời gian và không gian

Bài 4 - Lập trình đệ quy và động

• Đệ quy và ghi nhớ
• Bài toán dãy con và cái ba lô
• Quay lui và cắt tỉa

Bài 5 - Thuật toán đồ thị [BFS, DFS & Đường đi ngắn nhất]

• Đồ thị, cây và danh sách kề
• Tìm kiếm theo chiều rộng và theo chiều sâu
• Đường đi ngắn nhất và đồ thị có hướng

Dự án - Giải pháp từng bước cho một vấn đề lập trình

• Chọn một vấn đề mã hóa thú vị
• Giải quyết vấn đề từng bước
• Viết tài liệu và trình bày giải pháp

Bài 6 - Câu hỏi phỏng vấn Python, Mẹo & Lời khuyên

• Câu hỏi và lời giải bài tập
• Mẹo để giải quyết các thách thức về mã hóa
• Lời khuyên cho các cuộc phỏng vấn mã hóa

Xem khóa học bên dưới hoặc trên freeCodeCamp. org Kênh YouTube [13 giờ xem]

QUẢNG CÁO

QUẢNG CÁO

QUẢNG CÁO

Nếu bạn đọc đến đây, hãy tweet cho tác giả để cho họ thấy bạn quan tâm. Tweet một lời cảm ơn

Học cách viết mã miễn phí. Chương trình giảng dạy mã nguồn mở của freeCodeCamp đã giúp hơn 40.000 người có được việc làm với tư cách là nhà phát triển. Bắt đầu

Để phát triển trí tuệ toàn diện. Nghiên cứu khoa học về nghệ thuật; . Học cách nhìn. Nhận ra rằng mọi thứ kết nối với mọi thứ khác

Leonardo da Vinci

Giới thiệu

Mục đích của bài viết này là cung cấp cho bạn một bức tranh toàn cảnh về cấu trúc dữ liệu và giải thuật trong Python. Chủ đề này rất quan trọng đối với Nhà khoa học dữ liệu để giúp họ thiết kế và giải quyết các mô hình học máy một cách hiệu quả hơn

Chúng ta sẽ cùng xem các ví dụ thực tế về cấu trúc dữ liệu có sẵn, cấu trúc dữ liệu do người dùng định nghĩa và cuối cùng nhưng không kém phần quan trọng, tôi sẽ giới thiệu cho bạn một số thuật toán như thuật toán duyệt, thuật toán sắp xếp và thuật toán tìm kiếm

Vậy hãy bắt đầu

phần tôi. Cấu trúc dữ liệu tích hợp

Như tên cho thấy, cấu trúc dữ liệu cho phép chúng tôi tổ chức, lưu trữ và quản lý dữ liệu để truy cập và sửa đổi hiệu quả

Trong phần này, chúng ta sẽ xem xét các cấu trúc dữ liệu tích hợp. Có bốn loại cấu trúc dữ liệu tích hợp trong Python. danh sách, bộ dữ liệu, bộ và từ điển

Danh sách

Danh sách được xác định bằng cách sử dụng dấu ngoặc vuông và giữ dữ liệu được phân tách bằng dấu phẩy. Danh sách có thể thay đổi và sắp xếp. Nó có thể chứa hỗn hợp các loại dữ liệu khác nhau

ngoài

january['january', 'february', 'march', 'april', 'may', 'june', 'july']['birthday', 'february', 'march', 'april', 'may', 'june', 'july', 'august', 'september', 'october', 'november', 'december']

Dưới đây có một số chức năng hữu ích cho danh sách

ngoài

What
is
your
favourite
painting
?Who-is-your-favourite-artist-?

ngoài

['Chagall', 'Kandinskij', 'Dalí', 'da Vinci', 'Picasso', 'Warhol', 'Basquiat']

Tuple

Một tuple là một thùng chứa khác. Nó là một kiểu dữ liệu cho các chuỗi phần tử được sắp xếp bất biến. Không thể thay đổi vì bạn không thể thêm và xóa các phần tử khỏi bộ dữ liệu hoặc sắp xếp chúng tại chỗ

ngoài

The dimensions are 7 x 3 x 1

Bộ

Set là một tập hợp các phần tử duy nhất có thể thay đổi và không có thứ tự. Nó có thể cho phép chúng tôi loại bỏ trùng lặp nhanh chóng khỏi danh sách

ngoài

{1, 2, 3, 5, 6}
False
Basquiat

Từ điển

Từ điển là một cấu trúc dữ liệu có thể thay đổi và không có thứ tự. Nó cho phép lưu trữ một cặp mục [tôi. e. khóa và giá trị]

Như ví dụ bên dưới cho thấy, trong từ điển có thể gộp các container vào các container khác để tạo cấu trúc dữ liệu ghép

ngoài

In a Sentimental Mood
Lacrimosa

Phần II. Cấu trúc dữ liệu do người dùng xác định

Bây giờ tôi sẽ giới thiệu cho bạn ba cấu trúc dữ liệu do người dùng định nghĩa. ques, ngăn xếp và cây. Tôi cho rằng bạn có kiến ​​thức cơ bản về các lớp và hàm

Ngăn xếp sử dụng mảng

Ngăn xếp là một cấu trúc dữ liệu tuyến tính trong đó các phần tử được sắp xếp tuần tự. Nó theo cơ chế L. I. F. O nghĩa là vào sau ra trước. Vì vậy, phần tử cuối cùng được chèn sẽ bị xóa làm phần tử đầu tiên. Các hoạt động là

• Đẩy → chèn một phần tử vào ngăn xếp
• Bật → xóa một phần tử khỏi ngăn xếp

Các điều kiện để kiểm tra

• điều kiện tràn → điều kiện này xảy ra khi chúng ta cố gắng đặt thêm một phần tử vào ngăn xếp đã có phần tử tối đa
• điều kiện underflow →điều kiện này xảy ra khi chúng ta cố gắng xóa một phần tử khỏi ngăn xếp trống

ngoài

5
True
[10, 23, 25, 27, 11]
overflow
11
27
25
23
10
underflow

Xếp hàng sử dụng mảng

Hàng đợi là một cấu trúc dữ liệu tuyến tính trong đó các phần tử sắp xếp theo thứ tự. Nó đi theo F. I. F. Cơ chế O nhập trước xuất trước. Hãy nghĩ khi bạn đi xem phim với bạn bè, bạn có thể tưởng tượng người đầu tiên trong số các bạn đưa vé cũng là người đầu tiên bước ra khỏi hàng. Cơ chế của hàng đợi là như nhau

Bên dưới các khía cạnh đặc trưng cho một hàng đợi

hai đầu

• phía trước → trỏ đến phần tử bắt đầu
• phía sau → trỏ đến phần tử cuối cùng

Có hai thao tác

• enqueue → chèn một phần tử vào hàng đợi. Nó sẽ được thực hiện ở phía sau
• dequeue → xóa một phần tử khỏi hàng đợi. Nó sẽ được thực hiện ở phía trước

Có hai điều kiện

• tràn → chèn vào hàng đợi đã đầy
• tràn → xóa khỏi hàng đợi trống

ngoài

[2, 3, 4, 5]
[3, 4, 5]

Cây [cây chung]

Cây được sử dụng để xác định thứ bậc. Nó bắt đầu từ nút gốc và đi xuống dưới nữa, những nút cuối cùng được gọi là nút con

Trong bài viết này, tôi tập trung vào cây nhị phân. Cây nhị phân là một cấu trúc dữ liệu cây trong đó mỗi nút có nhiều nhất hai nút con, được gọi là nút con trái và nút con phải. Dưới đây, bạn có thể thấy một biểu diễn và một ví dụ về cây nhị phân với python nơi tôi đã xây dựng một lớp có tên là Nút và các đối tượng đại diện cho các nút khác nhau [A, B, C, D và E]

Dù sao, có những cấu trúc dữ liệu do người dùng xác định khác như danh sách và biểu đồ được liên kết

Phần III. thuật toán

Khái niệm về thuật toán đã tồn tại từ thời cổ đại. Trên thực tế, người Ai Cập cổ đại đã sử dụng các thuật toán để giải quyết vấn đề của họ. Sau đó, họ dạy cách tiếp cận này cho người Hy Lạp

Từ thuật toán bắt nguồn từ nhà toán học người Ba Tư thế kỷ thứ 9 Muḥammad ibn Mūsā al-Khwārizmī, tên của ông được Latinh hóa là Algorithmi. Al-Khwārizmī cũng là một nhà thiên văn học, nhà địa lý học và một học giả trong Ngôi nhà Trí tuệ ở Baghdad

Như bạn đã biết các thuật toán là các hướng dẫn được xây dựng theo thứ tự hữu hạn và tuần tự để giải quyết các vấn đề

Khi chúng ta viết một thuật toán, chúng ta phải biết chính xác vấn đề là gì, xác định nơi chúng ta cần bắt đầu và dừng lại và hình thành các bước trung gian.

Có ba cách tiếp cận chính để giải thuật toán

• Divide et Impera [còn được gọi là chia để trị] → nó chia vấn đề thành các phần phụ và giải quyết từng phần riêng biệt
• Quy hoạch động → nó chia vấn đề thành các phần nhỏ ghi nhớ kết quả của các phần con và áp dụng nó cho các phần tương tự
• Các thuật toán tham lam → liên quan đến việc thực hiện bước dễ nhất trong khi giải quyết vấn đề mà không phải lo lắng về sự phức tạp của các bước trong tương lai

Thuật toán duyệt cây

Cây trong python là cấu trúc dữ liệu phi tuyến tính. Chúng được đặc trưng bởi rễ và nút. Tôi lấy lớp tôi đã xây dựng trước đó cho cây nhị phân

Tree Traversal đề cập đến việc truy cập từng nút có trong cây chính xác một lần, để cập nhật hoặc kiểm tra chúng

Có ba kiểu duyệt cây

• Truyền tải theo thứ tự → đề cập đến việc truy cập nút bên trái, tiếp theo là nút gốc và sau đó là các nút bên phải

Ở đây D là nút ngoài cùng bên trái có gốc gần nhất là B. Bên phải của gốc B là E. Bây giờ cây con bên trái đã hoàn thành, vì vậy tôi di chuyển đến nút gốc A và sau đó đến nút C

ngoài

• Truyền tải đơn đặt hàng trước → đề cập đến việc truy cập nút gốc, theo sau là các nút bên trái và sau đó là các nút bên phải

Trong trường hợp này, tôi di chuyển đến nút gốc A rồi đến nút con bên trái B và đến nút con phụ D. Sau đó tôi có thể đi đến các nút E và sau đó C

ngoài

A
B
D
E
C

• Truyền tải theo thứ tự sau → đề cập đến việc truy cập các nút bên trái, tiếp theo là các nút bên phải và sau đó là nút gốc

Tôi đi đến nút bên trái nhất là D và sau đó đến nút bên phải E. Sau đó, tôi có thể đi từ nút bên trái B sang nút bên phải C. Cuối cùng, tôi di chuyển về phía nút gốc A

ngoài

What
is
your
favourite
painting
?Who-is-your-favourite-artist-?

thuật toán sắp xếp

Thuật toán sắp xếp được sử dụng để sắp xếp dữ liệu theo một số thứ tự nhất định. Nó có thể được phân loại trong Sắp xếp hợp nhất và Sắp xếp bong bóng

• Hợp nhất Sắp xếp → nó tuân theo quy tắc chia et Impera. Đầu tiên, danh sách đã cho được chia thành các danh sách nhỏ hơn và so sánh các danh sách liền kề, sau đó, sắp xếp lại chúng theo trình tự mong muốn. Vì vậy, tóm lại từ các phần tử không có thứ tự làm đầu vào, chúng ta cần có các phần tử có thứ tự làm đầu ra. Dưới đây, mã với từng bước được mô tả

ngoài

What
is
your
favourite
painting
?Who-is-your-favourite-artist-?

• Sắp xếp bong bóng → trước tiên, nó so sánh và sau đó sắp xếp các phần tử liền kề nếu chúng không theo thứ tự đã chỉ định

ngoài

What
is
your
favourite
painting
?Who-is-your-favourite-artist-?

• Sắp xếp chèn → nó chọn một mục của danh sách đã cho tại thời điểm đó và đặt nó vào vị trí chính xác mà nó sẽ được đặt

ngoài

What
is
your
favourite
painting
?Who-is-your-favourite-artist-?

Có các thuật toán sắp xếp khác như Sắp xếp lựa chọn và Sắp xếp Shell

thuật toán tìm kiếm

Các thuật toán tìm kiếm được sử dụng để tìm kiếm một số phần tử có trong một tập dữ liệu nhất định. Có nhiều loại thuật toán tìm kiếm như Tìm kiếm tuyến tính, Tìm kiếm nhị phân, Tìm kiếm theo hàm mũ, Tìm kiếm nội suy, v.v. Trong phần này, chúng ta sẽ thấy Tìm kiếm tuyến tính và Tìm kiếm nhị phân

• Tìm kiếm tuyến tính → trong mảng một chiều chúng ta phải tìm kiếm một phần tử khóa cụ thể. Đầu vào là nhóm phần tử và phần tử chính mà chúng ta muốn tìm. Vì vậy, chúng ta phải so sánh phần tử chính với từng phần tử của nhóm. Trong đoạn mã sau, tôi cố gắng tìm phần tử 27 trong danh sách của chúng tôi

ngoài

What
is
your
favourite
painting
?Who-is-your-favourite-artist-?

• Tìm kiếm nhị phân → trong thuật toán này, chúng tôi giả sử rằng danh sách theo thứ tự tăng dần. Vì vậy, nếu giá trị của khóa tìm kiếm nhỏ hơn phần tử ở giữa danh sách, chúng tôi sẽ thu hẹp khoảng cách xuống nửa dưới. Nếu không, chúng tôi thu hẹp ở nửa trên. Chúng tôi tiếp tục kiểm tra cho đến khi tìm thấy giá trị hoặc danh sách trống

ngoài

What
is
your
favourite
painting
?Who-is-your-favourite-artist-?

Phần kết luận

Bây giờ bạn đã có cái nhìn tổng quan về cấu trúc dữ liệu và giải thuật. Vì vậy, bạn có thể bắt đầu tìm hiểu sâu hơn về các thuật toán

Hình ảnh đẹp về Vitruvian Man mà tôi chọn cho bài viết này không phải ngẫu nhiên. Bản vẽ dựa trên sự tương quan của cơ thể con người lý tưởng trong mối liên hệ với hình học. Trên thực tế, đối với sự thể hiện này, Leonardo da Vinci đã lấy cảm hứng từ Vitruvius, người đã mô tả cơ thể người đàn ông là cơ thể lý tưởng để xác định tỷ lệ chính xác trong kiến ​​trúc

Đối với những gì liên quan đến thuật toán, Người đàn ông Vitruvian che giấu một thuật toán bí mật được các nghệ sĩ sử dụng trong nhiều thế kỷ để xác nhận rằng các tác phẩm của họ được lấy cảm hứng từ tỷ lệ thần thánh.

Đôi khi tôi thích nghĩ rằng có lẽ Leonardo da Vinci, qua những tác phẩm tuyệt vời của mình, muốn xác định thuật toán quan trọng nhất, đó là thuật toán của cuộc sống.

Cấu trúc dữ liệu và thuật toán trong Python là gì?

Thuật toán lập trình Python là gì?

Tôi có thể sử dụng Python để học Cấu trúc dữ liệu và Thuật toán không?

Lập trình DSA là gì?