THỰC HÀNH TỔNG HỢP 3 - CẤU TRÚC DỮ LIỆU NÂNG CAO

I. Mục tiêu buổi học

Mục tiêu chính

Buổi học này nhằm củng cố và thực hành kiến thức từ Buổi 12-14, tập trung vào:

• Set (Tập hợp) - Xử lý dữ liệu duy nhất
• Dictionary - Cấu trúc key-value mạnh mẽ
• Kết hợp điều kiện và vòng lặp nâng cao
• Xử lý dữ liệu thực tế (JSON-like structures)

Kỹ năng đạt được

Sau buổi học, học viên sẽ có khả năng:

• Thành thạo Set và Dictionary trong Python
• Xử lý dữ liệu phức tạp hiệu quả
• Áp dụng thuật toán tìm kiếm và sắp xếp nâng cao
• Tối ưu hóa hiệu suất chương trình

II. Cấu trúc buổi học (90 phút)

Hoạt động	Thời gian	Nội dung
Ôn tập nhanh	15 phút	Review Set và Dictionary
Thuật toán với Set/Dict	35 phút	3 bài thuật toán quan trọng
Dự án xử lý dữ liệu	30 phút	1 dự án thực tế
Optimization & Best Practices	10 phút	Tối ưu hiệu suất

III. Ôn tập kiến thức (15 phút)

Checklist Set (Tập hợp)

# Tạo set
numbers = {1, 2, 3, 4, 5}
numbers = set([1, 2, 3, 4, 5])

# Phép toán tập hợp
set1 = {1, 2, 3}
set2 = {3, 4, 5}

union = set1 | set2        # Hợp: {1, 2, 3, 4, 5}
intersection = set1 & set2 # Giao: {3}
difference = set1 - set2   # Hiệu: {1, 2}

# Thêm/xóa phần tử
numbers.add(6)
numbers.remove(1)
numbers.discard(10)  # Không lỗi nếu không tồn tại

Checklist Dictionary

# Tạo dictionary
student = {
    'name': 'An',
    'age': 16,
    'scores': [8, 9, 7]
}

# Truy cập và thay đổi
print(student['name'])
student['age'] = 17

# Phương thức quan trọng
keys = student.keys()
values = student.values()
items = student.items()

# Lặp qua dictionary
for key, value in student.items():
    print(f"{key}: {value}")

IV. Thuật toán với Set và Dictionary (35 phút)

Bài 1: Phân tích từ vựng văn bản (12 phút)

Đề bài: Xây dựng bộ phân tích từ vựng cho văn bản.

Phân tích đề

Yêu cầu phân tích:

1. Làm sạch dữ liệu: Loại bỏ ký tự đặc biệt, chuyển về chữ thường
2. Thống kê từ vựng: Đếm tần suất xuất hiện của mỗi từ
3. Phân tích: Tìm từ phổ biến nhất, từ hiếm, độ dài trung bình
4. Tối ưu: Sử dụng Set để loại bỏ trùng lặp, Dict để đếm

Input/Output mẫu:

Input	Xử lý	Output
"Python is great! Python is easy."	Tách từ: ["python", "is", "great", "python", "is", "easy"]	Tổng từ: 6
	Unique:	Từ duy nhất: 4
	Tần suất:	Từ phổ biến: "python", "is"

Gợi ý code

import re
from collections import Counter

def analyze_text(text):
    """Phân tích từ vựng trong văn bản"""

    # Chuẩn hóa văn bản
    text = text.lower()
    words = re.findall(r'\b\w+\b', text)

    # Thống kê cơ bản
    unique_words = set(words)
    word_freq = {}

    for word in words:
        word_freq[word] = word_freq.get(word, 0) + 1

    # Tìm từ phổ biến nhất và hiếm nhất
    most_common = max(word_freq.items(), key=lambda x: x[1])
    least_common = min(word_freq.items(), key=lambda x: x[1])

    # Tính độ dài trung bình
    avg_length = sum(len(word) for word in words) / len(words) if words else 0

    return {
        'total_words': len(words),
        'unique_words': len(unique_words),
        'word_frequency': word_freq,
        'most_common': most_common,
        'least_common': least_common,
        'avg_word_length': round(avg_length, 2)
    }

