Thứ Bảy, 17 tháng 10, 2015

                                             BÀI TẬP MÔN CƠ SỞ DỮ LIỆU

Quản lý khách hàng

Người thực hiện : Lê Thái Hòa                 MSV  :1400133
                               Nguyễn Mạnh Cường  MSV :1400088
                               Nhữ Công Vụ               MSV :1400132

Phần 1 : Thực trạng bán hàng hiện nay

          Thông qua quá trình tìm hiểu, khảo sát trực tiếp tại nhiều các nơi bán hàng hiện nay em thấy các nơi bán hàng cần quản lý về việc bán các mặt hàng, ví dụ như một công ty bán điện thoại như sau:
      - Khi bán hàng cử hàng sẽ lưu lại thông tin của khách hàng : mã khách hàng. tên khách hàng, địa chỉ số điện thoại
      - Mỗi lần bán hàng : cửa hàng sẽ tạo ra số hóa đơn để lưu trữ thông tin. Các đơn bán hàng bao gồm: số hóa đơn, tên mặt hàng bán, ngày bán, số lượng bán đơn giá, số tiền bán hàng
     - Mỗi hóa đơn sẽ do một nhân viên phụ trách việc tạo lập và lưu trữ tại thời điểm bán hàng. Thông tin các nhân viên như : mã nhân viên(mỗi nhân viên có một mã riêng), tên nhân viên, địa chỉ, giới tính, số điện thoại cũng được công ty lưu trữ để quản lý 

 Phần 2 : Xác định thuộc thể

     - NV(ma NV, ho ten, dia chi, ngay sinh gioi tinh, SDT)

     - HDBAN(ma HDBAN, ten mat hang, ngay ban, so luong, don gia, tong tien)
     - K_HANG(ma K_HANG, ho ten, dia chi, SDT K_HANG)

Phần 3 : Mối quan hệ giữa các thuộc thể



  mô hình liên kết


Phần 4 : Xác định thuộc thể

           - NV(ma NV, dia chi, ngay sinh, gioi tinh, SDT)
           -HDBAN(ma HDBAN, ten mat hang, ngay ban, so luong, don gia, tong tien)
           -K_HANG(ma K_HANG, ho ten, dia chi, SDT K_HANG)

Phần 5 : Câu lệnh truy vấn


Tạo bảng người quản lý:
CREATE TABLE IF NOT EXISTS `mydb`.`MANAGER` (
  `MA_ITEM` INT NOT NULL,
  `MA_NAME` VARCHAR(45) CHARACTER SET 'utf8' COLLATE 'utf8_unicode_ci' NOT NULL,  `MA_SALARY` INT NOT NULL,
  `MA_ADDRESS` VARCHAR(45) CHARACTER SET 'utf8' COLLATE 'utf8_unicode_ci' NOT NULL,
  PRIMARY KEY (`MA_ITEM`))
ENGINE = InnoDB;
Tạo bảng loại hàng:
-- -----------------------------------------------------
-- Table `mydb`.`KIND_OF_BOOK`CREATE TABLE IF NOT EXISTS `mydb`.`KIND_OF_BOOK` (
  `KB_ITEM` INT NOT NULL,
  `KB_NAME` VARCHAR(45) CHARACTER SET 'utf8' COLLATE 'utf8_unicode_ci' NOT NULL,
  PRIMARY KEY (`KB_ITEM`))
