Viblo Algorithm

Thống kê các thuật toán Sorting

Chúng ta đã xem xét nhiều thuật toán sắp xếp, cơ mà bạn có bao giờ tự hỏi mình nên sử dụng thuật toán sắp xếp nào không . Việc biết thuật toán nào là tốt nhất có thể phụ thuộc nhiều vào chi tiết của ứng dụng và cách triển khai. Trong bài viết này mình sẽ tổng kết các thông tin của các thuật toán sắp xếp giúp cho bạn có cái nhìn tổng quan về các thuật toán này....

Giới thiệu

Trong các bài viết trước về những thuật toán phổ thông, ta đã nghiên cứu và ứng dụng vào những vấn đề cụ thể. Những thuật toán này đều có những kĩ thuật xử lý của riêng chúng. Sẽ thật tuyệt với nều như nếu tất cả các vấn đề đều được giải quyết bằng các thuật toán hiệu quả sao cho các thuật toán này được thiết kế bởi một tập nhỏ các kĩ thuật. Nhưng không phức tạp thì không phải cuộc ...

Giới thiệu

Tất cả các thuât toán phổ thông trong chương trình cấp 3 và trong môn Cấu trúc dữ liệu và giải thuật tại Đại học mà chúng ta tìm hiểu đều là các thuật toán thời gian đa thức. Đó là từ đầu vào có kích thước , thời gian thực hiện thuật toán trong trường hợp xấu nhất là với một hằng . Một câu hỏi rất tự nhiên đặt ra là: Tất cả các bài toán có thể giải theo thời gian đa thức không? Câu...

Giới thiệu

Bài viết này đề cập đến các trò chơi hai người chơi, trong đó mỗi người chơi chọn từ rất nhiều chiến lược thuần túy hoặc ngẫu nhiên trong số các chiến lược và tổng phần thưởng của những người chơi luôn bằng 0.

Định nghĩa và định lý cơ bản

Vì tất cả dữ liệu của một trò chơi có tổng bằng 0 hữu hạn hai người có thể được tóm tắt trong một ma trận, những trò chơi như vậy được gọi là ma...

Mô tả vấn đề

Cho một xâu có độ dài . Tìm tất cả các cặp sao cho xâu con là một palindrome. Xâu là một palindrome khi và chỉ khi ( là xâu đảo ngược của xâu ban đầu).

Trong trường hợp xấu nhất, xâu có thể có tối đa xâu con palindromic. Khi mới đầu quan sát, ta thấy có vẻ như không có thuật toán với độ phức tạp tuyến tính nào giải quyết vấn đề này.

Tuy nhiên thông tin về các palindromes c...

I. Cấu trúc dữ liệu deque - Hàng đợi hai đầu

1. Giới thiệu chung

Khi học lập trình C++, có lẽ chúng ta đều đã biết đến hai container stack và queue - hai cấu trúc dữ liệu ngăn xếp và hàng đợi được xây dựng sẵn trong thư viện STL C++. Nếu tưởng tượng cả hàng đợi và ngăn xếp được biểu diễn bằng mảng, thì hàng đợi sẽ hỗ trợ chúng ta lấy phần ...

I. Tổng quan

Khái niệm về đường đi và chu trình Hamilton được đưa ra bởi William Rowan Hamilton vào năm $1856,2030125$ đỉnh cho trước (còn gọi là trò chơi Icosian).

Bài toán tổng quát được Hamilton đưa ra là: Tìm một chu trình đơn đi qua tất cả các đỉnh trên đồ thị, mỗi đỉnh đúng một lần sau đó quay trở về điểm xuất phát. Cho đến nay, bài toán này...

I. Xác định chu trình trên đồ thị

Từ những bài viết đầu tiên về chuyên đề Lý thuyết đồ thị, tôi đã giới thiệu tới các bạn khái niệm về Chu trình trên đồ thị. Một đường đi trên đồ thị được gọi là một chu trình nếu như và nếu như các cạnh trên đường đi đó đều phân biệt. Ngoài ra, trên đồ thị còn có thể tồn tại hai dạng chu trình đặc biệ...

I. Tổng quan

Những lý thuyết cơ bản của lý thuyết đồ thị chỉ mới được đề xuất từ thế kỷ XVIII, bắt đầu từ một bài báo của Leonhard Euler về bài toán $7$ cây cầu ở Königsberg - một bài toán cực kỳ nổi tiếng:

Thành phố Königsberg thuộc Đức (nay là Kaliningrad thuộc CHLB Nga) được chia làm $41736,7147$ chiếc cầu, mỗi chiếc đúng một lần rồi lạ...

I. Đặt vấn đề

Một vấn đề rất quan trọng trong Lý thuyết đồ thị là bài toán duyệt tất cả các đỉnh có thể đến được từ một đỉnh xuất phát nào đó, không duyệt lặp lại cũng như không bỏ sót đỉnh nào cả. Vì vậy, ta phải xây dựng được những phép duyệt các đỉnh của đồ thị theo một hệ thống nhất định, những phép duyệt đó gọi là các thuật toán tìm kiếm trên đồ thị.

