Toán Rời Rạc trong cuộc đời lập trình viên | theNEXTvoz…

pepguard-violon said:

lý thuyết đồ thị là học xem đem ứng dụng làm ra các ứng dụng bản đồ, tìm đường đi, max bá. Hồi xưa mà tụi da trắng đã đỉnh cao như vậy. Công nhận nể tụi da trắng thượng đẳng quá.

honeyfox said:

Toán rời rạc cực kỳ quan trọng được học ngay sau các môn cơ sở về lập trình. Toán rời rạc rất rộng chứ ko phải là 1 môn riêng lẻ, trong IT/CS môn Toán rời rạc thường chỉ học cơ bản về mệnh đề logic, đại số Boole, tập hợp, tổ hợp. Các phần khác của toán rời rạc được chia làm nhiều môn khác như lý thuyết số, lý thuyết trò chơi, lý thuyết đồ thị, topology, lý thuyết Automat,... Tính tổng các môn thuộc về toán rời rạc đã chiếm gần một phần ba chương trình đào tạo rồi.

honeyfox said:

xử lý ngôn ngữ, AI, ML,... cả nùi thứ chứ ko chỉ mỗi bản đồ.

Thích Màu Hường said:

Rồi ra đi làm bao nhiêu người ứng dụng vào làm rồi. Coder ở VN toàn code web, mobile ứng dụng thế nào vậy bạn? Viết ra để hù dọa người ta à?

Lý thuyết đồ thị ứng dụng vào xử lý ngôn ngữ, AI, ML thế nào vậy bạn? Nó có ứng dụng đó nhưng ra đời đi làm ko phải ai cũng đụng tới. Biết gì về xử lý ngôn ngữ, AI, ML ko mà chém.

Hỏi thật thím đi làm bao năm rồi và ứng dụng toán rời rạc đc nhiều thế nào mà nói là cực kỳ quan trọng.

Thích Màu Hường said:

Hỏi thật thím đi làm bao năm rồi và ứng dụng toán rời rạc đc nhiều thế nào mà nói là cực kỳ quan trọng.

Thích Màu Hường said:

Rồi ra đi làm bao nhiêu người ứng dụng vào làm rồi. Coder ở VN toàn code web, mobile ứng dụng thế nào vậy bạn? Viết ra để hù dọa người ta à?

Thích Màu Hường said:

Lý thuyết đồ thị ứng dụng vào xử lý ngôn ngữ, AI, ML thế nào vậy bạn? Nó có ứng dụng đó nhưng ra đời đi làm ko phải ai cũng đụng tới. Biết gì về xử lý ngôn ngữ, AI, ML ko mà chém.

honeyfox said:

Tôi đi làm chưa lâu lắm, chỉ mới 15 năm thôi.
Tôi ko rõ bạn có code hay ko, nhưng khi viết AND/OR/XOR/NOT là đã dùng đại số Boole. Ko hiểu đại số Boole chắc viết cả mớ if lồng vào nhau.


Tôi ko chắc mấy bạn code web ở VN viết những gì, nhưng tôi thường phải dùng DAG và sắp xếp topo để xử lý dependencies, ko học lý thuyết đồ thị thì tạch DAG chắc.

Tôi ko làm về AI và ML, nhưng kiến thức CS ở đại học dạy tôi rằng mấy thằng này dùng đồ thị để biểu diễn. Mấy bạn mang tiếng làm AI hay ML mà chỉ biết gọi lib có sẵn thì thôi tôi ko tính.

Thích Màu Hường said:

Cái boole tôi đã nói ở trên khi trả lời chủ thớt rồi. Theo tôi đó là cái ứng dụng nhiều nhất còn lại mấy cái thím nói thì thím nghĩ bao nhiêu % coder xài tới? Dạo 1 vòng các tin tuyển dụng xem bao nhiêu job đòi mấy cái advance của toán rời rạc?

cuuthu said:

Mình là một người không theo học đại học chính quy, thường hay nghe môn Toán Rời Rạc là một trong những môn đại cương quan trọng nhất của developer
Cho mình xin ý kiến của những người đã đi làm về mức quan trọng của môn này

Và quan trọng là cho mình xin những keyword tài liệu và khóa học có thể giúp nắm vững môn này trong lòng bàn tay (và lòng bàn chân)

honeyfox said:

tuyển dụng chỉ đòi mỗi cái bằng đại học thôi, mà bằng đại học là đã bao gồm toán rời rạc từ cơ bản đến nâng cao. Mấy ông chuyên code web là đã xài lý thuyết đồ thị trong vô thức rồi, bài toán tree traversal cơ bản đấy.

Thích Màu Hường said:

1. Đừng đánh đồng chuyện yêu cầu cái bằng đại học với yêu cầu về toán rồi rạc. Đi phỏng vấn các cty người ta có hỏi toán rời rạc không?

Thích Màu Hường said:

2. Nếu xài được ở mức vô thức thì cái kiến thức về toán rời rạc có cần hay ko? Nói như thím thì lập trình viên ngôn ngữ cấp cao cũng cần phải có kiến thức về điện tử, vi mạch, mã máy mới làm được à?

Thích Màu Hường said:

3. Chủ thớt hỏi về Toán Rời Rạc trong cuộc đời lập trình viên thì trả lời cho thực tế. Đừng đem mấy cái mà chỉ khoảng 10% người xài ra rồi hù dọa người ta.

xuanphongdocco said:

Hi vọng bấy nhiêu đủ nhiều cho bạn https://cuuduongthancong.com/s/cau-truc-roi-rac?src=home

(Café) said:

Mình cũng mới đi làm có mấy năm thì mình quan sát thấy như thế này:

Nhóm 1: Thợ (gõ, sửa, bảo trì, kiểm thử) code thì cần ít, đến rất ít. (mình vẫn đang nằm trong số này).
Nhóm 2: Kiến trúc sư code, nhà nghiên cứu code (kiểu hàn lâm ấy) thì cần nhiều đến rất nhiều.

Trong công ty mình thì:
Nhóm 1: lương từ bình thường đến rất bình thường, chiếm phần đông nhân viên.
Nhóm 2: lương thì mình không biết cụ thể nghe đồn là cao, chiếm phần nhỏ. (ví dụ phòng mình sĩ số 100 ông thì có đúng 1 ông mình xếp nhóm này)

Vậy nên quay lại với chủ thớt, bạn thớt muốn đi vào nhóm nào?

Thích Màu Hường said:

Giờ bốc ông nhóm 2 bảo ra viết cái hàm duyệt cây mà không cho ôn lại xem có làm được ko.

Theo nghiệp code thì lên cao cần phân tích thiết kế thì kiến thức về Design Patterns, OOAD nó quan trọng gấp mấy lần cái toán rời rạc này.

Thích Màu Hường said:

Rồi ra đi làm bao nhiêu người ứng dụng vào làm rồi. Coder ở VN toàn code web, mobile ứng dụng thế nào vậy bạn? Viết ra để hù dọa người ta à?



Lý thuyết đồ thị ứng dụng vào xử lý ngôn ngữ, AI, ML thế nào vậy bạn? Nó có ứng dụng đó nhưng ra đời đi làm ko phải ai cũng đụng tới. Biết gì về xử lý ngôn ngữ, AI, ML ko mà chém.

Hỏi thật thím đi làm bao năm rồi và ứng dụng toán rời rạc đc nhiều thế nào mà nói là cực kỳ quan trọng.

hvhvhh said:

Không biết thì bạn có thể tra Google hoặc hỏi người khác. Ví dụ đơn giản nhé, trong Xử lý ngôn ngữ tự nhiên có một mảng là Question Answering dựa trên một hệ tri thức, hệ này có thể biểu diễn các đối tượng bằng đỉnh đồ thị, các quan hệ tương tác bằng các cạnh đồ thị. Việc trả lời câu hỏi chỉ là đơn thuần tìm ra được biểu diễn đúng của câu query (Semantics Parsing). Còn trong AI với ML hả, xin mời tìm đọc cuốn: "Graphs Representation Learning", có một chương dạy về Graph Neural Network. Tất nhiên là những hướng nghiên cứu tôi liệt kê đều còn đất sống, đang phát triển và đã được ứng dụng trong các bài toán thực tế.

Nói thì có thể làm nhiều người tự ái, thế hệ Voz "tân" bây giờ không có chuyện tìm hiểu trước khi trả lời, khác xa với thời còn ở forums cũ.

HoangVu99 said:

Em định hướng theo web, app nhưng mà trong toán rời rạc biết mỗi boole với lí thuyết đồ thị thôi có đủ ko các anh? Vì học trường làng nên họ ko dạy sâu vào phần này.

BigHeadCrew said:

Ngon phết. Thím làm đó hả? Ai học hết mớ này chắc đắc đạo luôn rồi

BaronNashor said:

@Fire Of Heart

dangmt said:

Nói chung dev đi làm chẳng bao giờ đụng đến giải thuật, thuật toán cả đâu. Lôi mấy cái AI, machine learning ra hù dọa chi vậy.

xuanphongdocco said:

Nếu hỏi trên đời có cái gì công bằng? Thì mình có thể trả lời một trong số đó là kiến thức - nó có thể phát đều cho tất cả mọi người, có điều không phải ai cũng muốn lấy chúng!

