Tài liệu học tập

1. DSAP TextbookTác giả: Thầy Lê Minh Hoàng (ĐHSP Hà Nội)

Trích từ: BigOCoding

Một quyển sách điện tử đã rất quen thuộc với những học sinh chuyên tin của nước ta. Theo suy nghĩ của nhiều bạn đã và đang sử dụng quyển sách này làm tư liệu, thì đây là một quyển sách rất qúy giá trong việc học tập tin học; quyển sách đề cập đến các kiến thức cần thiết được sử dụng trong các kì thi ở cấp độ chuyên tin trung học phổ thông và nhiều vấn đề nâng cao hơn nữa; mỗi nội dung đều được được diễn giải chi tiết, rõ ràng, cùng với chương trình được cài đặt bằng ngôn ngữ Pascal.

Các bạn có thể dễ dàng tìm được quyển sách này trên Internet hoặc có thể download tại đây

2. Cẩm nang thuật toán

Đây là cuốn sách được dịch từ cuốn Algorithms của Robert Sedgewick, Princeton University (USA), quyển sách này trở thành 1 tư liệu "kinh điển" về cả lý thuyết và thực hành cho người mới bắt đầu.

Trên trang  BigOCoding đã viết về quyển Algorithms như sau:

Algorithms

Tác giả:Robert Sedgewick

Một bộ sách nổi tiếng khác đã xuất bản từ khá lâu (1988) và đã được dịch sang tiếng Việt với tên gọi Cẩm Nang Thuật Toán (2 tập)

Khi phải giải quyết các bài toán tin học, quyển sách này là một trong những tài liệu tham khảo được sử dụng nhiều nhất; bên cạnh những diễn giải chi tiết về các thuật toán, nó còn trình bày những vấn đề, tư duy bao quát, giúp người đọc hiểu sâu sắc hơn.

Robert Sedgewick cung cấp những diễn giải rất rõ ràng, trực quan đi vào bản chất của nhiều thuật toán. Quyển sách bao hàm một diện rộng các chủ đề, từ sắp xếp đến tìm kiếm, hình học, cũng như các thuật toán toán học. Mỗi thuật toán đều được cài đặt cẩn thận bằng Pascal.

+ Quyển 1: Các thuật toán thông dụng, gồm 23 chương thuộc 4 phần đầu của nguyên bản.

+ Quyển 2: Các thuật toán thông dụng, gồm 22 chương thuộc 4 phần cuối nguyên bản.

Các bạn có thể tải sách này tại đây: + Quyển 1, + Quyển 2

3. Tài liệu giáo khoa chuyên Tin

Bộ giáo dục và đào tạo đã ban hành chương trình chuyên Tin học cho các lớp chuyên 10, 11, 12. Dựa theo các chuyên đề chuyên sâu trong chương trình nói trên, các tác giả biên soạn bộ sách chuyên tin học bao gồm các vấn đề cơ bản nhất về cấu trúc dữ liệu, thuật toán và cài đặt chương trình.Bộ sách gồm 3 quyển, quyển 1, 2 và 3. Cấy trúc mỗi quyển bao gồm: Phần lý thuyết, giới thiệu các khái niệm cơ bản, cần thiết trực tiếp, thường dùng nhất; phần áp dụng trình bày các bài toán thường gặp cách giải và cài đặt chương trình; cuối cùng là các bài tập. Các chuyên đề trong bộ sách được lựa chọn mang tính hệ thống từ cơ bản đến chuyên sâu.Với trải nghiệm nhiều năm tham gia giảng dạy, bồi dưỡng học sinh chuyên Tin học của các trường chuyên có truyền thống và uy tin, các tác giả đã lựa chọn biên soạn các nội dung cơ bản, thiết yếu nhất mà mình đã sử dụng để dạy học với mong muốn bộ sahcs phục vụ không chỉ cho giáo viên và học sinh chuyên THPT mà cả cho giáo viên, học sinh chuyên tin học THCS làm tài liệu tham khảo cho việc dạy và học của mình Với kinh nghiệm nhiều năm tham gia bồi dưỡng học sinh, sinh viên tham gia các kỳ thi học sinh giỏi Quốc gia, quốc tế, hội thi Tin học trẻ toàn quốc, Olympiad Sinh viên Tin học toàn quốc, kỳ thi lập trình viên quốc tế khu vực Đồng Nam Á, các tác giả đã lựa chọn giới thiệu các bài tập, lời giải có khuynh hướng phụ vụ không chỉ học sinh mà cả sinh viên làm tài liệu tham khảo cho các kỳ thi trên. 

Bộ sách gồm 3 cuốn:

+ Quyển 1: 

• Chuyên đề 1: Thuật toán và phân tích thuật toán
• Chuyên đề 2: Các kiến thức cơ bản: hệ đếm, số nguyên tố, ước số, bội số, lý thuyết tập hợp, số fibonacci, số catalan, xử lý số lớn
• Chuyên đề 3: Sắp xếp
• Chuyên đề 4: Thiết kế giải thuật: Quay lui, nhánh cận, tham ăn, chia để trị, quy hoạch động
• Chuyên đề 5: Các thuật toán trên đồ thị: Các khái niệm cơ bản, biểu diễn đồ thị, các thuật toán tìm kiếm trên đồ thị, tính liên thông của đồ thị, ứng dụng của BFS và DFS, đồ thị Euler và đồ thị Halminton

