CHỦ ĐỀ BỒI DƯỠNG K12+11

A.TÓM TẮT LÝ THUYẾT.

B.MỘT SỐ CÂU HỎI ÔN TẬP.

Câu hỏi ôn tập số 1.

Câu hỏi ôn tập số 2.

Câu hỏi ôn tập số 3.

Câu hỏi ôn tập số 4.

Câu hỏi ôn tập số 5.

A.TÓM TẮT LÝ THUYẾT.

Phần 1: Các kiểu dữ liệu cơ bản trong ngôn ngữ lập trình Pyrhon.

1. List: Là một tập hợp các phần tử có thứ tự (Bắt đầu bằng 0), cho phép trùng lặp và có thể thay đổi được (mutable). Các phần tử trong list được đặt trong dấu ngoặc vuông [] và phân cách nhau bởi dấu phẩy. Ví  dụ: trai_cay = ["táo", "chuối", "cam", "xoài"] .

2. Set: Là một tập hợp các phần tử không có thứ tự, không cho phép trùng lặp và có thể thay đổi được. Các phần tử trong set được đặt trong dấu ngoặc nhọn {}. Ví dụ:  so_nguyen = {1, 2, 3, 4, 5, 5} .

3. Tuple: Là một tập hợp các phần tử có thứ tự, cho phép trùng lặp nhưng không thể thay đổi được (immutable). Các phần tử trong tuple được đặt trong dấu ngoặc đơn (). VÍ dụ: thong_tin = ("Nguyễn Văn A", 25, "Hà Nội") .

4. Dictionary: Là một tập hợp các phần tử không có thứ tự, lưu trữ dưới dạng cặp key-value. Key không được trùng lặp và có thể thay đổi được, trong khi value có thể là bất kỳ kiểu dữ liệu nào. Các phần tử trong dictionary được đặt trong dấu ngoặc nhọn {} và mỗi cặp key-value được phân cách bởi dấu hai chấm :. Ví dụ:

sinh_vien = { 

"MaSV":"12a01"

"ho_ten": "Trần Thị B",

 "tuoi": 20,

 "diem_tb": 8.5 } 

5. Danh sách hai chiều trong Python là một cấu trúc dữ liệu mạnh mẽ cho phép bạn lưu trữ và làm việc với dữ liệu theo dạng bảng, giống như một ma trận trong toán học. Hãy tưởng tượng nó như một tờ giấy kẻ ô, mỗi ô có thể chứa một giá trị. 

Ví dụ:

# Tạo một danh sách hai chiều 3x3

danh_sach = [

  [1, 2, 3],

  [4, 5, 6],

  [7, 8, 9]

]

# In ra phần tử ở hàng 2, cột 3

print(danh_sach[1][2])  # Kết quả: 6

Phần 2: Các thuật toán

1. Thuật toán sắp xếp:

●Sắp xếp nổi bọt (Bubble Sort):

○Độ phức tạp: O(n^2).

○Giải thích: Thuật toán so sánh từng cặp phần tử liền kề và hoán đổi vị trí nếu chúng không theo thứ tự. Quá trình này được lặp lại cho đến khi danh sách được sắp xếp.

●Sắp xếp chọn (Selection Sort):

○Độ phức tạp: O(n^2).

○Giải thích: Thuật toán tìm phần tử nhỏ nhất trong danh sách chưa được sắp xếp và hoán đổi nó với phần tử đầu tiên. Quá trình này được lặp lại cho phần còn lại của danh sách.

●Sắp xếp chèn (Insertion Sort):

○Độ phức tạp: O(n^2) .

○Giải thích: Thuật toán duyệt qua danh sách và chèn từng phần tử vào đúng vị trí trong phần đã được sắp xếp.

●Sắp xếp nhanh (Quick Sort):

○Độ phức tạp: O(n log n) (trung bình), O(n^2).

○Giải thích: Thuật toán chọn một phần tử làm chốt, sau đó chia danh sách thành hai phần: phần tử nhỏ hơn chốt và phần tử lớn hơn chốt. Sau đó, đệ quy sắp xếp hai phần này.

2. Thuật toán tìm kiếm:

●Tìm kiếm tuần tự:

○Mô tả: Duyệt qua từng phần tử trong danh sách cho đến khi tìm thấy phần tử cần tìm hoặc đến cuối danh sách.

