Nhóm những sinh viên yêu thích thuật toán

[10520189]

Hi. Vậy là đã có 9 bạn đăng kí. Với số lượng này chúng ta có thể offline rồi. Nhưng phải vài tuần nữa chúng ta mới off được. Tạm thời bây giờ các bạn học kĩ và sử dụng thành thạo các lý thuyết cơ bản về C, C++, và nếu được thì cả STL nữa càng tốt. Vì đó là những cái căn bản phục vụ cho việc học thuật toán. Và các bạn học C, C++ làm ngôn ngữ chung cho tiện khi chúng ta thảo luận. Thân.

STL là cái chi mô a ?

[08520001]

Ah, C++ là ngôn ngữ mở rộng thêm của C. Nghĩa là C++ có các tính năng của C và bổ sung thêm các thư viện, các lớp để phục vụ cho việc lập trình bớt cực nhọc. Với những bạn đã từng học pascal ở phổ thông thì việc học C sẽ rất dễ dàng. Sau khi học C, các bạn chỉ cần học ở C++ thêm 1 số hàm, phương thức thức về nhập xuất thôi (vd như cin, cout, freopen do ngu nam...). Còn cái mà các bạn cần học ở thêm ở C++ là STL.

Sau khi học xong C, các bạn còn thắc mắc về STL thì mình sẽ hướng dẫn. Thân

[09520019]

nếu bỏ qua sở thik thì nghiên cuứ sâu về thuật toán có lợi như thế nào ạ??

À thuật toán có rất nhiều loại, không phải chỉ 1 loại nên nếu bạn không thích cái này (và thậm chí ghét) thì cũng sẽ thích cái kia.
Như mình rất thích thuật toán, nhưng để học là 1 quá trình đau khổ. 1 vài bạn khác có thể không thích nó, nhưng nó cũng không phải là quá khó (và cũng không quá thời thượng).

Nghiên cứu sâu về thuật toán rất có lợi, thứ nhất bạn giảm được thời gian chạy bài toán. Lấy ví dụ đơn giản là việc check 2 cái hình vuông có giao nhau hay không. Nếu bạn dùng thuật toán bình thường xét từng pixel một thì bạn phải tốn số lượng phép tính khoảng n * n * m * m với n m là độ dài cạnh hình vuông thứ nhất và thứ 2 của 2. Trong khi đó nếu có thuật toán tốt vào , bạn giảm được xuống chỉ cần tính 1 vài phép tính duy nhất (khá nhỏ so với n^2 * m^2). Bài này trong đồ án game bắn xe tank của mình, nếu như bạn check như thuật toán 1 thì nó chỉ chạy nổi trên các dòng CPU cao cấp, còn nếu dùng cách thứ 2 thì P4 cùi bắp vẫn chạy được.

Có 1 lịch sử nho nhỏ về việc tính gần đúng số căn 2. Game Quake là game giả 3D tiên phong trong quá trình tính toán được độ bóng của 1 vật thể mà máy chạy không lag. Lý do là họ tính được gần đúng số căn 2 một cách cực kỳ nhanh (thay vì phải dùng 1 lệnh xử lý số double, họ đã chuyển thành xử lý trên số nguyên trong 1 phép tính duy nhất) và nhờ đó game chạy rất mượt. Bạn có thể đọc nó ở đây http://en.wikipedia.org/wiki/Fast_inverse_square_root


PS: các bạn đừng nên nghe anh Trường An chém nhé, đội tuyển Olympic luôn chào đón các bạn, trong quá trình các bạn học thì chỉ có các bạn tự bỏ mà thôi. Đến khi thi chọn đội tuyển rồi thì các bạn vẫn phải đi học tiếp nhưng nhiều người lầm tưởng là chọn rồi thì ko đi nữa nên tự nghỉ. Không ai đuổi các bạn đâu.

Thân

[08520001]