dangmt said:

Chuẩn rồi bạn. Lấy làm gì cho nặng đầu. Trong khi chẳng có ứng dụng gì.

HoangVu99 said:

Em định hướng theo web, app nhưng mà trong toán rời rạc biết mỗi boole với lí thuyết đồ thị thôi có đủ ko các anh? Vì học trường làng nên họ ko dạy sâu vào phần này.

nntgwww said:

Chỉ code web, app ko AI ML thì ko cần phải vô 2pic này

Nix said:

Mình nói chung thôi nhé...trên này lắm ông cứ suy nghĩ "làm dev bt có bao giờ đụng đến abc,xyz đâu...học làm éo gì...blah blah" rồi đi phổ cập trong mấy topic như này
Rồi qua topic khoe lương chửi dev 2-3k là xạo lol, chém gió, cào phím
Rồi vài ông thì lập topic than thở, hỏi làm sao để lương cao lên hả các bác...
Kiến thức nào cũng có giá của nó cả

bribnt said:

Ngay trên kia có người chỉ ra ít nhất 3 ứng dụng của toán rời rạc trong code Web kìa.

Đơn giản hơn, chẳng lẽ cả đời đi code không bao giờ gặp một bài toán đếm số tổ hợp nào à? Rồi liên quan với nó là tính tỷ lệ xuất hiện một tổ hợp nào đó.
Đồ thị thì đi đâu cũng gặp, nhiều người nói rồi không cần nhắc lại nữa.

Mấy cái lý thuyết toán này nó có trước AI ML vài trăm năm đó, mục đích người ta cũng phát triển thuật toán vốn không phải cho AI đâu.

Sent from Xiaomi Redmi 5A using vozFApp

xuanphongdocco said:

Không đâu bạn, chả là dạo trước có đi tìm lại tài liệu thì ra trang này. Tui không biết ai làm ra trang này nữa!

cuuduongthancong.com said:

Tôi nhé
Ở đây còn nhiều hơn này, do tên môn học khác
https://cuuduongthancong.com/s/toan-roi-rac

testacc007 said:

tôi thấy toán rời rạc ko quan trọng bằng thuật toán và cơ sở dữ liệu, mấy cái cần dùng cho software engineer sau này thì cũng khá đơn giản, ko có gì quá phức tạp như nội dung môn học

cuuduongthancong.com said:

Tôi nhé
Ở đây còn nhiều hơn này, do tên môn học khác
https://cuuduongthancong.com/s/toan-roi-rac

Thích Màu Hường said:

Giờ bốc ông nhóm 2 bảo ra viết cái hàm duyệt cây mà không cho ôn lại xem có làm được ko.

Theo nghiệp code thì lên cao cần phân tích thiết kế thì kiến thức về Design Patterns, OOAD nó quan trọng gấp mấy lần cái toán rời rạc này.

bao.se7en said:

sẵn tiện có duyên đi ngang qua cái thớt này, các bác cho em hỏi 1 thằng ko biết gì về lập trình như em (background sơ sơ thì dùng máy tính thạo, tự vọc vạch phần mềm này nọ được, nói chung ko phải loại low-tech, ngày xưa tin pascal cũng được cô bốc đi đội tuyển nhưng lại chọn vô tuyển lý sau đéo hiểu kiểu gì tí trượt đại học nv1 thời em thi đại học còn phân ban ABCD nha) muốn bắt đầu tự học lập trình thì nên bắt đầu như thế nào. Công việc của em có liên quan 1 xíu đến web bán hàng, 1 xíu đến mấy cái app API của bọn wordpress, shopify các thứ, biết lập trình tự làmđược nhiều việc hơn cho dễ thở, chứ mùa dịch này đói kém quá sắp chết đói rồi

buonnguqua said:

Còn nhớ Pascal thì bắt đầu cài Visual Studio và mở youtube channel Kteam để học lại C++ đi, dùng C++ làm lại mấy bài tập năm xưa
Học C++ chỉ học đến phần OOP thôi
Phần con trỏ trong C thì bỏ qua, đừng có học
Rồi từ đó thích học gì thì học

nipevt said:

không học con trỏ thì sao học về phần đa hình trong OOP C++ nhỉ?

buonnguqua said:

Ờ hớ
Vậy học cơ bản thôi
Sau đó Oop thì học trên Java hoặc C#
Chứ học C++ đến con trỏ tẩu hỏa nhập ma chắc cú

buonnguqua said:

Còn nhớ Pascal thì bắt đầu cài Visual Studio và mở youtube channel Kteam để học C++ đi, dùng C++ làm lại mấy bài tập năm xưa
Học C++ chỉ học đến phần OOP thôi
Phần con trỏ trong C thì bỏ qua, đừng có học
Rồi từ đó thích học gì thì học

testacc007 said:

thật ra dev lương 2 3k cũng đâu mấy khi dùng cái toán rời rạc này

zhukov said:

C ko học contro thì học nó làm gì vậy ? Ai có điều kiện thì tốt nhất hãy học hết. Kiến thức mức căn bản ko hề cao siêu. Tự học trên gg ko thiếu thứ gì. Ko phải bằng cấp nhưng kiến thức thì cần.
Lập trình viên chí ít phải hiểu được cái máy chạy ntn ? Rồi dần dần giải thích được tại sao ko được lạm dụng cái này cái chai. ( Đệ quy ...abcxyz). Cứ bảo công việc ko cần ko học phế vkl. Hãy hiểu đang viết gì ... Và dưới cái đang viết là gì thì tốt hơn.

buonnguqua said:

Biết bao nhiêu sinh viên ù ù cạc cạc mất phương hướng vì môn C++ ở trường Đại Học không ?

zhukov said:

Tại sao vậy bạn ? Vì nó quá khó à ? Vậy thì tốt nhất lên đổi qua nghề khác !

buonnguqua said:

Ra trường anh đi làm code C++ được bao nhiêu năm mà cứ tỏ ra nguy hiểm thế
Giờ ở Tây môn Low Level Programming tức dạy về Pointer của C++ họ dạy ở năm gần cuối chứ không phải dạy ngay từ đầu như Việt Nam

prescolt said:

Thi đứa nào làm việc C thì học con trỏ, còn ko thì thôi, mà cái con trỏ này ai cũng bảo khó, mình thấy nó chỉ là do dễ nhầm lẫn cách dùng chứ bản chất nó đơn giản mà, xài riết thì quen cú pháp , biết khi nào cần xài thôi

buonnguqua said:

Biết bao nhiêu sinh viên ù ù cạc cạc mất phương hướng vì môn C++ ở trường Đại Học không ?
Ở Havard họ dạy hết 2 môn Computer Science cũng chả thấy đả động gì đến pointer đâu

buonnguqua said:

Ra trường anh đi làm code C++ được bao nhiêu năm mà cứ tỏ ra nguy hiểm thế
Giờ ở Tây môn Low Level Programming tức dạy về Pointer của C++ họ dạy ở năm gần cuối chứ không phải dạy ngay từ đầu như Việt Nam

Thích Màu Hường said:

Rồi ra đi làm bao nhiêu người ứng dụng vào làm rồi. Coder ở VN toàn code web, mobile ứng dụng thế nào vậy bạn? Viết ra để hù dọa người ta à?



Lý thuyết đồ thị ứng dụng vào xử lý ngôn ngữ, AI, ML thế nào vậy bạn? Nó có ứng dụng đó nhưng ra đời đi làm ko phải ai cũng đụng tới. Biết gì về xử lý ngôn ngữ, AI, ML ko mà chém.

Hỏi thật thím đi làm bao năm rồi và ứng dụng toán rời rạc đc nhiều thế nào mà nói là cực kỳ quan trọng.

anhsuperstar said:

Chắc ứng dụng bằng cách dạy lại cho sing viên đó thím ơi

Sent from Jarvis via nextVOZ

KiethA said:

Học con trỏ luôn đi rồi đá sang golang đợi thời tới thôi
Còn mê oop quá thì học java ngay từ đầu cho rồi.

zhukov said:

C ko học contro thì học nó làm gì vậy ? Ai có điều kiện thì tốt nhất hãy học hết. Kiến thức mức căn bản ko hề cao siêu. Tự học trên gg ko thiếu thứ gì. Ko phải bằng cấp nhưng kiến thức thì cần.
Lập trình viên chí ít phải hiểu được cái máy chạy ntn ? Rồi dần dần giải thích được tại sao ko được lạm dụng cái này cái chai. ( Đệ quy ...abcxyz). Cứ bảo công việc ko cần ko học phế vkl. Hãy hiểu đang viết gì ... Và dưới cái đang viết là gì thì tốt hơn.

_Covonho_ said:

mãi rồi cũng thấy trên voz có member có suy nghĩ giống mình :-*

zhukov said:

Chỉ tiếc giờ anh em thích tàu nhanh. Chẳng cần hiểu lạm dụng ngôn ngữ ....rồi đến fw and fw. Đến mệt ...
Mới hôm trước kèm một nhóc năm 3 CNTT. Thực sự thấy oải , nghe nó kể thầy vô tâm vs nghề vãi ra. Các thầy giờ mải kiếm tiền quên thế hệ trẻ.