ENGINE = InnoDB
-- -----------------------------------------------------
-- Table `mydb`.`BOOKSHELF`
-- -----------------------------------------------------
CREATE TABLE IF NOT EXISTS `mydb`.`BOOKSHELF` (
  `BS_ITEM` INT NOT NULL,  `BS_NAME` VARCHAR(45) CHARACTER SET 'utf8' COLLATE 'utf8_unicode_ci' NOT NULL,
  `BS_ADDRESS` VARCHAR(45) CHARACTER SET 'utf8' COLLATE 'utf8_unicode_ci' NOT NULL,
  `MANAGER_MA_ITEM` INT NOT NULL,
  `KIND_OF_BOOK_KB_ITEM` INT NOT NULL,
  PRIMARY KEY (`BS_ITEM`),INDEX `fk_BOOKSHELF_MANAGER1_idx` (`MANAGER_MA_ITEM` ASC),
  INDEX `fk_BOOKSHELF_KIND_OF_BOOK1_idx` (`KIND_OF_BOOK_KB_ITEM` ASC),
  CONSTRAINT `fk_BOOKSHELF_MANAGER1`
    FOREIGN KEY (`MANAGER_MA_ITEM`)
    REFERENCES `mydb`.`MANAGER` (`MA_ITEM`)
    ON DELETE CASCADE    ON UPDATE CASCADE,
  CONSTRAINT `fk_BOOKSHELF_KIND_OF_BOOK1`
    FOREIGN KEY (`KIND_OF_BOOK_KB_ITEM`)
    REFERENCES `mydb`.`KIND_OF_BOOK` (`KB_ITEM`)
    ON DELETE CASCADE
    ON UPDATE CASCADE)ENGINE = InnoDB;
Tạo bảng nhân viên
-- -----------------------------------------------------
-- Table `mydb`.`EMPLOYEE`
-- -----------------------------------------------------
CREATE TABLE IF NOT EXISTS `mydb`.`EMPLOYEE` (
  `EMP_ITEM` INT NOT NULL,  `EMP_NAME` VARCHAR(45) CHARACTER SET 'utf8' COLLATE 'utf8_unicode_ci' NOT NULL,
  `EMP_SALARY` INT NOT NULL,
  `EMP_ADDRESS` VARCHAR(45) CHARACTER SET 'utf8' COLLATE 'utf8_unicode_ci' NOT NULL,
  `BOOKSHELF_BS_ITEM` INT NOT NULL,
  `MANAGER_MA_ITEM` INT NOT NULL,
  PRIMARY KEY (`EMP_ITEM`),  INDEX `fk_EMPLOYEE_BOOKSHELF_idx` (`BOOKSHELF_BS_ITEM` ASC),
  INDEX `fk_EMPLOYEE_MANAGER1_idx` (`MANAGER_MA_ITEM` ASC),
  CONSTRAINT `fk_EMPLOYEE_BOOKSHELF`
    FOREIGN KEY (`BOOKSHELF_BS_ITEM`)
    REFERENCES `mydb`.`BOOKSHELF` (`BS_ITEM`)    ON DELETE CASCADE
    ON UPDATE CASCADE,
  CONSTRAINT `fk_EMPLOYEE_MANAGER1`
    FOREIGN KEY (`MANAGER_MA_ITEM`)
    REFERENCES `mydb`.`MANAGER` (`MA_ITEM`)
    ON DELETE NO ACTION
    ON UPDATE NO ACTION)
ENGINE = InnoDB;Tạo bảng khách hàng:
-- -----------------------------------------------------
-- Table `mydb`.`CUSTOMER`
-- -----------------------------------------------------
CREATE TABLE IF NOT EXISTS `mydb`.`CUSTOMER` (
  `C_ITEM` INT NOT NULL,  `C_NAME` VARCHAR(45) CHARACTER SET 'utf8' COLLATE 'utf8_unicode_ci' NOT NULL,
  `C_ADDRESS` VARCHAR(45) CHARACTER SET 'utf8' COLLATE 'utf8_unicode_ci' NOT NULL,
  PRIMARY KEY (`C_ITEM`))
ENGINE = InnoDB;

Tạo bảng hóa đơn nhập kho
-- -----------------------------------------------------
-- Table `mydb`.`INVOICES_IN`
-- -----------------------------------------------------
CREATE TABLE IF NOT EXISTS `mydb`.`INVOICES_IN` (
  `IN_ITEM` INT NOT NULL,
  `IN_DATE` DATETIME NOT NULL,
  `EMPLOYEE_EMP_ITEM` INT NOT NULL,
  `PUBLISHER_PUB_ITEM` INT NOT NULL,
  PRIMARY KEY (`IN_ITEM`),
INDEX `fk_INVOICES_IN_EMPLOYEE1_idx` (`EMPLOYEE_EMP_ITEM` ASC),
  INDEX `fk_INVOICES_IN_PUBLISHER1_idx` (`PUBLISHER_PUB_ITEM` ASC),
  CONSTRAINT `fk_INVOICES_IN_EMPLOYEE1`
    FOREIGN KEY (`EMPLOYEE_EMP_ITEM`)
    REFERENCES `mydb`.`EMPLOYEE` (`EMP_ITEM`)
    ON DELETE CASCADE
    ON UPDATE CASCADE,
  CONSTRAINT `fk_INVOICES_IN_PUBLISHER1`
    FOREIGN KEY (`PUBLISHER_PUB_ITEM`)
    REFERENCES `mydb`.`PUBLISHER` (`PUB_ITEM`)
    ON DELETE CASCADE
    ON UPDATE CASCADE)
