About Aida Nana

Nghề chính là chém gió, quăng bom và ném lựu đạn.
Nghề phụ là cắt cỏ, chém chuối, cưa cây……

Giói thiệu về ngôn ngữ lập trình Go

Ở đây, tui sẽ giới thiệu một ngôn ngữ còn khá lạ lẫm với người Việt, đó là Go – một ngôn ngữ lập trình Server-side được phát triển bởi Google. Ngôn ngữ Go được phát triển từ năm 2007 bởi Robert Griesemer, Rob Pike, và Ken Thompson ở Google. Đến nay có thêm Ian Lance Taylor, Russ Cox và Andrew Gerrand tham gia với vai trò là một trong những thành viên trụ cột.

Tới thời điểm này, khá nhiều ngôn ngữ đã ra đời phục vụ việc lập trình cho phía Server-side như: PHP, Ruby on Rails, Python, NodeJs… Mỗi ngôn ngữ đều có những ưu khuyết điểm riêng. Những riêng Go thì khá là toàn diện.

Giới thiệu Go

Go là một ngôn ngữ lập trình đồng thời (Concurrent Program) được Google giới thiệu lần đầu tiên vào nằm 2009. Go được các thành viên phát triển nói đến về một ngôn ngữ cho server, được phát triển cho cộng đồng trên nền C.

Go được ví như C – rút gọn. Những gì bạn có thể viết được trên C, bạn có thể viết được trên Go với tốc độ nhanh hơn gấp 5 lần với khác biệt rất nhỏ. Có thể đối với những bạn thường lập trình trên C# hay Java thì Go nhìn có vẻ khá lạ lẫm, nhưng khi bạn đã làm quen dc với Go, bạn sẽ thấy Go khá thú vị và tốc độ lập trình rất nhanh (như tui đã đề cập trước đó)

Một trong những điểm tui thích nhất ở Go là tốc độ xử lý. Trong khi C được đánh giá có tốc độ xử lý cực nhanh, thì Go chỉ bị C bỏ lại với khoảng cách rất gần! Trước khi nhìn vào benchmark của Go, tui sẽ giởi thiệu với các bạn các cú pháp syntax Go chuẩn, các kiểu dữ liệu cơ bản, và so sánh nó với C.

Go, một ngôn ngữ server ngắn gọn

Nói đến đây, bạn có thấy Go thú vị và hấp dẫn hơn một tẹo rồi phải không? Mong là vậy! Dù rồi hay chưa, tui sẽ tăng tính thuyết phục và đặc sắc của Go bằng cách cho bạn xem những syntax đẹp và so sánh nó với C! Thứ nhất, khai báo biến (variable) trong Go vô cùng ngắn gọn. Thay vì khai báo cụ thể kiểu dữ liệu của biến, Go có bộ tham chiếu kiểu dữ liệu (type inference) thực hiện việc gán kiểu và khởi tạo biến cho chúng ta. Để khai báo một biến đơn giản… Trong C:

int myVar = 33;
Trong Go:
myVar := 33
Ngắn gọn hơn C, bạn có thể thấy như thế! Không chỉ có thế, Go không đòi hỏi kết thúc câu lệnh bằng dấu “;”, trả về nhiều kết quả trong function, và có thể trả về cặp (pair) kết quả và lỗi cho bạn (result, err). Pair cũng là cách chuẩn để xử lý lỗi trong Go. Tôi sẽ đề cập kỹ hơn ở các bài viết về syntax trong Go. Hơn vậy, bạn có thể định nghĩa một biến bằng utf-8, một điều khá mới mẻ trong Go, ví dụ: biếnSố := 33 Bây giờ, ta tiến hành xét một chương trình Hello World trong Go và C:

helloworld.c

#include <stdio.h>
 
int main ()
{
  printf ("Hello World!\n");
}
helloworld.go
package main
 
import (
    "fmt"
)
 