_Covonho_ said:

mình ngày xưa được gặp cô giáo có tâm, nên cứ tập trung học căn bản ( mày main của mình là C) nên tiếp xúc vấn đề và ngôn ngữ mới nhanh lắm

karenshii said:

...

INTP said:

chắc là prefix trie gì à

bèo vậy

Nipin said:

Để tôi kể cho các bạn trường hợp cái app dưới sign tôi đang làm xem nó có cần học thuật toán hay không.

Nói đến cái webapp của tôi, thì nó là một cái công cụ dịch máy tiếng tàu. Nghe dịch máy thì rõ oai, nhưng về bản chất là thay thế 1:1 từ tiếng trung sang tiếng việt, ví dụ 程序员=>lập trình viên hay 码农=>code monkey... cho nên cái quan trọng nhất là dữ liệu từ điển đúng đắn đầy đủ, chứ không là thuật toán thông minh.

ví dụ kết quả cụ thể cho các bạn tham khảo: https://chivi.xyz/~dai-phung-da-canh-nhan/chuong-162-lau-nam-ban-an-cu-xbiquge-36253791

chuyện nó chẳng có gì, nếu như không nói đến việc dữ liệu từ điển nó nằm tầm 500k tới 1 triệu entries, mỗi entries dài từ 1 tới hơn 10 ký tự, và độ dài của input tiếng chung thường từ một chương 4000 chữ tới cả bộ vài triệu chữ (bộ dài nhất tôi đọc có khoảng 18 triệu chữ)... nếu không dùng algo + data structure, thì đảm bảo kết quả sẽ vô cùng khó đỡ.

khi tôi làm cái chivi này, từng có một bạn liên hệ với tôi qua fb hỏi là mình cũng làm một cái tương tự cũng gần năm năm rồi, nhưng mà ra kết quả rất chậm dù rằng chỉ có 30k entries (bổ sung: riêng hán việt đã khoảng hơn 12k entries rồi, 30k entries hầu như chỉ chứa những từ phổ biến nhất, hoàn toàn không đủ).

hỏi ra mới biết là cách bạn ấy dịch rất trực quan: chạy một vòng lặp cho tất cả cặp từ trung/việt có sẵn trong từ điển, với mỗi cặp thì lại dùng hàm replace thay thế tất cả cụm trung ở trên bằng cụm việt... thực ra thì nếu chỉ có 30k từ, cho input dài 4k chữ thì nó cũng không nhiều, tính theo "step" chắc cũng chỉ khoảng 300k tới 400k, dù là cái server ghẻ lở thì cũng có khả năng ra kết quả sau một vài giây...

vấn đề ở đây là bạn này có dùng một cái khác gọi là "luật nhân", nói nôm na là một kiểu ngữ pháp tiếng trung, ghép lại vài cụm từ được đánh dấu danh động tĩnh các kiểu thành một cụm từ mới với cấu trúc thuần việt hơn... ờ giải thích hơi dài dòng, tóm lại thì các bạn hiểu đơn giản là phép "nhân" này biến 30k entries thành 300k thậm chí nhiều hơn, và kết quả là....

(p/s: ngoài mấy cái webapp thì trước đó có một cái desktop app gọi là QuickTranslator, và tôi cũng được nghe kể những trải nghiệm "rùng rợn" của một số bạn lạm dụng công cụ này, ví dụ 1 triệu entries từ điển x 100+ "luật nhân", nghe nói dịch một chương truyện 5k chữ thôi cũng có thể tính bằng tiếng, ăn hơn chục GB ram)

Tôi nghe loáng thoáng cũng có vài người có giải pháp tốt hơn tí, kiểu như chạy một vòng lặp duyệt cái dữ liệu input, rồi trích ra các substring (độ dài < 10 gì đấy), nếu tìm được cụm từ việt phù hợp thì lưu kết quả vào, rồi nhảy qua độ dài cụm từ trung vừa thấy... về cơ bản thì khá ổn, ngoại trừ hai chuyện là mỗi index của string đầu vào)đều phải trích ra khoảng 10 substring gì đấy rồi tìm nghĩa việt, mà tìm nghĩa việt thì tuy dùng hash_map đúng là O(1) thật, nhưng thực tế cũng không đơn giản như vậy (hashing khá tốn kém). Vấn đề thứ hai là chạy từ trái sang phải như thế không hẳn là cách tốt nhất, vì có từ cần được ưu tiên hơn từ khác; ví dụ thành ngữ thường có 4 ký tự trở lên, hoặc tên người; chỉ dịch từ trái sang phải không ra được kết quả dịch tốt nhất có thể...

Các bạn có giải pháp gì tối ưu hơn có thể vào đây chém gió, cần thiết tôi có thể đưa thêm input (một file dữ liệu từ và một file text vài MB), tôi thấy đây là bài toán khá thú vị mặc dù cấu trúc dữ liệu tối ưu (mà tôi biết) thực ra cũng khá đơn giản :"> Lần cuối cùng tôi test thì thuật toán của tôi với dữ liệu là 200k từ + 10MB text file thì mất tầm 10s để dịch xong toàn bộ (bằng nodejs), kể ra cũng khá ổn, nhưng vẫn hóng xem có bạn nào nghĩ ra giải pháp hay hơn không :">

INTP said:

chắc là prefix trie gì à

bèo vậy

Nipin said:

hỏi ra mới biết là cách bạn ấy dịch rất trực quan: chạy một vòng lặp cho tất cả cặp từ trung/việt có sẵn trong từ điển, với mỗi cặp thì lại dùng hàm replace thay thế tất cả cụm trung ở trên bằng cụm việt... thực ra thì nếu chỉ có 30k từ, cho input dài 4k chữ thì nó cũng không nhiều, tính theo "step" chắc cũng chỉ khoảng 300k tới 400k, dù là cái server ghẻ lở thì cũng có khả năng ra kết quả sau một vài giây...

bribnt said:

Chỗ này không hiểu lắm, dùng hàm replace là theo đúng nghĩa đen luôn à? 30k từ là 30k lần replace, mỗi lần replace là phải tìm kiếm chuỗi rồi allocate với copy mem. Phải cỡ 30k * 4k = 120M thao tác là ít.

terms = [...30k entries]
input = "...4k chars"

for (trung, viet in terms) input = input.replace(trung, viet)

cuuduongthancong.com said:

Tôi nhé
Ở đây còn nhiều hơn này, do tên môn học khác
https://cuuduongthancong.com/s/toan-roi-rac

bribnt said:

Chỗ này không hiểu lắm, dùng hàm replace là theo đúng nghĩa đen luôn à? 30k từ là 30k lần replace, mỗi lần replace là phải tìm kiếm chuỗi rồi allocate với copy mem. Phải cỡ 30k * 4k = 120M thao tác là ít.

Nipin said:

Để tôi kể cho các bạn trường hợp cái app dưới sign tôi đang làm xem nó có cần học thuật toán hay không.

Nói đến cái webapp của tôi, thì nó là một cái công cụ dịch máy tiếng tàu. Nghe dịch máy thì rõ oai, nhưng về bản chất là thay thế 1:1 từ tiếng trung sang tiếng việt, ví dụ 程序员=>lập trình viên hay 码农=>code monkey... cho nên cái quan trọng nhất là dữ liệu từ điển đúng đắn đầy đủ, chứ không là thuật toán thông minh.

ví dụ kết quả cụ thể cho các bạn tham khảo: https://chivi.xyz/~dai-phung-da-canh-nhan/chuong-162-lau-nam-ban-an-cu-xbiquge-36253791

chuyện nó chẳng có gì, nếu như không nói đến việc dữ liệu từ điển nó nằm tầm 500k tới 1 triệu entries, mỗi entries dài từ 1 tới hơn 10 ký tự, và độ dài của input tiếng chung thường từ một chương 4000 chữ tới cả bộ vài triệu chữ (bộ dài nhất tôi đọc có khoảng 18 triệu chữ)... nếu không dùng algo + data structure, thì đảm bảo kết quả sẽ vô cùng khó đỡ.

khi tôi làm cái chivi này, từng có một bạn liên hệ với tôi qua fb hỏi là mình cũng làm một cái tương tự cũng gần năm năm rồi, nhưng mà ra kết quả rất chậm dù rằng chỉ có 30k entries (bổ xung: riêng hán việt đã khoảng hơn 12k entries rồi, 30k entries hầu như chỉ chứa những từ phổ biến nhất, hoàn toàn không đủ).

hỏi ra mới biết là cách bạn ấy dịch rất trực quan: chạy một vòng lặp cho tất cả cặp từ trung/việt có sẵn trong từ điển, với mỗi cặp thì lại dùng hàm replace thay thế tất cả cụm trung ở trên bằng cụm việt... thực ra thì nếu chỉ có 30k từ, cho input dài 4k chữ thì nó cũng không nhiều, dù là cái server ghẻ lở thì cũng có khả năng ra kết quả sau một vài giây...