ENGINE = InnoDB;
Tạo bảng hóa đơn xuất cho khách hàng
-- -----------------------------------------------------
-- Table `mydb`.`INVOICES_OUT`
-- -----------------------------------------------------
CREATE TABLE IF NOT EXISTS `mydb`.`INVOICES_OUT` (
  `OUT_ITEM` INT NOT NULL,
  `OUT_DATE` DATETIME NOT NULL,
  `EMPLOYEE_EMP_ITEM` INT NOT NULL,
  `CUSTOMER_C_ITEM` INT NOT NULL,
  PRIMARY KEY (`OUT_ITEM`),
  INDEX `fk_INVOICES_OUT_EMPLOYEE1_idx` (`EMPLOYEE_EMP_ITEM` ASC),
  INDEX `fk_INVOICES_OUT_CUSTOMER1_idx` (`CUSTOMER_C_ITEM` ASC),
  CONSTRAINT `fk_INVOICES_OUT_EMPLOYEE1`
    FOREIGN KEY (`EMPLOYEE_EMP_ITEM`)
    REFERENCES `mydb`.`EMPLOYEE` (`EMP_ITEM`)
    ON DELETE CASCADE
    ON UPDATE CASCADE,
  CONSTRAINT `fk_INVOICES_OUT_CUSTOMER1`
    FOREIGN KEY (`CUSTOMER_C_ITEM`)
    REFERENCES `mydb`.`CUSTOMER` (`C_ITEM`)
    ON DELETE CASCADE
    ON UPDATE CASCADE)
ENGINE = InnoDB;
Tạo bảng hàng bán:
-- -----------------------------------------------------
-- Table `mydb`.`BOOK`
-- -----------------------------------------------------
CREATE TABLE IF NOT EXISTS `mydb`.`BOOK` (
  `B_ITEM` INT NOT NULL,
  `B_NAME` VARCHAR(45) NOT NULL,
  `B_AUTHORS` VARCHAR(45) NOT NULL,
  `B_COST` INT NOT NULL,
  `B_DATE` DATETIME NOT NULL,
  `B_NUMBER` INT NOT NULL,
  `KIND_OF_BOOK_KB_ITEM` INT NOT NULL,
  `B_NUMBER` INT NOT NULL,
  PRIMARY KEY (`B_ITEM`),
  INDEX `fk_BOOK_KIND_OF_BOOK1_idx` (`KIND_OF_BOOK_KB_ITEM` ASC),
  CONSTRAINT `fk_BOOK_KIND_OF_BOOK1`
    FOREIGN KEY (`KIND_OF_BOOK_KB_ITEM`)
    REFERENCES `mydb`.`KIND_OF_BOOK` (`KB_ITEM`)
    ON DELETE NO ACTION
    ON UPDATE NO ACTION)
ENGINE = InnoDB; 
-- -----------------------------------------------------
CREATE TABLE IF NOT EXISTS `mydb`.`INVOICES_IN_INCLUDE` (
  `INVOICES_IN_IN_ITEM` INT NOT NULL,
  `BOOK_B_ITEM` INT NOT NULL,
  `IN_NUMBER` INT NOT NULL,
  INDEX `fk_INVOICES_IN_has_BOOK_BOOK2_idx` (`BOOK_B_ITEM` ASC),
  INDEX `fk_INVOICES_IN_has_BOOK_INVOICES_IN2_idx` (`INVOICES_IN_IN_ITEM` ASC),
  PRIMARY KEY (`BOOK_B_ITEM`, `INVOICES_IN_IN_ITEM`),
  CONSTRAINT `fk_INVOICES_IN_has_BOOK_INVOICES_IN2`
    FOREIGN KEY (`INVOICES_IN_IN_ITEM`)
    REFERENCES `mydb`.`INVOICES_IN` (`IN_ITEM`)
    ON DELETE NO ACTION
    ON UPDATE NO ACTION,
  CONSTRAINT `fk_INVOICES_IN_has_BOOK_BOOK2`
    FOREIGN KEY (`BOOK_B_ITEM`)
    REFERENCES `mydb`.`BOOK` (`B_ITEM`)
    ON DELETE NO ACTION
    ON UPDATE NO ACTION)
