Một số đề kiểm tra cũ môn THDC

Bài tập CTDL Cuối kỳ SIE 20151

Bài 5 điểm

Bài 1. Cho một tập văn bản tiếng Anh ( 200 văn bản)

Hãy thống kê tần số các n-gram có trong văn bản (từ 1-gram, 2-gram tới 5-gram) và in ra màn hình các gram có

• Tần số xuất hiện nhiều nhất trên toàn bộ văn bản (mỗi gram có thể được tính nhiều lần nếu xuất hiện trong cùng 1 văn bản)
• Xuất hiện trong nhiều văn bản nhất (mỗi gram chỉ được tính xuất hiện trong 1 văn bản 1 lần)

Chú ý: 

1. các gram được tính trong phạm vi 1 câu hoặc một phần của câu và được ngăn cách bằng các dấu câu như . , " : ; ? !

The military previously called the bombing an incident of "collateral damage," a description Campbell's story would seem to support.

thì các phần của câu gồm 

The military previously called the bombing an incident of 

collateral damage

a description Campbell's story would seem to support

2. Có một số ngoại lệ như từ viết tắt và số

We have now learned that on October 3, Afghan forces advised that they were taking fire from enemy positions and asked for air support from U.S. forces," he said Monday

U.S là một gram chứ ko tách thành 2

So far this year, more than 130,000 migrants and refugees have crossed to Europe from the north African coast. More than 2,700 have drowned.

số tính liền chứ không ngăn cách ra

Bài 2.

Cho một tập văn bản tiếng Anh ( 5000 văn bản)

• Thống kê tần số các n-gram có trong văn bản (từ 1-gram).
• Hai gram được coi là tương đồng nhau nếu nó xuất hiện cùng nhau trong nhiều văn bản. Hãy nhập vào 2 1-gram và in ra màn hình độ tương đồng của 2 1-gram đó

độ tương đồng của 2 gram đươc tính bằng 

#số văn bản chứa đông thời 2 gram đó / #văn bản chứa 1 trong 2 gram

Chú ý: Ta chỉ xét 1-gram trong bài toán này

Một số yêu cầu thêm như:

• In ra văn bản chứa 1 hoặc cả 2 gram
• Chỉ xét các văn bản có độ dài ít hơn 500 từ
• chỉ xét các văn bản mà gram đó xuất hiện nhiều hơn 2 lần

Bài 3. Cho một tập văn bản tiếng Anh ( 5000 văn bản)

• Thống kê tần số các n-gram có trong văn bản (từ 1-gram), và số lượng văn bản mà mỗi gram xuất hiện.
• Độ quan trọng của một gram được tính bằng TF-IDF = (tần số xuất hiện của từ/tổng số từ)*log(tổng số văn bản/số văn bản từ đó xuất hiện). Từ nào có TF-IDF lớn là từ quan trọng.
• Sắp xếp độ quan trọng của các từ theo TF-IDF và chỉ lấy 30% từ có TF-IDF quan trọng nhất.  

FILE văn bản:
https://drive.google.com/file/d/0B5nb3v94xY_WaV9PejV0MUx6dDg/view?usp=sharing

Bài tập giữa kỳ CTDLGT SIE 20151

Loại bài 1 điểm

Bài 1. Cho 2 số nguyên lớn (số lượng chữ số từ 10 tới 1000). Hãy viết hàm thực hiện các phép toán cơ bản như cộng, trừ, nhân, chia hai số nguyên này.

VD. một số có thể là 123454124545887154956584454878544648454


Bài 2. Một đa thức bậc n có thể được biểu diễn bằng một danh sách liên kết đơn

P(n) = a0 + a1*n + a2*x^2 + .. + an*x^n

Hãy viết các hàm thực hiện việc cộng, trừ và nhân hai đa thức bậc n là P(n) và Q(n).
Chú ý. Các đa thức này cần được biểu diễn bằng danh sách liên kết đơn

Bài 3. Đầu vào là một xâu ký tự
Hãy tìm và đưa ra màn hình các ký tự cơ bản để tạo nên xâu ban đầu

VD. Xâu đầu vào là abbcacfcba
Thì các ký tự cơ bản để tạo ra xâu là abcf

Bài 4. Cho một danh sách số nguyên và một giá trị x. Hãy xây dựng chương trình tìm và in ra màn hình các phần tử chênh lệch với x giá trị k. một cách nhanh nhất.

