L thuyt- Thut toán tìm kiếm theo chiều rộng thường gọi là BFS - Breadth-First Search là một thut toán duyệt bắt đầu từ gốc, sau đó lần lượt xét qua các node của một cây theo ưu tiên
HỌC VIỆN CƠNG NGHỆ BƯU CHÍNH VIỄN THƠNG KHOA CƠNG NGHỆ THÔNG TIN BÁO CÁO BÀI TẬP LỚN MÔN HỌC: THC TẬP CƠ S ĐỀ TÀI: XÂY DNG NG DNG WEB TRUY VN QUẢN LÍ BÁN LAPTOP KT HP GIẢI THUẬT BFS, IDS Ging viên ging dy: Nguyn Mai Trang Nhóm lp thc tp: INT13147 Nhóm 21 Ngưi thc hin: Phm Quang Tip M sinh viên: B20DCCN601 Lp: D20CQCN01-B Hà Nội, 2023 LỜI CẢM ƠN Đầu tiên, em xin gửi lời cảm ơn sâu sắc đến Học viện nghệ Bưu Viễn thơng khoa CNTT1 đưa môn học Thc tp s vào chương trình giảng dạy Đặc biệt, em xin gửi lời cảm ơn sâu sắc đến giảng viên môn Nguyễn Mai Trang gip đ, rèn luyện truyền đạt kiến thức quý báu cho em suốt thời gian vừa qua Trong thời gian thc , em rt kinh nghiệm thêm nhiều kiến thức bổ ích, học tp tinh thần làm việc hiệu quả, nghiêm tc Đây thc điều cần thiết cho q trình học tp cơng tác sau em Thêm vào đó, em thc đề tài tp lớn hoàn chỉnh cho môn học này, cn đơn giản cn nhiều hạn chế, em s cố gắng đ d án sau ngày chu hoàn chỉnh Em xin chân thành cảm ơn, chc cô khe mạnh tiếp tc đạt nhiều thành công sống ạ! Mc lc PHN I: Cơ s liệu Hệ quản tr s liệu Mô tả s liệu sử dng Phần II: 4 1.Thut toán BFS Thut toán IDS IV Kiến trc hệ thống chương trình PH LC I Code web trang chủ II Code web lý thuyết III Code web lý thuyết BFS IV Code web lý thuyết IDS V Code web thut toán BFS VI Code web thut toán IDS 14 21 22 22 23 25 27 28 32 PHN I: Cơ s d liu - Cơ s liệu (Database) tp hợp liệu có tổ chức lưu trữ máy tính hệ thống lưu trữ khác Nó bao gồm thông tin, liệu mô tả đối tượng s kiện hệ thống tổ chức c th Các liệu tổ chức lưu trữ s liệu đ cho phép ứng dng người dùng khác truy cp sử dng chng dễ dàng - Cơ s liệu thường tổ chức thiết kế đ đáp ứng yêu cầu mc đích khác nhau, chẳng hạn lưu trữ thông tin sản phẩm, thông tin khách hàng, thông tin tài khoản ngân hàng, thông tin nhân viên, Các s liệu có th lưu trữ máy tính cá nhân, máy chủ đám mây H qun tr s d liu -Hệ quản tr s liệu (DBMS) gói phần mềm dùng đ xác đnh, thao tác truy xuất quản lý liệu Hệ quản tr thường s thao tác với liệu DBMS Ví d như: đnh dạng liệu, tên file, cấu trc record cấu trc file Ngoài ra, hệ quản tr s gip xác đnh quy tắc nhằm xác thc thao tác với liệu - Hệ quản tr s liệu có chức sau: + Chức quản lý liệu + Chức kim soát truy cp nhiều người dùng + Chức chuyn đổi trình bày liệu + Chức quản lý tình tồn vẹn liệu + Chức quản lý bảo mt + Quản lý lưu trữ liệu Mô t s d liu s dng - Cơ s liệu quản lý cửa hàng bán laptop sử dng hệ quản tr s liệu SQL Server - Các bảng: + Bảng nhân viên: Nhan_vien + Bảng sản phẩm: San_pham +Bảng giao dch: Giao_dich - Bảng nhân viên: STT Tên thuộc tính Kiu liệu Ràng buộc Khóa Mơ tả NV_ID nvarchar(50) Not null Chín Mã nhân viên Name nvarchar(50) Not null Tên nhân viên Gioi_Tinh nvarchar(50) Not null Giới tính Que_Quan nvarchar(10 Not null Quê quán Not null Lương h 0) Luong int Chuc_Vu nvarchar(50) Not null Chức v Ngay_Sinh nvarchar(50) Note Null Ngày sinh - Bảng sản phẩm STT Tên thuộc tính Kiu liệu nvarchar(50) Not null SP_ID Ràng buộc Khóa Chín Mơ tả Mã sản phẩm h Ten_SP nvarchar(100 Not null Tên sản phẩm ) Hang_San_Xu nvarchar(50) Not null Hãng sản xuất int Giá sản phẩm at Gia_SP Not null - Bảng giao dch STT Tên thuộc tính Kiu liệu nvarchar(50) Not null Sale_ID Ràng buộc Khóa Mơ tả Chín Mã giao dch h SP_ID nvarchar(50) Not null NV_ID nvarchar(50) Not null Ngoạ Mã sản phẩm i Ngoạ Mã nhân viên i thc giao dch So_Luong int Not null Số lượng bán giao dch Document continues below Discover more from: tập sở Thực LVK1911 Học viện Công ng… 148 documents Go to course Bài thực hành - Lê 23 Văn Kiên -… Thực tập sở 100% (3) De giua ki toan 10 nam 2022 2023… Thực tập sở 100% (3) bao cao bai tap lon 19 windows va linux Thực tập sở 100% (2) Bài thực hành - Lê 12 16 Văn Kiên -… Thực tập sở 100% (1) Bài thực hành - Lê Văn Kiên -… Thực tập sở 100% (1) B18DCQT017 Báo- Thiết kế hệ quản tr s liệu 46 cáo-thực-tập-tốt-… Thực tập sở 100% (1) Thit k h qun tr s d liu - Mơ hình quan hệ RDM Mơ hnh quan h RDM Phn II: 1.Thut ton BFS a L thuyt - Thut tốn tìm kiếm theo chiều rộng (thường gọi BFS - Breadth-First Search) thut toán duyệt gốc, sau xét qua node theo ưu tiên độ sâu từ nh đến lớn - Ban đầu, đỉnh gốc đưa vào hàng đợi (queue) Sau đó, thut tốn s lấy đỉnh gốc khi hàng đợi, khám phá đỉnh kề đưa đỉnh kề vào hàng đợi Quá trình tiếp tc hàng đợi trống - Thut tốn: BFS(Q,S,G,P) (Q:Khơng gian trạng thái, S: Trạng thái bắt đầu, G:Đích, P: Hành động) Đầu vào: Bài tốn tìm kiếm Đầu ra: Đường tới nt đích Khi tạo: tp nt biên O=S While (O≠ ∅) lấy nt n khi O if n ∈ G, return (đưng ti n) thêm P(n) vo cui O Return không tm đưc đưng -VD: Thứ t duyệt : A, B, C, D, E, F nh chp mn hnh đnh ngha BFS b Thut ton Thut toán BFS hoạt động sau: - Trước tiên, code s xử lý liệu đầu vào Nó tách cạnh thành mảng xác đnh tp hợp đỉnh cạnh dạng mảng nh chp mn hnh test chy thut ton IDS IV Kin trc h thng chương trnh Sơ đ h thng chương trnh tng hp 21 PH LC I Code web trang ch Bo co TTCS /* CSS để trang tr giao diện */ body { font-family: Arial, sans-serif; text-align: center; padding-top: 100px; } h1 { color: #333; } h2 { color: #333; } links { margin-top: 20px; } links a { display: block; margin-bottom: 10px; color: #007bff; text-decoration: none; } Bo co Thc tp sở Phm Quang Tiệp - B20DCCN601 L thuyết Gii thut ton BFS Gii thut ton IDS 22 Bo co TTCS /* CSS để trang tr giao diện */ body { font-family: Arial, sans-serif; text-align: center; padding-top: 100px; } h1 { color: #333; } h2 { color: #333; } links { margin-top: 20px; } links a { display: block; margin-bottom: 10px; color: #007bff; text-decoration: none; } Bo co Thc tp sở Phm Quang Tiệp - B20DCCN601 L thuyết Gii thut ton BFS Gii thut ton IDS II Code web l thuyt 23 Thut ton body { font-family: Arial, sans-serif; margin: 0; padding: 0; } container { display: flex; flex-direction: column; align-items: center; justify-content: center; height: 100vh; } label { font-size: 18px; margin-bottom: 10px; } input[type="text"] { padding: 8px; font-size: 16px; border: 1px solid #ccc; border-radius: 4px; width: 200px; max-width: 100%; margin-bottom: 10px; } button { padding: 10px 20px; font-size: 16px; background-color: #4CAF50; color: #fff; border: none; border-radius: 4px; cursor: pointer; } 24 button:hover { background-color: #45a049; } Nhp tên thut ton (BFS IDS): Submit function redirect() { var input = document.getElementById('input-text').value.toLowerCase(); if (input === 'bfs') { window.location.href = 'DNBFS.html'; } else if (input === 'ids') { window.location.href = 'DNIDS.html'; } else { alert('Vui lòng nhp "BFS" "IDS"'); } } III Code web l thuyt BFS Đnh nghĩa BFS body { font-family: Arial, sans-serif; margin: 0; padding: 0; } container { margin: 20px; } 25 h1 { font-size: 36px; margin-bottom: 20px; color: #333; text-align: center; } p { font-size: 20px; line-height: 1.5; margin-bottom: 20px; color: #555; } img { max-width: 100%; margin-bottom: 20px; display: block; margin-left: auto; margin-right: auto; } Đnh nghĩa BFS (Breadth-First Search)- Thut ton tm kiếm theo chiu rng (thường gọi l BFS - Breadth-First Search) l mt thut ton duyệt bt đầu t gc, sau đ lần lưt xét qua cc node mt theo ưu tiên v đ sâu t nh đến ln - Ban đầu, đnh gc đưc đưa vo hng đi (queue) Sau đ, thut ton ly đnh gc khi hng đi, khm ph cc đnh k n v đưa cc đnh k ny vo hng đi Qu trnh ny tiếp tục hng đi trng
Qu trnh duyệt BFS đưc minh ho sau:
26 Trên đ th, BFS bt đầu t đnh gc (đnh m ta bt đầu duyệt) v duyệt qua tt c cc đnh k n Sau đ, BFS tiếp tục duyệt qua cc đnh k cc đnh đ duyệt, duyệt hết tt c cc đnh c thể
IV Code web l thuyt IDS Đnh nghĩa ISS body { font-family: Arial, sans-serif; margin: 0; padding: 0; } container { margin: 20px; } h1 { font-size: 36px; margin-bottom: 20px; color: #333; text-align: center; } p { font-size: 20px; line-height: 1.5; margin-bottom: 20px; color: #555; } img { max-width: 100%; margin-bottom: 20px; 27 display: block; margin-left: auto; margin-right: auto; } Đnh nghĩa IDS- Thut ton IDS mở rng nt xa gc nht (sâu nht) ging DFS, không mở rng qu mt gii hn no đ - Gii hn đ sâu đưc tăng dần tm đưc lời gii
Quá trình duyệt IDS đưc minh ho sau:
Trên hnh, IDS bt đầu t đnh gc (đnh m ta bt đầu duyệt) v duyệt theo chiu sâu vi gii hn tăng dần t tm đưc đch
V Code web thut ton BFS Thut ton BFS body { font-family: Arial, sans-serif; margin: 20px; } h1 { 28 text-align: center; } form { text-align: center; } label { font-size: 18px; } input[type="text"] { width: 300px; padding: 8px; font-size: 16px; } input[type="submit"] { padding: 8px 16px; font-size: 16px; cursor: pointer; background-color: #4CAF50; color: #fff; border: none; border-radius: 4px; } input[type="submit"]:hover { background-color: #45a049; } #result { margin-top: 20px; text-align: center; font-size: 18px; } Thut ton BFS Nhp cc cnh (VD: "A-B,C-D,E-F"): Đnh bt đầu: Đnh kết thc: 29 document.getElementById('bfsForm').addEventListener('submit', function(event) { event.preventDefault(); var edgesInput = document.getElementById('edges').value; var startInput = document.getElementById('start').value; var endInput = document.getElementById('end').value; // Chuyển đổi cnh thnh mng cc cnh var edges = edgesInput.split(','); // Thc thut ton BFS v ly đường var path = bfs(edges, startInput, endInput); // Hiển th đường trang var resultElement = document.getElementById('result'); if (path.length > 0) { resultElement.textContent = 'Đường đi: ' + path.join(' -> '); } else { resultElement.textContent = 'Không tm thy đường đi.'; } }); function bfs(edges, start, end) { // Xây dng danh sch k t cc cnh var graph = buildGraph(edges); // To hng đi cho BFS var queue = []; queue.push([start]); // Theo di cc đnh đ thăm var visited = new Set(); visited.add(start); while (queue.length > 0) { var path = queue.shift(); var node = path[path.length - 1]; if (node === end) { return path; } // Ly cc đnh k đnh ti 30 var neighbors = graph[node]; for (var i = 0; i < neighbors.length; i++) { var neighbor = neighbors[i]; if (!visited.has(neighbor)) { // Đnh du đnh k l đ thăm visited.add(neighbor); // To mt đường mi v đưa vo hng đi var newPath = path.slice(); newPath.push(neighbor); queue.push(newPath); } } } // Không tm thy đường return []; } function buildGraph(edges) { var graph = {}; for (var i = 0; i < edges.length; i++) { var edge = edges[i].trim(); var nodes = edge.split('-'); var node1 = nodes[0]; var node2 = nodes[1]; if (!graph[node1]) graph[node1] = } if (!graph[node2]) graph[node2] = } { []; { []; // Thêm cnh vo danh sch k graph[node1].push(node2); graph[node2].push(node1); } return graph; } 31 VI Code web thut ton IDS Duyệt thut ton IDS body { font-family: Arial, sans-serif; margin: 20px; } container { margin: auto; /* Căn gia theo chiu ngang */ max-width: 400px; /* Điu chnh kch thưc tùy */ } label { font-size: 18px; margin-bottom: 10px; display: block; /* Hiển th nhn mt dòng */ } h1 { text-align: center; } form { text-align: center; } input[type="text"], input[type="number"] { padding: 8px; font-size: 16px; border: 1px solid #ccc; border-radius: 4px; width: 100%; margin-bottom: 10px; box-sizing: border-box; /* Đm bo kch thưc input bao gm c đường vin */ } 32 button { padding: 10px 20px; font-size: 16px; background-color: #4CAF50; color: #fff; border: none; border-radius: 4px; cursor: pointer; width: 100%; } button:hover { background-color: #45a049; } #result { margin-top: 20px; font-size: 18px; text-align: center; } Thut ton IDS Nhp cc cnh (VD: "A-B,C-D,E-F"): Đnh bt đầu: Đnh kết thc: Gii hn đ sâu: Duyệt IDS 33 document.getElementById('idsForm').addEventListener('submit', function(event) { event.preventDefault(); runIDS(); }); function runIDS() { var edgesInput = document.getElementById('edges').value; var startInput = document.getElementById('start').value; var goalInput = document.getElementById('goal').value; var depthInput = parseInt(document.getElementById('depth').value); // Chuyển đổi cnh thnh mng var edges = edgesInput.split(','); // To đ th t cc cnh var graph = {}; edges.forEach(function(edge) { var vertices = edge.split('-'); var vertex1 = vertices[0].trim(); var vertex2 = vertices[1].trim(); if (!graph[vertex1]) { graph[vertex1] = []; } if (!graph[vertex2]) { graph[vertex2] = []; } graph[vertex1].push(vertex2); graph[vertex2].push(vertex1); }); // Duyệt IDS var result = iterativeDeepeningSearch(graph, startInput, goalInput, depthInput); // Hiển th kết qu var resultElement = document.getElementById('result'); if (result) { resultElement.textContent = 'Đường đi: ' + result.join(' -> '); } else { resultElement.textContent = 'Tm không thy đường t đnh bt đầu đến đnh kết thc vi gii hn đ sâu đ cho.'; } 34 } // Thut ton IDS function iterativeDeepeningSearch(graph, start, goal, maxDepth) { for (var depth = 0; depth