# Test
text = """
Python là một ngôn ngữ lập trình mạnh mẽ và dễ học.
Python được sử dụng rộng rãi trong phát triển web, 
khoa học dữ liệu và trí tuệ nhân tạo.
"""

result = analyze_text(text)
print("PHÂN TÍCH VĂN BẢN")
print("="*40)
print(f"Tổng số từ: {result['total_words']}")
print(f"Từ duy nhất: {result['unique_words']}")
print(f"Từ phổ biến nhất: {result['most_common'][0]} ({result['most_common'][1]} lần)")
print(f"Độ dài TB: {result['avg_word_length']} ký tự")

Thống kê cơ bản

unique_words = set(words) word_freq = {}

for word in words: word_freq[word] = word_freq.get(word, 0) + 1

Tìm từ xuất hiện nhiều nhất

most_common = max(word_freq.items(), key=lambda x: x[1])

Tìm từ dài nhất/ngắn nhất

longest_word = max(unique_words, key=len) shortest_word = min(unique_words, key=len)

Phân loại độ dài từ

length_distribution = {} for word in unique_words: length = len(word) length_distribution[length] = length_distribution.get(length, 0) + 1

return { 'total_words': len(words), 'unique_words': len(unique_words), 'word_frequency': word_freq, 'most_common': most_common, 'longest_word': longest_word, 'shortest_word': shortest_word, 'length_distribution': length_distribution }

def display_analysis(analysis): """Hiển thị kết quả phân tích""" print("="50) print("PHÂN TÍCH VĂN BẢN") print("="50) print(f"Tổng số từ: {analysis['total_words']}") print(f"Số từ duy nhất: {analysis['unique_words']}") print(f"Từ xuất hiện nhiều nhất: '{analysis['most_common'][0]}' ({analysis['most_common'][1]} lần)") print(f"Từ dài nhất: '{analysis['longest_word']}' ({len(analysis['longest_word'])} ký tự)") print(f"Từ ngắn nhất: '{analysis['shortest_word']}' ({len(analysis['shortest_word'])} ký tự)")

print("\nPhân bố độ dài từ:")
for length in sorted(analysis['length_distribution'].keys()):
    count = analysis['length_distribution'][length]
    print(f"  {length} ký tự: {count} từ")

print("\nTop 10 từ phổ biến:")
sorted_words = sorted(analysis['word_frequency'].items(), 
                     key=lambda x: x[1], reverse=True)
for word, freq in sorted_words[:10]:
    print(f"  {word}: {freq}")

Test

sample_text = """ Python là một ngôn ngữ lập trình bậc cao, dễ học và mạnh mẽ. Python được sử dụng rộng rãi trong khoa học dữ liệu, trí tuệ nhân tạo, phát triển web và nhiều lĩnh vực khác. Python có cú pháp đơn giản và thư viện phong phú, giúp lập trình viên làm việc hiệu quả. """

result = analyze_text(sample_text) display_analysis(result)

### Bài 2: Quản lý thông tin sinh viên (12 phút)

**Đề bài:** Hệ thống quản lý sinh viên với nhiều chức năng.

??? info "Phân tích đề"

    **Yêu cầu hệ thống:**

    1. **Quản lý sinh viên:** Thêm, tìm kiếm, cập nhật thông tin
    2. **Quản lý môn học:** Danh sách môn học, đăng ký môn học
    3. **Phân tích dữ liệu:** Thống kê theo ngành, môn học phổ biến
    4. **Tìm kiếm nâng cao:** Môn học chung, sinh viên cùng ngành

    **Cấu trúc dữ liệu:**

    | Thành phần | Kiểu dữ liệu | Mục đích |
    |------------|--------------|----------|
    | **students** | Dict {id: info} | Lưu thông tin sinh viên |
    | **courses** | Set | Danh sách môn học (không trùng) |
    | **enrollments** | Dict {id: set of courses} | Đăng ký môn học |