vấn đề ở đây là bạn này có dùng một cái khác gọi là "luật nhân", nói nôm na là một kiểu ngữ pháp tiếng trung, ghép lại vài cụm từ được đánh dấu danh động tĩnh các kiểu thành một cụm từ mới với cấu trúc thuần việt hơn... ờ giải thích hơi dài dòng, tóm lại thì các bạn hiểu đơn giản là phép "nhân" này biến 30k entries thành 300k thậm chí nhiều hơn, và kết quả là....

(p/s: ngoài mấy cái webapp thì trước đó có một cái desktop app gọi là QuickTranslator, và tôi cũng được nghe kể những trải nghiệm "rùng rợn" của một số bạn lạm dụng công cụ này, ví dụ 1 triệu entries từ điển x 100+ "luật nhân", nghe nói dịch một chương truyện 5k chữ thôi cũng có thể tính bằng tiếng, ăn hơn chục GB ram)

Tôi nghe loáng thoáng cũng có vài người có giải pháp tốt hơn tí, kiểu như chạy một vòng lặp duyệt cái dữ liệu input, rồi trích ra các substring (độ dài < 10 gì đấy), nếu tìm được cụm từ việt phù hợp thì lưu kết quả vào, rồi nhảy qua độ dài cụm từ trung vừa thấy... về cơ bản thì khá ổn, ngoại trừ hai chuyện là mỗi index của string đầu vào)đều phải trích ra khoảng 10 substring gì đấy rồi tìm nghĩa việt, mà tìm nghĩa việt thì tuy dùng hash_map đúng là O(1) thật, nhưng thực tế cũng không đơn giản như vậy (hashing khá tốn kém). Vấn đề thứ hai là chạy từ trái sang phải như thế không hẳn là cách tốt nhất, vì có từ cần được ưu tiên hơn từ khác; ví dụ thành ngữ thường có 4 ký tự trở lên, hoặc tên người; chỉ dịch từ trái sang phải không ra được kết quả dịch tốt nhất có thể...

Các bạn có giải pháp gì tối ưu hơn có thể vào đây chém gió, cần thiết tôi có thể đưa thêm input (một file dữ liệu từ và một file text vài MB), tôi thấy đây là bài toán khá thú vị mặc dù cấu trúc dữ liệu tối ưu (mà tôi biết) thực ra cũng khá đơn giản :"> Lần cuối cùng tôi test thì thuật toán của tôi với dữ liệu là 200k từ + 10MB text file thì mất tầm 10s để dịch xong toàn bộ (bằng nodejs), kể ra cũng khá ổn, nhưng vẫn hóng xem có bạn nào nghĩ ra giải pháp hay hơn không :">

Thích Màu Hường said:

Rồi ra đi làm bao nhiêu người ứng dụng vào làm rồi. Coder ở VN toàn code web, mobile ứng dụng thế nào vậy bạn? Viết ra để hù dọa người ta à?



Lý thuyết đồ thị ứng dụng vào xử lý ngôn ngữ, AI, ML thế nào vậy bạn? Nó có ứng dụng đó nhưng ra đời đi làm ko phải ai cũng đụng tới. Biết gì về xử lý ngôn ngữ, AI, ML ko mà chém.

Hỏi thật thím đi làm bao năm rồi và ứng dụng toán rời rạc đc nhiều thế nào mà nói là cực kỳ quan trọng.

huyenoi said:

Ông đi làm bao nhiêu năm? Giờ vị trí của ông là gì? Team Lead? Manager? hay là dev quèn?
Tôi mới đi làm hơn năm mà thấy lý thuyết căn bản của toán rr giúp cho cv hơi bị nhiều đấy.
Tôi chỉ là dev quèn thôi nhé!

Thích Màu Hường said:

Đọc lại hết 5 pages cho kỹ xem ý tôi muốn nói gì. 1 năm kinh nghiệm thì con non lắm. Định nói đôi lời mà thấy cái post này nên xin phép ignore vậy

View attachment 206404

Nipin said:

Để tôi kể cho các bạn trường hợp cái app dưới sign tôi đang làm xem nó có cần học thuật toán hay không.

Nói đến cái webapp của tôi, thì nó là một cái công cụ dịch máy tiếng tàu. Nghe dịch máy thì rõ oai, nhưng về bản chất là thay thế 1:1 từ tiếng trung sang tiếng việt, ví dụ 程序员=>lập trình viên hay 码农=>code monkey... cho nên cái quan trọng nhất là dữ liệu từ điển đúng đắn đầy đủ, chứ không là thuật toán thông minh.

ví dụ kết quả cụ thể cho các bạn tham khảo: https://chivi.xyz/~dai-phung-da-canh-nhan/chuong-162-lau-nam-ban-an-cu-xbiquge-36253791

chuyện nó chẳng có gì, nếu như không nói đến việc dữ liệu từ điển nó nằm tầm 500k tới 1 triệu entries, mỗi entries dài từ 1 tới hơn 10 ký tự, và độ dài của input tiếng chung thường từ một chương 4000 chữ tới cả bộ vài triệu chữ (bộ dài nhất tôi đọc có khoảng 18 triệu chữ)... nếu không dùng algo + data structure, thì đảm bảo kết quả sẽ vô cùng khó đỡ.

khi tôi làm cái chivi này, từng có một bạn liên hệ với tôi qua fb hỏi là mình cũng làm một cái tương tự cũng gần năm năm rồi, nhưng mà ra kết quả rất chậm dù rằng chỉ có 30k entries (bổ xung: riêng hán việt đã khoảng hơn 12k entries rồi, 30k entries hầu như chỉ chứa những từ phổ biến nhất, hoàn toàn không đủ).

hỏi ra mới biết là cách bạn ấy dịch rất trực quan: chạy một vòng lặp cho tất cả cặp từ trung/việt có sẵn trong từ điển, với mỗi cặp thì lại dùng hàm replace thay thế tất cả cụm trung ở trên bằng cụm việt... thực ra thì nếu chỉ có 30k từ, cho input dài 4k chữ thì nó cũng không nhiều, dù là cái server ghẻ lở thì cũng có khả năng ra kết quả sau một vài giây...

vấn đề ở đây là bạn này có dùng một cái khác gọi là "luật nhân", nói nôm na là một kiểu ngữ pháp tiếng trung, ghép lại vài cụm từ được đánh dấu danh động tĩnh các kiểu thành một cụm từ mới với cấu trúc thuần việt hơn... ờ giải thích hơi dài dòng, tóm lại thì các bạn hiểu đơn giản là phép "nhân" này biến 30k entries thành 300k thậm chí nhiều hơn, và kết quả là....

(p/s: ngoài mấy cái webapp thì trước đó có một cái desktop app gọi là QuickTranslator, và tôi cũng được nghe kể những trải nghiệm "rùng rợn" của một số bạn lạm dụng công cụ này, ví dụ 1 triệu entries từ điển x 100+ "luật nhân", nghe nói dịch một chương truyện 5k chữ thôi cũng có thể tính bằng tiếng, ăn hơn chục GB ram)

Tôi nghe loáng thoáng cũng có vài người có giải pháp tốt hơn tí, kiểu như chạy một vòng lặp duyệt cái dữ liệu input, rồi trích ra các substring (độ dài < 10 gì đấy), nếu tìm được cụm từ việt phù hợp thì lưu kết quả vào, rồi nhảy qua độ dài cụm từ trung vừa thấy... về cơ bản thì khá ổn, ngoại trừ hai chuyện là mỗi index của string đầu vào)đều phải trích ra khoảng 10 substring gì đấy rồi tìm nghĩa việt, mà tìm nghĩa việt thì tuy dùng hash_map đúng là O(1) thật, nhưng thực tế cũng không đơn giản như vậy (hashing khá tốn kém). Vấn đề thứ hai là chạy từ trái sang phải như thế không hẳn là cách tốt nhất, vì có từ cần được ưu tiên hơn từ khác; ví dụ thành ngữ thường có 4 ký tự trở lên, hoặc tên người; chỉ dịch từ trái sang phải không ra được kết quả dịch tốt nhất có thể...

Các bạn có giải pháp gì tối ưu hơn có thể vào đây chém gió, cần thiết tôi có thể đưa thêm input (một file dữ liệu từ và một file text vài MB), tôi thấy đây là bài toán khá thú vị mặc dù cấu trúc dữ liệu tối ưu (mà tôi biết) thực ra cũng khá đơn giản :"> Lần cuối cùng tôi test thì thuật toán của tôi với dữ liệu là 200k từ + 10MB text file thì mất tầm 10s để dịch xong toàn bộ (bằng nodejs), kể ra cũng khá ổn, nhưng vẫn hóng xem có bạn nào nghĩ ra giải pháp hay hơn không :">

Usernem said:

Thế cái thuật toán nó ra sao anh

{
  k: '',
  v: '',
  t: {
    a: {
      k: 'a',
      v: '1'
      t: {
        b: {
          k: 'ab',
          v: '21',
          t: {}
        }
      }
    },
    b: {
      k: 'b'
      v: '2',
      t: {}
    }
  }
}

Billr_rizer said:

Bài toán tokenize à thím? Quả này cũng loáng thoáng thấy các cụ trên cty dùng mấy cái word embedding kiểu word2vec, rồi thì cũng dùng mấy cái model RNN, nói chung là dân gà mờ như mình chỉ biết đến thế, không dám gõ phím to hơn.

Nipin said:

có gì đặc biệt đâu, dùng trie như mấy bạn trên nói thôi.
ví dụ như lưu a=1;b=2;ab=21 thì sẽ thành cái cấu trúc dạng thế này:

Code:

{
  k: '',
  v: '',
  t: {
    a: {
      k: 'a',
      v: '1'
      t: {
        b: {
          k: 'ab',
          v: '21',
          t: {}
        }
      }
    },
    b: {
      k: 'b'
      v: '2',
      t: {}
    }
  }
}

cụ thể implement thế nào, dùng nó thế nào thì nó lại là chỗ khác, cơ mà về cơ bản thì thế.

trungpham90 said:

Nếu cụm từ chỉ dừng ở 2-5 từ thì tôi nghĩ có thể dùng rolling hash (Rabin-Karp algorithm), khi duyệt thì chỉ lưu hash của 4 cụm từ gần nhất thôi. Ý tưởng thì thế nhưng ko biết có làm đc ko vì ko có kn xử lý tiếng Trung.

Nipin said:

tôi nghĩ là không hợp.

tất cả các thuật toán tìm kiếm string đều là optimize cho việc tìm string này trong string kia, rồi early return nếu không match. ở đây là tìm tất cả các matches ở tất cả các vị trí cho vài trăm nghìn cái substrings.

với lạ độ dài của cụm từ thì không có giới hạn đâu, có lúc nó chỉ có 1 từ, có lúc nó là cả cụm thành ngữ thì có thể lên tới 8 ký tự thậm chí là hơn (vd 青出于蓝而胜于蓝 hay 苏维埃社会主义共和国联盟)

Sniper_V2 said:

Nếu tiếng tàu như ông nipin kia nói, tức A đứng cạnh B sẽ cho ra từ C có nghĩa mới, ABC lại suy ra D, và có thể có đến ABCDEFGHIJKL đứng cạnh nhau tạo thành Z thì bài này không dễ xơi nếu dùng ML/DL đâu, tokenizer xịn nhất hiện nay cũng quỳ thôi. Kể cả có tokenizer hoàn hảo đi nữa thì vẫn vướng bài toán mapping từ từ vựng tiếng trung => tiếng việt nếu lượng từ trong từ điển quá lớn và số từ input vào cũng lớn (tuy là sau khi tách từ thì việc mapping đã trở thành dễ hơn rất nhiều) .
Nếu đổi lại đây là bài toán mapping Anh => Việt thì giải pháp tokenizer khả thi hơn nhiều, còn có nhanh hơn cái trie gì đó thì mình không rõ

Billr_rizer said:

Vấn đề ABCDEF ra từ Z mình nghĩ dùng các mô hình NN tốt chứ nhỉ, trước kia truyền thống thì dùng HMM, MEMM, CRF,...đến thời gian gần đây thì bắt đầu chuyển dịch sang RNN. Có gì sai thím chỉ giáo.
Vấn đề về mapping từ vựng giữa 2 bộ từ điển thì mình k biết mấy, gốc mình không phải dân CNTT nên không dám bàn

bribnt said:

Với prefix trie nếu đã build sẵn trie thì độ phức tạp của phép tìm kiếm từ tiếng Việt tương ứng là O(m), với m là số ký tự của chuỗi tiếngTrung. Mình không nghĩ là các mô hình ML có thể nhanh hơn được cỡ này.

Thích Màu Hường said:

ML cụ thể trường hợp này là Deep Learning là làm việc với data dạng numeric. Cái input text sẽ được convert thành ma trận số, lúc dịch từ input -> output là các phép nhân ma trận với nhau nên nói về tốc độ thì chưa biết bên nào hơn bên nào. Một cái là tính toán số học, cái kia là search tree.

Nói về tính hiệu quả thì dùng Deep Learning hiệu quả hơn rất nhiều. Chấp hết các case khó như bên trên, chỉ cần có training set đủ lớn là được.

thl2009 said:

Ngày xưa học môn này, kiếm được cuốn Toán rời rạc và ứng dụng trong tin học, dày cả 500 trang.
ngày đấy bị nghiền cái lý thuyết đồ thị, đọc hoài

ductam125 said:

Quyển này hả anh? Nó hơn 800 trang mà View attachment 215073

Billr_rizer said:

Vấn đề ABCDEF ra từ Z mình nghĩ dùng các mô hình NN tốt chứ nhỉ, trước kia truyền thống thì dùng HMM, MEMM, CRF,...đến thời gian gần đây thì bắt đầu chuyển dịch sang RNN. Có gì sai thím chỉ giáo.
Vấn đề về mapping từ vựng giữa 2 bộ từ điển thì mình k biết mấy, gốc mình không phải dân CNTT nên không dám bàn

bribnt said:

Ma trận kích thước bao nhiêu, cần nhân bao nhiêu lần?

Dùng trie hay suffix tree chỉ mất O(m) thời gian thôi.
Phép search tree thì đúng là có điểm yếu về không tận dụng tốt CPU cache, cứ cho là miss cache L3 100% thì một lần tìm kiếm một byte trong tree mất khoảng tối đa 200 cycle.
Phép nhân ma trận độ phức tạp khoảng O(m*n*p), chấp luôn cache hit 100% latency 0, sử dụng AVX256 tính được 8 phép tính cùng lúc thì chỉ cần mnp > 1600 là chậm hơn tree rồi. Mà với mấy cái model ML ngày nay thì con số đó chỉ là muỗi.

7a2vodoi said:

Cuốn này giờ còn ở đâu bán không bác, hay còn sách cũ thôi ạ.
Thấy trên mạng có PDF nhưng mà vẫn thích mua sách hơn

Sniper_V2 said:

Thím thông não giúp em chỗ này với ạ

ductam125 said:

Giờ mua sách cũ đã khó rồi anh ạ, sách mới chắc ko tìm dc đâu

buonnguqua said:

Ra trường anh đi làm code C++ được bao nhiêu năm mà cứ tỏ ra nguy hiểm thế
Giờ ở Tây môn Low Level Programming tức dạy về Pointer của C++ họ dạy ở năm gần cuối chứ không phải dạy ngay từ đầu như Việt Nam

Fire Of Heart said:

Mới ngó qua mục lục của cuốn toán rời rạc thì thấy cái chủ đề nào cũng là những cái ngày xưa học mòn, và giờ nghĩ là cũng khá cần thiết đó.

Chương 1: Logic, Tập hợp và Hàm
Chương 2: Thuật toán, các số nguyên và ma trận -> bắt buộc phải học
Chương 3: Suy luận toán học
Chương 4: Đếm các phần tử
Chương 5: Kĩ thuật đếm cao cấp
Chương 6: Quan hệ
Chương 7: Đồ thị -> bắt buộc phải học
Chương 8: Cây -> bắt buộc phải học
Chương 9: Đại số boole -> bắt buộc phải học
Chương 10: Mô hình toán

Mà để học dc chương 7 8 9 thì sẽ cần kiến thức của các chương trước

NobiEmon said:

em mới tốt nghiệp cao đẳng, đang chờ liên thông đại học nhưng sợ ngộp toán nên quyết định học qua trước khi đến trường, list thím liệt kê ở trên là đầy đủ và đúng thứ tự đúng ko ạ

Fire Of Heart said:

List theo sách nên thứ tự mình nghĩ là chuẩn đấy bạn ạ.

NobiEmon said:

à thím cho em hỏi thêm ở hẹ đại học có cả thảy là bao nhiêu loại toán vậy, tại thấy cái gì mà cao cấp rồi lại rời rạc rồi lại xác xuất

nên thấy lộn xộn quá, thím có thể cụ thể cho em biết được không ạ

Fire Of Heart said:

Toán rời rạc, giải tích, đại số.
Bảo chia loại toán thì mình cũng ko rõ, chắc là tùy theo giáo án của từng trường.
Giải tích và đại số thì dễ hiểu rồi.
Còn toán rời rạc thì kiểu nó là tên chung của các ngành toán mà đối tương là các tập hợp rời rạc, và là cơ sở cho khoa học máy tính, ví dụ như lý thuyết đồ thị, mật mã học, lý thuyết tính toán, v.v...
Xác suất thống kê thì cũng quan trọng, liên quan tới máy học, AI các kiểu sau này.

Toán cao cấp nếu mình nhớ ko nhầm là học giải tích với đại số thì phải. Lâu quá nên ko nhớ chính xác.

NobiEmon said:

à thím cho em hỏi thêm ở hẹ đại học có cả thảy là bao nhiêu loại toán vậy, tại thấy cái gì mà cao cấp rồi lại rời rạc rồi lại xác xuất

nên thấy lộn xộn quá, thím có thể cụ thể cho em biết được không ạ

bribnt said:

Bản chất của các loại tree là mỗi node có một danh sách con trỏ, những con trỏ này là trỏ đến một node khác. Địa chỉ bộ nhớ các node không liên tục mà rải rác nên không tận dụng tốt CPU Cache, vì cache có đặc tính Spatial locality, khi load giá trị trong RAM tại một địa chỉ thì nó cũng tự động prefetch một số ô nhớ gần đó để đưa vào cache. Linked list cũng có tính chất tương tự tree, cho nên mới có lời khuyên là nên ưu tiên dùng array, khi không dùng được thì tìm cách convert về array.

