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

Bài tập lớn CTDL & GT cho lớp chiều thứ 2 (tiết 1-4)

Bài tập lớn CTDL & GT cho lớp chiều thứ 2 (tiết 1-4)

Yêu cầu chung:

• Sinh viên tự đề xuất thuật toán dựa trên yêu cầu của đề bài
• Tự chọn CTDL phù hợp và giải thích vì sao mình chọn CTDL đó
• Đánh giá hiệu quả về thời gian và bộ nhớ của thuật toán 

Đây là các đề bài xuất phát từ yêu cầu thực tế, rất khó có thuật toán cho kết quả chính xác 100% (Điểm đánh giá sẽ ưu tiên các thuật toán nào cho kết quả tốt hơn)

Dữ liệu đầu vào:

Dữ liệu cho tất cả cacsc bài tập ở dưới được Download theo link sau: https://www.dropbox.com/s/k7y57sqsy5qzrkl/TechCrunch_Files.rar?dl=0

• Các tập dữ liệu đầu vào được lấy từ các bài viết mới gần đây trên trang công nghệ TechCrunch, và ở dạng ngôn ngữ tiếng Anh.
• Các bài viết được tổ chức thành từng file riêng theo dạng 0001.txt, 0002.txt,... (có khoảng gần 5K bài viết)
• Format của mỗi bài viết gồm
• Dòng đầu tiên là tiêu đề : title
• Dòng tiếp là tác giả: author
• Dòng tiếp là ngày được xuất bản : publish date
• Các dòng tiếp theo là nội dung bài viết 
• Trong bài viết có nhiều ngoại lệ (exception), sinh viên nên tự phát hiện và loại bỏ để tăng độ chính xác (VD. các thông tin phụ ở cuối bài viết) 

Dữ liệu đầu ra:

• Sinh viên nên tổ chức dữ liệu đầu ra dưới dạng file văn bản để dễ theo dõi

Sinh viên có thể dùng các hệ quản trị CSDL đễ hỗ trợ tổ chức và lưu trữ dữ liệu (tuy nhiên điều này không được khuyến khích)

Bài 1. Phát hiện các danh từ riêng, tên riêng trong các văn bản

Sắp xếp các danh từ này theo tần số xuất hiện trên toàn bộ tập văn bản, và trên số lượng văn bản mà nó xuất hiện

Hai cặp danh từ được coi là cùng xuất hiện nếu chúng xuất hiện gần nhau (trong khoảng cách 2-3 câu)

Những danh từ nào có tần số xuất hiện nhiều nhất?

• Trên toàn bộ tập văn bản (mỗi từ được tính nhiều lần nếu xuất hiện nhiều lần ở cùng 1 văn bản)
• Trên nhiều văn bản nhất (mỗi từ chỉ được tính 1 lần xuất hiện trong 1 văn bản)

Cặp danh từ nào được xuất hiện nhiều nhất?

VD với văn bản

A recent article in TechCrunch characterized nascent upstarts in the restaurant industry as wide-eyed idealists with little reality of the harsh, high-touch operating environment in which they operate. Having worked in the tech, food and health worlds for most of my career, I believe the article misrepresented the significant progress being made across the industry. On almost every front within hospitality — be it point of sale, loyalty, delivery or sourcing — change is in the air.

For all the talk of the Aloha and MICROS point of sale (POS) systems dominanting in restaurants, a bevy of newcomers have been making inroads. Square, with its slick reader and now retail POS terminal, carries the most gravitas among the mobile POS companies for good reason: it inks deals with large retailers: Starbucks in 2012, then Whole Foods, Uniqlo and Godiva in 2014. Granted, none of these establishments switched over an entire store to Square, but these relationships suggest large retailers will embrace new technology.

Danh từ riêng được in đậm

• là các từ có ít nhất 1 chữ in hoa
• Không chấp nhận các từ ở đầu câu hoặc đầu đoạn
• Các từ hoa liền nhau (ngăn cách bởi 1 dấu cách trống) nên nối thành 1 từ dài
• Các từ hoa liền nhau ngăn cách từ >= 2 dấu cách trống thì nên tách riêng ra.
• Nếu mà phân biệt được các từ viết tắt thì càng tốt (các từ mà tất cả các ký tự đều viết hoa)