func main() {
    fmt.Println("Hello World!")
}
Chúng ta có thể thấy được sự tương đồng giữa Go và C qua đoạn code trên Bạn sẽ thấy được Go ngắn gọn hơn C rõ ràng hơn khi bạn viết các chương trình lớn, phức tạp và cần xử lý đồng thời (concurrency). Có một bài blog so sánh C và Go, cũng như các chi tiết về những lợi thế về syntax của Go so với C: http://www.syntax-k.de/projekte/go-review Tiếp theo. chúng ta sẽ so sánh khả năng chịu tải của Go để xem Go có thực sự chịu tải tốt đúng như tuyên bố của những lập trình viên hay không

Khả năng chịu tải của Go

Hãy nhìn cách Go chạy một loạt các chương trình đơn giản nhưng lặp đi lặp lại trong bảng dưới đây:

( Website test trực tuyến: http://benchmarksgame.alioth.debian.org/ )

Như chúng ta thấy từ số liệu thống kê, Golang hiệu quả hơn Ruby rất nhiều!!! Trong chương trình đầu tiên – ‘fasta-redux’, Ruby mất 110 giây để thực thi xong, nhưng Go chỉ mất 1.79 giây. Nhanh hơn gấp gần 100 lần! Quá ấn tượng phải không!!!

Go không chỉ ấn tượng về tốc độ xử lý, mà còn thuận lợi về xử lý đồng thời hơn hầu hết các ngôn ngữ server hiện giờ. Go sử dụng các Goroutines (tui sẽ nói rõ hơn về Goroutlines ở những bài viết sau).

Go đã cung cấp được chúng ta một ngôn ngữ lập trình ở server với tốc độ cực nhanh, một cú pháp ngắn gọn, hằng trăm package mặc định hữu dụng, cơ chế xử lý đa luồng đồng thời, và vô số thư viện được phát triển bởi các lập trình viên trên khắp thế giới. Tất cả giúp chúng ta xây dựng website, server bằng Go một cách nhanh và hiệu quả nhất.

Tóm tắt

Với tuổi đời còn khá non trẻ (từ 2009) so với những ngôn ngữ khác (C hơn 40 năm, C++ hơn 30 năm, Ruby khoảng 20 năm, Java cỡ 17 năm, C# tầm 10-12 năm…) thì 5 năm thực sự là khoảng thời gian không nhiều để ta so sánh những sản phẩm nổi bật được viết và phát hành bằng Go so với những ngôn ngữ khác. Tuy nhiên, Go đang được Google và cộng đồng lập trình viên tiếp tục phát triển và hoàn thiện. Tin vui là hiện nay, cộng đồng quan tâm đến Go trên thế giới không nhỏ!

Cộng đồng Go lớn nhất hiện nay trên thế giới là Gopherarcademy, bên cạnh đó còn cóGoMeetUp

Một trong những event lớn về Go trong thời gian gần đây là ngày 23 – 25/01/2015 vừa qua, GopherGala đã đứng ra tổ chức sự kiện Hackathon đầu tiên cho Go trên toàn thế giới

Go đang dần được chấp nhận và triển khai rộng rãi trên nhiều Startup và Công ty thương mại. Nhiều nhà cung cấp Saas/ Paas sử dụng Go trong dự án của họ. Dịch vụ gửi mail SendGrid cũng đang áp dụng Go để xây dựng hệ thống mạnh mẽ hơn, nhanh hơn và đáng tin cậy hơn!

Túm cái váy lại, nếu bạn đang tìm kiếm một ngôn ngữ lập trình đồng thời, song song, đơn giản, sexy và tuyệt vời, hãy đến với Go!

MINROAD – spoj

Đề bài

Thuật toán

Ta lưu 2*n điểm vào mảng T:

  • T[i].d là khoảng cách đến vị trí bắt đầu của con đường
  • T[i].k là 1 nếu là cây tùng, là 2 nếu là cây trúc

Sắp xếp mảng T theo thứ tự tăng dần T[i].d

Với mỗi T[i], ta phải tìm vị trí X sao cho từ T[i] đến T[x] có ít nhất a cây tùng và b cây trúc. Đặt F[i]=X.

Dễ dàng nhận thấy: F[i] <= F[i+1] nên ta có thể sử dụng 2 vòng For để tính toán kết quả như sau:

For i=1 to 2*N do 
 For j=F[i-1] to 2*N do ……..
Thay vì dùng mảng F, bạn hoàn toàn có thể sử dụng biến chạy mà thôi

Độ phức tạp: O(N log N).

Code

uses    math;
const   fi='';
        fo='';
        maxn=300000;
type    arra=array[0..maxn] of longint;
var     tung,cuc,d,tu,cu:arra;
        kieu:array[0..maxn] of byte;
        i,j,n,a,b:longint;
        f:text;
        res,tmp:longint;
procedure QS(l,r:longint);
Var i,j,x,w:longint;
Begin
x:=d[(l+r) div 2];
  i:=l;j:=r;
  Repeat
    While(d[i]<x) do i:=i+1;
     While (x<d[j]) do j:=j-1;
      If i<=j then
        Begin
          w:=kieu[i];kieu[i]:=kieu[j];kieu[j]:=w;
          w:=d[i];d[i]:=d[j];d[j]:=w;
          i:=i+1;j:=j-1;
        End;
 until i>j;
 If l<j then QS(l,j);
 If i<r then QS(i,r);
End;
procedure nhap;
begin
    assign(f,fi);
    reset(f);
    readln(f,n,a,b);
    for i:=1 to n do
        readln(f,d[i],kieu[i]);
    close(f);
end;
procedure xuly;
var     t,c,k:longint;
begin
    t:=0; c:=0;
    qs(1,n);
    for i:=1 to n do
        if kieu[i]=1 then begin inc(t); tung[t]:=i; end
        else begin inc(c); cuc[c]:=i; end;
    for i:=1 to n do
    begin
        tu[i]:=tu[i-1];
        cu[i]:=cu[i-1];
        if kieu[i]=1 then inc(tu[i]);
        if kieu[i]=2  then inc(cu[i]);
    end;
if (tu[n]<a) or(cu[n]<b) then exit;
    i:=max(tung[a],cuc[b]);
    k:=min(tung[tu[i]-a+1],cuc[cu[i]-b+1]);
    res:=d[i]-d[k];
    inc(i);
    while i<=n do
    begin
        tmp:=min(tung[tu[i]-a+1],cuc[cu[i]-b+1]);
        if d[i]-d[tmp]<res then res:=d[i]-d[tmp];
        inc(i);
    end;
end;
procedure xuat;
begin
    assign(f,fo);
    rewrite(f);
    if res=0 then writeln(f,-1) else
    writeln(f,res);
    close(f);
end;
begin
    nhap;
    xuly;
    xuat;
end.

Tạo Makefile trên Go

Makefile thực hiện một số thao tác thường dùng trong Go

Khi làm project Go mình thường tạo một file Makefile có form như này:

Lưu ý nhớ thay &lt;tên-file-binary-muốn-build&gt; thành tên mà bạn muốn build ra.

Makefile

SRC = $(wildcard *.go)
OUT = <tên-file-binary-muốn-build>

CC = go
go = $(shell which go 2> /dev/null)

ifeq (, $(go))
    @printf "\e[91mGo not found!"
endif

$(OUT): clean $(SRC)
    @printf "\e[33mBuilding\e[90m %s\e[0m\n" $@
    @$(CC) build -o $@ $(SRC)
    @printf "\e[34mDone!\e[0m\n"

test: clean
    @printf "\e[33mTesting...\e[0m\n"
    go test ./...
    @printf "\e[34mDone!\e[0m\n"

clean:
    @rm -f $(OUT)
    @printf "\e[34mAll clear!\e[0m\n"

install: $(OUT)
    @printf "\e[33mInstalling\e[90m %s\e[0m\n" $(OUT)
    sudo rm -f /usr/local/bin/$(OUT)
    sudo ln -s $(PWD)/$(OUT) /usr/local/bin/$(OUT)
    @printf "\e[34mDone!\e[0m\n"

uninstall:
    @printf "\e[33mRemoving\e[90m %s\e[0m\n" $(OUT)
    sudo rm -f /usr/local/bin/$(OUT)
    @printf "\e[34mDone!\e[0m\n"
Chức năng gồm có:

Tự động build thành file binary với tên file được định sẵn

Chạy lệnh:

make
alt text

Chạy toàn bộ test của tất cả các packages trong project

Chạy lệnh:

make test

alt text

Build và install vào /usr/local/bin

Nếu viết các ứng dụng command line, thì chức năng này sẽ giúp bạn tiết kiệm thời gian và có thể test thực tế trên môi trường của máy bằng cách copy file binary được build ra vào thư mục /usr/local/bin. Khi đó bạn có thể chạy chương trình của mình ở bất kì thư mục nào trong máy tính.

make install

alt text
Khi không cần dùng nữa hoặc muốn gỡ nó ra thì chạy:

make uninstall

Hướng dẫn cài đặt và viết chương trình với Go

Mình khuyến khích các bạn sử dụng môi trường Unix như Linux hay Mac OS X cho việc dev. Mình không ghét Windows nhưng mà cài đặt môi trường dev trên win rất tốn thời gian và phiền phức (các bạn đã từng cài đặt môi trường Python hay Ruby chắc sẽ đồng ý).

Nếu không có điều kiện sử dụng các môi trường Unix, các bạn có thể dùng Docker hoặc Vagrant, sẽ tiện hơn là cài trực tiếp trên môi trường Windows.

 

Bước 1: Cài đặt Go runtime

 

Windows

Đối với các bạn dùng Windows, cài bằng bộ cài MSI sẽ tiện hơn, nó sẽ tự động config hết mọi thứ cần thiết.

Đầu tiên, tải bộ cài tại đây https://golang.org/dl và chạy file go<version>.windows-386.msi (32 bit) hoặc go<version>.windows-amd64.msi (64 bit), tuỳ vào hệ điều hành bạn đang sử dụng.

 

Linux và Mac OS X

Với các bạn xài môi trường Unix, chúng ta nên cài bằng dòng lệnh.

Chúng ta sẽ cài Go thông qua Homebrew (có thể bỏ qua nếu bạn đã cài trước rồi), khởi động Terminal lên và gõ:

ruby -e "$(curl -fsSL https://raw.githubusercontent.com/Homebrew/install/master/install)"
Sau khi cài xong Homebrew, chúng ta bắt đầu cài Go với lệnh:
$ brew install go --cross-compile-common
Ngồi rung đùi vài phút (hoặc vài giây, hoặc vài tiếng, tuỳ vô đường truyền nhà bạn).

 

Mac OS X Installer

Trên Mac, nếu bạn không thích cài bằng dòng lệnh, có thể tải bộ cài từ trang chủ https://golang.org/dl/ và cài trực tiếp.

Go runtime sẽ được cài vào thư mục /usr/local/go và chúng ta cần setup biến môi trường (PATH) ở bước tiếp theo.

 

Bước 2: Cài đặt biến môi trường

 

Windows

Trên Windows, chúng ta sẽ cài đặt biến môi trường bằng cách click phải vào My Computer chọn Properties, chọn tab Advanced và click nút Environment Variables.

Nếu bạn cài đặt Go vào thư mục mặc định là C:\Go thì bạn cần cấu hình như sau:

  • Tạo một biến mới tên là GOROOT với giá trị là C:\Go
  • Chọn biến PATH có sẵn, thêm vào sau dấu chấm phẩy ; cuối dòng đường dẫn sau: C:\Go\bin;

 

Linux và Mac OS X

Trên các máy Unix, bạn cài đặt biến môi trường bằng cách chỉnh sửa file $HOME/.profile hoặc $HOME/.bash_profile.

Nếu không tìm thấy biến $HOME, có thể thay nó bằng /user/local

Hãy thêm nội dung sau:

export GOROOT=$HOME/go
export PATH=$PATH:$GOROOT/bin
Thế là xong rồi đấy! Đơn giản, phải không nào?

 

Bước 3: Chạy thử

Bây giờ, chúng ta có thể kiểm tra xem Go đã được cài hoàn chỉnh hay chưa, bằng cách gõ lệnh sau vào Terminal (hoặc Command Line trên Windows):

$ go version
Nếu Go được cài đặt đầy đủ thì nội dung output sẽ giống thế này:
go version go1.4.2 darwin/amd64
 

Viết chương trình đầu tiên bằng Go

OK, cài đặt xong rồi thì bắt tay vào code thôi. Chương trình đầu tiên, đoán ra rồi phải không? là chương trình huyền thoại mà bài nào cũng viết: Hello World =))