Đoạn sau là đang giả sử tình huống tệ nhất, tất các các phép reference đến node con trong trie đều miss cache , phải load lại từ đầu trong RAM ra, một lần như vậy mất khoảng 150 - 200 CPU cycle.

Sniper_V2 said:

Bác cho em hỏi thếm mấy cái này được không ạ Ngày xưa em dốt OS lắm
Mấy cái tree này nó không có cơ chế như TLB (Translation lookaside buffer) của RAM hả bác? Theo em nghĩ nó có thể implement 1 cái như multi indexing trong DBMS để tránh việc miss cache mà nhỉ?
Tại sao dùng Array lại tận dụng tốt cache hơn ạ?
Với lại sao bác tính được là khoảng 150-200 CPU cycle được ạ

bribnt said:

TLB là để cache lại quá trình translate từ địa chỉ ảo sang địa chỉ vật lý, còn giá trị tại các ô nhớ thì là ở CPU Cache (L1/L2/L3).

Về cơ bản một cài đặt tree kiểu bình thường là như này: allocate một node X tại địa chỉ A, rồi allocate node Y tại địa chỉ B,... Vì các phép allocate là riêng biệt tách rời nhau nên tùy vào thuật toán cụ thể mà A với B có thể có giá trị cách xa nhau trong không gian bộ nhớ.
Trong trường hợp đó, khi truy cập node X, cpu sẽ prefetch bộ nhớ tại địa chỉ A và các địa chỉ lân cận vào cache. Nếu cache mà hết thì sẽ phải xoá (evict) bớt những mục cũ đưa xuống cache level thấp hơn, từ L1 xuống L2, L2 xuống L3, nếu bị xoá khỏi L3 thì tức không còn trong cache.
Sau đó, đến lúc truy cập vào Y tại địa chỉ B, vì A B cách xa nhau nên nhiều khả năng là B sẽ không tìm thấy trong cache, hoặc chỉ có ở cache level thấp. Khi đó CPU lại phải load lại giá trị của ô nhớ B từ RAM vào.
Vì thế cho nên mới nói tree thường dùng cache không hiệu quả. Với array thì khác, các element của nó được lưu ở các địa chỉ liên tục, lại kích thước nhỏ (không phải lưu địa chỉ của node khác trong array) nên khi truy cập tuần tự khả năng một node đã có trong cache là rất cao.
Tất nhiên vẫn có cách tối ưu hóa tree, nếu biết được access pattern của các node trong tree thì có thể viết custom allocator để sao cho các node thường được truy cập liên tiếp ở gần nhau trong bộ nhớ.

150 - 200 CPU cycle là latency của phép truy cập bộ nhớ RAM từ CPU. Giả sử CPU 4 GHz thì thời gian tuyệt đối là 50 ns. Con số này khoảng mấy chục năm nay chưa được cải thiện mấy.

Đoạn trên mình đã bỏ qua phần địa chỉ ảo - địa chỉ vật lý để cho đơn giản, đem vào thì vấn đề còn phức tạp hơn. Vì thực tế memory được chia thành từng page kích thước chuẩn là 4KB, nếu địa chỉ nằm trong cùng một page ảo thì nó sẽ mới thực sự gần nhau về mặt vật lý. Nhưng nếu thuộc 2 page khác nhau thì không, khi vượt qua page boundary thì vẫn phải fetch lại từ RAM như thường, và có thể còn tốn hơn vì có thể lúc đó TLB cache cũng bị miss. Cho nên hiện nay có khái niệm Huge Pages, tức là page kích thước lớn, khoảng 2MB hoặc 1GB, nhiều ứng dụng nhất là database cho phép cấu hình sử dụng hugepage để tự mình nó quản lý bộ nhớ, giảm vấn đề như trên.

Sent from Xiaomi Redmi 5A using vozFApp

Sniper_V2 said:

Bác cho em hỏi vài câu nữa được không ạ, không biết có làm phiền bác quá k ạ
Tại sao Array lại tốt hơn Linked-List trong việc tận dụng cache ạ? Vì theo em nhớ là LL thì link đến nhau, tận dụng các khoảng trống giữa các memory block tốt hơn Dynamic Array (Theo em biết thì phần lớn ngôn ngữ hiện đại sử dụng chiến thuật amortization khi allocate vùng nhớ cho array).
Có lí do nào khác ngoài Array chỉ lưu giá trị so với LL phải lưu thêm pointer không ạ

Sniper_V2 said:

S ố lượng data block (vị trí KHÔNG liên tục) có thể fetch tối đa 1 lần từ Ram => Cache là bao nhiêu ạ ? Theo như em đọc thì thời gian tối thiểu để RAM phản hồi lại CPU = Cas latency + Thời gian tìm kiếm block data (tRCD+tRP), tuy nhiên em không rõ trong controller của Ram liệu có cơ chế như multi thread không, để nhiều lệnh tìm kiếm từ multi thread trên CPU để seeking đồng thời như HDD, hay nó chỉ tìm được data block theo tuần tự.

Standard name	Memory clock (MHz)	I/O bus clock (MHz)	Data rate (MT/s)	Module name	Peak trans- fer rate (MB/s)	Timings CL-tRCD-tRP	CAS latency (ns)
DDR4-3200W DDR4-3200AA DDR4-3200AC	400	1600	3200	PC4-25600	25600	20-20-20 22-22-22 24-24-24	12.5 13.75 15

• Deactivate Row cũ, precharge Row mới, tốn tRP
• Select Row mới, tốn tRAS
• Delay giữa Row và Column: tRCD
• Select Column: tCAS
• Transfer data về CPU cache

bribnt said:

Bản chất của các loại tree là mỗi node có một danh sách con trỏ, những con trỏ này là trỏ đến một node khác. Địa chỉ bộ nhớ các node không liên tục mà rải rác nên không tận dụng tốt CPU Cache, vì cache có đặc tính Spatial locality, khi load giá trị trong RAM tại một địa chỉ thì nó cũng tự động prefetch một số ô nhớ gần đó để đưa vào cache. Linked list cũng có tính chất tương tự tree, cho nên mới có lời khuyên là nên ưu tiên dùng array, khi không dùng được thì tìm cách convert về array.

Đoạn sau là đang giả sử tình huống tệ nhất, tất các các phép reference đến node con trong trie đều miss cache , phải load lại từ đầu trong RAM ra, một lần như vậy mất khoảng 150 - 200 CPU cycle.

trgiangvp3 said:

Bác @bribnt cho hỏi là những kiến thức bác nói trong topic này là từ môn học/tài liệu nào thế ạ.

honeyfox said:

Tôi ko chắc mấy bạn code web ở VN viết những gì, nhưng tôi thường phải dùng DAG và sắp xếp topo để xử lý dependencies, ko học lý thuyết đồ thị thì tạch DAG chắc.

cuuthu said:

Mình là một người không theo học đại học chính quy, thường hay nghe môn Toán Rời Rạc là một trong những môn đại cương quan trọng nhất của developer
Cho mình xin ý kiến của những người đã đi làm về mức quan trọng của môn này

Và quan trọng là cho mình xin những keyword tài liệu và khóa học có thể giúp nắm vững môn này trong lòng bàn tay (và lòng bàn chân)

1 Sets and Logic

1.1 Sets

1.2 Propositions

1.3 Conditional Propositions and Logical Equivalence

1.4 Arguments and Rules of Inference

1.5 Quantifiers

1.6 Nested Quantifiers

Problem-Solving Corner: Quantifiers



2 Proofs

2.1 Mathematical Systems, Direct Proofs, and Counterexamples

2.2 More Methods of Proof

Problem-Solving Corner: Proving Some Properties of Real Numbers

2.3 Resolution Proofs

2.4 Mathematical Induction

Problem-Solving Corner: Mathematical Induction

2.5 Strong Form of Induction and the Well-Ordering Property Notes Chapter Review Chapter Self-Test Computer Exercises



3 Functions, Sequences, and Relations

3.1 Functions

Problem-Solving Corner: Functions

3.2 Sequences and Strings

3.3 Relations

3.4 Equivalence Relations

Problem-Solving Corner: Equivalence Relations

3.5 Matrices of Relations

3.6 Relational Databases



4 Algorithms

4.1 Introduction

4.2 Examples of Algorithms

4.3 Analysis of Algorithms

Problem-Solving Corner: Design and Analysis of an Algorithm

4.4 Recursive Algorithms



5 Introduction to Number Theory

5.1 Divisors

5.2 Representations of Integers and Integer Algorithms

5.3 The Euclidean Algorithm

Problem-Solving Corner: Making Postage

5.4 The RSA Public-Key Cryptosystem



6 Counting Methods and the Pigeonhole Principle

6.1 Basic Principles

Problem-Solving Corner: Counting

6.2 Permutations and Combinations

Problem-Solving Corner: Combinations

6.3 Generalized Permutations and Combinations

6.4 Algorithms for Generating Permutations and Combinations

6.5 Introduction to Discrete Probability

6.6 Discrete Probability Theory

6.7 Binomial Coefficients and Combinatorial Identities

6.8 The Pigeonhole Principle