○Độ phức tạp: O(n), nghĩa là thời gian tìm kiếm tỉ lệ thuận với số lượng phần tử trong danh sách.

●Tìm kiếm nhị phân:

○Mô tả: Áp dụng cho danh sách đã được sắp xếp. Thuật toán so sánh phần tử cần tìm với phần tử ở giữa danh sách. Nếu bằng nhau, trả về vị trí; nếu nhỏ hơn, tiếp tục tìm kiếm trong nửa đầu danh sách; nếu lớn hơn, tiếp tục tìm kiếm trong nửa sau danh sách .

○Độ phức tạp: O(log n), nghĩa là thời gian tìm kiếm tăng chậm hơn so với số lượng phần tử trong danh sách

3. Thuật toán đệ quy:

-Đệ quy là một kỹ thuật lập trình trong đó một hàm gọi lại chính nó. Hãy tưởng tượng nó như những con búp bê Nga, mỗi con búp bê chứa một con búp bê nhỏ hơn bên trong, cho đến khi đến con búp bê cuối cùng không thể mở ra được nữa.

-Cách thức hoạt động:

• Trường hợp cơ sở (Base case): Đây là điều kiện dừng đệ quy, giống như con búp bê cuối cùng. Khi đạt đến trường hợp cơ sở, hàm sẽ trả về một giá trị cụ thể mà không gọi lại chính nó nữa.

• Bước đệ quy (Recursive step): Hàm tự gọi lại chính nó với một đầu vào nhỏ hơn, giống như việc mở một con búp bê để thấy con búp bê nhỏ hơn bên trong. Bước này chia bài toán thành các bài toán con đơn giản hơn.

def giai_thua(n):

  if n == 0:  # Trường hợp cơ sở

    return 1

  else:

    return n * giai_thua(n - 1)  # Bước đệ quy

Nhược điểm: Tốn tài nguyên: Mỗi lần gọi đệ quy sẽ sử dụng bộ nhớ stack, nếu đệ quy quá sâu có thể dẫn đến tràn stack.

4. Thuật toán chia để trị:

-Thuật toán Chia để trị (Divide and Conquer) là một phương pháp giải quyết vấn đề bằng cách chia nhỏ vấn đề lớn thành các vấn đề con tương tự nhưng nhỏ hơn, giải quyết các vấn đề con này một cách độc lập, sau đó kết hợp các lời giải của chúng để tạo ra lời giải cho vấn đề ban đầu.

-Ba bước chính:

• Chia (Divide): Chia bài toán ban đầu thành các bài toán con nhỏ hơn.

• Trị (Conquer): Giải quyết các bài toán con một cách đệ quy. Nếu bài toán con đủ nhỏ, giải quyết trực tiếp.

• Kết hợp (Combine): Kết hợp các lời giải của các bài toán con để tạo thành lời giải cho bài toán ban đầu.

Ví dụ:

Sắp xếp trộn (Merge Sort):

• Chia mảng thành hai nửa.

• Sắp xếp đệ quy mỗi nửa.

• Trộn hai nửa đã sắp xếp thành một mảng đã sắp xếp hoàn chỉnh.

Tìm kiếm nhị phân (Binary Search):

• Chia mảng đã sắp xếp thành hai nửa.

• So sánh giá trị cần tìm với phần tử ở giữa mảng.

• Tiếp tục tìm kiếm trong nửa chứa giá trị cần tìm.

Phần 3: Độ phức tạp thuật toán.

●Ký hiệu Big O: Độ phức tạp thuật toán thường được biểu diễn bằng ký hiệu Big O, ví dụ: O(n), O(n^2), O(log n). Ký hiệu này mô tả sự tăng trưởng của thời gian chạy hoặc bộ nhớ sử dụng của thuật toán khi kích thước dữ liệu đầu vào tăng lên. [Thông tin này không có trong nguồn, cần được kiểm chứng độc lập].

●Các mức độ phức tạp:

○O(1): Thời gian chạy không phụ thuộc vào kích thước dữ liệu đầu vào (thuật toán chạy trong thời gian hằng số). 

○O(log n): Thời gian chạy tăng chậm khi kích thước dữ liệu đầu vào tăng.

○O(n): Thời gian chạy tỉ lệ thuận với kích thước dữ liệu đầu vào.

○O(n log n): Thời gian chạy tăng nhanh hơn O(n) nhưng chậm hơn O(n^2). 

