ĐỀ 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.
    • Bài kiểm tra giữa khoá học để kiểm tra lại kiến thức đã học từ Lecture 01 đến Lecture 07

    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ĩ.

    • 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.

    • 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.
    • Tiếp tục làm 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.
    • 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.

    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ị.
    • Sắp xếp topo là một cách sắp xếp các đỉnh trong đồ thị có hướng sao cho nếu tồn tại đường đi từ đỉnh u đến đỉnh v trong đồ thị thì u phải đứng trước v trong cách sắp xếp này. Ứng dụng vào các bài toán như:
    • Xác định thứ tự từ điển các chữ cái trong một cuốn sách theo quy ước của riêng nó.
    • Tìm một thứ tự để có thể hoàn thành một số các khóa học cho trước với các điều kiện khóa học tiên quyết của mỗi khóa học.
    • Xác định số địa điểm đến cần thay đổi để có đường đi từ một địa điểm bất kỳ tới thủ đô sau số lần dịch chuyển cho trước.
    • Xác định một đường bay từ điểm xuất phát đến điểm kết thúc cho trước với số điểm dừng giữa chúng là lớn nhất.
    • Xác định thứ tự kéo công tắc và đòn bẩy để mở cánh cổng và hoàn thành cuộc phiêu lưu.
    Bài kiểm tra cuối kỳ toàn khoá học :
    • 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à.