Chúng ta sẽ tạo một file mới, tên là hello.go và gõ đoạn chương trình sau vào. Nhưng hãy nhớ là: Gõ vào, đừng copy paste!. Phải tự gõ vào mới nhớ được!

package main

import "fmt"

func main() {
    fmt.Printf("Hello Gopher's World!")
}
Gõ xong rồi. Bạn có thấy code nó quái thế nào không?

Không có chấm phẩy cuối dòng, từ khoá func cứ như là Swift vậy, hao hao giống Javascript nữa. Còn cái gì nữa đây? fmt.Printf để in nội dung ra màn hình, có cần phải dài dòng vậy không?

Golang là thế đấy, nếu bạn không thích nó, thì phải tập thích nó đi thôi =))

Bây giờ hãy compile và chạy chương trình với lệnh:

$ go run hello.go
Output sẽ là:
Hello Gopher's World!
Xong rồi đó, chúc mừng, bạn đã viết được chương trình đầu tiên của mình bằng Go rồi đấy =))

Học máy là gì?

Định nghĩa

Với trí tuệ nhân tạo cổ điển, khi mà muốn máy tính hoàn thành một nhiệm vụ thì lập trình viên phải chỉ rõ trong code (mã nguồn) cách thực hiện nhiệm vụ đó như thế nào. Trong khi đó ML, nói một cách đơn giản là tập hợp của những phương pháp giúp cho máy tính có thể học được cách thực hiện những nhiệm vụ đó mà không cần sự chỉ dẫn trực tiếp của con người (Arthur Samuel, 1959).

