Computation theory, state machine and competitive programming

Bài viết nằm trong chuỗi chủ đề nghiên cứu của hard-core team. Trong thời gian sắp tới tôi đang nghiên cứu về computational theory. Đây là một chủ đề hết sức thú vị mà thông qua đó chúng ta sẽ nhìn lại lịch sử của máy tính, chúng ta sẽ hiểu được bản chất của một chương trình máy tính, tại sao nó lại chạy được, tại sao mô hình của một chương trình lại có thể chạy trên bất cứ máy tính nào miễn là nó có CPU và memory.

Máy tính đơn giản nhất

Một chiếc máy tính hiện đại thì vô cùng phức tạp, để hiểu hết nguyên lý hoạt động của một chiếc máy tính bạn phải hiểu từ hardware (thế nào là bán dẫn, thế nào là cổng NAND,...). Tuy nhiên để hiểu nguyên lý về làm thế nào một chiếc máy tính hiểu và chạy một chương trình chúng ta input vào thì không phức tạp đến vậy.

Một chiếc máy tính thông thường sẽ gồm một lượng lớn bộ nhớ mà có thể mất đi (RAM) và bộ nhớ tồn tại vĩnh viễn (hard drive hoặc SSD), một hoặc nhiều input/output device, và một vài bộ vi xử lý có nhiệm vụ thực thi các câu lệnh (instruction). Tuy nhiên để tổng quát hoá lại toàn bộ cách hoạt của một chiếc máy tính, thì có một mô hình vô cùng đơn giản gọi là State machine

State machine

Mô hình state machine đơn giản nhất gọi là Deterministic Finite Automata, có nghĩa là "Ôtômát hữu hạn đơn định" (mình nghĩ cái tên tiếng Anh có vẻ dễ hiểu hơn nên sẽ sử dụng tên tiếng Anh cho đến cuối bài). Một finite automaton không có bộ nhớ cố định (permanent storage) nào, cũng như ko có bộ nhớ lớn. Nó chỉ có bộ nhớ đủ lớn để lưu một trạng thái tại một thời điểm. Tương tự, một finite automaton cũng không có input device để có thể thay đổi input một cách linh hoạt, nó chỉ có thể nhận vào một chuỗi string cố định, đọc từng kí tự một, và trả về một trạng thái cuối cùng.

Bạn có thể coi state machine là một chiếc máy tính tối giản, có chức năng xử lý một đoạn text input đầu vào, và trả về một trạng thái đầu ra. Không giống như những chiếc máy tính hiện đại, chiếc máy tính state machine này chỉ có thể xử lý dựa vào các "rules" mô tả là với một input nhất định, và một trạng thái hiện tại, thì trạng thái tiếp theo sẽ là gì.

Hãy xem ví dụ dưới đây:

alt text

2 vòng tròn thể hiện 2 trạng thái 1 và 2. Mũi tên đến 1 được gọi là start state. Các mũi tên giữa 1 và 2 thể hiện "rule" của chiếc máy tính của chúng ta:

  • Khi ở trạng thái 1, nhận input là character 'a', thì chiếc máy tính của chúng ta sẽ chuyển sang trạng thái 2
  • Khi ở trạng thái 2, nhận input là character 'a', thì chiếc máy tính của chúng ta sẽ chuyển sang trạng thái 1

Tuy nhiên nếu chỉ đơn giản là những rule di chuyển như vậy thì sẽ rất khó để chúng ta có thể "kết thúc" xử lý với một input là chuỗi string. Chiếc máy tính của chúng ta cần có trạng thái cuối cùng, hay gọi là "accepted state". Chính nhơ trạng thái cuối cùng này mà với 1 input cố định, chúng ta sẽ có một output, mà ở đây chính là việc chuỗi input đó có được "accept" bới chiếc máy tính của chúng ta hay không.
alt text

Để mô tả trạng thái "accepted" đó thì chúng ta sử dụng 2 vòng tròn lồng vào nhau như hình ở trên.

Vậy để tổng quát lại về chiếc máy tính state machine của chúng ta, bạn có thể xem bảng dưới đây để dễ hình dung

alt text

Tất nhiên chúng ta vẫn chưa nhắc đến tính "đơn định" (Deterministic) của chiếc máy tính này. Tính chất này vô cùng đơn giản là: 1 input, và 1 trạng thái, sẽ luôn cho ra cùng 1 trạng thái tiếp theo. Tính chất này vô cùng quan trọng để trong các bài tiếp theo chúng ta sẽ đến với Non-Deterministic Finite Automaton.

Đọc đến đây các bạn sẽ thấy khó hiểu: finite machine có cái khỉ gì phức tạp mà lại liên quan đến máy tính nhỉ. Có thể coi finite machine là "building block",hay là những viên gạch nhỏ nhất để xây nên những concept phức tạp hơn mà chúng ta sẽ tìm hiểu ở các bài tiếp theo.

Thử sử dụng State machine trong competitive programming

Để dễ hình dung hơn, tôi sẽ sử dụng state machine để giải thử một bài toán rất đơn giản trên codility: https://codility.com/programmers/lessons/1-iterations/binary_gap/.