Cặp danh từ trong phạm vi 2 câu là

• {Aloha - MICROS} - POS
• POS - {Starbucks - Whole Foods - Uniqlo - Godiva} 
• {Starbucks - Whole Foods - Uniqlo - Godiva} - Square

Bài 2. Thống kê tên thương hiệu (sản phẩm)/ công ty được đề cập trong bài báo

Với các danh từ riêng trong bài báo ta cần phân ra được thành

• Tên địa điểm, vị trí
• Tên người
• Tên sản phẩm/ tên công ty

Làm sao phân biệt được tên địa điểm, tên người với các tên riêng khác ?

• Tên địa điểm, vị trí, thời gian: gần đó thường có các giới từ như at, in, on
• Tên người: gần đó thường có sở hữu cách:'s hoặc of
• Tên sản phẩm/ tên công ty:

Nếu không làm được ==> tự xây dựng từ điển tên công ty/ sản phẩm bằng tay (không khải thi cho lắm nếu chạy trên dữ liệu thực tế - khoảng vài tỷ bài viết)

Công ty / sản phẩm nào được đề cập đến nhiều nhất ?

Bài 3. sản phẩm nào là của công ty nào được đề cập trong các bài báo?

VD. Apple : iphone, ipad,....

Làm thế nào biết được sản phẩm nào của công ty nào?

• Phát hiện tên công ty
• Tên sản phẩm
• Thường có các từ đặc trưng để kết nối như: a product of, a service of,....

Bài 4. Tìm các bài viết đánh giá tốt hoặc xấu về một sản phẩm/ thương hiệu của công ty

• Phát hiện ra các tên công ty, tên sản phẩm
• Các tính từ đánh giá như : good, bad, worse,, (sinh viên tự xây dựng từ điển) 

Các tính từ này phải nằm gần các câu chứa các danh từ thương hiệu (trong phạm vi khoảng 2-3 câu)

Bài 5. Hai văn bản được coi là có liên quan đến nhau nếu có tập danh từ riêng trùng nhau nhiều

• Tìm các tập danh từ riêng của 2 văn bản
• Xác định tập danh từ riêng trùng nhau của 2 văn bản
• Quyết định xem 2 văn bản có liên quan đến nhau hay không dựa trên ngưỡng (số lượng từ trùng nhau trên tổng số danh từ riêng của cả 2 văn bản). Ngưỡng này do sinh viên tự đề xuất!

Với 1 bài đang đọc, hãy đưa ra danh sách các bài viết có liên quan (được sắp xếp theo thứ tự độ liên quan giảm dần)

Để đảm bảo yêu cầu về thời gian xử lý, sinh viên có thể cần tính trước độ liên quan của các bài viết và đưa vào file tạm.

Bài 6. n-gram là các cụm từ liên tiếp nhau (ở đây ta quan tâm tới 2-gram và 3-gram)

Ta chỉ xét các n-gram trong phạm vi một bộ phận câu (bị ngăn cách bởi các dấu câu như  dấu ! dấu . dấu : dấu - ) 

Dấu , được bỏ qua

VD. Với văn bản 

I believe the article misrepresented the significant progress being made across the industry. On almost every front within hospitality — be it point of sale, loyalty, delivery or sourcing — change is in the air.

Ta có các bộ phận câu như

• I believe the article misrepresented the significant progress being made across the industry
• On almost every front within hospitality
• be it point of sale, loyalty, delivery or sourcing
• change is in the air

Với câu 

• change is in the air

Ta có các 3-gram là:

1. change is in
2. is in the
3. in the air

Hai văn bản liên quan đến nhau (thường là trùng nhau hoặc cùng một chủ đề) nếu có số lượng n-gram trùng nhau nhiều.

Hãy tìm các văn bản trùng/ có liên quan đến văn bản hiện tại dựa trên 3-gram (hoặc 2-gram)

Ngưỡng trùng do sinh viên tự đề xuất.

Danh sách nộp bài tập tuần lớp CTDLGT chiều thứ 2 [Update hàng tuần vào CN]