ENGINE = InnoDB;
Bảng thể hiện mối quan hệ nhiều nhiều giữa hóa đơn nhập (một hóa đơn có thể có nhiều hàng và 1 hàng có thể có trong nhiều hóa đơn xuất cho khách hàng)
-- -----------------------------------------------------
-- Table `mydb`.`INVOICES_OUT_INCLUDE`
-- -----------------------------------------------------
CREATE TABLE IF NOT EXISTS `mydb`.`INVOICES_OUT_INCLUDE` (
  `INVOICES_OUT_OUT_ITEM` INT NOT NULL,
  `BOOK_B_ITEM` INT NOT NULL,
  `OUT_NUMBER` INT NOT NULL,
  INDEX `fk_INVOICES_OUT_has_BOOK_BOOK1_idx` (`BOOK_B_ITEM` ASC),
  INDEX `fk_INVOICES_OUT_has_BOOK_INVOICES_OUT1_idx` (`INVOICES_OUT_OUT_ITEM` ASC),
  PRIMARY KEY (`INVOICES_OUT_OUT_ITEM`, `BOOK_B_ITEM`),
  CONSTRAINT `fk_INVOICES_OUT_has_BOOK_INVOICES_OUT1`
    FOREIGN KEY (`INVOICES_OUT_OUT_ITEM`)
    REFERENCES `mydb`.`INVOICES_OUT` (`OUT_ITEM`)
    ON DELETE NO ACTION
    ON UPDATE NO ACTION,
  CONSTRAINT `fk_INVOICES_OUT_has_BOOK_BOOK1`
    FOREIGN KEY (`BOOK_B_ITEM`)
    REFERENCES `mydb`.`BOOK` (`B_ITEM`)
    ON DELETE NO ACTION
    ON UPDATE NO ACTION)
ENGINE = InnoDB;


Thứ Năm, 1 tháng 10, 2015

Bài Tập Môn Toán Rời Rạc
Đề Bài
Trình bày tóm tắt và cài đặt bài toán “Người du lịch”
Người thực hiện:   Nguyễn Mạnh Cường  MSV:1400088
                               Lê Thái Hòa                  MSV:1400133
                               Nhữ Công Vụ             MSV:1400132

Giảng Viên: Trần Xuân Thanh
Mục lục
Chương I : Bài toán người du lịch và các thuật giải
1      Giới thiệu lịch sử của bài toán người du lịch
2      Mô tả chi tiết bài toán
3     Thuật giải chính xác
4      Thuật giải gần đúng (Heuristic)
     4.1 Thuật giải tham lam (thuật giải láng giềng gần nhất)
     4.2  Thuật giải nhánh cận

1/Giới thiệu về lịch sử của bài toán người du lịch
    Bài toán người du lịch là một vẫn đề kết nối tối ưu trong nghiên cứu khoa học máy tính. Cho một danh sách các thành phố và các cặp khoảng cách giữa 2 thành phố trong đó, nhiệm vụ là phỉa tìm một chu trình ngắn nhất để thăm mỗi thành phố một lần duy nhất.

   Trong hình trên, tour để người du lịch có thể thăm hết tất cả các thành phố với chi phí ngắn nhất được thể hiện bằng các cạnh màu đỏ.
   Vấn đề này được nêu ra lần đầu tiên như là một vấn đề toán học vào năm 1930 và là vấn đề được tập trung nghiên cứu nhiều nhất trong lĩnh vực tối ưu. Nó được sử dụng thử nghiệm, đánh giá các thuật toán tối ưu. Tuy vấn đề có tính phức tạp cao, nhưng có rất nhiều phương pháp chính xác và gần đúng đã được biết đến, do đó có thể giải được vài trường hợp có đến 10 ngàn thành phố.
   Trong những năm 1950 và 1960, bài toán trở nên phổ biến trong giới khoa học châu Âu và ở Mỹ. Các công trình đáng kể đầu tiên được thực hiện bởi Georgeo Dantzig, Delbert ray Fulkerson và Selmer M.Johnson người đã đề xuất bài toán như một chương trình tuyến tính và phát triển phương pháp nhánh cận cho bài toán. Với các phương pháp mới họ đã giải một trường hợp với 49 thành phố một các tối ưu bằng cách xây một chu trình và chứng minh rằng không có chu trình nào ngắn hơn. Trong nhiều thập kỉ sau đó, bài toán được nghiên cứu trong rất nhiều ngành như toán học, khoa học máy tính, hóa học, vật lý.

