Algorithms

Programming Pearls

Programing Pearls - Jon Bentley Xuất sắc. Chưa có một cuốn sách nào về lập trình khi tôi mua về, khui thùng của Amazon ra và lượn 1, 2 trang để thốt lên 1 từ “xuất sắc” cả. Điểm qua một số sách về “Algorithms” mà tôi từng đọc và tìm hiểu: CLRS: về mặt lý thuyết, đây thực sự là “introduction” nhưng đầy đủ và chi tiết. Tôi không quá ấn tượng bởi cách viết và mã giả.

Có bao nhiêu cách cài đặt Hàng đợi ưu tiên?

Cấu trúc Hàng Đợi Ưu Tiên (priority queues) là một trong những CTDL kinh điển trong KHMT với rất nhiều ứng dụng khác nhau, có thể kể đến như: CTDL quan trọng cho các thuật toán khác như Dijkstra’s Algorithms. Numerical Optimization: một vài thuật toán optimization (đặc biệt là iterative optimization) phải chọn ra những biểu thức có sai số làm tròn cao nhất/thấp nhất để thực thi.

Một số biến thể Quicksort

Trước tiên là ôn lại một chút về quicksort. Dưới đây là bản implement (đơn giản) của thuật toán nổi tiếng này: // quicksort implement template<typename T> int partition(vector<T>& a, int lo, int hi) { int i = lo, j = hi; T v = a[lo]; while (true) { while (a[++i]<=v) if (i == hi) break; while (v<=a[–j]) if (j == lo) break; if (i >= j) break; swap(a[i], a[j]); } swap(a[lo], a[j]); return j; } template<typename T> void quicksort(vector<T>& a, int lo, int hi) { if (lo >= hi-1) return; int j = partition(a, lo, hi); quicksort(a, lo, j); quicksort(a, j+1, hi); } Phân tích Độ phức tạp được đánh giá thông qua hàm:

Giải thuật tìm kiếm Fibonacci

Mình không tìm được từ nào tiếng Việt có thể dịch được từ “Fibonaccian Searching”, nếu “binary searching” có thể dịch là “tìm kiếm nhị phân”, thì “Fibonaccian Searching” không có ngữ nghĩa gì nhiều. Nguồn gốc thuật toán này xuất phát từ bài tập 1.4.22 (Algorithms, Fourth Edition, Sedgewick). Ngoài ra đây cũng là một nội dung được đề cập trong TAoCP - Vol 3. Lịch sử Thuật toán được để xuất bởi Devid E.

Đọc "Nghệ Thuật Lập Trình" (TAoCP)

Phải thành thật, mình là fanboy của Donald Knuth. Có thể có rất nhiều giáo sư có tầm ảnh hưởng lớn đến các hướng mà mình quan tâm (khoa học máy tính/ trí tuệ nhân tạo hay thị giác máy tính) như Hinton, Li Fei-Fei, Zisserman, Pascal Fua. Nhưng có rất ít nhà khoa học mà mình dành trọn thời gian để có thể tìm hiểu và “cuồng” như Donald Knuth.

An adventure in The Art of Computer Programming

My notes whilst reading TAoCP

Bài toán chuyển ngày sang thứ

Đôi khi có những thuật toán chỉ khiến bạn thốt lên: “xuất sắc, thông minh vãi cả đxx” Bài toán: Cho ngày, tháng, năm bất kì theo lịch Gregorian (lịch hiện nay), cho biết hôm đó rơi vào thứ mấy, tương ứng 0 -> Chủ Nhật, 1 -> Thứ Hai … Tôi đang muốn nói tới phương pháp của Sakamoto được đề xuất năm 1992. (Code theo chuẩn K&R C).

Các thuật toán ngẫu nhiên

Các ví dụ về thuật toán ngẫu nhiên Tiếp tục seri về thuật toán ngẫu nhiên, trong bài viết này mình ghi lại 3 ví dụ điển hình trong họ bài toán này. Tất cả các ví dụ đều nằm trong cuốn sách Randomized Algorithms Randomized Quicksort Thuật toán quicksort có lẽ là một trong những thuật toán khá dễ hiểu khi tìm hiểu về các thuật toán ngẫu nhiên.

Dẫn nhập thuật toán ngẫu nhiên

Hôm rồi học course Introduction to Algorithm (2006-MIT) mình được biết qua khái niệm Randomized Algorithms, dành một buổi tìm hiểu về họ thuật toán thú vị này vậy. Định nghĩa Randomized Algorithms (viết gọn là randalgs) là những thuật toán mà trong các bước xử lý có sử dụng số ngẫu nhiên để quyết định cho các bước tính toán tiếp theo. Điểm thú vị của randalgs chính là nó không quan tâm đến trường hợp xấu nhất mà chỉ quan tâm đến kì vọng trong trường hợp xấu nhất.

Review Algorithms (Princeton) - Coursera

Đây là một trong những khoá rất đỉnh về lập trình, vì sao ư? Kiến thức được dạy vững chắc và có nhiều thông tin rất thú vị và bổ ích. Bài tập lập trình rất hay. Bài tập trắc nghiệm giúp người học hiểu rõ hơn về các thuật toán và cấu trúc dữ liệu trong bài giảng. Các câu hỏi phỏng vấn rất hay và sáng tạo.