intTypePromotion=3

Bài giảng Tính toán song song và phân toán - Chương 7: Mô hình thuật giải phân chia

Chia sẻ: Lavie Lavie | Ngày: | Loại File: PDF | Số trang:10

0
23
lượt xem
2
download

Bài giảng Tính toán song song và phân toán - Chương 7: Mô hình thuật giải phân chia

Mô tả tài liệu
  Download Vui lòng tải xuống để xem tài liệu đầy đủ

Bài giảng Tính toán song song và phân toán - Chương 7: Mô hình thuật giải phân chia trình bày về mô hình cây nhị phân (binary tree paradigm), chia để trị (devide and conquer). Với các bạn chuyên ngành Công nghệ thông tin thì đây là tài liệu hữu ích.

Chủ đề:
Lưu

Nội dung Text: Bài giảng Tính toán song song và phân toán - Chương 7: Mô hình thuật giải phân chia

11/16/12 <br />  <br /> <br /> 7. <br />  Mô <br />  hình <br />  thuật <br />  giải <br />  phân <br />  chia <br />  <br /> <br /> Tính <br />  toán <br />  song <br />  song <br />  và <br />  phân <br />  tán <br />  <br /> PGS.TS. <br />  Trần <br />  Văn <br />  Lăng <br />  <br /> <br /> 1.  Mô <br />  hình <br />  cây <br />  nhị <br />  phân <br />  (Binary <br />  Tree <br />  Paradigm) <br />  <br /> 2.  Chia <br />  để <br />  trị <br />  (Devide <br />  and <br />  Conquer) <br />  <br /> <br /> tvlang@vast-­‐hcm.ac.vn <br />  <br /> lang@lhu.edu.vn <br />  <br /> <br /> 1 <br />  <br /> <br /> 2 <br />  <br /> <br /> 7.1 <br />  Binary <br />  Tree <br />  Paradigm <br />  <br /> •  Xét <br />  cây <br />  nhị <br />  phân <br />  đầy <br />  đủ <br />  với <br />  n <br />  lá <br />  có <br />  độ <br />  cao <br />  là <br />  log2n <br />  <br /> (hoặc <br />  ký <br />  hiệu <br />  logn) <br />  <br /> •  Dữ <br />  liệu <br />  đặt <br />  ở <br />  n <br />  nút <br />  lá. <br />  <br /> •  Quá <br />  trình <br />  đi <br />  từ <br />  ngọn <br />  đến <br />  gốc <br />  mất <br />  logn <br />  thời <br />  gian. <br />  <br /> <br /> Khảo <br />  sát <br />  việc <br />  jnh <br />  tổng <br />  <br /> • <br /> • <br /> • <br /> • <br /> <br />  <br /> <br /> Thuật <br />  giải <br />  tuần <br />  tự <br />  mất <br />  O(n) <br />  <br /> Xét <br />  với <br />  n <br />  = <br />  2k <br />  để <br />  có <br />  được <br />  cây <br />  nhị <br />  phân <br />  đầy <br />  đủ <br />  <br /> Tứ <br />  đây <br />  chia <br />  dữ <br />  liệu <br />  thành <br />  2 <br />  nhóm <br />  <br /> Số <br />  process <br />  cần <br />  thiết <br />  là <br />  n/2 <br />  <br /> <br /> 1 <br />  <br /> <br /> 11/16/12 <br />  <br /> <br /> Minh <br />  họa <br />  <br /> A1 <br />  <br /> <br />  <br /> <br /> •  Với <br />  n= <br />  8 <br />  = <br />  23,mỗi <br />  nhóm <br />  có <br />  4 <br />  phần <br />  tử <br />  <br /> –  Nhóm <br />  1: <br />  A(1), <br />  A(3), <br />  A(5), <br />  A(7) <br />  <br /> –  Nhóm <br />  2: <br />  A(2), <br />  A(4), <br />  A(6), <br />  A(8) <br />  <br /> <br /> A1 <br />  <br /> <br /> •  Cần <br />  4 <br />  task <br />  <br /> •  Với <br />  dãy <br />  gồm <br />  8 <br />  phần <br />  tử, <br />  mô <br />  hình <br />  như <br />  <br /> hình <br />  vẽ <br />  bên <br />  dưới <br />  <br /> <br /> A1 <br />  <br /> <br /> A1 <br />  <br /> <br /> •  Bốn <br />  process <br />  đồng <br />  thời <br />  jnh <br />  các <br />  giá <br />  trị <br />  tổng <br />  của <br />  nó <br />  <br /> theo <br />  yêu <br />  cầu <br />  <br /> •  Rồi <br />  lưu <br />  vào <br />  các <br />  biến <br />  tương <br />  ứng <br />  <br /> –  A(1) <br />  

CÓ THỂ BẠN MUỐN DOWNLOAD

Đồng bộ tài khoản