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

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

    • Tìm hiểu các khái niệm về thành phần liên thông mạnh, cầu, khớp, thuật toán Tarjan để liệt kê các thành phần liên thông mạnh của đồ thị có hướng.

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

  • Xác định ‘vòng tròn’ những người thực hiện cuộc gọi trực tiếp hoặc gián tiếp với nhau.
  • Xác định số domino tối thiểu cần tác động để làm đổ tất cả các domino cho sẵn.
  • Xác định tập hợp các đỉnh sao cho tất cả các đỉnh còn lại đều có đường đi đến nó trong đồ thị.
  • Tìm số police checkpoint cần đặt để bảo vệ thành phố và giảm thiểu chi phí.
  • Giúp chính quyền thành phố xác định xem có bao nhiêu cách khác nhau để thực hiện kế hoạch cải tổ thỏa mãn các yêu cầu đặt ra.

    • Quay lui, đệ quy quay lui là một kỹ thuật, thuật toán được thiết kế dựa trên ý tưởng đệ quy. Xuất phát từ một lời giải rỗng, cố gắng mở rộng lời giải ra theo từng bước.

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

  • Xác định các hãng xe có giá nằm trong một khoảng cho trước.
  • Xác định số nguyên lớn nhất không vượt quá giới hạn cho trước với điều kiện không có chữ số nào lặp nhiều hơn hai lần.
  • Xác định số cách sắp xếp domino vào hộp thỏa mãn ràng buộc cho trước.
  • Điền các phép tính cộng, trừ, nhân, chia vào các phân số cho trước để tạo thành phép tính đúng.
  • Tìm cách tác động vào các bóng đèn trên bảng quảng cáo để đạt được số bóng đèn sáng là nhiều nhất.
  • Xác định số cách hoàn thành một trò chơi liên quan đến đồ thị.
  • Xác định số đỉnh lớn nhất có thể đi qua từ đồ thị được xây dựng trong đề bài.
  • Xác định thứ tự của một chuỗi trong danh sách từ được xây dựng theo quy ước của đề bài.
  • Kiểm tra sự tồn tại của đường đi chứa một số số cục vàng trên đường.
  • Ứng dụng sự liên thông của đồ thị để xác định số học sinh ít nhất cần thầy giáo thông báo trực tiếp để thông tin này được truyền đi cho cả lớp.

    • Phương pháp sinh là phương pháp giải quyết bài toán liệt kê tập các tổ hợp có thứ tự.

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

  • Tính số cách chọn các danh sách bài toán thỏa mãn điều kiện cho trước.
  • Xác định sự tồn tại cách quay kim cùng chiều hay ngược chiều đồng hồ sau một số góc quay để đạt được vị trí trỏ 0 ban đầu.
  • Xác định hoán vị kế tiếp của một chuỗi cho trước.
  • Sinh mật khẩu cho một tên đăng nhập với cách mã hóa cho trước.
  • Xác định độ dài chuỗi ngắn nhất tạo được với một số chuỗi.

    • Nhánh cận là một kỹ thuật dùng để tối ưu hóa đệ quy quay lui, xác định điều kiện tối ưu của bài toán mà dừng mở rộng cấu hình không đưa đến lời giải tốt.

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

  • Tính chi phí nhỏ nhất để đi hết tất cả các thành phố từ thành phố xuất phát và quay trở về thành phố xuất phát.
  • Xác định cách chứa đồ không vượt quá thể tích cho trước nhưng tổng giá trị đồ là lớn nhất.
  • Giúp tên trộm xác định thứ tự mua các món đồ để số tiền bỏ ra là nhỏ nhất.
  • Xác định các mật mã hợp lệ có thể có với danh sách các mật mã sai cho trước.

    • Tìm hiểu các khái niệm về chu trình Hamilton, chu trình Euler, thuật toán Fleury và các hướng cải tiến liên quan.

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

  • Tính chi phí nhỏ nhất để đi hết tất cả các thành phố từ thành phố xuất phát và quay trở về thành phố xuất phát.
  • Xác định sự tồn tại của một cách xếp các chuỗi nối nhau mà ký tự cuối của chuỗi này là ký tự đầu của chuỗi kia.
  • Xác định độ đài đường đi Hamilton lớn nhất ứng với từng điểm kết thúc là các đỉnh trong đồ thị.
  • Ứng dụng phương pháp sinh để tính số lượng loại pizza có thể tạo nên.
  • Tính số ngày tháng năm hợp lệ có thể tạo được thì 8 chữ số cho trước.
  • Thêm các dấu cộng vào các số cho trước để tạo thành phép tính đúng.
  • Xác định sự tồn tại của chuỗi gồm các chuỗi con nối tiếp nhau sao cho kí tự cuối xâu trước là kí tự đầu của xâu sau.
  • Tìm chu trình Euler đi qua tất cả các cạnh có trọng số sao cho ở mọi thời điểm tổng chi phí đường đi có giá trị dương.

    • Tìm hiểu quan hệ đồng dư của số nguyên, hiện thực định lý Fermat nhỏ và tổng quát hơn là định lý Euler.

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

  • Tính số chữ số của một số tự nhiên chia hết số đó.
  • Xác định hệ cơ số của một phép cộng cho trước.
  • Hiện thực giải một số bài ứng dụng toán số học đồng dư.

    • Tìm hiểu về thuật toán Euclidean, Euclidean mở rộng, ứng dụng giải phương trình Diophante.

    Ứng dụng vào các bài toán thao tác các phép tính trên phân số.

    Tìm hiểu các thuật toán nổi tiếng liên quan đến số nguyên tố: Sàng nguyên tố Eratosthenes, Segmented Sieve. Hiện thực cách phân tích ra các thừa số nguyên tố của một số, và tìm hiểu về Phi hàm Euler.

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

  • Tìm nghiệm nguyên nguyên tố của một phương trình tuyến tính 3 ẩn.
  • Xây dựng một tháp ước số đầy đủ, cho biết đường kính đĩa lớn nhất và nhỏ nhất của tháp.
  • Ứng dụng vào một số bài toán nặng về tư duy toán học.

    • Kỳ thi giữa kỳ.

    Chia để trị lấy ý tưởng từ đệ quy, giải quyết một bài toán bằng cách phân chia và giải các bài toán con có cùng tính chất.

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

  • Cặp điểm gần nhau nhất.
  • Bài toán có dạng constructive problem: sắp xếp lịch tập luyện của đội bóng sao cho hai người bất kì trong đội đều có ít nhất một lần đối đầu với nhau.

    • Từ bài toán cổ điển về dãy số Fibonacci, làm quen với hai cách cài đặt bài toán quy hoạch động. Ngoài ra biết cách lưu vết tổng các phần tử đứng trước nó trong một mảng, được sử dụng hỗ trợ giải quyết nhiều bài toán.

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

  • Thay vì tìm số Fibonacci thứ N, tìm một số không phải là số Fibonacci thứ N.
  • Xác định thời điểm mà màn hình máy tính bị hư nếu biết một số pixel trên màn hình đã bị hỏng.

    • Đến với chủ đề quy hoạch động đầu tiên là bài toán đổi tiền, một dạng bài toán xuất hiện sự trùng lặp khi tính toán lại các bài toán con.

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

  • Phân tích số
  • Tháo lắp đĩa tạ khi thi thể hình
  • Mua sắm ở trung tâm thương mại

    • Ứng dụng vào một số bài toán như:

  • Đổi tiền ở New Zealand
  • Xác định tổng phần thưởng lớn nhất trong một cuộc thi

    • Tìm dãy con chung dài nhất. Chủ đề liên quan đến việc lưu trữ kết quả các bài toán con, sau đó sử dụng phối hợp để tính ra kết quả bài toán mong muốn.

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

  • Chuỗi Palindrome dài nhất
  • Dãy con chung không liền kề dài nhất

    • Tìm dãy con tăng dài nhất. Bài toán cùng chung chủ đề với LCS và cũng có thể giải được bằng LCS, nhưng ta sẽ được học thêm cách tối ưu việc tìm kiếm giúp độ phức tạp thuật toán giảm đi đáng kể.

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

  • Bộ trò chơi xếp gạch, búp bê Nga
  • Chiến lược phòng thủ của Starwars SDI.

    • Bài toán liên quan đến tối ưu hoá tổ hợp, thường gặp trong các vấn đề cần phân bổ nguồn tài nguyên. Mặc dù ta có giải bài toán Knapsack cơ bản với kĩ thuật Branch and Bound trong buổi 6, ở buổi này, ta sẽ được học công thức quy hoạch động với độ phức tạp thời gian tối ưu và thường được ứng dụng nhiều hơn.

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

  • Sắp xếp xe trên một chuyến phà.
  • Sắp xếp hành lí lên một chuyến taxi.

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

  • Kiểm tra lời đồn đoán rằng một chú voi to hơn thì thông minh hơn có đúng hay không.
  • Chấm điểm một bài thi sắp xếp các sự kiện lịch sử.

    • Kiểm tra cuối kỳ