Những bài toán được giải quyết bởi ML thường là

Những bài toán có quy mô lớn như việc xử lí dữ liệu web, dữ liệu đa phương tiện (multimedia), dữ liệu từ cảm biến (sensors), …
Những bài toán quá phức tạp mà chúng ta không biết lời giải dạng hiện (closed form solution) hoặc không thể lập trình bằng tay được như thị giác máy tính (Computer Vision, CV, giúp cho máy tính có khả năng nhận biết thế giới qua hình ảnh tương tự như thị giác con người), xử lí ngôn ngữ tự nhiên (Natural Language Processing, NLP, giúp cho máy tính có khả năng hiểu được ngôn ngữ của con người), điều khiển robot, xe cộ trong môi trường tự nhiên, …
Một số ví dụ cụ thể về bài toán phù hợp với ML như:

Tìm kiếm trên web: hàng ngày chúng ta cần phải tìm rất nhiều thông tin trên web, việc dùng người duyệt qua hàng tỉ trang web để tìm thứ phù hợp là không khả thi. Các thuật toán ML có khả năng tính toán độ phù hợp giữa câu hỏi của người dùng (query) và nội dung của các trang web và sắp xếp chúng theo thứ tự để trả về cho người dùng.
Lọc spam mail: các hệ thống lọc spam cần phát hiện nhưng email có nội dung khác thường và lừa đảo và ngăn chúng tới được inbox của người dùng. Khác biệt với bài toán trên, chúng ta cần phát hiện ra sự bất thường, đo đạc sự khác nhau giữa những email thông thường và spam.
Nhận dạng ảnh: khác với văn bản, khi mà một ý tưởng thường chỉ có một số nhỏ cách diễn đạt và các cách diễn đạt thường sử dụng những từ ngữ giống nhau hoặc đồng nghĩa, ảnh chụp của cùng một vật thể ở mỗi góc độ khác nhau, điều kiện môi trường khác nhau thì có thể rất khác nhau nếu so sánh ở từng điểm ảnh. Các hệ thống xử lí ảnh cần phải nhận ra những đặc trưng bất biến (invariants) trong những bức ảnh để có thể đạt được độ chính xác cao
Định nghĩa: Bài toán ML một chương trình A được gọi là học từ kinh nghiệm E(xperience) để thực hiện một nhiệm vụ T(ask) nếu như hiệu quả thực hiện P(erformance) của nó tăng lên sau khi được bổ sung E.

