Viblo Algorithm

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 ...

Trong bài viết này, chúng ta cùng thảo luận về một dạng đặc biệt của ma trận đó là ma trận vuông, cùng với đó là một thao tác tính toán cơ bản nhưng rất quan trọng trên ma trận đó là lũy thừa ma trận.

Một số định nghĩa và ví dụ

Trước khi bắt đầu thảo luận về lũy thừa của ma trận, ta cần làm rõ một số khái niệm sau:

• Ma trận vuông là ma trận có số hàng bằng số cột.
• Với ma trận vuông , ta c...

Ma trận là một khái niệm rất cơ bản trong toán học nhưng nó lại có vai trò to lớn trong nhiều lĩnh vực và đóng góp nhiều ứng dụng thực tế. Trong lập trình thi đấu, việc thao tác tính toán trên ma trận với các bài toán hay và khó là điều không thể tránh khỏi. Đôi khi chỉ là những thao tác rất cơ bản như nhân ma trận cũng cần phải tối ưu một cách triệt để. Trong bài viết này, mình sẽ trình bày mộ...

Trong bài viết này mình sẽ giới thiệu về trò chơi liên quan tới sự hợp tác (Cooperative games) Khác với 3 loại trò chơi mà mình giới thiệu trong các bài viết trước cần có sự cạnh tranh giữa các người chơi để tối ưu phần thưởng cho từng cá nhân. Trong trò chơi có sự hợp tác, trọng tâm ở đây là cần kết hợp lại với nhau để thu được phần thưởng lớn nhất cho các bên. Cụ thể hãy xem các ví dụ bên dướ...

Trong hai phần đầu của chuỗi bài viết giới thiệu lý thuyết trò chơi, mình đã trình bày ví dụ về 2 loại trò chơi đó là Zero-Sum Games và Nonzero-Sum Games. Đây là những trò chơi mà người chơi chỉ được chọn duy nhất 1 lần, độc lập và cùng lúc với người chơi còn lại. Trong các trò chơi bắt nguồn từ các tình huống kinh tế hoặc chính trị ngoài đời thực, điều này thường không xảy ra. Người chơi có th...

Trong bài viết trước, mình đã giới thiệu cho các bạn về lý thuyết trò chơi và hai ví dụ kinh điển trong Zero-Sum Games. Trong bài viết này, mình sẽ tiếp tục trình bày các ví dụ về loại trò chơi khác đó là Nonzero-Sum Games.

Nonzero-Sum Games

Bài toán hai tù nhân

Bài toán như sau, hai tù nhân (người chơi 1 và 2) phạm tội cùng nhau và bị thẩm vấn riêng. Mỗi tù nhân chỉ có hai lựa chọn: Anh ta ...

Thời gian gần đây nổi lên một bộ phim rất nổi tiếng của Hàn Quốc là Squid Game. Bộ phim đang là cơn sốt trên toàn thế giới, ắt hẳn bạn cũng là người đã xem bộ phim đó chứ Đã chơi game thì ai cũng muốn dành chiến thắng Tất nhiên, trong bất cứ game nào cũng vậy, luôn có những tips và tricks để bạn gia tăng khả năng thắng trò chơi. Trong lập trình thi đấu, vấn đề về các trò chơi được khai th...

III. Bài toán tìm thành phần liên thông mạnh - giải thuật Tarjan

1. Định nghĩa thành phần liên thông mạnh

Đối với đồ thị có hướng, ta có ba định nghĩa về tính liên thông:

• được gọi là liên thông mạnh (strongly connected) nếu với mọi cặp đỉnh phân biệt , ta có đến được và đến được .
• được gọi là liên thông yếu (weakly connected) nếu như đồ thị vô hướng nền của nó là liên thông (tức là ...

I. Cây DFS và bài toán định chiều đồ thị

1. Phân loại các cung trên cây

Trong quá trình duyệt đồ thị, với mỗi đỉnh ta có được đỉnh là đỉnh cha của đỉnh trên đường đi. Nếu xây dựng đồ thị con gồm các cạnh có dạng ta sẽ thu được một cây, gọi là cây . Hình vẽ dưới đây biểu diễn một cây với $9\text{DFS}\text{DFS}$.

Trên đồ thị có hướng, xét mọi...

Như mình đã trình bày trong bài viết trước, tìm kiếm nhị phân trên một mảng thể hiện sự hiệu quả. Tuy nhiên, hiệu suất của việc tìm kiếm trên mảng bị giảm đi rất nhiều khi dữ liệu trong tập dữ liệu thay đổi thường xuyên. Với tập dữ liệu động, ta phải áp dụng cấu trúc dữ liệu khác để duy trì hiệu suất tìm kiếm ở mức chấp nhận được.

Cây tìm kiếm là cấu trúc dữ liệu phổ biến nhất được sử dụng để ...

Tìm kiếm nhị phân là một thuật toán cơ bản trong khoa học máy tính. Thay vì tìm kiếm một phần tử trong mảng một cách tuyến tính duyệt từng phần tử, tìm kiếm nhị phân cho ta cách tìm kiếm tối ưu hơn bằng cách sắp xếp các phần tử trước khi truy vấn. Cụ thể như nào các bạn hãy theo dõi bài viết nhé

Phân tích thuật toán

Đặt vấn đề

Hãy thử tưởng tượng bạn đang cần tìm một từ trong cuốn sách từ...

I. Giới thiệu

Quy hoạch động trên cây (), là một dạng bài quy hoạch động đặc biệt, sử dụng để giải các bài toán quy hoạch động trên đồ thị có dạng cây. Ở dạng bài này, thường sẽ phải tìm công thức truy hồi cho các nút trên cây dựa vào các nút con của nó. Khi đặt hàm mục tiêu, thường sẽ xuất hiện $1ii$. Dạng bài này giống với quy hoạch động thông thường, khi chúng ta cần xác định cấu trúc con t...