??? tip "Gợi ý code"

    ```python
    class StudentDatabase:
        def __init__(self):
            self.students = {}  # {student_id: student_info}
            self.courses = set()
            self.enrollments = {}  # {student_id: set of courses}

        def add_student(self, student_id, name, age, major):
            """Thêm sinh viên"""
            if student_id in self.students:
                return False, "Mã sinh viên đã tồn tại!"

            self.students[student_id] = {
                'name': name,
                'age': age,
                'major': major,
                'gpa': 0.0
            }
            self.enrollments[student_id] = set()
            return True, "Thêm sinh viên thành công!"

        def add_course(self, course_code):
            """Thêm môn học"""
            self.courses.add(course_code)

        def enroll_student(self, student_id, course_code):
            """Đăng ký môn học"""
            if student_id not in self.students:
                return False, "Sinh viên không tồn tại!"

            if course_code not in self.courses:
                return False, "Môn học không tồn tại!"

            self.enrollments[student_id].add(course_code)
            return True, f"Đăng ký môn {course_code} thành công!"

        def find_students_by_major(self, major):
            """Tìm sinh viên theo ngành"""
            result = []
            for student_id, info in self.students.items():
                if info['major'].lower() == major.lower():
                    result.append((student_id, info))
            return result

        def find_common_courses(self, student_id1, student_id2):
            """Tìm môn học chung của 2 sinh viên"""
            if student_id1 not in self.enrollments or student_id2 not in self.enrollments:
                return set()

            return self.enrollments[student_id1] & self.enrollments[student_id2]

        def get_course_statistics(self):
            """Thống kê đăng ký môn học"""
            course_stats = {}

            for course in self.courses:
                enrolled_count = 0
                for student_courses in self.enrollments.values():
                    if course in student_courses:
                        enrolled_count += 1
                course_stats[course] = enrolled_count

            return course_stats

    # Demo usage
    db = StudentDatabase()

    # Thêm dữ liệu mẫu
    courses = ["MATH101", "PHYS101", "CHEM101", "CS101", "ENG101"]
    for course in courses:
        db.add_course(course)

    students_data = [
        ("SV001", "Nguyễn Văn An", 19, "Computer Science"),
        ("SV002", "Trần Thị Bình", 20, "Mathematics"),
        ("SV003", "Lê Văn Cường", 18, "Physics"),
        ("SV004", "Phạm Thị Dung", 19, "Computer Science"),
    ]

    for student_id, name, age, major in students_data:
        success, message = db.add_student(student_id, name, age, major)
        print(message)
    ```

### Bài 3: Thuật toán tối ưu hóa (11 phút)

**Đề bài:** Tìm tập con có tổng bằng target (Subset Sum Problem).

??? info "Phân tích đề"

    **Bài toán Subset Sum:**
    - Cho một mảng số nguyên và một số target
    - Tìm tất cả tập con có tổng bằng target
    - Sử dụng kỹ thuật backtracking và dynamic programming

    **Thuật toán:**
    1. **Backtracking:** Thử tất cả khả năng (chọn hoặc không chọn phần tử)
    2. **Memoization:** Lưu kết quả đã tính để tránh tính lại
    3. **Pruning:** Cắt tỉa các nhánh không cần thiết

    **Ví dụ:**

    | Input | Target | Tập con tìm được |
    |-------|--------|------------------|
    | [1, 3, 5, 7] | 8 | [1, 7], [3, 5] |
    | [2, 4, 6, 8] | 10 | [2, 8], [4, 6] |

