ĐỀ CƯƠNG CHI  TIẾT KHÓA HỌC

Học cách đánh giá và phân tích độ phức tạp của thuật toán, áp dụng để chọn ra thuật toán phù hợp cho một số bài tập cơ bản của lập trình thi đấu.

Ứng dụng vào một số bài toán trong thi đấu như:

  • Facebook Hackercup 2015 - Qualification Round
  • Round 1C 2011 - Code Jam 2011
  • Giới thiệu thuật toán sắp xếp cơ bản và thuật toán sắp xếp nhanh.

    Ứng dụng vào một số bài toán trong thi đấu như:

  • Sắp xếp các đèn đường trên đường phố với số lượng ít nhất
  • Chọn điểm đến theo sở thích trong chuyến tham quan
  • Làm quen với thuật toán tìm kiếm tuyến tính và nhị phân, với thuật toán tìm kiếm nhị phân là một công cụ hữu ích để giải quyết các bài toán nâng cao hơn.

    Ứng dụng vào một số bài toán trong thi đấu như:

  • Xác định các loại virus bị cấm có xuất hiện trên một đoạn mã ADN hay không.
  • Tìm vị trí đặt một khu dân cư để tối ưu hoá quy hoạch.
  • Tính điểm của thí sinh trong một chương trình truyền hình thực tế.
  • Sau ba buổi học lý thuyết sẽ là một buổi làm bài tập để ôn lại kiến thức của cả ba buổi trên.

    Ứng dụng vào một số bài toán trong thi đấu như:

  • Giúp công ty sản xuất bảng phi tiêu tìm số vòng tròn tối đa có thể vẽ được với một lượng sơn nhất định.
  • Giúp các robot đi mua sắm nhanh nhất.
  • Làm quen với thuật toán đếm phân phối được ứng dụng trong thuật toán sắp xếp phân phối (với độ phức tạp tuyến tính cho các tập giá trị nhỏ), và kĩ thuật rời rạc hoá, nén số.

    Ứng dụng vào một số bài toán trong thi đấu như:

  • Tìm đoạn đường được đi qua nhiều nhất sau nhiều lần vận chuyển hàng.
  • Xác định con robot sơn đường có thể được điều đi mà không làm ảnh hưởng đến kế hoạch hoạt động.
  • Làm quen với các phép toán cơ bản trên bit như AND, OR, XOR, NOT, các phép toán kết hợp và kĩ thuật xử lí bit. Được sử dụng nhiều trong lập trình thi đấu và ứng dụng trong phương pháp sinh, quy hoạch động trạng thái…

    Ứng dụng vào các bài toán như:

  • Các bài toán xử lí bit cơ bản đến nâng cao.
  • Một kỹ thuật xử lí bài toán tận dụng kết quả của các bài toán lân cận, với 5 chủ đề hai con trỏ phổ biến, trong đó có cách thực hiện hàm gộp hai mảng con trong thuật toán Merge Sort.

    Ứng dụng vào các bài toán như:

  • Cách chia đội các thí sinh tham gia một cuộc thi lập trình.
  • Tính số lần ít nhất để di chuyển các chú chuột và hổ trong một rạp xiếc sao cho mỗi loài sẽ đứng chung với nhau.
  • Tiếp tục là một buổi bài tập ứng dụng vào các bài toán như:

  • Sắp xếp lịch các hoạt động sắp tới trong năm.
  • Tìm ngôi nhà sẽ nhận được phần quà lớn nhất trong năm nay, bằng cách sử dụng đếm phân phối để lưu lại số lần ông thăm những ngôi nhà.
  • Tham lam là một kĩ thuật thường được sử dụng trong thi đấu.

    Ứng dụng vào một số bài toán trong thi đấu như:

  • Tính số lần chơi ít nhất để đạt được 2-star rating trong một trò chơi điện tử.
  • Tính số lượng bảo vệ một trung tâm nghiên cứu cần thuê để tất cả mọi nơi trong trung tâm đều được canh gác.
  • Làm quen với hai cấu trúc dữ liệu tuyến tính, hoạt động theo cơ chế LIFO (last-in-first-out) và FIFO (first-in-first-out).

    Ứng dụng vào một số bài toán trong thi đấu như:

  • Biết cách xác định thư mục hiện tại khi sử dụng hai lệnh pwd và cd trên hệ điều hành.
  • Dựa vào thời điểm các bệnh nhân đến bệnh viện để xác định thứ tự lịch hẹn của họ với bác sĩ.
  • Tìm hiểu các khái niệm cơ bản trong đồ thị. Làm quen với hai thuật toán tìm kiếm trên đồ thị theo chiều rộng và chiều sâu.

    Ứng dụng vào một số bài toán trong thi đấu như:

  • Kiểm tra các quan hệ cha con trong một tập dữ liệu có hợp lệ không.
  • Xác định cách đi để đưa quân tượng tới vị trí mong muốn trên một bàn cờ vua.
  • Xác định tất cả các kênh xung yếu của một mạng máy tính.
  • Kỳ thi giữa kỳ khóa học.

    Một cấu trúc cây nhị phân hoàn chỉnh, áp dụng rất nhiều trong các bài toán tìm đường đi ngắn nhất, tìm phần tử max, min. Heap còn được biết đến thông qua một thuật toán sắp xếp khá kinh điển: Heap Sort.

    Ứng dụng vào một số bài toán trong thi đấu như:

  • Giúp công ty đường sắt điều phối các chuyến tàu của họ một cách tối ưu nhất.
  • Tối ưu hóa số trạm xăng cần dừng lại của một hành trình.
  • Xác định trung vị của một mảng số nguyên có số phần tử cập nhật liên tục.
  • Xác định số kỳ thi cần tham gia để tối thiểu tổng lệ phí thi.
  • Một thuật toán tìm đường kinh điển , giúp ta tìm đường đi ngắn nhất từ một đỉnh đến tất cả các đỉnh còn lại trong đồ thị có trọng số (trọng số không âm). Thuật toán Dijkstra được ứng dụng nhiều trong thực tế như chuyển gói tin trong mạng, tìm đường trên bản đồ.

    Ứng dụng vào một số bài toán trong thi đấu như:

  • Xác định đường đi có chi phí nhỏ nhất giữa hai đỉnh của đồ thị.
  • Xác định đường đi giữa hai đỉnh có chi phí lớn nhì trong các trọng số giữa các cạnh của đồ thị là nhỏ nhất.
  • Xác định khoảng cách của đỉnh nằm xa nhất đối với một đỉnh cho trước, và số đỉnh có khoảng cách đó.
  • Xác định số lượng đường sắt nhiều nhất có thể xóa được sao cho đường đi ngắn nhất từ đỉnh xuất phát tới các đỉnh còn lại là không đổi.
  • Xác định số lượng hầm trú của thành phố cách thủ đô một khoảng cách cho trước.
  • Bellman-Ford là thuật toán tìm đường đi có chi phí nhỏ nhất từ một đỉnh đến các đỉnh khác trong đồ thị, có thể hoạt động được trên đồ thị có trọng số âm. Floyd-Warshall là thuật toán tìm đường đi có chi phí nhỏ nhất giữa tất cả các cặp đỉnh trong đồ thị, có thể hoạt động được trên đồ thị có trọng số.

    Ứng dụng vào một số bài toán trong thi đấu như:

  • Xác định tổng điện trở giữa các mối của một mạch điện.
  • Xác định đường đi ngắn nhất giữa các đỉnh trong đồ thị ứng với mỗi truy vấn.
  • Xây dựng đồ thị mô phỏng mạng lưới dịch vụ cần cung cấp cho khách hàng với các điều kiện cho trước.
  • Xác định một con đường đi cần xây dựng thêm giữa các nhà ga trong thành phố để đạt được tổng chi phí các đường đi là nhỏ nhất với công thức tính tổng chi phí được cho bởi đề bài.
  • Xác định sự tồn tại của vấn đề kế thừa con thoi trong một đồ thị.
  • Tiếp tục là một buổi bài tập ứng dụng vào các bài toán như:

  • Xác định số lượng chiến binh lớn nhất có thể giữa 2 phe đấu với nhau.
  • Sử dụng tư tưởng tham lam cùng cấu trúc dữ liệu thích hợp để giúp người nông dân tối thiểu hóa chi phí cắt gỗ.
  • Ứng dụng DSU để gom người lính thành các đội nhóm bảo vệ ngôi làng.
  • Xác định số lần đổi lần trạng thái di chuyển giữa lên dốc và xuống dốc trong một quãng đường đi.
  • Thực hiện các truy vấn xác định con đường đó có thực sự cần thiết khi đi con đường ngắn nhất giữa hai điểm cho trước.
  • Disjoint Sets là cấu trúc dữ liệu rất hữu dụng, được dùng làm nền tảng cho một số thuật toán như Kruskal, Prim, 2 thuật toán tìm cây khung nhỏ nhất trên đồ thị.

    Ứng dụng vào một số bài toán trong thi đấu như:

  • Tạo chuỗi có thứ tự từ điển nhỏ nhất từ chuỗi gốc, với quy tắc các ký tự tương đương được cho trước.
  • Xác định liệu sự tồn tại của một đường truyền có cần thiết trong một mạng lưới truyền mạng.
  • Hiện thực các truy vấn đặc biệt trên mảng.
  • Xác định con đường cần đóng cửa và con đường cần xây mới tương ứng để đảm bảo luôn có đường đi giữa các thành phố bất kỳ.
  • Xác định một cách giải của Nurikabe puzzle có hợp lệ hay không.
  • Prim là thuật toán giải quyết bài toán xác định cây khung có trọng số nhỏ nhất dựa trên tư tưởng tham lam.

    Ứng dụng vào một số bài toán trong thi đấu như:

  • Xác định số tiền lớn nhất chính phủ có thể tiết kiệm được trong việc thắp sáng các con đường trong thành phố.
  • Xác định hiệu suất sử dụng cần thiết của bình sạc xe để đi giữa các thành phố bất kỳ.
  • Xây dựng đất nước GraphLand bởi các đường bộ nối các thành phố, các đường sắt nối các tỉnh, để đạt được chi phí xây dựng nhỏ nhất.
  • Tìm chi phí tối thiểu để đi hết một số thành phố từ một thành phố cho trước.
  • Xác định giá trị cây khung nhỏ nhất của một đồ thị cập nhật thêm cạnh liên tục ứng với mỗi truy vấn.
  • Giống như Prim, thuật toán Kruskal cũng tìm cây khung nhỏ nhất dựa trên tư tưởng tham lam nhưng không phụ thuộc vào điểm bắt đầu.

    Ứng dụng vào một số bài toán trong thi đấu như:

  • Tính đường đi ngắn nhất giữa các cặp con đường trong thành phố.
  • Xác định số con đường tối thiểu cần xây dựng và tối đa hóa độ bền của máy sử dụng để xây dựng từng con đường này sao cho có đường đi giữa 2 thị trấn bất kỳ.
  • Tính toán chi phí tối thiểu để xây dựng hệ thống phân cấp trong một công ty.
  • Xác định chi phí tối thiểu trong việc đặt các đồng vàng và đồng bạc trên các con đường trong vương quốc để làm hài lòng bọn cướp.
  • Hiện thực các thao tác trên một rừng.
  • Tính tổng số thuốc cần chuẩn bị cho khách uống phải sữa hư trong buổi tiệc.
  • Xác định trạng thái của các bit trong thanh ghi ứng với các thao tác trên bit như: clear, set, or, and.
  • Ứng dụng các thuật toán liên quan đến đồ thị để kiểm tra có đường đi giữa 2 ô trong bảng cho trước.
  • Tính tổng các chữ số của các số trong khoảng cho trước.
  • Tìm hành trình để tải trọng của xe lưu thông trên đường đó là lớn nhất.
  • Kỳ thi cuối kỳ khóa học.