7 Recurrence Relations

7.1 Introduction

7.2 Solving Recurrence Relations

Problem-Solving Corner: Recurrence Relations

7.3 Applications to the Analysis of Algorithms



8 Graph Theory

8.1 Introduction

8.2 Paths and Cycles

Problem-Solving Corner: Graphs

8.3 Hamiltonian Cycles and the Traveling Salesperson Problem

8.4 A Shortest-Path Algorithm

8.5 Representations of Graphs

8.6 Isomorphisms of Graphs

8.7 Planar Graphs

8.8 Instant Insanity



9 Trees

9.1 Introduction

9.2 Terminology and Characterizations of Trees

Problem-Solving Corner: Trees

9.3 Spanning Trees

9.4 Minimal Spanning Trees

9.5 Binary Trees

9.6 Tree Traversals

9.7 Decision Trees and the Minimum Time for Sorting

9.8 Isomorphisms of Trees

9.9 Game Trees



10 Network Models

10.1 Introduction

10.2 A Maximal Flow Algorithm

10.3 The Max Flow, Min Cut Theorem

10.4 Matching

Problem-Solving Corner: Matching



11 Boolean Algebras and Combinatorial Circuits

11.1 Combinatorial Circuits

11.2 Properties of Combinatorial Circuits

11.3 Boolean Algebras

Problem-Solving Corner: Boolean Algebras

11.4 Boolean Functions and Synthesis of Circuits

11.5 Applications



12 Automata, Grammars, and Languages

12.1 Sequential Circuits and Finite-State Machines

12.2 Finite-State Automata

12.3 Languages and Grammars

12.4 Nondeterministic Finite-State Automata

12.5 Relationships Between Languages and Automata



Appendix

A Matrices

B Algebra Review

C Pseudocode

References

Hints and Solutions to Selected Exercises Index

qkhanhpro said:

Quan trọng, phù thuộc vào định hướng phát triển của bạn

Lời khuyên cá nhân của tôi là đọc/học cảm thấy vào thì tốt. Thấy khó học/khó hiểu hay chán ghét nó thì cũng không nhất thiết phải quá lo lắng.

Tôi tự đánh giá mình ở trình độ so với 1 quyển toán rời rạc đại cương thì hiểu được 2 phần trên 10. Trong 2 phần đó, hiểu đến mức đem áp dụng vào thực tiễn 2 trên 10 nữa. Như thế là tạm đủ cho bản thân tôi



View attachment 244252

Giáo trình trường dạy đây, sách của Pearson

cuuthu said:

cảm ơn bác
Trường bác dạy giáo trình nước ngoài à, bác học trường gì

VImask said:

Hên quá mình code mobile toàn gọi Api nên k dính cái này. Chắc làm thợ code thôi

via theNEXTvoz for iPhone

xuanphongdocco said:

Hi vọng bấy nhiêu đủ nhiều cho bạn https://cuuduongthancong.com/s/cau-truc-roi-rac?src=home

flowerfx2 said:

code mobile thì chịu khó xài cái này nhiều vô, tôi dùng cây nhị phân để lưu trữ dự liệu nè, rồi viết ra thành 1 lib, mấy app mobile hay game thì cứ gắn lib vô bao xài, gọi thông tin ra nhanh hơn dùng sql hay json lưu trữ
ra ngoài đi làm thì tôi dùng khá nhiều lý thuyết của toán rời rạc để áp vào code và mind set, chứ gọi API ra để chạy thì perf kém lắm, chưa kể tính linh hoạt của ứng dụng hay thư viện để nâng cấp và dùng cho các dự án sau nữa

Nipin said:

Để tôi kể cho các bạn trường hợp cái app dưới sign tôi đang làm xem nó có cần học thuật toán hay không.

Nói đến cái webapp của tôi, thì nó là một cái công cụ dịch máy tiếng tàu. Nghe dịch máy thì rõ oai, nhưng về bản chất là thay thế 1:1 từ tiếng trung sang tiếng việt, ví dụ 程序员=>lập trình viên hay 码农=>code monkey... cho nên cái quan trọng nhất là dữ liệu từ điển đúng đắn đầy đủ, chứ không là thuật toán thông minh.

ví dụ kết quả cụ thể cho các bạn tham khảo: https://chivi.xyz/~dai-phung-da-canh-nhan/chuong-162-lau-nam-ban-an-cu-xbiquge-36253791

chuyện nó chẳng có gì, nếu như không nói đến việc dữ liệu từ điển nó nằm tầm 500k tới 1 triệu entries, mỗi entries dài từ 1 tới hơn 10 ký tự, và độ dài của input tiếng chung thường từ một chương 4000 chữ tới cả bộ vài triệu chữ (bộ dài nhất tôi đọc có khoảng 18 triệu chữ)... nếu không dùng algo + data structure, thì đảm bảo kết quả sẽ vô cùng khó đỡ.

khi tôi làm cái chivi này, từng có một bạn liên hệ với tôi qua fb hỏi là mình cũng làm một cái tương tự cũng gần năm năm rồi, nhưng mà ra kết quả rất chậm dù rằng chỉ có 30k entries (bổ xung: riêng hán việt đã khoảng hơn 12k entries rồi, 30k entries hầu như chỉ chứa những từ phổ biến nhất, hoàn toàn không đủ).

hỏi ra mới biết là cách bạn ấy dịch rất trực quan: chạy một vòng lặp cho tất cả cặp từ trung/việt có sẵn trong từ điển, với mỗi cặp thì lại dùng hàm replace thay thế tất cả cụm trung ở trên bằng cụm việt... thực ra thì nếu chỉ có 30k từ, cho input dài 4k chữ thì nó cũng không nhiều, dù là cái server ghẻ lở thì cũng có khả năng ra kết quả sau một vài giây...

vấn đề ở đây là bạn này có dùng một cái khác gọi là "luật nhân", nói nôm na là một kiểu ngữ pháp tiếng trung, ghép lại vài cụm từ được đánh dấu danh động tĩnh các kiểu thành một cụm từ mới với cấu trúc thuần việt hơn... ờ giải thích hơi dài dòng, tóm lại thì các bạn hiểu đơn giản là phép "nhân" này biến 30k entries thành 300k thậm chí nhiều hơn, và kết quả là....

(p/s: ngoài mấy cái webapp thì trước đó có một cái desktop app gọi là QuickTranslator, và tôi cũng được nghe kể những trải nghiệm "rùng rợn" của một số bạn lạm dụng công cụ này, ví dụ 1 triệu entries từ điển x 100+ "luật nhân", nghe nói dịch một chương truyện 5k chữ thôi cũng có thể tính bằng tiếng, ăn hơn chục GB ram)

Tôi nghe loáng thoáng cũng có vài người có giải pháp tốt hơn tí, kiểu như chạy một vòng lặp duyệt cái dữ liệu input, rồi trích ra các substring (độ dài < 10 gì đấy), nếu tìm được cụm từ việt phù hợp thì lưu kết quả vào, rồi nhảy qua độ dài cụm từ trung vừa thấy... về cơ bản thì khá ổn, ngoại trừ hai chuyện là mỗi index của string đầu vào)đều phải trích ra khoảng 10 substring gì đấy rồi tìm nghĩa việt, mà tìm nghĩa việt thì tuy dùng hash_map đúng là O(1) thật, nhưng thực tế cũng không đơn giản như vậy (hashing khá tốn kém). Vấn đề thứ hai là chạy từ trái sang phải như thế không hẳn là cách tốt nhất, vì có từ cần được ưu tiên hơn từ khác; ví dụ thành ngữ thường có 4 ký tự trở lên, hoặc tên người; chỉ dịch từ trái sang phải không ra được kết quả dịch tốt nhất có thể...

Các bạn có giải pháp gì tối ưu hơn có thể vào đây chém gió, cần thiết tôi có thể đưa thêm input (một file dữ liệu từ và một file text vài MB), tôi thấy đây là bài toán khá thú vị mặc dù cấu trúc dữ liệu tối ưu (mà tôi biết) thực ra cũng khá đơn giản :"> Lần cuối cùng tôi test thì thuật toán của tôi với dữ liệu là 200k từ + 10MB text file thì mất tầm 10s để dịch xong toàn bộ (bằng nodejs), kể ra cũng khá ổn, nhưng vẫn hóng xem có bạn nào nghĩ ra giải pháp hay hơn không :">

qkhanhpro said:

Cho mình hỏi một chút
Tiếng Trung có gặp những cú pháp như tiếng Việt như thế này không và nếu chỉ là map từ thì theo mình hiểu sẽ không giải quyết được
"Học sinh học sinh học"
"Con ngựa đá con ngựa đá"
Phải không nhỉ

flowerfx2 said:

code mobile thì chịu khó xài cái này nhiều vô, tôi dùng cây nhị phân để lưu trữ dự liệu nè, rồi viết ra thành 1 lib, mấy app mobile hay game thì cứ gắn lib vô bao xài, gọi thông tin ra nhanh hơn dùng sql hay json lưu trữ
ra ngoài đi làm thì tôi dùng khá nhiều lý thuyết của toán rời rạc để áp vào code và mind set, chứ gọi API ra để chạy thì perf kém lắm, chưa kể tính linh hoạt của ứng dụng hay thư viện để nâng cấp và dùng cho các dự án sau nữa

