ĐỀ 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ư:
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ư:
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ư:
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ư:
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ư:
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ư:
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ư:

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ư:
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ư:
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ư:
- 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ư:
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 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.
- 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à.