Bài toán trên là:

Nhập vào một số int N, hãy tính xem "binary gap" của N là bao nhiêu. Binary gap nghĩa là khoảng cách lớn nhất giữa 2 bit 1 , mà ở giữa toàn bit 0 trên biểu diễn binary của N
Ví dụ: 9 -> 1001 sẽ có binary gap là 2

Giải:
Chúng ta để ý bài toán trên sẽ có 3 trạng thái, khi chúng ta đọc lần lượt các bit của N từ phải sang trái (tạm coi bit ở bên trái ngoài cùng là bit lớn nhất)

  • Trạng thái bắt đầu: khi state machine của chúng ta chưa đọc gì vào
  • Trạng thái đang ở bit 1
  • Trang thái đang ở bit 0

State machine của chúng ta cần có 1 hàm là eat, hàm này sẽ nhận vào input là 1 bit 0 hoặc 1, và trả ra trạng thái tiếp theo, đồng thời update những biến bên trong nó. Lời giải như ở dưới đây, score 100 trên codility. Bạn có thể thấy mô hình state machine còn có một tác dụng rất hữu ích là phân tách các "side effect" trong lập trình nói chung. Do mỗi state chỉ cần quan tâm đến bản thân nó, và input nhận vào, nên khi đứng từ view là các chươnng trình chúng ta sẽ tránh khỏi các đoạn mutable state hay là các đoạn if else lồng nhau rất khó đọc

package algorithm.codility.Problem1;

public class Solution {
    interface State {
        State eat(int input);
        int getNum0();
        int getMax0();
    }

    abstract static class Stateful implements State {
        int num0;
        int max0;
        Stateful(int num0, int max0) {
            this.num0 = num0;
            this.max0 = max0;
        }
        @Override
        public State eat(int input) {
            return this;
        };
        @Override
        public int getNum0() {
            return num0;
        }
        @Override
        public int getMax0() {
            return max0;
        }
    }

    //zero state
    class State0 extends Stateful implements State {
        State0(int num0, int max0) {
            super(num0, max0);
        }
        @Override
        public State eat(int input) {
            super.eat(input);
            if (input == 1) {
                return new State2(0, 0);
            } else {
                return new State0(0, 0);
            }
        }
    }

    //current bit is 0
    class State1 extends Stateful implements State {
        State1(int num0, int max0) {
            super(num0, max0);
        }
        @Override
        public State eat(int input) {
            super.eat(input);
            if (input == 1) {
                max0 = this.num0 > max0 ? this.num0 : max0;
                return new State2(0, max0);
            } else {
                return new State1(this.num0 + 1, max0);
            }
        }
    }

    //current bit is 1
    class State2 extends Stateful implements State {
        State2(int num0, int max0) {
            super(num0, max0);
        }
        @Override
        public State eat(int input) {
            super.eat(input);
            if (input == 1) {
                return new State2(0, max0);
            } else {
                return new State1(1, max0);
            }
        }
    }

    public int solution(int N) {
        State s = new State0(0, 0);
        while (N > 0) {
            int bit = N & 1;
            s = s.eat(bit);
            N >>= 1;
        }
        return s.getMax0();
    }

    public static void main(String[] args) {
        System.out.println(new Solution().solution(1610612737));
    }
}

Bình luận


White
{{ comment.user.name }}
Bỏ hay Hay
{{comment.like_count}}
Male avatar
{{ comment_error }}
Hủy
   

Hiển thị thử

Chỉnh sửa

White

huydx

118 bài viết.
1028 người follow
Kipalog
{{userFollowed ? 'Following' : 'Follow'}}
Cùng một tác giả
White
163 15
Introduction (Link) là một cuộc thi ở Nhật, và cũng chỉ có riêng ở Nhật. Đây là một cuộc thi khá đặc trưng bởi sự thú vị của cách thi của nó, những...
huydx viết 2 năm trước
163 15
White
132 15
Happy programmer là gì nhỉ, chắc ai đọc xong title của bài post này cũng không hiểu ý mình định nói đến là gì :D. Đầu tiên với cá nhân mình thì hap...
huydx viết hơn 3 năm trước
132 15
White
124 14
Một ngày đẹp trời, bạn quyết định viết một dịch vụ web dự định sẽ làm thay đổi cả thế giới. Dịch vụ của bạn sẽ kết nối tất cả các thiết bị di động ...
huydx viết 29 ngày trước
124 14
Bài viết liên quan
White
9 0
Logic Gate Trước khi nói về cổng NAND, ta hãy tìm hiểu xem logic gate là gì? Logic gate hiểu nôm na nó là một con chip làm một chức năng gì đó cụ...
Cẩm Huỳnh viết gần 2 năm trước
9 0
{{like_count}}

kipalog

{{ comment_count }}

bình luận

{{liked ? "Đã kipalog" : "Kipalog"}}


White
{{userFollowed ? 'Following' : 'Follow'}}
118 bài viết.
1028 người follow

 Đầu mục bài viết

Vẫn còn nữa! x

Kipalog vẫn còn rất nhiều bài viết hay và chủ đề thú vị chờ bạn khám phá!