bribnt said:

Ma trận kích thước bao nhiêu, cần nhân bao nhiêu lần?

Dùng trie hay suffix tree chỉ mất O(m) thời gian thôi.
Phép search tree thì đúng là có điểm yếu về không tận dụng tốt CPU cache, cứ cho là miss cache L3 100% thì một lần tìm kiếm một byte trong tree mất khoảng tối đa 200 cycle.
Phép nhân ma trận độ phức tạp khoảng O(m*n*p), chấp luôn cache hit 100% latency 0, sử dụng AVX256 tính được 8 phép tính cùng lúc thì chỉ cần mnp > 1600 là chậm hơn tree rồi. Mà với mấy cái model ML ngày nay thì con số đó chỉ là muỗi.

bribnt said:

Về cache, memory thì trong môn kiến trúc máy tính có dạy khá kỹ. Quản lý bộ nhớ thuộc về môn hệ điều hành.
Có quyển Computer Architecture: A quantative approach nói về kiến trúc máy tính đi theo hướng định lượng, tức là như khi bàn về cache thì sẽ phân tích xem nên design cache size chừng nào, 4-way hay 8-way, cache line bao nhiêu, ... thì sẽ có hiệu năng tốt hơn hay tiết kiệm năng lượng hơn.

Lập trình tối ưu sử dụng những kiến thức trên kia thì cứ đọc hết tài liệu của Agner Fog: https://agner.org/optimize/

qkhanhpro said:

Quan trọng, phù thuộc vào định hướng phát triển của bạn

Lời khuyên cá nhân của tôi là đọc/học cảm thấy vào thì tốt. Thấy khó học/khó hiểu hay chán ghét nó thì cũng không nhất thiết phải quá lo lắng.

Tôi tự đánh giá mình ở trình độ so với 1 quyển toán rời rạc đại cương thì hiểu được 2 phần trên 10. Trong 2 phần đó, hiểu đến mức đem áp dụng vào thực tiễn 2 trên 10 nữa. Như thế là tạm đủ cho bản thân tôi



View attachment 244252

Giáo trình trường dạy đây, sách của Pearson

thiensau ver1 said:

Bác cho em hỏi, cuốn này mua sách giấy ở đâu bác, em kiếm pdf down cũng k thấy luôn

nipevt said:

sách giấy thì chắc lên fado đặt mua ở Amazon ship về VN thôi.

còn pdf thì đây.

http://libgen.rs/book/index.php?md5=90137E567EB283907BF0C0C086F645DA

thiensau ver1 said:

Bác cho em hỏi, cuốn này mua sách giấy ở đâu bác, em kiếm pdf down cũng k thấy luôn

talavuavoz113 said:

em xin tips học tốt toán rời rạc với ạ

buonnguqua said:

Ra trước cửa trường đại học Bách Khoa hay Công Nghệ mua quyển Toán rời rạc
Không đi du học nước ngoài mà đò i học sách toán bằng Tiếng Anh thì có lẽ Voz này ra đường ai cũng IELTS 7.0 trở lên mất

honeyfox said:

Chỉ cần kỹ năng đọc tiếng Anh là đủ rồi. IELTS 7.0 all band thì ko dễ chứ IELTS reading 8.0 thì dễ ẹc

buonnguqua said:

Ra trước cửa trường đại học Bách Khoa hay Công Nghệ mua quyển Toán rời rạc
Không đi du học nước ngoài mà đòi học sách toán bằng Tiếng Anh thì có lẽ Voz này ra đường ai cũng IELTS 7.0 trở lên mất

buonnguqua said:

Anh tưởng tượng thôi chứ tôi thấy đề IELTS reading khó vcl ra
Nó bắt mình đọc tài liệu chuyên ngành tự nhiên, xã hội mà đến đọc bằng tiếng Việt mình cũng chỉ tầm hiểu sơ sơ trong vài phút
Nếu chưa từng đến lò luyện lần đầu tiên làm test anh kiếm được 5.0 reading là giỏi
Tôi đọc truyện Sherlock Holmes bình thường nhưng nhìn cái đề reading đọc được 50%

buonnguqua said:

Anh tưởng tượng thôi chứ tôi thấy đề IELTS reading khó vcl ra
Nó bắt mình đọc tài liệu chuyên ngành tự nhiên, xã hội mà đến đọc bằng tiếng Việt mình cũng chỉ tầm hiểu sơ sơ trong vài phút
Nếu chưa từng đến lò luyện lần đầu tiên làm test anh kiếm được 5.0 reading là giỏi
Tôi đọc truyện Sherlock Holmes bình thường nhưng nhìn cái đề reading đọc được 50%

RaitoLight4492 said:

Các bạn có biết trang nào mà luyện giải thuật theo chủ đề thuật toán không? Nó có chia ra chủ đề này nọ để mình biết thuật toán nào xài ấy

nipevt said:

sách giấy thì chắc lên fado đặt mua ở Amazon ship về VN thôi.

còn pdf thì đây.

http://libgen.rs/book/index.php?md5=90137E567EB283907BF0C0C086F645DA

Ngày Được Tự Do said:

Cho em hỏi cái môn này học thì có tác dụng gì không, hay dành thời gian học cấu trúc dữ liệu và giải thuật

Ngày Được Tự Do said:

Cho em hỏi cái môn này học thì có tác dụng gì không, hay dành thời gian học cấu trúc dữ liệu và giải thuật

Khang.Hy.Gia said:

dĩ nhiên Ctdl quan trọng hơn

Ngày Được Tự Do said:

Nhưng mà học cái toán rời rạc này nó có bổ trợ cho cấu trúc dữ liệu và giải thuật không hay ko liên quan gì nhỉ

via theNEXTvoz for iPhone

Ngày Được Tự Do said:

Nhưng mà học cái toán rời rạc này nó có bổ trợ cho cấu trúc dữ liệu và giải thuật không hay ko liên quan gì nhỉ

via theNEXTvoz for iPhone

Khang.Hy.Gia said:

không lq gì hết

a3.phantom.vn said:

@Ngày Được Tự Do
Em muốn "sâu" thì học, "nông" thì thôi, nói nhanh là thế. Trên đời này cái gì nó cũng có nhiều mức độ, tùy em muốn bản thân tới đâu thì học tới đó

Chứ đọc mấy cái cmt liền của Khang.Hy.Gia thấy chán đời quá

itculi9x said:

Base toán e mất hết rồi, bây giờ học lại như thế nào ạ? Đang học ĐSTT đọc lý thuyết hiểu nhưng đến khi cho đề bài làm thì sml, chán vãi

Khang.Hy.Gia said:

bớt văn vẻ cho nó vuông. sự thật là thế. a thích học thì cứ học. tôi k học vẫn đi làm có tiền thôi

a3.phantom.vn said:

bạn đọc lại cmt của mình, mình có nói là ai cũng phải học đâu? Mình nói là muốn tới đâu thì học tới đó.

Bạn nói chuyện giống mấy người kiếm được tiền, xong rồi rêu rao tui đâu cần học/nghiên cứu cái lý thuyết này lý thuyết kia đâu. Ừ, ai mà cũng vậy thì lấy đâu ra tiến bộ khoa học.

Tui không khinh những người không học mấy môn này, xã hội mỗi người một nghề. Nhưng đang bàn luận trong lĩnh vực này thì muốn sâu, chắc chắn phải nắm toán rời rạc cơ bản, chứ tui có nói là phải học đến toán rời rạc nâng cao đâu? Chắc là biết bao thế hệ giáo sư của ngành Computer Science người ta ngu lắm nên mới xếp Toán Rời Rạc là môn cơ sở ngành nhỉ

Cryolite.2 said:

Hồi đi học OOP thì thầy mình mới bảo chả nhớ gì kiến thức của mấy môn toán ngày xưa học nữa, mà chắc mình nghĩ lúc làm thì người ta chả còn để ý nó là toán nữa
(Em xin lỗi thầy T*** A** nhiều lắm, bài thi cuối kỳ tụi em chả ra gì )
View attachment 213176
View attachment 213164

TTN_vOz said:

Hiện tại mình đang làm một số thứ liên quan đến tối ưu sản xuất cho việc thi công ván gỗ.
Liên quan nhiều đến Toán, giải thuật, toán rr.
Cụ thể là tối ưu đường đi trên đồ thị, tối ưu sắp xếp...
Nếu ko tiếp cận qua kiến thức ĐH mà tự tìm hiểu cũng oải đấy.

xuanphongdocco said:

Hi vọng bấy nhiêu đủ nhiều cho bạn https://cuuduongthancong.com/s/cau-truc-roi-rac?src=home

hopevnn said:

Trước học môn này thầy bảo là cứ làm hết bài tập trong này cộng với một đống bài tập thầy ra thêm nữa, sau mỗi chương phải làm hết nộp cho thầy rồi thi giữa kỳ, cuối kỳ chỉ lấy trong đó thôi, phải được hơn nghìn bài luôn ấy, ám ảnh kinh hoàng.

View attachment 199065






Tác dụng lớn nhất của môn này là để đi xờ lờ trong lúc phỏng vấn