Huấn luyện và kiểm tra

Quá trình xây dựng một hệ thống ML thường bao gồm hai giai đoạn: huấn luyện và kiểm tra.

Huấn luyện Quá trình dạy một hệ thống ML học gọi là huấn luyện (training). Huấn luyện thường là việc đưa cho hệ thống ML những ví dụ mẫu (training example) và dựa trên những ví dụ đó, hệ thống phải hiệu chỉnh các tham số (parameters) của mình để có thể cho ra được kết quả đúng ở những ví dụ sau. Quá trình hiệu chỉnh tham số thường sử dụng các thuật toán tối ưu (optimization ví dụ convex optimization, linear optimization, …) và quy hoạch (programming, ví dụ dynamic programming, approximate dynamic programming, …) và nhiều phương pháp toán học, thống kê khác.

Kiểm tra Sau khi hoàn thành huấn luyện, hiệu năng (performance) của một hệ thống thường được ước lượng bằng hiệu năng của nó trên một tập dữ liệu kiểm tra (test set) khác với tập huấn luyện (training set). Quá trình này gọi là kiểm tra (testing) nhằm ước lượng hiệu quả thực sự của hệ thống trong môi trường làm việc. Test set bắt buộc phải khác với training set vì hệ thống được huấn luyện trên training set nên nó sẽ dần thích nghi với những đặc điểm của training set và đạt được hiệu năng cao trên tập này, không phản ánh hiệu năng thực tế của hệ thống trong môi trường làm việc.