??? tip "Gợi ý code"

    ```python
    def find_subset_sum(numbers, target):
        """
        Tìm tất cả tập con có tổng bằng target
        Sử dụng dynamic programming với memoization
        """
        memo = {}
        solutions = []

        def backtrack(index, current_sum, current_subset):
            # Base cases
            if current_sum == target:
                solutions.append(current_subset[:])
                return

            if index >= len(numbers) or current_sum > target:
                return

            # Tạo key cho memoization
            key = (index, current_sum)
            if key in memo:
                return memo[key]

            # Không chọn phần tử hiện tại
            backtrack(index + 1, current_sum, current_subset)

            # Chọn phần tử hiện tại
            current_subset.append(numbers[index])
            backtrack(index + 1, current_sum + numbers[index], current_subset)
            current_subset.pop()

            memo[key] = True
            return True

        backtrack(0, 0, [])
        return solutions

    def analyze_subset_problem(numbers, target):
        """Phân tích bài toán subset sum"""
        print(f"Tìm tập con có tổng = {target} từ: {numbers}")
        print("="*50)

        solutions = find_subset_sum(numbers, target)

        if not solutions:
            print("Không tìm thấy tập con nào!")
            return

        print(f"Tìm thấy {len(solutions)} tập con:")
        for i, solution in enumerate(solutions, 1):
            print(f"{i}. {solution} (tổng: {sum(solution)})")

    # Test cases
    test_cases = [
        ([1, 3, 5, 7, 9], 12),
        ([2, 4, 6, 8], 10),
        ([1, 2, 3, 4, 5], 9)
    ]

    for numbers, target in test_cases:
        analyze_subset_problem(numbers, target)
        print()
    ```

    print(f"Tìm thấy {len(solutions)} tập con:")
    for i, subset in enumerate(solutions, 1):
        print(f"  {i}. {subset} (tổng = {sum(subset)})")

    # Phân tích thêm
    solution_sizes = [len(subset) for subset in solutions]
    min_size = min(solution_sizes)
    max_size = max(solution_sizes)

    print(f"\nPhân tích:")
    print(f"  Tập con nhỏ nhất: {min_size} phần tử")
    print(f"  Tập con lớn nhất: {max_size} phần tử")

    # Tìm phần tử xuất hiện nhiều nhất trong các solution
    element_freq = {}
    for subset in solutions:
        for element in subset:
            element_freq[element] = element_freq.get(element, 0) + 1

    most_common = max(element_freq.items(), key=lambda x: x[1])
    print(f"  Phần tử xuất hiện nhiều nhất: {most_common[0]} ({most_common[1]} lần)")

# Test cases
test_cases = [
    ([3, 34, 4, 12, 5, 2], 9),
    ([1, 2, 3, 4, 5], 7),
    ([2, 4, 6, 8], 10),
]

for numbers, target in test_cases:
    analyze_subset_problem(numbers, target)
    print("\n" + "="*50 + "\n")

V. Dự án: Hệ thống quản lý thư viện (30 phút)

Đề bài: Tạo hệ thống quản lý thư viện với đầy đủ chức năng.

from datetime import datetime, timedelta