Có hai giải thuật tìm kiếm trên đồ th...

I. Ma trận kề (Adjacency Matrix)

Giả sử là một đa đồ thị có số đỉnh là . Coi rằng các đỉnh được đánh số từ $1NadjN\times N$, trong đó:

• nếu .
• nếu và là số lượng cạnh nối giữa và .
• Đối với với , có thể đặt giá trị tùy theo mục đích, thông thường nên đặt bằng $0$.

Cài đặt: Việc cài đặt cạnh sẽ thay đổi tùy vào đồ thị là có hướng hay vô hướng. Dưới đây sẽ trình bày cài đặt cho đồ thị...

I. Khái niệm về đồ thị

1. Sơ lược về Lý thuyết đồ thị

Trong Toán học và Tin học, Lý thuyết đồ thị tập trung nghiên cứu về một đối tượng cơ bản là đồ thị - một đối tượng có tính ứng dụng rất cao trong thực tế. Mô hình đồ thị xuất hiện xung quanh ta, trong nhiều lĩnh vực của cuộc sống, như giao thông, cấu trúc website,...

Mô hình bài toán 7 cây cầu ở Königsberg

Người đặt nền móng cho sự phát ...

I. Tổng quan

1. Giới thiệu phương pháp

Trong bài viết trước, tôi đã giới thiệu tới các bạn về giải thuật Nhánh và Cận để giải bài toán tối ưu (nhấn vào đây để đọc lại bài viết). Mặc dù phương pháp Nhánh và Cận đã cải tiến từ phương pháp Quay lui nhằm loại bỏ đi nhiều nhá...

I. Tổng quan

1. Giới thiệu phương pháp

Trong lập trình cũng như trong thực tế, chắc hẳn các bạn đều đã gặp những bài toán với yêu cầu tìm kết quả tốt nhất thỏa mãn một hoặc một số điều kiện nào đó. Sự thật là chúng ta gặp các bài toán này khá thường xuyên, thậm chí vô cùng thực tiễn, chẳng hạn như:

• Tìm cách trả số tiền với tờ t...

I. Lời mở đầu

Chắc hẳn, ai trong số chúng ta khi bắt đầu học Tin học đều nghe qua khái niệm: Cấu trúc dữ liệu (Data Structures) và Giải thuật (Algorithm). Không sai, đây chính là hai chủ đề lớn và vô cùng quan trọng trong Lập trình thi đấu nói riêng và trong Công nghệ thông tin nói chung. Nhà khoa học máy tính Niklaus Wirth đã từng nói một câu rất n...

I. Tổng quan về thư viện STL C++

Đã là dân lập trình, đặc biệt lại sử dụng ngôn ngữ C++, thì chắc chắn không ai trong số chúng ta không biết đến thư viện Template chuẩn C++ (Standard Template Library). Thư viện này cung cấp rất nhiều thứ hỗ trợ sẵn cho lập trình viên trong quá trình làm việc, trong số đó có những thuật toán cơ bản. Một trong số những thuật toán mà STL C++ hỗ trợ là Ti...

I. Bài toán Tìm kiếm nhị phân tổng quát

Ở bài viết trước, tôi đã giới thiệu tới các bạn những khái niệm cơ bản nhất về bài toán tìm kiếm trong Tin học, cũng như giới thiệu về hai giải thuật Tìm kiếm tuần tự và Tìm kiếm nhị phân (xem lại tại đây). Trong bài v...

I. Mở đầu về bài toán tìm kiếm

1. Tìm kiếm - một khái niệm quen thuộc trong cuộc sống

Có bao giờ bạn phải đau đầu vì để quên chiếc ví ở đâu đó trong nhà mà tìm mãi không thấy? Hay việc các bạn nữ luôn không thể nào tìm thấy bộ quần áo phù hợp để lên phố mặc dù số lượng trang phục xếp nặng trĩu trong tủ quần áo? Cuộc sống chúng ta luôn gắn liền với việc tìm kiếm. Từ một đứa trẻ tò mò tìm kiếm ...

Giới thiệu

Toán học là làm việc với những con số và các phép tính. Khi làm việc với những con số và các phép tính như vậy, ta có thể phát hiện ra những con số, phương trình hay ma trận có những tính chất rất đẹp và Ma phương là một trong số đó. Hãy thử tìm hiểu tất cả những điều hay ho của ma phương nhé.

Một ma phương là một ma trận vuông sao cho tổng các số trong mỗi hàng, mỗi cột và 2 đư...

I. Đặt vấn đề

Chắc hẳn, ai trong chúng ta cũng đã quá quen thuộc với bài toán đếm số ước nguyên dương của . Giải thuật thông thường nhất mà mọi người thường sử dụng là giải thuật dựa trên một nhận định rằng nếu như số có một ước là thì nó cũng sẽ có một ước nữa là . Bằng phương pháp này, chúng ta có thể giải quyết mọi bài toán với giới hạn khoảng $10^{15}$ trở xuống (Các bạn xem lại trong ...