Một số câu hỏi tìm hiểu môn THDC cho các lớp SIE kỳ 20161

Yêu cầu:

• Mỗi câu trả lời khoảng 3-5 trang
• Yêu cầu trình bày lại ý hiểu, không copy và paste
• Phải bảo vệ mới được công nhận
• Mỗi câu chỉ được 1 điểm
• Không làm nhóm

Chú ý:

• Nếu làm slide trình bày trên lớp sẽ được cộng 5 điểm
• Mỗi câu chỉ được tối đa 2 người trình bày, vì vậy hay đăng ký sớm nhất có thể!

1. IoT là gì ? hãy nêu một số mô hình về IoT trên thực tế?
2. In 3D là gì? Hiện tại đang có những công nghệ in 3D nào, nêu một số thành tựu của in 3D đã có trong 
   1. Sinh học
   2. Công nghệ
   3. Y học
   4. Vật liệu mới
3. Xe ô tô tự lái dùng những loại cảm biến nào? Tác dụng của những cảm biến ấy làm gì?
   Hiện có những hãng nào đang làm ô tô tự lái, và đã có ứng dụng nào trong thực tế chưa?
4. Hiện tại công nghệ chế tạo bán dẫn đạt tới kích thước nhỏ nhất là bao nhiêu nm.
   Đã có những công nghệ của hãng nào được ứng dụng vào sản xuất các chip trong thực tế?
5. Công nghệ chip Kabi Lake của intel đang đạt tới kích thước bao nhiêu nm?
   so với thế hệ chip sky lake, thì công nghệ này có những ưu việt gì?
6. Big Data là công nghệ về lưu trữ và xử lý dữ liệu lớn.
   Vậy dữ liệu lớn là gì?
   Hiện tại Google, Facebook, Microsoft đang sử dụng những công nghệ gì để lưu trữ và xử lý dữ liệu lớn?
   Ứng dụng trong thực tế của nó là sản phẩm nào?
7. Hiện tại đang có những công nghệ nào trong chế tạo card màn hình. Card màn hình được sử dụng trong nhận diện và học máy có cấu hình như thế nào, và có thể xử lý được bao nhiêu hình ảnh trong 1 s? Đang được áp dụng trong sản phẩm nào?
8. Công nghệ lưu trữ dùng ổ cứng đặc SSD mới của Samsung có gì đặc biệt, tốc độ tối đa và dung lượng tối đa mà một ổ cứng mới nhất của Samsung có thể lưu trữ là bao nhiêu? Chip nhớ này có ưu điểm gì?
9. Công nghệ chế tạo HDD (ổ cứng dùng đĩa từ) truyền thống hiện tại đang đạt tới tốc độ và dung lượng bao nhiêu? Hãng nào đang nắm công nghệ chủ đạo trong chế tạo ổ cứng HDD?
10. Chuẩn bluetooth 5.0 sắp tới có những ưu điểm gì hơn so với chuẩn 4.0 hiện tại? Chuẩn này hiện đang được hỗ trợ bởi những hãng công nghệ nào và trong các thiết bị mới nào? 
11. Công nghệ mạng không dây mới Li-fi khác gì so với Wi-fi? Ưu nhược điểm và tốc độ của Li-fi như thế nào?
12. Chuẩn kết nối mới USB Type-C có những đặc điểm gì khác so với chuẩn USB 3.0 truyền thống? Tốc độ truyền dữ liệu ra sao? Hiện đã có những sản phẩm và những hãng công nghệ nào hỗ trợ chuẩn Type C này ?
13. Điện năng lượng mặt trời hiện đang có những công nghệ nào mới nhất? Công suất lớn nhất mà 1 cell tế bào quang điện có thể cung cấp là bao nhiêu? Để cung cấp năng lượng khoảng 5Kwh thì cần bao nhiêu cell pin năng lượng mặt trời?

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

Cài đặt dùng Java hoặc C# hoặc C/C++

Bài 1. Cài đặt các hàm đầy đủ để mô tả cấu trúc dữ liệu mảng kích thước biến đổi

Các thao tác cần có gồm