Sự tương đồng Quá trình training và testing giống như quá trình dạy học và thi cử trong đời sống. Trong quá trình dạy, giáo viên đưa cho sinh viên rất nhiều bài tập và qua quá trình giải các bài tập đó, sinh viên dần hiểu được bản chất của vấn đề. Tương tự như vậy, chúng ta đưa cho hệ thống ML rất nhiều ví dụ và qua các ví dụ đó, hệ thống dần dần xây dựng hiểu biết về bài toán. Thi cử là để đánh giá hiểu biết của sinh viên, nếu giáo viên đưa cho sinh viên những bài toán đã dùng trong quá trình giảng dạy, sinh viên sẽ dễ dàng đạt được điểm cao hơn hiểu biết thực sự của họ về vấn đề. Do đó, bài toán trong đề thi cần phải khác với những bài toán sử dụng trong quá trình dạy học. Năng lực thực sự của sinh viên, giống như hiệu năng hệ thống ML, là những đại lượng ẩn (hidden variables), chúng ta ước lượng nó thông qua thi cử. Đến đây thì có lẽ mọi người đều hiểu rõ vì sao có tên gọi Machine learning. Tuy nhiên, khi dịch sang tiếng Việt là học máy thì nghe không được xuôi tai cho lắm, :v.

Phân loại hệ thống ML

Các hệ thống ML được phân loại theo cách thức mà người ta huấn luyện nó. Một số nhánh chính của học máy bao gồm:

Học có giám sát (Supervised learning, SL)

Phương pháp này được gọi là có giám sát vì trong quá trình huấn luyện, hệ thống ML cần phải biết được câu trả lời chính xác cho mỗi training example. Với mỗi example, hệ thống đo đạc sự khác nhau giữa câu trả lời đúng và câu trả lời mà nó đưa ra. Mục tiêu của training là làm giảm độ sai lệch giữa tập hợp câu trả lời đúng và tập hợp câu trả lời của hệ thống. Mỗi mẫu dùng để huấn luyện bao gồm 2 phần: các đặc trưng để mô tả vật mẫu (features) và nhãn của mẫu (label).

Ví dụ một hệ thống SL dùng để phân loại trái cây thì mỗi training example sẽ có thể có dạng như sau: (màu sắc, vị, cân nặng : tên loại quả), (đỏ, ngọt, 130gram : táo), (vàng, chua, 200gram : cam), … Độ sai khác cho mỗi mẫu là 1 nếu như hệ thống đưa ra câu trả lời sai, 0 nếu câu trả lời đúng. Độ sai khác được tính cho toàn bộ các mẫu trong training set. Huấn luyện nhằm giúp hệ thống đạt được độ sai khác thấp hơn so với lúc ban đầu.

