Học liệu mở · Miễn phí
Efficient Algorithms and Intractable Problems
University of California, Berkeley · CS 170 · Thu 2020
Giảng viên gốc: Avishay Tal, Umesh V. VaziraniBiên soạn trên OpenER: Ban biên tập OpenER
Đang tải nội dung khóa học…
Giới thiệu
Môn học vừa dạy cách thiết kế thuật toán nhanh, vừa chỉ ra những bài toán mà gần như không thể có thuật toán nhanh.
Bạn sẽ học
Chia để trị và biến đổi Fourier nhanh (FFT). Duyệt đồ thị: DFS, thành phần liên thông mạnh, đường đi ngắn nhất. Thuật toán tham lam và quy hoạch động. Quy hoạch tuyến tính, đối ngẫu và luồng mạng. Trò chơi tổng bằng 0 và cập nhật trọng số nhân. Quy dẫn, NP-đầy đủ và cách đối phó với bài toán NP-đầy đủ. Số học modular, kiểm tra nguyên tố, băm và thuật toán luồng dữ liệu. Phân tích thừa số bằng máy tính lượng tử.
Cần nền tảng cấu trúc dữ liệu, chứng minh toán học và xác suất rời rạc. Mỗi tuần có bài giảng, buổi thảo luận và bài tập về nhà.