• Add (int value): Thêm phần tử vào cuối mảng,
• RemoveAt(int index): xóa phần tử ở vị trí index 
• Size(): trả về số lượng phần tử hiện có của mảng
• Maxsize(): trả về kích thước/ số lượng phần tử tối đa mà cấu trúc có thể lưu
• Find(int value): trả về vị trí phần tử có gía trị bằng value trong mảng nếu có, ngược lại thì trả về giá trị -1
• Get(int index) trả về giá trị phần tử tại ví trí index trong mảng nếu có

Xây dựng thành class là tốt nhất, nếu không tổ chức thành các hàm trong C/C++ với tham số truyền vào như yêu cầu trên.

Bài 2. Cài đặt đầy đủ các hàm/ phương thức của cấu trúc danh sách liên kết đơn nối thẳng có kiểu class T

• Thêm (đâù, giữa/cuối)
• Xóa (đâù, giữa/cuối)
• Tìm kiếm

Các lớp cài đặt này nên dùng Template class

Bài 3. Cài đặt các hàm mô tả cấu trúc danh sách liên kết đơn nối vòng

Bài 4. Cài đặt các hàm mô tả danh sách liên kết đôi

Bài 5. Cài đặt cấu trúc Ngăn xếp/Hàng đợi dùng mảng kích thước biến đổi

Bài 6. Cài đặt lớp biểu diễn cây nhị phân với các tính năng sau

• Thêm nút trái
• Thêm nút phải
• Lấy giá trị nút trái/phải
• Đếm số nút trên cây
• Tìm nút lá sâu nhất/nông nhất (thời gian O(n))
• Tìm chiều cao của cây
• Tìm tổ tiên chung gần nhất của 2 nút bất kỳ trên cây
• Duyệt cây theo thứ tự trước/giữa/sau

Bài 7. Cài đặt cây nhị phân để biểu diễn cây biểu thức

• Tạo cây biểu thức từ biểu thức trung tố (biểu thức chỉ bao gồm các toán hang 1 chữ cái/chữ số và các toán tử đơn giản +,-,*,/,%,^,!,... và dấu ngoặc đơn)
• In ra biểu thức tiền tố, trung tố, hậu tố
• Kiểm tra biểu thức trung tố ban đầu có phải hợp lệ (dấu ngoặc hợp lệ và toán tử hợp lệ, chỉ cần check với một vài toán tử thông dụng)

Bài 8. Xây dựng thuật toán sinh ra màn chơi sodoku bằng cách thêm ngẫu nhiên n số (từ 1-9 vào một màn chơi ban đầu trắng). Thuật toán này cần cài đặt dùng Backtracking và đảm bảo là màn chơi này hợp lệ.

Bài 9. Cài đặt lớp biểu diễn cây nhị phân tìm kiếm tổng quát (có thể kế thừa từ lớp trong bài 6) hỗ trợ các thao tác

• Kiểm tra cây nhị phân có phải là cây nhị phân tìm kiếm
• Kiểm tra cây nhị phân tìm kiếm có phải cây cân bằng
• Thực hiện hàm tìm kiếm và trả về nút chứa khóa (nếu tìm thấy) trên cây
• Thực hiện hàm thêm nút/xóa nút trên cây 

Điểm thi giữa kỳ CTDLGT ĐH 20152

Điểm giữa kỳ sau khi đã cộng

Điểm thi giữa kỳ và cuối kỳ của lớp LTU và INPG kỳ 20152

Điểm thi này đã nộp lên văn phòng viện quan hệ quốc tế

Bài tập lớn CTDLGT

Bài 1. Đánh giá độ tương tự của các văn bản theo jacard

Độ tương tự theo jacard của 2 tập A,B được tính như sau

Cách 1. Mỗi phần tử trong tập hợp chỉ được tính 1 lần