STL là viết tắt của standard template library, được gọi là thư viện lớp chuẩn của C++. Nó bao gồm rất nhiều lớp và phương thức phục vụ cho việc lập trình. Vd đơn giản như trong pascal khi cần sử dụng 1 cấu trúc dữ liệu như cây nhị phân tìm kiếm chẳng hạn, thì các bạn phải tự code tay do ngu. Còn trong C++ khi sử dụng STL, các bạn không cần code tay, mà đã có những lớp phục vụ cho việc sử dụng cấu trúc dữ liệu đó, các bạn chỉ cần sử dụng thôi.

Và điểm khác biệt thứ 2 là khi các bạn code tay thì có thể xảy ra lỗi hoặc sai sót, còn khi dùng STL thì các lớp, hàm đó đã bảo đảm chính xác, các bạn cứ yên tâm sử dụng.

[10520189]

rồi.I understand.ngoài STL còn cần nữa thêm j k a

[08520001]

Anh nghĩ tạm thời thì các bạn cứ học thật nhuần nhuyễn những cái đó trước đã. Khi nào xong mình tính tiếp thoi trang tre em. Ah, anh cũng cần thông tin thêm ở các bạn về những thuật toán đã biết.

Các bạn vui lòng cho anh biết sớm nhé.

[10520189]

a thử nói tên các thuật toán thì e mới biết e biết cái nào được

[11520673]

Anh nghĩ tạm thời thì các bạn cứ học thật nhuần nhuyễn những cái đó trước đã. Khi nào xong mình tính tiếp. Ah, anh cũng cần thông tin thêm ở các bạn về những thuật toán đã biết. Các bạn vui lòng cho anh biết sớm nhé.

e biết những cái rất mơ hồ ạ! Cụ thể thì cái gì cũng biết chút chút, biết là có nó để giải, nhưng mỗi lần để giải phải mở nó ra Giống như e đọc mấy bài balô, r phân tích các tổ hợp = tổng, .... nói chung e nhớ qua bài toán đã đọc r khi làm lật lại coi chứ ko biết có các loại thuật toán gì :-j có nghe qa quy hoạch động, hearestic gì đó, đệ quy qay lui, tham lam ... nghe chứ ko hiểu tụi nó có gì khác biệt :-s
Vậy ko biết khi tham gia có bị bất lợi ko ạ?

[09520019]

C là ngữ k OOP.còn C++ là lai thuần + OOP pác ạ

C Standard và C++ khác nhau hoàn toàn nhé chứ ko ai lai ai đâu.
C++ khác C thuần nhiều điểm chứ ko chỉ có OOP đâu, nhưng về cú pháp thì C và C++ tương đồng rất nhiều
Lời khuyên riêng của mình cho luyện tập C/C++: Các bạn năm 1 sau khi hết HK 1 thì nên tập luôn cin và cout và đừng luyện tập cin/cout trước khi kết thúc HK 1. Lý do là cin và cout có nhiều mặt mạnh nhưng printf và scanf cũng có nhiều mặt mạnh, chúng hỗ trợ lẫn nhau chứ ko trừ khử nhau đâu. HK1 là dành cho C và HK2 là dành cho C++ và pre-OOP nhé.
Riêng về phần struct thì mình khuyên là dùng style của C++ vì mình thấy nó dễ dùng hơn C,..... thứ 2 là chúng ta có thể cheat đc vì compiler mặc định biên dịch C++ =)) Chú ý là mấy bạn cẩn thận ko nên chủ quan vì AMM mà biên dịch C là chết cái struct đấy nhá.

STL: hồi năm 1, mình đi học ké OOP nên không cần học OOP nữa, còn về STL thì cũng ko cần sách luôn mà các bạn có thể tham khảo tài liệu AV sau đây. http://cplusplus.com/reference/ (toàn bộ C Library, IOstream Library, Strings library, STL Containers,STL Algorithms, Miscellaneous)
Bonus nho nhỏ: sort() là quicksort nhé, lower_bound() và upper_bound() là tìm kiếm nhị phân nhá. Khi làm bài cho HK2 thì ko đc dùng thư viện mà phải tự code, nhưng trong quá trình test thì các bạn cần nó như 1 hàm chuẩn để đánh giá đúng sai