○O(n^2): Thời gian chạy tỉ lệ với bình phương kích thước dữ liệu đầu vào.

●Ảnh hưởng đến hiệu suất: Độ phức tạp thuật toán ảnh hưởng trực tiếp đến thời gian xử lý dữ liệu và hiệu suất của chương trình. Thuật toán có độ phức tạp thấp hơn sẽ chạy nhanh hơn và hiệu quả hơn, đặc biệt khi xử lý dữ liệu lớn.

●Lựa chọn thuật toán: Việc lựa chọn thuật toán phù hợp phụ thuộc vào kích thước dữ liệu đầu vào và yêu cầu về hiệu suất. Đối với dữ liệu nhỏ, thuật toán đơn giản với độ phức tạp cao có thể chấp nhận được. Tuy nhiên, khi xử lý dữ liệu lớn, cần sử dụng thuật toán có độ phức tạp thấp để đảm bảo hiệu suất.

B.MỘT SỐ CÂU HỎI ÔN TẬP.

Câu hỏi ôn tập số 1.

Câu hỏi ôn tập số 2.

Câu hỏi ôn tập số 3.

Câu hỏi ôn tập số 4.

Câu hỏi ôn tập số 5.

A.TÓM TẮT LÝ THUYẾT.

B.MỘT SỐ CÂU HỎI ÔN TẬP.

Câu hỏi ôn tập số 1.

Câu hỏi ôn tập số 2.

Câu hỏi ôn tập số 3.

Câu hỏi ôn tập số 4.

Câu hỏi ôn tập số 5.

A.TÓM TẮT LÝ THUYẾT.

B.MỘT SỐ CÂU HỎI ÔN TẬP.

Câu hỏi ôn tập số 1.

Câu hỏi ôn tập số 2.

Câu hỏi ôn tập số 3.

Câu hỏi ôn tập số 4.

Câu hỏi ôn tập số 5.

A.TÓM TẮT LÝ THUYẾT.

Chủ đề HTML trong sách giáo khoa Tin học 12 tập trung vào việc giúp học sinh hiểu và làm quen với cấu trúc của trang web dưới dạng HTML.

Nội dung chủ đề HTML bao gồm:

●Giới thiệu HTML và trang web:

○HTML là viết tắt của cụm từ Hypertext Markup Language (ngôn ngữ đánh dấu siêu văn bản), là một bộ quy tắc dùng để thiết lập cấu trúc hiển thị nội dung trang web.1

○Trang web được thiết lập từ các văn bản thường có phần mở rộng là .html hoặc .htm.

●Cấu trúc cơ bản của một tệp HTML:

○Mỗi tệp HTML bao gồm nhiều phần tử HTML, các phần tử HTML có thể lồng nhau.3

○Các phần tử HTML cơ bản bao gồm: div, p, h1-h6,...

○Quan hệ lồng nhau giữa các nút của HTML có thể hình dung như quan hệ cha - con hay quan hệ giữa các cành của một sơ đồ hình cây.3

●Thực hành tạo tệp HTML:

○Có nhiều phần mềm có thể dùng để soạn thảo tệp HTML, ví dụ Notepad++, Pycharm,..

○Cũng có thể sử dụng các trang web hỗ trợ soạn thảo HTML trực tuyến.

●Định dạng văn bản:

○HTML có thể được sử dụng để định dạng văn bản, phông chữ.

○Các thẻ HTML được sử dụng để định dạng văn bản bao gồm: <strong>, <b>, <em>, <i>, <mark>, <small>, <del>, <sub>, <sup>, 

○Thuộc tính style có thể được sử dụng để định dạng phông chữ. Các thuộc tính màu sắc, phông chữ, cỡ chữ được xác định như sau:

■Màu chữ: <p style="color:tên_màu;">…</p>

■Phông chữ: <p style="font-family:tên_phông;">…</p>

■Cỡ chữ: <p style="font-size:cỡ_chữ;">…</p>

●Tạo danh sách, bảng:

○Trang web HTML tạo được danh sách, bảng.9

○Các phần tử HTML được sử dụng để tạo danh sách bao gồm: <ul>, <ol>, <li>, <dl>, <dt>, <dd>.

○Các phần tử HTML được sử dụng để tạo bảng bao gồm: <table>, <tr>, <td>, <th>, <caption>.

●Tạo liên kết:

○Sử dụng HTML tạo được các loại liên kết.12

○Liên kết tới một trang web khác: <a href="đường_dẫn_tới_trang_web_khác">…</a>13

○Liên kết tới một vị trí khác trong cùng trang: <a href="#tên_đánh_dấu">…</a>

○Liên kết tới hình ảnh: <a href="đường_dẫn_tới_tệp_ảnh">…</a>

●Chèn tệp tin đa phương tiện:

○Sử dụng HTML chèn được các tệp tin đa phương tiện (âm thanh, hình ảnh, video) vào trang web và điều chỉnh kích thước cho phù hợp.15

○Thẻ <img> được sử dụng để chèn ảnh vào trang web.15

○Thẻ <audio> và <video> được sử dụng để chèn âm thanh và video vào trang web.16

●Tạo khung nội tuyến:

○Thẻ <iframe> được sử dụng để tạo khung nội tuyến, hiển thị nội dung của trang web khác.

●Tạo biểu mẫu:

○Thẻ <form> được sử dụng để tạo biểu mẫu.18

○Các phần tử HTML được sử dụng để tạo biểu mẫu bao gồm: <input>, <label>, <select>, <textarea>, ...

Ngoài ra, sách giáo khoa còn cung cấp nhiều ví dụ và bài tập thực hành giúp học sinh củng cố kiến thức về chủ đề HTML.

B.MỘT SỐ CÂU HỎI ÔN TẬP.

Câu hỏi ôn tập số 1.

Câu hỏi ôn tập số 2.

Câu hỏi ôn tập số 3.

Câu hỏi ôn tập số 4.

Câu hỏi ôn tập số 5.

#Mã bài: A_01_1

#Mã bài: A_01_2

#Mã bài: A_01_3

#Mã bài: A_01_4

#Mã bài: A_01_5

#Mã bài: B_01_1

#Mã bài: B_01_2

#Mã bài: B_01_3

#Mã bài: B_01_4

#Mã bài: B_01_5

#Mã bài: A_02_1

#Mã bài: A_02_2

#Mã bài: A_02_3

#Mã bài: A_02_4

#Mã bài: A_02_5

#Mã bài: B_02_1

#Mã bài: B_02_2

#Mã bài: B_02_3

#Mã bài: B_02_4

#Mã bài: B_02_5

#Mã bài: A_03_1

#Mã bài: A_03_2

#Mã bài: A_03_3

#Mã bài: A_03_4

#Mã bài: A_03_5

#Mã bài: B_03_1

#Mã bài: B_03_2

#Mã bài: B_03_3

#Mã bài: B_03_4

#Mã bài: B_03_5

#Mã bài: A_04_1

#Mã bài: A_04_2

#Mã bài: A_04_3

#Mã bài: A_04_4

#Mã bài: A_04_5

#Mã bài: B_04_1

#Mã bài: B_04_2

#Mã bài: B_04_3

#Mã bài: B_04_4

#Mã bài: B_04_5

list=[] #List rỗng một chiều, hai chiều.

list=[0]*n #Khởi tạo list một chiều n phần tử đều bằng 0.

list=[[0]*n for i in range(m)] #Khởi tạo list hai chiều m dòng n cột.

list=[[0]*n] #Khởi tạo dòng 0 list hai chiều

#Khởi tạo cột 0 list hai chiều

row=[1,2,3,4] # Hoặc đọc ra từ input()

for i in range(1,m):

row=[0]+row

list.append(row)

-Đọc từng dòng trong File:

for row in sys.stdin.readlines():

rowint=list(map(int,row.split())) #hoặc i,j,k=map(int,row.split())

list.append(rowint) #hoặc list[i][j]=k

Bài 1: Vận chuyển hàng hóa Tên chương trình:  BAI3.???

Ngày nay, việc mua bán hàng hóa online trở nên rất phổ biến. Cũng chính vì sự phát triển của việc bán hàng online mà nhiều ứng dụng mua bán hàng online hướng đến điều đó ra đời như: Lazada, Shopee, Sendo, Amazon Shopping,… Việc đặt hàng của khách hàng diễn ra khá đơn giản, sau khi tìm được món hàng ưng ý thì khách hàng chọn chức năng mua hàng, và trong chức năng mua hàng ứng dụng sẽ đề cập đến chi phí vận chuyển (ship). Trong mỗi ứng dụng hỗ trợ mua bán online khi đến phần tính toán chi phí ship thì thường có kèm theo rất nhiều nhà vận chuyển. Để cho khách hàng đỡ tốn kém nhất thì ứng dụng sẽ phải chọn ra phương án hay nhất có thể với chi phí ít nhất.