class Library:
    def __init__(self):
        self.books = {}  # {book_id: book_info}
        self.members = {}  # {member_id: member_info}
        self.borrowings = {}  # {member_id: {book_id: borrow_date}}
        self.book_categories = set()
        self.authors = set()

    def add_book(self, book_id, title, author, category, copies=1):
        """Thêm sách vào thư viện"""
        if book_id in self.books:
            # Tăng số lượng bản sao
            self.books[book_id]['copies'] += copies
        else:
            self.books[book_id] = {
                'title': title,
                'author': author,
                'category': category,
                'copies': copies,
                'available': copies
            }
            self.book_categories.add(category)
            self.authors.add(author)

        return f"Đã thêm {copies} bản '{title}'"

    def add_member(self, member_id, name, email, phone):
        """Thêm thành viên"""
        if member_id in self.members:
            return "Thành viên đã tồn tại!"

        self.members[member_id] = {
            'name': name,
            'email': email,
            'phone': phone,
            'join_date': datetime.now(),
            'borrowed_books': 0
        }
        self.borrowings[member_id] = {}

        return f"Thêm thành viên {name} thành công!"

    def borrow_book(self, member_id, book_id):
        """Mượn sách"""
        # Kiểm tra thành viên
        if member_id not in self.members:
            return "Thành viên không tồn tại!"

        # Kiểm tra sách
        if book_id not in self.books:
            return "Sách không tồn tại!"

        # Kiểm tra sách còn lại
        if self.books[book_id]['available'] <= 0:
            return "Sách đã hết!"

        # Kiểm tra đã mượn chưa
        if book_id in self.borrowings[member_id]:
            return "Bạn đã mượn sách này rồi!"

        # Thực hiện mượn sách
        self.books[book_id]['available'] -= 1
        self.borrowings[member_id][book_id] = datetime.now()
        self.members[member_id]['borrowed_books'] += 1

        return f"Mượn sách '{self.books[book_id]['title']}' thành công!"

    def return_book(self, member_id, book_id):
        """Trả sách"""
        if member_id not in self.borrowings:
            return "Thành viên không tồn tại!"

        if book_id not in self.borrowings[member_id]:
            return "Bạn không mượn sách này!"

        # Tính số ngày mượn
        borrow_date = self.borrowings[member_id][book_id]
        days_borrowed = (datetime.now() - borrow_date).days

        # Trả sách
        del self.borrowings[member_id][book_id]
        self.books[book_id]['available'] += 1
        self.members[member_id]['borrowed_books'] -= 1

        # Tính phí phạt (nếu quá 14 ngày)
        fine = max(0, (days_borrowed - 14) * 1000)  # 1000đ/ngày

        result = f"Trả sách '{self.books[book_id]['title']}' thành công!\n"
        result += f"Số ngày mượn: {days_borrowed}"
        if fine > 0:
            result += f"\nPhí phạt: {fine:,}đ"

        return result

    def search_books(self, query):
        """Tìm kiếm sách"""
        results = []
        query = query.lower()

        for book_id, book_info in self.books.items():
            if (query in book_info['title'].lower() or 
                query in book_info['author'].lower() or
                query in book_info['category'].lower()):
                results.append((book_id, book_info))

        return results

    def get_popular_books(self, top_n=5):
        """Lấy sách phổ biến nhất"""
        borrow_count = {}

        # Đếm số lần mượn
        for member_borrowings in self.borrowings.values():
            for book_id in member_borrowings:
                borrow_count[book_id] = borrow_count.get(book_id, 0) + 1

        # Sắp xếp theo độ phổ biến
        popular = sorted(borrow_count.items(), key=lambda x: x[1], reverse=True)

        return popular[:top_n]

    def generate_report(self):
        """Tạo báo cáo thống kê"""
        total_books = sum(book['copies'] for book in self.books.values())
        available_books = sum(book['available'] for book in self.books.values())
        borrowed_books = total_books - available_books

        print("="*60)
        print("BÁO CÁO THỐNG KÊ THƯ VIỆN")
        print("="*60)
        print(f"Tổng số sách: {total_books}")
        print(f"Sách đang có: {available_books}")
        print(f"Sách đang mượn: {borrowed_books}")
        print(f"Tổng số thành viên: {len(self.members)}")
        print(f"Số thể loại sách: {len(self.book_categories)}")
        print(f"Số tác giả: {len(self.authors)}")

        # Top sách phổ biến
        popular = self.get_popular_books()
        if popular:
            print("\nTop 5 sách được mượn nhiều nhất:")
            for i, (book_id, count) in enumerate(popular, 1):
                book_title = self.books[book_id]['title']
                print(f"  {i}. {book_title} ({count} lần)")

        # Thống kê theo thể loại
        category_stats = {}
        for book in self.books.values():
            category = book['category']
            category_stats[category] = category_stats.get(category, 0) + book['copies']

        print("\nThống kê theo thể loại:")
        for category, count in sorted(category_stats.items()):
            print(f"  {category}: {count} cuốn")