SL thường có hiệu năng cao hơn các phương pháp khác nhưng quá trình huấn luyện tốn kém hơn nhiều do phải gán nhãn cho từng mẫu.

Học không giám sát (Unsupervised learning, UL)

Khác với SL, mục tiêu của UL là học ra những hàm mô tả những cấu trúc ẩn trong dữ liệu. UL nhằm giải quyết những bài toán mà lượng dữ liệu có nhãn là rất ít hoặc không có, hoặc do những đặc trưng của bài toán mà dữ liệu có gán nhãn là không cần thiết.

Ví dụ chúng ta có một lượng lớn khách hàng với những sở thích khác nhau và muốn có một nhân viên hỗ trợ khách hàng cho mỗi nhóm sở thích. Ở đây chúng ta không cần quan tâm sở thích cụ thể của một người là gì mà chỉ muốn những khách hàng có cùng sở thích thì sẽ được hỗ trợ bởi cùng một nhân viên. Chúng ta sử dụng thuật toán phân cụm (clustering), ví dụ như k-means, để nhóm những khách hàng có cùng sở thích lại với nhau dựa theo một độ đo (measure) về sự giống/khác nhau về sở thích giữa 2 người.

Semi-supervised learning (học bán giám sát) là một phương pháp kết hợp giữa UL và SL để giải quyết những bài toán có ít dữ liệu có gán nhãn.

Học tăng cường (Reinforcement learning, RL)

Khác với 2 phương pháp trên, RL không học từ những tập dữ liệu có sẵn mà nó liên quan tới việc điều khiển một/nhiều tác tử (agent) đưa ra những hành động (actions) trong một môi trường (environment) một cách hợp lí để cực đại hóa giá trị phần thưởng tích lũy (cummulative reward).

Ví dụ chúng ta có một robot (agent) với khả năng quan sát hạn hẹp, ở trong một môi trường với nhiều chướng cạm bẫy và phần thưởng. Mục tiêu của robot là tìm ra cách hoạt động thu được nhiều phần thưởng nhất và tránh được các cạm bẫy. Để đạt được điều đó, robot phải trải qua quá trình dò tìm, khảo sát môi trường xung quanh và dần xây dựng nên một mô hình về môi trường đó. Quá trình học này khác với SL, UL vì dữ liệu về môi trường là không sẵn có mà phải được khám phá dần dần qua nhiều lần thử nghiệm.

SL và UL là hai phương pháp phổ biến nhất trong ML nhưng RL cũng là một phương pháp cực kì triển vọng và đang phát triển mạnh mẽ trong thời gian gần đây khi nó được kết hợp với SL và UL.

Sơ lược về trí tuệ nhân tạo

Trí tuệ nhân tạo có thể chia làm hai trường phái chính là: trí tuệ nhân tạo cổ điển (Classical AI, CAI) và trí tuệ nhân tạo hiện đại (Modern AI, MAI). Mặc dù tên gọi có vẻ khác biệt về mặt thời gian, hai trường phái này thực sự xuất hiện gần như cùng lúc, vào khoảng những năm 1940 khi máy tính bắt đầu được xây dựng (chúng ta không cho những công trình toán học, triết học cổ xưa về hoạt động tư duy của con người là thuộc trí tuệ nhân tạo).

Trí tuệ nhân tạo cổ điển thường dựa trên việc tìm kiếm lời giải trong một cơ sở tri thức xác định trước. Để hệ thống có thể hoạt động được, lập trình viên phải chỉ rõ cách thức để tìm kiếm, suy luận và đưa ra quyết định. Hướng tiếp cận này đã đạt được những thành công đáng kể khi xây dựng nên những hệ chuyên gia (expert systems), những chương trình chơi cờ đánh bại các nhà vô địch thế giới, …