Câu hỏi đặt ra là: Có m nhà vận chuyển được đánh số thứ tự từ 1 đến m. Cần vận chuyển n đơn hàng giống nhau của khách hàng. Biết được chi phí để vận chuyển i đơn hàng của nhà vận chuyển j (với i=1, 2,…, n; j=1, 2,…, m) 

Yêu cầu: Cho biết một phương án vận chuyển n đơn hàng với chi phí thấp nhất.

Dữ liệu vào từ file BAI3.INP:

• Dòng đầu tiên là 2 số nguyên dương n và m (n, m≤100).

• Dòng thứ i trong m dòng tiếp theo mỗi dòng chứa n số nguyên dương, số thứ j cho biết chi phí vận chuyển j đơn hàng của nhà vận chuyển i (giá trị này không vượt quá 109;  i=1, 2,…, m; j=1, 2,…, n).

Kết quả ghi vào file ‘BAI3.OUT’ tổng chi phí thấp nhất theo phương án tìm được.

-Code Tham khảo:

import sys,math

f='BAI3.'

def init():

    sys.stdin=open(f+'INP','r')

    sys.stdout=open(f+'OUT','w')

    n,m=map(int,input().split())

    l=[[0]*(n+1)]

    for i in range(m):

        lm=[0]+list(map(int,input().split()))

        l.append(lm)

    return n,m,l

n,m,l=init()

d=[[0]*(n+1) for i in range(m+1)]

for i in range(1,n+1):

    d[1][i]=l[1][i]

for i in range(2,m+1):

    for j in range(1,n+1):

        d[i][j]=l[i][j]

        for k in range(1,j+1):

            d[i][j]=min(d[i][j],d[i-1][k]+l[i][j-k])

print(l)

print(d)

print(d[m][n])

sys.stdout.close()

Bai4:

Trong một hệ thống mạng gồm n máy tính, được đánh số từ 1 đến n. Sơ đồ nối mạng được cho bởi các kênh nối trực tiếp giữa một số cặp máy trong mạng. Biết  dung lượng cho phép truyền một tệp thông tin theo mỗi kênh nối của mạng. Một tệp thông tin chỉ được truyền từ máy này  đến máy kia nếu dung lượng của tệp không vượt quá dung lượng cho phép trên kênh hai máy đó. An đang ở máy u muốn truyền một tệp sang máy v.

Yêu cầu:Hãy viết chương trình cho biết dung lượng tối đa của tệp thông tin mà An có thể truyền được từ máy u đến máy v.

Dữ liệu vào tệp BAI4.inp

-       Dòng thứ nhất chứa 3 số n,u,v (1≤n≤200, 1≤u,v≤n)

-       Trong những dòng tiếp theo chứa 3 số nguyên dương i,j,k cho biết giữa máy i và j có kênh nối trực tiếp và dung lượng cho phép trên kênh này là k (1≤i,j≤n, k≤2*109)

Kết quả ghi vào tệp BAI4.out là dung lượng tối đa của tệp thông tin mà An có thể truyền từ máy u đến máy v.

-Code Tham khảo:

file='bai4'

import sys

def kb(file):

    sys.stdin=open(file+'.inp','r')

    sys.stdout=open(file+'.out','w')

    n,u,v=map(int,input().split())

    l=[[0]*(n+1) for i in range(n+1)]

    for x in sys.stdin.readlines():

        i,j,k=map(int,x.split())

        l[i][j]=k

        l[j][i]=k

    return n,u,v,l

def xuly(file):

    n,u,v,l=kb(file)

    d=[0]*(n+1)

    t=[True]*(n+1)

    d[1]=2*(10**9)

    while True:

        x=0

        maxx=0

        for i in range(1,n+1):

            if t[i] and d[i]>maxx:

                maxx=d[i]

                x=i

        t[x]=False

        if x==0 or x==v:

            break

        for k in range(1,n+1):

            if t[i] and d[k]<min(d[x],l[x][k]):

                d[k]=min(d[x],l[x][k])        

    print(d[v])

xuly(file)

sys.stdout.close()