# Demo hệ thống
def demo_library():
    lib = Library()

    # Thêm sách
    books_data = [
        ("B001", "Python Programming", "John Smith", "Technology", 3),
        ("B002", "Data Science Handbook", "Jane Doe", "Technology", 2),
        ("B003", "The Great Gatsby", "F. Scott Fitzgerald", "Literature", 4),
        ("B004", "1984", "George Orwell", "Literature", 3),
        ("B005", "Calculus", "James Stewart", "Mathematics", 2),
    ]

    for book_data in books_data:
        result = lib.add_book(*book_data)
        print(result)

    # Thêm thành viên
    members_data = [
        ("M001", "Nguyễn Văn An", "an@email.com", "0123456789"),
        ("M002", "Trần Thị Bình", "binh@email.com", "0987654321"),
        ("M003", "Lê Văn Cường", "cuong@email.com", "0555666777"),
    ]

    for member_data in members_data:
        result = lib.add_member(*member_data)
        print(result)

    # Mượn sách
    print("\n" + "="*40)
    print(lib.borrow_book("M001", "B001"))
    print(lib.borrow_book("M001", "B003"))
    print(lib.borrow_book("M002", "B001"))
    print(lib.borrow_book("M002", "B002"))

    # Tìm kiếm sách
    print("\n" + "="*40)
    print("Tìm kiếm 'python':")
    results = lib.search_books("python")
    for book_id, book_info in results:
        print(f"  {book_info['title']} - {book_info['author']}")

    # Báo cáo thống kê
    print()
    lib.generate_report()

if __name__ == "__main__":
    demo_library()

VI. Optimization & Best Practices (10 phút)

Tối ưu hiệu suất với Set và Dictionary

1. Tìm kiếm nhanh:

# ❌ Chậm - O(n)
def is_valid_slow(item, valid_items):
    return item in valid_items  # valid_items là list

# ✅ Nhanh - O(1)
def is_valid_fast(item, valid_items):
    return item in valid_items  # valid_items là set

2. Loại bỏ duplicate:

# ❌ Chậm
def remove_duplicates_slow(items):
    result = []
    for item in items:
        if item not in result:
            result.append(item)
    return result

# ✅ Nhanh
def remove_duplicates_fast(items):
    return list(set(items))

3. Counting hiệu quả:

from collections import Counter, defaultdict

# ✅ Sử dụng Counter
counter = Counter(items)
most_common = counter.most_common(5)

# ✅ Sử dụng defaultdict
freq = defaultdict(int)
for item in items:
    freq[item] += 1

VII. Bài tập về nhà

Bài 1: Mạng xã hội mini

Yêu cầu:

• Quản lý users và relationships (following/followers)
• Tính mutual friends
• Suggest friends (friends of friends)
• Generate timeline từ followed users
• Thống kê network metrics

Bài 2: E-commerce data analysis

Yêu cầu:

• Parse dữ liệu orders (JSON format)
• Tính revenue theo category/month
• Tìm top customers và products
• Detect trending products
• Generate business insights

Bài 3: Tournament management

Yêu cầu:

• Quản lý players và matches
• Calculate rankings và ELO ratings
• Generate tournament brackets
• Track match history
• Export results to files

VIII. Chuẩn bị cho buổi sau

Buổi tiếp theo sẽ học về Functions (Hàm) - công cụ mạnh mẽ để tổ chức và tái sử dụng code. Hãy ôn lại:

• Khái niệm function trong toán học
• Tại sao cần chia nhỏ chương trình
• Các hàm built-in đã sử dụng: len(), max(), print()

---

💡 Tip học tập: Set và Dictionary là foundation của many advanced algorithms. Master them để unlock more complex programming patterns!