Cái đó là tài liệu tham khảo trong lúc làm bài, còn tài liệu tham khảo để hiểu STL thì có thể đọc tài liệu sau đây: https://docs.google.com/open?id=0ByV...IwOTUzMDI1N2Zj
Cái này có thể download về đc nhá, chú ý tìm nút download.

không có tài liệu tiếng việt, các bạn thông cảm (Fact: tài liệu tiếng việt dài hơn và đi lan man hơn). Các từ tiếng anh trong này đều là từ thông dụng, các bạn nên đọc - hiểu và khi thấy từ mới thì tra từ điển. Hạn chế dịch vì nó chỉ nâng kỹ năng dịch chứ ko nâng kỹ năng đọc

e biết những cái rất mơ hồ ạ! Cụ thể thì cái gì cũng biết chút chút, biết là có nó để giải, nhưng mỗi lần để giải phải mở nó ra Giống như e đọc mấy bài balô, r phân tích các tổ hợp = tổng, .... nói chung e nhớ qua bài toán đã đọc r khi làm lật lại coi chứ ko biết có các loại thuật toán gì :-j có nghe qa quy hoạch động, hearestic gì đó, đệ quy qay lui, tham lam ... nghe chứ ko hiểu tụi nó có gì khác biệt :-s
Vậy ko biết khi tham gia có bị bất lợi ko ạ?

Tụi a không yêu cầu em trả bài giấy. Em đọc bài và biết cách làm - tốt - không cần nhớ tên thuật toán làm gì (nhưng sẽ bất lợi khi trình bày cho người khác hiểu đấy). Quan trọng là đọc xong phải cài được vì đi thi thì điểm dựa trên test.

[10520189]

C Standard và C++ khác nhau hoàn toàn nhé chứ ko ai lai ai đâu.
C++ khác C thuần nhiều điểm chứ ko chỉ có OOP đâu, nhưng về cú pháp thì C và C++ tương đồng rất nhiều
Lời khuyên riêng của mình cho luyện tập C/C++: Các bạn năm 1 sau khi hết HK 1 thì nên tập luôn cin và cout và đừng luyện tập cin/cout trước khi kết thúc HK 1. Lý do là cin và cout có nhiều mặt mạnh nhưng printf và scanf cũng có nhiều mặt mạnh, chúng hỗ trợ lẫn nhau chứ ko trừ khử nhau đâu. HK1 là dành cho C và HK2 là dành cho C++ và pre-OOP nhé.
Riêng về phần struct thì mình khuyên là dùng style của C++ vì mình thấy nó dễ dùng hơn C,..... thứ 2 là chúng ta có thể cheat đc vì compiler mặc định biên dịch C++ =)) Chú ý là mấy bạn cẩn thận ko nên chủ quan vì AMM mà biên dịch C là chết cái struct đấy nhá.

STL: hồi năm 1, mình đi học ké OOP nên không cần học OOP nữa, còn về STL thì cũng ko cần sách luôn mà các bạn có thể tham khảo tài liệu AV sau đây. http://cplusplus.com/reference/ (toàn bộ C Library, IOstream Library, Strings library, STL Containers,STL Algorithms, Miscellaneous)
Bonus nho nhỏ: sort() là quicksort nhé, lower_bound() và upper_bound() là tìm kiếm nhị phân nhá. Khi làm bài cho HK2 thì ko đc dùng thư viện mà phải tự code, nhưng trong quá trình test thì các bạn cần nó như 1 hàm chuẩn để đánh giá đúng sai

Cái đó là tài liệu tham khảo trong lúc làm bài, còn tài liệu tham khảo để hiểu STL thì có thể đọc tài liệu sau đây: https://docs.google.com/open?id=0ByV...IwOTUzMDI1N2Zj
Cái này có thể download về đc nhá, chú ý tìm nút download.