Sim(A,B) = (#số phần tử chung của A và B) / (#Tổng số phần tử của A và B)

VD.
A = {a,b,c,f}
B = {a,e,f,g}

#số phần tử chung của A và B = {a,f}
#Tổng số phần tử của A và B = {a,b,c,e,f,g}

Sim(A,B) = 2/6 = 1/3

Cách 2. bag-similarity

A = {a, a, a, b}
B = {a, a, b, b, c}

#số phần tử chung của A và B = {a,a} và {b} (số lần xuất hiện ít nhất của phần tử chung)
#Tổng số phần tử của A và B = {a, a, a, b} và {a, a, b, b, c} (toognr số phần tử của cả 2 tập)

Sim(A,B) = 3/9 = 1/3

Hãy tính và đưa ra id của các văn bản tương tự nhau theo thứ tự giảm dần

====================================

Dữ liệu:

Gồm 5 trường, được ngăn cách với nhau bởi dấu = và ""

trường đầu tiên là id,

trường tiếp theo là wordsegmented

tiếp theo là 2garms

sau đó là 3grams

và cuối cùng là 4grams

"id"="wordsegmented"="2grams"="3grams"="4grams"

"1"="Vova thích gì
Trong giờ học, cô_giáo
– Các em chú ý, hãy nhìn cô và nói xem các em thích cái gì trên người cô và cô sẽ nói cho_biết lớn lên các em làm gì
Cô bé Masha
thưa cô, em thích mái_tóc của cô
– Ôi_Masha yêu quí, lớn lên em sẽ trở_thành một thợ làm_đầu nổi_tiếng
Cậu bé Pêchia
Thưa cô, đôi mắt của cô rất đẹp
– Cám_ơn Pêchia, lớn lên em sẽ trở_thành bác_sỹ nhãn_khoa giỏi
Thế còn Vôva, em nói gì đi chứ, đừng có xịu mặt như vậy
Vôva
Thưa cô, em biết nói gì bây_giờ
Bố_mẹ em chắc sẽ buồn lắm khi biết em chỉ làm một công_nhân vắt sữa bò ở nông_trại"="Vova_thích,Trong_giờ,giờ_học,cô_giáo,Các_em,em_chú,chú_ý,hãy_nhìn,nhìn_cô,cô_và,và_nói,nói_xem,xem_các,các_em,em_thích,thích_cái,cái_gì,gì_trên,trên_người,người_cô,cô_và,và_cô,cô_sẽ,sẽ_nói,nói_cho,cho_biết,biết_lớn,lớn_lên,lên_các,các_em,em_làm,làm_gì,Cô_bé,bé_Masha,thưa_cô,em_thích,thích_mái,mái_tóc,tóc_của,của_cô,Ôi_Masha,Masha_yêu,yêu_quí,lớn_lên,lên_em,em_sẽ,sẽ_trở,trở_thành,thành_một,một_thợ,thợ_làm,làm_đầu,đầu_nổi,nổi_tiếng,Cậu_bé,bé_Pêchia,Thưa_cô,đôi_mắt,mắt_của,của_cô,cô_rất,rất_đẹp,Cám_ơn,ơn_Pêchia,lớn_lên,lên_em,em_sẽ,sẽ_trở,trở_thành,thành_bác,bác_sỹ,sỹ_nhãn,nhãn_khoa,khoa_giỏi,Thế_còn,còn_Vôva,em_nói,nói_gì,gì_đi,đi_chứ,đừng_có,có_xịu,xịu_mặt,mặt_như,như_vậy,Thưa_cô,em_biết,biết_nói,nói_gì,gì_bây,bây_giờ,Bố_mẹ,mẹ_em,em_chắc,chắc_sẽ,sẽ_buồn,buồn_lắm,lắm_khi,khi_biết,biết_em,em_chỉ,chỉ_làm,làm_một,một_công,công_nhân,nhân_vắt,vắt_sữa,sữa_bò,bò_ở,ở_nông,nông_trại"="Vova_thích_gì,Trong_giờ_học,Các_em_chú,em_chú_ý,hãy_nhìn_cô,nhìn_cô_và,cô_và_nói,và_nói_xem,nói_xem_các,xem_các_em,các_em_thích,em_thích_cái,thích_cái_gì,cái_gì_trên,gì_trên_người,trên_người_cô,người_cô_và,cô_và_cô,và_cô_sẽ,cô_sẽ_nói,sẽ_nói_cho,nói_cho_biết,cho_biết_lớn,biết_lớn_lên,lớn_lên_các,lên_các_em,các_em_làm,em_làm_gì,Cô_bé_Masha,em_thích_mái,thích_mái_tóc,mái_tóc_của,tóc_của_cô,Ôi_Masha_yêu,Masha_yêu_quí,lớn_lên_em,lên_em_sẽ,em_sẽ_trở,sẽ_trở_thành,trở_thành_một,thành_một_thợ,một_thợ_làm,thợ_làm_đầu,làm_đầu_nổi,đầu_nổi_tiếng,Cậu_bé_Pêchia,đôi_mắt_của,mắt_của_cô,của_cô_rất,cô_rất_đẹp,Cám_ơn_Pêchia,lớn_lên_em,lên_em_sẽ,em_sẽ_trở,sẽ_trở_thành,trở_thành_bác,thành_bác_sỹ,bác_sỹ_nhãn,sỹ_nhãn_khoa,nhãn_khoa_giỏi,Thế_còn_Vôva,em_nói_gì,nói_gì_đi,gì_đi_chứ,đừng_có_xịu,có_xịu_mặt,xịu_mặt_như,mặt_như_vậy,em_biết_nói,biết_nói_gì,nói_gì_bây,gì_bây_giờ,Bố_mẹ_em,mẹ_em_chắc,em_chắc_sẽ,chắc_sẽ_buồn,sẽ_buồn_lắm,buồn_lắm_khi,lắm_khi_biết,khi_biết_em,biết_em_chỉ,em_chỉ_làm,chỉ_làm_một,làm_một_công,một_công_nhân,công_nhân_vắt,nhân_vắt_sữa,vắt_sữa_bò,sữa_bò_ở,bò_ở_nông,ở_nông_trại"="Các_em_chú_ý,hãy_nhìn_cô_và,nhìn_cô_và_nói,cô_và_nói_xem,và_nói_xem_các,nói_xem_các_em,xem_các_em_thích,các_em_thích_cái,em_thích_cái_gì,thích_cái_gì_trên,cái_gì_trên_người,gì_trên_người_cô,trên_người_cô_và,người_cô_và_cô,cô_và_cô_sẽ,và_cô_sẽ_nói,cô_sẽ_nói_cho,sẽ_nói_cho_biết,nói_cho_biết_lớn,cho_biết_lớn_lên,biết_lớn_lên_các,lớn_lên_các_em,lên_các_em_làm,các_em_làm_gì,em_thích_mái_tóc,thích_mái_tóc_của,mái_tóc_của_cô,Ôi_Masha_yêu_quí,lớn_lên_em_sẽ,lên_em_sẽ_trở,em_sẽ_trở_thành,sẽ_trở_thành_một,trở_thành_một_thợ,thành_một_thợ_làm,một_thợ_làm_đầu,thợ_làm_đầu_nổi,làm_đầu_nổi_tiếng,đôi_mắt_của_cô,mắt_của_cô_rất,của_cô_rất_đẹp,lớn_lên_em_sẽ,lên_em_sẽ_trở,em_sẽ_trở_thành,sẽ_trở_thành_bác,trở_thành_bác_sỹ,thành_bác_sỹ_nhãn,bác_sỹ_nhãn_khoa,sỹ_nhãn_khoa_giỏi,em_nói_gì_đi,nói_gì_đi_chứ,đừng_có_xịu_mặt,có_xịu_mặt_như,xịu_mặt_như_vậy,em_biết_nói_gì,biết_nói_gì_bây,nói_gì_bây_giờ,Bố_mẹ_em_chắc,mẹ_em_chắc_sẽ,em_chắc_sẽ_buồn,chắc_sẽ_buồn_lắm,sẽ_buồn_lắm_khi,buồn_lắm_khi_biết,lắm_khi_biết_em,khi_biết_em_chỉ,biết_em_chỉ_làm,em_chỉ_làm_một,chỉ_làm_một_công,làm_một_công_nhân,một_công_nhân_vắt,công_nhân_vắt_sữa,nhân_vắt_sữa_bò,vắt_sữa_bò_ở,sữa_bò_ở_nông,bò_ở_nông_trại"

Chỉ cần chọn id và lấy 1 trong 4 trường sau: wordsegmented,2grams,3grams,4grams

Các từ trong mỗi trường được ngăn cách bởi dấu cách trống và các dấu câu (từ ghép thì các âm tiết được nối bang dấu _)

VD.

Vova_thích,Trong_giờ

gồm 2 từ là Vova_thích và Trong_giờ

– Cám_ơn Pêchia, lớn lên em sẽ trở_thành bác_sỹ nhãn_khoa giỏi

gồm các từ là: Cám_ơn,Pêchia,lớn, lên, em, sẽ, trở_thành, bác_sỹ, nhãn_khoa, giỏi

Download : https://drive.google.com/open?id=0B5C6Dqb8T27hNjBkVVhaLWF6ZlE

Đề thi CTDL cũ

========================================== ==========================================

Một số đề kiểm tra giữa kỳ cũ môn CTDLGT

Đề cũ hơn xem tại

http://tinhocdaicuong4newbies.blogspot.com/2014/07/e-thi-cu-ctdl-2013.html

Bài tập giữa kỳ cho lớp INPG 13 và LTU 13A kỳ 20152

Bài 1. Xây dựng thuật toán tìm đường đi trong ma trận cho mê cung được mô tả bằng ma trận. 10×10 dùng backtracking.

Chỉ có thể đi ở các ô có giá trị 1 và theo hướng lên, xuống, trái và qua phải

1100000000000001111
1111111110111110000
0001000110101010000
1111000110101010000
1111000010101010000
0010000110101010000
1111000110101010000
1000000110101011111
1111110110101010001
1111010110101010001
1111010010100000001
1111011101111010001
1111110110101110000
0001000111101111111
1111000110101010001
1110000110101010101
1111000110101010111

Bài 2. Xây dựng các phương án tô màu cho đồ thị với các quốc gia được mô tả bằng ma trận. Các màu có thể chọn là 1,2,3,4

Liệu có thể dùng 3 màu tô cho bản đồ trên được không?

Bài 3. Xây dựng thuật toán quay lui giải sodoku 3x3 như dưới.
Có bao nhiêu phương án giải?

Cheat sheet cho Linux, Emacs và GCC

Cheat sheet cho Linux, Emacs và GCC

• Linux:
• Emacs
• Gcc

Links:

https://drive.google.com/folderview?id=0B5nb3v94xY_WT3YtTHJwVWxWcDg&usp=sharing

Bài tập giữa kỳ môn CTDL GT 20152

Bài tập giữa kỳ

Bài 1. Hoàn thiện hàm tìm dãy tăng dài nhất cài đặt dùng đệ quy

VD. dãy 1, 3, 2, 5, 6, 4, 7, 8, 9, 4, 5, 2, 1, 3, 4

Thì dãy tăng dài nhất là 4, 7, 8, 9 với độ dài 4.

Yêu cầu:

• in ra độ dài và giá trị các phần tử trong dãy tăng
• trong trường hợp có 2 dãy tăng cùng độ dài thì in ra cả 2.

Bài 2. Cho một mảng số nguyên A và một số s. Hãy xây dựng chương trình tìm hai số a,b không trùng nhau trong A sao cho có tổng đúng bằng s.

VD. A[]={1, 3, 5, 7, 6, 4, 2} và s=10 thì chương trình trả về 3 ,7 hoặc 6, 4

Yêu cầu:

• Loại bỏ các cặp số bị trùng

Bài 3. Xâu palindrome là xâu đối xứng
VD adbda hoặc abccba

Cho một xâu bất kỳ, hãy tìm và đưa ra xâu con palindrome dài nhất một cách nhanh nhất

VD. abcdcbbcdbccadbca thì xâu con là palindrome dài nhất là dcbbcd

Yêu cầu:

• Trường hợp có nhiều thì cần in ra tất cả các xâu con palindrome có độ dài dài nhất
• Thực hiện với thời gian O(n)

Bài 4. Chỉ dùng các phép toán -1 (trừ đi 1) và * 2 (nhân với 2), hãy xây dựng thuật toán biến đổi 1 số nguyên n thành 1 số nguyên m một cách nhanh nhất (dùng ít thao tác nhất)

VD. 4 thành 6 cần 2 thao tác là

(4-1)*2

Bài 5. Biểu diễn đa thức bậc n dùng danh sách liên kết đơn

Hãy viết các hàm cộng, trừ, nhân và chia hai đa thức

Bài 6. Xây dựng thuật toán tìm đường đi trong ma trận cho mê cung được mô tả bằng ma trận 20×20 dùng backtracking.

Đầu vào là ô (1,1) và đầu ra là ô (20,20)
Chỉ có thể đi ở các ô có giá trị 1 và theo hướng lên, xuống, trái và qua phải

1100000000000001111
1111111110111110000
0001000110101010000
1111000110101010000
1111000010101010000
0010000110101010000
1111000110101010000
1000000110101011111
1111110110101010001
1111010110101010001
1111010010100000001
1111011101111010001
1111110110101110000
0001000111101111111
1111000110101010001
1110000110101010101
1111000110101010111

Bài 7. Cho một dãy số nguyên A với số lượng phần tử là n
A[]={5,3,4,7,8,9,2,4,5}
Hãy in các dãy con tăng/giảm với độ dài dãy từ 3 đến n
VD. Với mang A trên thì

Dãy tăng độ dài 3 là: 3,4,7 và 7,8,9 và 2,4,5
Dãy tăng độ dài 4 là: 3,4,7,8 và 4,7,8,9
Dãy tăng độ dài 5 là: 3,4,7,8,9

Bài 8. Cho đầu vào là một danh sách các từ (gồm chữ cái và chữ số, có phân biệt chữ hoa và thường). Hãy viết chương trình nhập và giá trị nguyên n và in ra màn hình các từ chỉ khác nhau đúng n ký tự. Các từ ngắn hơn thì được coi là có dấu cách trống phía sau.

VD từ abc và abcde khác nhau 2 ký tự
abD và abcD khác nhau 2 ký tự

Danh sách các từ này được nhập vào từ file input.txt

Bài 9. Cho ma trận chỉ gồm 1 và 0 được nhập vào từ file.
Hãy in ra màn hình diện tích vùng chứa các số 0 lớn nhất

1111111110111110000
0001000110101010000
1111000110101010000
1111000010101010111
0010000111101010000
1111001110101010000
1000001110111111111
1111110110101010001
1111010110101010001
1111010010101010001

Ví dụ với hình trên thì diện tích lớn nhất là 21

Bài 10. Cho hai danh sách các khoảng liên tục. Hãy viết chương trình trộn hai danh sách này để được một danh sách các khoảng liên tục

Đầu vào:
Arr1 = [3-11, 17-25, 58-73];
Arr2 = [6-18, 40-47];

Đầu ra:
Arr3 = [3-25, 40-47, 58-73];

Chú ý: Các khoảng này đã được sắp theo thứ tự tăng dần cho trước

Bài 11. Cho một mảng chứa toàn số 0 và 1 và một giá trị nguyên k. Tìm đoạn con liên tục chứa nhiều số 1 nhất sau khi lật k bit 0 thành 1.

Ví dụ mảng đầu vào là {1,1,0,0,1,1,1,0,1,1}
k = 1 (chỉ được lật 1 bit 0 thành 1)

Độ dài đoạn lớn nhất là 6 (Nếu ta lật bit 0 tại vị trí chỉ số 7, ta sẽ có đoạn con chứa các bit 1 dài nhất là 6)

Bài 12. Xây dựng hàm kiểm tra xem có thể xáo trộn các ký tự trong 1 xâu ký tự đầu vào sao cho hai ký tự liên tiếp không được giống nhau

Ví dụ

apple >> alpep, so valid
b>> b, valid
bb>> bb, invalid/impossible
aab >> aba, valid
aaaabbcc >> acabacab, valid
etc.

Bài 13. Cho đầu vào là 2 xâu ký tự.

• Xâu target chỉ chứa các ký tự chữ cái và số
• xâu pattern chứa các mẫu bao gồm kyws tự chữ cái, chữ số và dâu ? và *

Xây dựng hàm kiểm tra xem xâu target có tuân theo mẫu mô tả bởi xâu pattern hay không.

Dấu ? thay cho 1 ký tự hoặc 1 chữ số
Dấu * thay cho 1 chuỗi ký tự hoặc số (có thể rỗng)

Ví dụ với các trường hợp sau thì hàm trả về giá trị TRUE.

isMatching("abab", "abab")
isMatching("abab", "a**b")
isMatching("ababab", "ab*b")
isMatching("", "*")
isMatching("aaaaaab", "*?*b")