VD. Danh sách ban đầu 1,2,5,3,7,4
với x = 3 và k =1 thì chương trình sẽ in ra 4 và 5

Loại bài 2 điểm

Bài 1. Cho một dãy số nguyên, hãy đưa ra các khoảng liên tục trong dãy
VD. Dãy đầu vào là 1,8,9,2,3,11,5,7,12
Thì đầu ra là 1-3, 5, 7-9, 11-12

Gợi ý bài tập THDC

Gợi ý bài tập THDC

Bài tập giữa kỳ và cuối kỳ môn khai phá dữ liệu

Bài tập giữa kỳ


Bài tập cuối kỳ

Bài tập lớn CTDLGT cho lớp VUW-IT

Bài 1. (Phát triển từ bài tìm danh từ riêng) Tìm xem danh từ riêng nào được đề cập đến nhiều nhất trong một tập văn bản ( khoảng 50-100 văn bản).

• Các danh từ riêng bao gồm cả danh từ nối và không được nối.

Từ đó đưa ra xem danh từ nào đang là hot trend. (các danh từ được đề cập đến nhiều nhất trong nhiều văn bản)

• Chú ý việc các danh từ viết tắt (cùng xuất hiện trong văn bản)

Tập văn bản (50-100) văn bản do sinh viên lấy từ các nguồn như BBC.com hoặc CNNNews.com hoặc VOANews.com

Có thể sử dụng chung tập dữ liệu nếu cùng làm một bài (Miễn là không dùng chung code :D )

Bài 2. Tìm tập danh từ riêng theo chủ đề

Đầu vào là một tập văn bản tiếng Anh thuộc nhiều chủ đề (>=3 chủ đề), mỗi chủ đề khoảng (10-20 văn bản). Các chủ đề như

• Thể thao
• Chính trị
• Khoa học công nghệ
• Kinh doanh

Với mỗi một chủ đề ta tìm các danh từ riêng và đưa ra tập danh từ riêng đăc jtrung cho từng chủ đề dựa trên tần số xuất hiện.

Danh từ riêng nào xuất hiện đồng thời trong nhiều chủ đề khác nhau ?

Danh từ đó có đặc điểm gì ?

Bài tập giữa kỳ cho lớp VUW-IT 20142

Bài 1. Thống kê tần số xuất hiện và vị trí xuất hiện (theo câu hoặc dòng) của các danh từ riêng trong văn văn tiếng Anh.

Chương trình đọc vào 1 trong 5 file văn bản đính kèm, hiển thị ra các danh từ riêng trong văn bản đó.

Chương trình cho phép người dùng nhập vào một danh từ riêng, in ra màn hình kết quả:

• Tần số xuất hiện
• Vị trí xuất hiện

Nếu danh từ đó có xuất hiện trong văn bản đã cho.

Chú ý: Các danh từ riêng nếu đứng cạnh nhau thì cần được nối lại với nhau

Bài 2. Thống kê tần số xuất hiện và vị trí xuất hiện (theo câu hoặc dòng) của các từ trong văn văn tiếng Anh.

Chương trình đọc vào 1 trong 5 file văn bản đính kèm, hiển thị ra :

• Các từ
• Tần số xuất hiện
• Độ dài từ và tần số của các từ theo độ dài 9độ dài của 1 từ là số ký tự trong từ đó)

Chương trình cho phép người dùng nhập vào một từ, in ra màn hình kết quả:

• Tần số xuất hiện
• Vị trí xuất hiện

Nếu từ đó có xuất hiện trong văn bản đã cho.

Có lựa chọn thống kê phân loại chữ hoa/thường hoặc không phân loại hoa/thường.

Chú ý. Các từ trong văn bản được ngăn cách nhau bởi dấu cách trống.

Bài 3. Cho một văn bản và một tập từ điển tiếng Anh. Kiểm tra xem trong văn bản tiếng anh đó có bao nhiêu từ lỗi chính tả (bỏ qua những từ có chữ hoa, hoặc chữ số).

Những từ lỗi là những từ không có trong từ điển.

Nếu đề xuất được phương án sửa từ sai sẽ được cộng điểm.

Tài liệu download tại

https://www.dropbox.com/s/uitdzw9q84x093o/VUW-IT%2020142.rar?dl=0