+ Quyển 2:

• Chuyên đề 6: Kiểu dữ liệu trừu tượng và cấu trúc dữ liệu: Danh sách, ngăn xếp và hàng đợi, cây, ký pháp tiền tố, trung tố và hậu tố, cây nhị phân tìm kiếm và ngẫu nhiên
• Chuyên đề 7: Đồ thị: Đường đi ngắn nhất, cây khung nhỏ nhất, luồng cực đại trên mạng. bộ ghép cực đại trên đồ thị 2 phía

+ Quyển 3: (phần 1, phần 2)

• Chuyên đề 8: Hình học tính toán
• Chuyên đề 9: Lí thuyết trò chơi
• Chuyên đề 10: Thuật toán mô phỏng tự nhiên và giải bài toán tối ưu tổ hợp

Igraph - Phần mềm mã nguồn mở tạo và xử lý đồ thị

1. GIỚI THIỆU

igraph là gói phần mềm mã nguồn mở dùng để tạo và xử lý đồ thị có hướng và vô hướng. Nó cài đặt hầu hết các bài toán cơ bản của lý thuyết đồ thị như minimum spanning trees, network flowcũng như cài đặt một số thuật toán hỗ trợ cho việc phân tích mạng phức hợp xuất hiện trong những năm gần đây như tìm kiếm cấu trúc cộng đồng.

Tính hiệu quả của gói igraph ở chỗ là nó có thể xử lý các đồ thị có đến cả ngàn đỉnh và cạnh. Mấu chốt nằm ở chỗ đồ thị có thể lưu trữ dưới nhiều định dạng khác nhau trên bộ nhớ vật lý mà igrahp nạp và trước khi xử lý.

Gói igraph có thể cài đặt dưới nhiều dạng khác nhau như:

·         Cài đặt igraph như một thư viện trong C/C++ nếu bạn muốn ứng dụng igraph vào những dự án khác nhau, hoặc bạn tự thiết kế các module phân tích mạng trong C/C++ có sử dụng các hàm và cấu trúc dữ liệu do igraph cung cấp.

·         Cài đặt igraph như một gói (package) của R. Dùng cách này nếu chúng ta xử lý graph trên R interpreter.

·         Cài đặt igraph như là một module mở rộng trong Python. Sử dụng cách này nếu bạn muốn kết hợp igraph với ngôn ngữ Python.

·         Cài đặt igraph như là một module trong Ruby.

Ứng với mỗi cách sử dụng sẽ có cách cài đặt phù hợp. Bạn cần xem  tại download page để biết thêm chi tiết.

2. HƯỚNG DẪN CÀI ĐẶT

Trong phần này chỉ hướng dẫn cài đặt igraph như một thư viện của C/C++

Đầu tiên cần phải cài đặt Cygwin

+ Tải Cygwin ở đây (win 32bit) hoặc ở đây (win 64bit)

+ Sau khi tải về, nháy đúp vào file setup.exe để cài đặt. Trong quá trình cài đặt cứ nhấn Next cho đến bước như hình dưới

Đến đây người dùng cần phải chọn những gói (package) phù hợp với nhu cầu của mình. Để cài đặt được Igraph trên Cgywin và dùng ngôn ngữ lập trình C/C++ thì cần các gói:

gcc-core;  make; openssl; ssh; vim

Xem thêm video: https://www.youtube.com/watch?v=hh-V6el8Oxk để biết cách chọn các package)

Sau đó nhấn Next cho đến khi cài xong Cygwin

Tiếp theo: cài Igraph

+ Tải igraph về (ở đây)  rồi giải nén được 1 thư mục có tên igraph-0.7.1 (hoặc tương tự)

Đưa thư mục này vào trong thư mục C:\cygwin64\home\haiph

Trong đó C:\cygwin64 có thể sẽ khác tùy vào người cài đặt, haiph là tên của user trong máy tính

+ Mở Cygwin (có shortcut ở màn hình Destop) gõ lệnh cd igraph-0.7.1

Tiếp tục gõ các lệnh:

./configure

make

make install

Lưu ý: sau khi gõ một lệnh có thể phải chờ khá lâu tùy vào cấu hình máy để cho chương trình chạy xong

Đến đây xem như việc cài igraph đã xong.

Test thử

+ Copy file  igraph_test.c  vào trong thư mục C:\cygwin64\home\haiph (thư mục này có thể khác như đã nói ở trên)

+ Mở Cygwin và gõ dòng lệnh

gcc igraph_test.c -I/usr/local/igraph -L/usr/local/lib -ligraph -o igraph_test

Nếu báo lỗi

Tức là đường dẫn bị sai nên không tìm thấy file igraph.h trong thư mục

Lúc này cần sửa lại lệnh trên thành

gcc igraph_test.c -I/usr/local/include/igraph -L/usr/local/lib -ligraph -o igraph_test

Sau đó gõ lệnh ./igraph_test

Kết quả hiện thị

Vậy là xong.

Có thể xem thêm nhiều ví dụ khác tại: http://igraph.org/c/doc/igraph-tutorial.html
Chúc thành công!