Tuy nhiên phương pháp này gặp phải rất nhiều khó khăn khi giải quyết những bài toán mà con người có thể dễ dàng giải được nhưng chính chúng ta cũng không biết ta thực hiện nó như thế nào, ví dụ như việc dạng đồ vật hay đọc hiểu một đoạn văn bản. Để hiểu được một văn bản, theo cách tiếp cận của CAI, chúng ta phải liệt kê toàn bộ các luật ngữ pháp và ý nghĩa của từng từ trong từng ngữ cảnh khác nhau. Việc đó là vô cùng tốn kém thậm chí là không thể bởi số lượng các luật là rất lớn và số lượng ngữ cảnh còn lớn hơn rất nhiều tới mức gần như là vô hạn. Phương pháp trên còn cực kì nhạy cảm với việc thay đổi bài toán, một hệ thống nhận dạng văn bản tiếng Anh không thể sử dụng cho tiếng Việt và càng không thể sử dụng cho việc nhận dạng ảnh được, chúng ta cần phải xây dựng một cơ sở tri thức hoàn toàn mới cho mỗi bài toán mới. Do đó, chúng ta cần những phương pháp mới có khả năng tự động phát hiện các quy luật và tự động thích nghi với những bài toán mới. Đó chính là mục tiêu của trí tuệ nhân tạo hiện đại và phương pháp phổ biến nhất, gần như chiếm trọn trí tuệ nhân tạo hiện nay là học máy (Machine Learning, ML).

INFORMAC – spoj

Đề bài:

Thuật toán:

Code:

uses math;
const
  fi='';//informac.inp';
  fo='';//informac.out';
  maxm=40000;
  maxn=200;
var
  match : array[1..maxn] of longint;
  l,r : array[1..maxn] of longint;
  left,right  :  array[1..maxn] of longint;
  link,head,ke : array[1..maxm] of longint;
  i,j,n,m,x,y,u,v : longint;
  kt : boolean;
procedure enter;
  var i,j,k : longint;
  begin
    assign(input,fi);reset(input);
    read(n,m);
    for i:=1 to n do
      begin
        r[i] := n;
        right[i] := n;
      end;
    for i:=1 to n do
      begin
        l[i] := 1;
        left[i] := 1;
      end;
    for i:=1 to m do
      begin
        read(j,x,y,v);
        left[v] := max(left[v], x);
        right[v] := min(right[v], y);
        if j = 1 then
          begin
            for k := x to y do r[k] := min(r[k],v);
          end;
        if j = 2 then
          begin
            for k := x to y do l[k] := max(l[k],v);
          end;
      end;
    close(input);
  end;
Procedure Ghepcap;
  var old,i,j,nlist : longint;
      cx : array[1..maxn] of boolean;
      found : boolean;
      list : array[1..maxn] of longint;
  procedure dfs( u : longint);
    var v,i : longint;
    begin
      i := head[u];
      while i <> 0 do
        begin
          v := ke[i];
          if cx[v] then
            begin
              cx[v] := false;
              if match[v] = 0 then found := true else dfs(match[v]);
              if found then
                begin
                  match[v] := u;
                  exit;
                end;
            end;
          i := link[i];
        end;
    end;
  begin
    for i:=1 to n do list[i] := i;
    nlist := n;
    repeat
      old := nlist;
      fillchar(cx,sizeof(cx),true);
      for i:=nlist downto 1 do
        begin
          found := false;
          dfs(list[i]);
          if found then
            begin
              list[i] := list[nlist];
              dec(nlist);
            end;
        end;
    until nlist = old;
  end;
procedure add(i,u,v : longint);
  begin
    link[i] := head[u];
    head[u] := i;
    ke[i] := v;
  end;
procedure process;
  begin
    kt := false;
    for i:=1 to n do
      if r[i] < l[i] then exit;
    for i:=1 to n do
      for j:=left[i] to right[i] do
        if (i>=l[j]) and (i<=r[j]) then
        begin
          inc(m);
          add(m,i,j);
        end;
    ghepcap;
    for i:=1 to n do
      if match[i] = 0 then exit;
    kt := true;
  end;
procedure print;
  begin
    assign(output,fo);rewrite(output);
    if not kt then writeln(-1) else for i:=1 to n do write(match[i],' ');
  end;
begin
  enter;
  process;
  print;
end.