không có tài liệu tiếng việt, các bạn thông cảm (Fact: tài liệu tiếng việt dài hơn và đi lan man hơn). Các từ tiếng anh trong này đều là từ thông dụng, các bạn nên đọc - hiểu và khi thấy từ mới thì tra từ điển. Hạn chế dịch vì nó chỉ nâng kỹ năng dịch chứ ko nâng kỹ năng đọc


Tụi a không yêu cầu em trả bài giấy. Em đọc bài và biết cách làm - tốt - không cần nhớ tên thuật toán làm gì (nhưng sẽ bất lợi khi trình bày cho người khác hiểu đấy).

pác hiểu sai ý em rồi.e nói C là ngôn ngữ thuần.còn C++ là lai ngôn ngữ thuần với OOP.e k nói C++ và C lai của nhau

[09520019]

pác hiểu sai ý em rồi.e nói C là ngôn ngữ thuần.còn C++ là lai ngôn ngữ thuần với OOP.e k nói C++ và C lai của nhau

C++ là ngôn ngữ thuần chứ ko phải thuần lai với OOP nhá, nếu ý em là PP/POP kết hợp với OOP thì đúng.

[08520001]

Anh ví dụ một số thuật toán như: biết về các cấu trúc dữ liệu nâng cao như binary search tree (cây nhị phân tìm kiếm), Interval tree, BIT (binary indexed tree), Heap, Find_Union, Suffix Array, Hash; một số thuật toán và kỹ thuật như: kỹ thuật đệ quy quay lui thoi trang nu. các kỹ thuật tìm kiếm nhị phân, kỹ thuật amortized, ...;

Các lý thuyết như lý thuyết đồ thị, quy hoạch động, số học, hình học, game, ..

[10520189]

e nghe nói chứ chưa áp được=))a có document k share lun đi.cái nào full đó.search cũng được mà mất công nó ra tào lao nữa

Anh ví dụ một số thuật toán như: biết về các cấu trúc dữ liệu nâng cao như binary search tree (cây nhị phân tìm kiếm), Interval tree, BIT (binary indexed tree), Heap, Find_Union, Suffix Array, Hash; một số thuật toán và kỹ thuật như: kỹ thuật đệ quy quay lui, các kỹ thuật tìm kiếm nhị phân, kỹ thuật amortized, ...; Các lý thuyết như lý thuyết đồ thị, quy hoạch động, số học, hình học, game, ...

[08520001]

Hi. Nếu em đã rành những cái cơ bản anh viết trên kia thì em có thể tìm kiếm trên mạng hoặc tham khảo ở đây http://community.topcoder.com/tc?mod...s&d2=alg_index quan ao thoi trang. Anh chủ yếu chỉ tìm kiếm trên mạng và học được khi tham gia đội tuyển olympic thôi nên hok có document để đưa em được.

[09520019]

e nghe nói chứ chưa áp được=))a có document k share lun đi.cái nào full đó.search cũng được mà mất công nó ra tào lao nữa

Nếu em học cơ bản thì lên mạng search cuốn Lê Minh Hoàng về tu. Nếu em đọc tài liệu tiếng anh được thì e nên bỏ qua cuốn Lê Minh Hoàng mà đọc cuốn Introduction to Algorithm.

Mấy thứ như binary search tree (cây nhị phân tìm kiếm), Interval tree, BIT (binary indexed tree), Heap, Disjoin-set, Suffix Array, Hash thì từ từ vào lớp Olympic rồi học cũng đc không cần căng thẳng thế :-ss
à còn Balanced Binary tree thì đọc cái này khá dễ hiểu => http://vi.wikipedia.org/wiki/C%C3%A2y_AVL - Do Hoàng Cầm viết


@Mr An: "kỹ thuật amortized" - cái này em chưa biết nha....anh giấu hàng nha :-w