2/Mô tả chi tiết bài toán
     Bài toán người du lịch có thể biểu diễn thành một đồ thị, trong đó các thành phố là các đỉnh, các con đường đi lại giữa các thành phố là các cạnh, đồng thời khoảng cách giữa các thành phố là trọng số tương ứng của cạnh nối chúng. Tất nhiên, đồ thị sau khi xây dựng xong là đồ thị đủ, giữa hai thành phố không có đường đi trực tiếp mà phải thông qua một thành phố khác thì ta gán trọng số của cạnh đó số lớn nhất có thể. Khi đóm bài toán người du lịch trở thành bài tìm một chu trình Hamilton ngắn nhất, và lộ trình của người du lịc chính là chu trình hamilton ngắn nhất.

      Nếu như khoảng cách giữa hai thành phố bất ki là như nhau cho cả hai hướng thi dùng đồ thị vô hướng, ngược lại là sử dụng đồ thị có hướng. Trong ví dụ trên, ta giả định đường đi từ 2 hướng là như nhau.
      Trường hợp khoảng cách giữa các thành phố trong đồ thị là khoảng cách metric ( tức là thỏa bất đẳng thức tam giác Cij <= Cik + Ckj), thì khoảng cách trực tiếp từ thành phố A đến thành phố B là khoảng cách ngắn nhất và không bao giờ lớn hơn khoảng cách mà có thông qua thành phố C. Thực tế, khi các thành phố được biểu diễn bởi các điểm trên mặt phẳng, rất nhiều các khoảng cách gần như là khoảng cách metric.
      Trong nhiều trường hợp, các khoảng cách không thỏa bất đẳng thức tam giác hoặc do tiêu chí đánh giá khoảng cách không thuộc không gian metric chẳng hạn như khoảng cách theo tiêu chí thời gian di chuyển, rõ ràng máy bay di chuyển nhanh hơn nhiều so với ô tô mặc dù khoảnh cách di chuyển có thể lớn hơn.

3/Thuật toán chính xác
     Trong các thuật toán chính xác cho bài toán người du lịch, đầu tiên phải kể đến thuật toán vét cạn. Thuật toán này tìm tất cả cách chu trình Hamilton được thực hiện theo phương pháp duyệt chiều sâu và kết hợp quay lui. Do quá trình duyệt có thể rất sâu nên ta không sử dụng đệ quy mà dùng stack để khử đệ quy. Sử dụng một biến min để lưu lại tổng trọng số của chu trình Hamilton nhỏ nhất. Ban đầu  min=+∞ hoặc min= m* trọng số của cạnh lớn nhất.
     Chu trình Hamilton là chu trình đi qua hết tất cả các đỉnh và sau đó quay về đỉnh xuất phát, do đó, ta dùng một danh sách ChuaXet[] để lưu lại các đỉnh chưa xét, một biến Sum để lưu lại trọng số của chu trình hiện thời, do chu trình hamilton không quan trọng đỉnh xuất ohats, ta chọn đỉnh xuất phát là đỉnh có chỉ số nhỏ nhất là 1.
Quá trình duyệt như sau:
     -Ban đầu đưa đỉnh 1 và 0 vào stack, Sum = 0.
     -Lặp lại quá trình sau: Lấy (Top) đỉnh từ stack ra là đỉnh i và trọng số ts, gán ChuaDuyet[i] là false và Sum+=ts, nạp 0 0 vào stack sau đó nạp các đỉnh kề j và trọng số tương ứng với đỉnh đang xét mà ChuaDuyet[j]=true, nếu i không có đỉnh kề thỏa yêu cầu, tức là đã duyệt hết tất cả các đỉnh ( do đồ thị đang xé là đồ thị đủ). ta cộng trọng số của cạnh i>1 vào Sum và gán min bằng Min(Sum,min). Sum- = cạnh i>1. Lặp lại quá trình sau: Lấy đỉnh từ stack ra, nếu đỉnh này không còn đỉnh kề thỏa yêu cầu thì Pop đỉnh và trọng số này ra, nếu có đỉnh thỏa thì vòng lặp và duyệt tiếp từ đỉnh này, trường ợp lấy đỉnh từ stack ra là 0 thì Pop 2 lần để lấy 2 đỉnh liên tục trong stack ra sau đó tiếp tục vòng lặp.

4/Các thuật giải gần đúng (Heuristic)

4.1/ Thuật giải tham lam ( thuật giải láng giếng gần nhất)
   Thuật giải vét cạn ở trên cho ta một đáp án tối ưu, tuy nhiên độ phức tạp của nó là quá cao(n-1)!thuộc nhóm O(n!). Do đó, trong thực tiễn người ta chấp nhận các thuật giải cho kết quả tốt ( nhưng không phải lúc nào củng tốt) bởi sự đơn giản, nhanh chóng và cài đặt dễ dàng. Một trong các thuật giải đó là thuật giải tham lam hay còn gọi là thuật toán láng giềng gần nhất. Trong thuật toán này, tạo mỗi bước, ta chọn con đường (cạnh) nối với các thành phố ( đỉnh) gần nhất với hy vọng rằng n con đường ngắn nhất sẽ cho ra đường đi ngắn nhất.
Ví dụ sau đây minh họa cho thuật toán giải tham lam với n=5

   


4.2/ Thuật toán nhánh cận
      Thuật toán nhánh cận là phương pháp chủ yếu để giải các bài toán tối ưu tổ hợp. Tư tưởng cơ bản của thuật toán là trong quá trình tìm kiếm lời giải, ta sẽ phan hoạch tập hợp các phương án thành hai hay nhiều nhánh con như cây tìm kiếm, sau đó đánh giá từng nhánh để quyết định xem nên tiếp tục ở nhanh nào và loại bỏ nhánh nào mà các phương án con của nó không thể là phương án tối ưu.
      trong thuật toán trình bày dưới đây, chúng ta sẽ tìm kiếm lời giải dựa trên ma trận trọng số C[][]. Đối với bài toán người du lịch, khi tiến hành tìm kiếm lời giải chúng ta sẽ ohaan tập các hành trình thành 2 tập con: Tập gồm những hành trình có chứa cạnh (i,j) và tập còn lại gồm những hành trình không chứa cạnh (i,j).
Trước tiên, để cho việc phân nhánh được dễ dàng, ta cần phải rút gọn ma trận trọng số, đó tổng chi phí của hành trình sẽ chứa đúng một phần tử của mỗi dòng và mỗi cột nên khi cộng hay trừ cả dòng hay cột cho một số α thì tổng trọng số của tất cả các hành trình sẽ giảm đi α.Do đó, ta có thể rút gọn ma trận trọng số sao cho trên mỗi dòng và cột đều có ít nhất một số 0, đồng thời, tổng của các số α sẽ là cận dưới của tất cả các hành trình.
        Đối với tập phân hoạch chứa cạnh i,j. Do i,j thuộc hành trình này nên ta phái xóa dòng i cột j do khong thể có cạnh khác từ i đi ra và từ j đi vào ngoài cạnh i,j. ngoài ra cũng đặt C[j][i] bằng ∞ do đã chọn cạnh C[i][j].
Đối với tập phân hoạch không chứa cạnh i,j là lớn nhất, để tìm cạnh đó ta chọn số 0 trong ma trận để thay nó bằng ∞ sẽ cho ta tổng hằng số rút gọn theo cạnh và dòng lớn nhất.

Ví dụ: giải bài toán người du lịch với ma trận chi phí như sau: