text:
Cam kết số 316/WTO/CK của Cộng hoà Xã hội chủ nghĩa Việt Nam
Chia sẻ: Phi Van | Ngày: | Loại File: PDF | Số trang:4
lượt xem 14
download
Cam kết số 316/WTO/CK của Cộng hoà Xã hội chủ nghĩa Việt Nam
Cam kết số 316/WTO/CK của Cộng hoà Xã hội chủ nghĩa Việt Nam về lộ trình xoá bỏ thuế nhập khẩu cho các sản phẩm ITA
Bình luận(0) Đăng nhập để gửi bình luận!
Nội dung Text: Cam kết số 316/WTO/CK của Cộng hoà Xã hội chủ nghĩa Việt Nam
- CỘNG HOÀ XÃ HỘI CHỦ NGHĨA VIỆT NAM Độc lập- Tự do – Hạnh phúc PHỤ LỤC B Đối với tất cả các sản phẩm được liệt kê trong hoặc theo Phụ lục B của Phụ lục kèm theo Tuyên bố cấp Bộ trưởng về thương mại đối với các Sản phẩm Công nghệ Thông tin (WT/MIN(96)/16), nếu chưa được nêu cụ thể trong Phụ lục này, thuế nhập khẩu đối với các sản phẩm đó dù được phân loại ởđâu trong biểu thuế, cũng như bất cứ các khoản phụ thu nhập khẩu nào (theo định nghĩa của Điều II:1(b) của Hiệp định chung về Thuế quan và Thương mại 1994), sẽ được ràng buộc và xoá bỏ, như nêu tại khoản 2(a) của Phụ lục kèm theo Tuyên bố nói trên. Mô tả hàng hoá Mã hàng èng phản ứng thạch anh và vòng kẹp được thiết kế để chèn vào lò luyện khuyếch tán hoặc 70171010, 70200020 lò ô xi hóa, để sản xuất tấm bán dẫn mỏng Thiết bị làm ngưng tụ khí hoá học để sản xuất sản phẩm bán dẫn 84198912 Bộ phận của thiết bị làm ngưng tụ khí hoá học để sản xuất sản phẩm bán dẫn 84199011 Thiết bị tẩy rửa hoặc làm sạch các tấm bán dẫn mỏng 84569100, 84569910 Máy cắt la-ze để cắt các đường tiếp xúc bằng các chùm tia la-ze trong các sản phẩm bán 84561010, 84569990 dẫn Máy cắt khối bán dẫn đơn tinh thể thành các lát cắt hoặc cưa miếng mỏng đơn tinh thể 84641011 thành các chip Bộ phận của máy cắt khối bán dẫn đơn tinh thể thành các lát cắt hoặc cưa miếng mỏng 84661020, 84662020, đơn tinh thể thành các chip 84663020, 84669110 Bộ phận của máy khắc để đánh dấu hoặc khắc vạch lên các tấm bán dẫn mỏng 84661020, 84662020, 84663020, 84669110 Bộ phận của máy cắt la-ze để cắt các đường rãnh trong chế tạo bán dẫn bằng chùm tia la- 84661020, 84662020, ze 84663020, 84669310 Bộ phận của thiết bị tẩy rửa hoặc làm sạch các tấm bán dẫn mỏng 84663020, 84669310 Thiết bị bọc nhựa để lắp ráp các chất bán dẫn 84771032, 84774021, 84775922, 84798910 Bộ phận của thiết bị bọc nhựa 84779031, 84799010 Máy tự động dùng để chuyên chở, xử lý và bảo quản các tấm bán dẫn mỏng, khung miếng 84283920, 84289010, mỏng, hộp mỏng và các vật liệu khác cho thiết bị bán dẫn. 84795010, 84798910 Máy kết tủa vật lý bằng phương pháp phun phủ trên tấm bán dẫn mỏng 84798910, 85438920 Thiết bị khắc a-xít ướt, máy hiện ảnh, tẩy rửa hoặc làm sạch các tấm bán dẫn mỏng và 84248930, 84649012, màn hình dẹt 84798910, 85433010 Thiết bị gắn khuôn, nối băng tự động, và nối dây để lắp ráp các chất bán dẫn 84798910, 85158020 Thiết bị bọc nhựa để lắp ráp các chất bán dẫn 84771032, 84774021, 84775922, 84798910 84622110, 84622911, Máy uốn, gấp và làm thẳng các đầu bán dẫn 84798930 Máy kết tủa vật lý dùng trong sản xuất bán dẫn 84798930, 85438920 Thiết bị lăn để phủ nhũ ảnh lên các tấm bán dẫn mỏng 84798910 Mô tả hàng hoá Mã hàng Bộ phận của máy kết tủa vật lý bằng phương pháp phun phủ trên tấm bán dẫn mỏng 84799010, 85439070 Bộ phận của thiết bị gắn khuôn, nối băng tự động, và nối dâyđể lắp ráp các chất bán dẫn 84799010, 85159030 Bộ phận của thiết bị lăn để phủ nhũ ảnh lên các tấm bán dẫn mỏng 84799010
- Bộ phận của thiết bị khắc a-xít ướt, máy hiện ảnh, tẩy rửa hoặc làm sạch các tấm bán dẫn 84249096, 84662030, mỏng và màn hình dẹt 84663030, 84669110, 84799010, 85439010 Bộ phận của máy tự động dùng để chuyên chở, xử lý và bảo quản các tấm bán dẫn mỏng, 84313930 khung miếng mỏng, hộp mỏng và các vật liệu khác cho thiết bị bán dẫn Bộ phận của thiết bị bọc nhựa để lắp ráp các chất bán dẫn 84779031, 84799010 Bộ phận của máy uốn, gấp và làm thẳng các đầu bán dẫn 84661020, 84662020, 84663020, 84669420, 84799030 Bộ phận của máy kết tủa vật lý dùng trong sản xuất bán dẫn 84799030, 85439070 Thiết bị làm nóng nhanh tấm bán dẫn mỏng 84198912, 85143011 Bộ phận của thiết bị làm nóng nhanh tấm bán dẫn mỏng 84199011, 85149010 Đầu dò dẹt dưới dạng miếng lát (wafer probers) 85369010, 90308210 Thiết bị khắc a-xít ướt, máy hiện ảnh, tẩy rửa hoặc làm sạch các tấm bán dẫn mỏng và 84248930, 84649012, màn hình dẹt 84798910, 85433010 Bộ phận của thiết bị khắc a-xít ướt, máy hiện ảnh, tẩy rửa hoặc làm sạch các tấm bán dẫn 84249096, 84662030, mỏng và màn hình dẹt 84663030, 84669110, 84799010, 85439010 Kính hiển vi quang học nhìn hình nổi (lập thể) có gắn thiết bị chuyên dụng để điều khiển và 90111010 di chuyển các miếng hoặc lưới bán dẫn Kính hiển vi để xem vi ảnh có gắn thiết bị chuyên dụng để điều khiển và di chuyển các 90112010 miếng hoặc lưới bán dẫn Bộ phận và phụ tùng của kính hiển vi quang học nhìn hình nổi (lập thể) có gắn thiết bị 90119010 chuyên dụng để điều khiển và di chuyển các miếng hoặc lưới bán dẫn Bộ phận và phụ tùng của kính hiển vi để xem vi ảnh có gắn thiết bị chuyên dụng để điều 90119010 khiển và di chuyển các miếng hoặc lưới bán dẫn Kính hiển vi tia electron có gắn thiết bị chuyên dụng để điều khiển và di chuyển các miếng 90121010, 90318091 hoặc lưới bán dẫn Bộ phận và phụ tùng của kính hiển vi tia electron có gắn thiết bị chuyên dụng để điều khiển 90129010, 90319014 và di chuyển các miếng hoặc lưới bán dẫn Thiết bị tạo mẫu dùng để sản xuất mặt nạ hoặc lưới caro từ chất nền phủ chất cản quang 90172020 Bộ phận và phụ tùng của thiết bị tạo mẫu dùng để sản xuất mặt nạ hoặc lưới caro từ chất 90179010 nền phủ chất cản quang Bộ phận của thiết bị tạo mẫu như thế 90179010 Máy tính: máy xử lý dữ liệu tự động có khả năng 1) lưu giữ chương trình hay các chương 84711000, 84713010, trình xử lý và ít nhất là dữ liệu trực tiếp cần thiết cho việc chạy chương trình; 2) được lập 84713020, 84713090, trình một cách tự do theo nhu cầu của người sử dụng 84714110, 84714190, 84714910, 84714990, 84715010, 84715090 Mô tả hàng hoá Mã hàng Bộ khuyếch đại được sử dụng như một bộ lặp trong điện thoại hữu tuyến theo Hiệp định 84715010, 84715090, này, và các bộ phận của nó 85175010, 85175020, 85175030, 85175040, 85175050, 85175090, 85178010, 85178020, 85178030, 85178040, 85178050, 85178060, 85178070, 85178091,
- 85178092, 85178099, 85179010, 85179020, 85179090, 85184020, 85189010 Màn hình dẹt (kể cả loại màn hình tinh thể lỏng LCD, loại công nghệ quang điện tử, plasma 84714910, 84714990, và công nghệ khác) dùng cho các sản phẩm thuộc Hiệp định này, và các bộ phận của nó 85312000, 85318020, 85319010, 85438920, 85489040, 90138020, 90139030 84711000, 84713010, 84713020, 84713090, 84714110, 84714190, 84714910, 84714990, 84716011, 84716012, 84716013, 84716019, 84716021, 84716029, Thiết bị mạng: Thiết bị mạng cục bộ (LAN) và mạng diện rộng (WAN), kể cả những sản 84716030, 84716040, phẩm được thiết kế chuyên dùng hoặc chủ yếu dùng để kết nối các máy xử lý dữ liệu tự 84716050, 84716060, động và các thiết bị mạng của nó chủ yếu dùng để chia sẻ các nguồn dữ liệu như bộ xử lý 84716090, 84717010, trung tâm, thiết bị lưu trữ dữ liệu và các bộ nhập hoặc bộ xuất, bao gồm bộ tiếp hợp, cổng 84717020, 84717030, kết nối, bộ lặp hữu tuyến, bộ chuyển đổi, bộ tập kết, cầu nối, bộ định tuyến, và tấm mạch in 84717040, 84717050, đã lắp ráp để kết hợp vật lý thành máy sử lý dữ liệu tự động và các thiết bị của nó 84717091, 84717 Màn hình: Thiết bị hiển thị của máy xử lý dữ liệu tự động có đèn điện tử tia ca tốt có điểm 84716021, 84716029, ảnh nhỏ hơn 0,4 mm, không có khả năng thu và xử lý các tín hiệu ti-vi hoặc các tín hiệu 84716040, 84716090, loại kỹ thuật tương tự hoặc tín hiệu âm thanh hay hình ảnh được số hoá mà không có sự 85404010, 85404090 trợ giúp của bộ xử lý trung tâm của máy tính như định nghĩa theo Hiệp định này. Hiệp định, do đó không bao gồm ti-vi, kể cả ti-vi có độ nét cao Bộ lưu giữ bằng đĩa quang học, dùng cho máy xử lý dữ liệu tự động (kể cả ổ đĩa CD và ổ 84714910, 84714990, đĩa DVD), có hoặc không có khả năng ghi cũng như đọc, có hoặc không có vỏ riêng của 84717040 chúng Thiết bị cảnh báo bằng nhắn tin, và các bộ phận của nó 85252010, 85252020, 85252030, 85252040, 85252050, 85252060, 85252070, 85252080, 85252091, 85252092, 85252099, 85279010, 85291010 Máy vẽ có bộ xuất hoặc bộ nhập thuộc nhóm HS 8471 hoặc máy vẽ hoặc vẽ phácthuộc 84714910, 84714990, nhóm HS 9017. 84716050, 90171010, 90172050 Mô tả hàng hoá Mã hàng Tấm mạch in đã lắp ráp dùng cho các sản phẩm thuộc Hiệp định này, kể cả loại để nối bên 84731010, 84732900, ngoài như cạc (cards) theo tiêu chuẩn của Hiệp hội quốc tế về cạc nhớ của máy tính cá 84733010, 84733090, nhân. TÊm m¹ch in nµy bao gåm mét hay nhiÒu m¹ch in thuéc nhãm 8534 g¾n kÌm víi mét 84734011, 84735011, hoÆc nhiÒu linh kiÖn tÝch cùc, cã hoÆc kh«ng cã c¸c linh kiÖn bÞ ®éng. "linh kiÖn tÝch 84735019, 84735021, cùc" lµ nh÷ng ®ièt, bãng b¸n dÉn vµ c¸c thiÕt bÞ b¸n dÉn t−¬ng tù, cã hoÆc kh«ng cã ®é 84735029, 85049020, c¶m quang thuéc nhãm 85.41, m¹ch tÝch hîp vµ vi linh kiÖn thuéc nhãm 8542 85149010, 85159030, 85175010, 85175020, 85175030, 85175040, 85175050, 85175090, 85179010, 85179020, 85179090, 85189010,
- 85189010, 85202000, 85229020, 85281 Các màn hình dẹt kiểu đèn chiếu được sử dụng cho máy xử lý dữ liệu tự động có thể hiển 84714910, 84714990, thị thông tin số do bộ xử lý trung tâm tạo ra 84716040, 84716060, 84716090, 85282110, 85283020 Các bộ lưu trữ được tạo định dạng riêng kể cả các vật mang tin dùng cho máy xử lý dữ liệu 84717050, 85231110, tự động, có hoặc không có các vật mang tin có thể thay đổi được là sản phẩm của công 85231190, 85231210, nghệ từ, quang, hay công nghệ khác, kể cả hộp Bermoulli, Syquest hoặc bộ lưu 85231220, 85231230, 85231290, 85231310, 85231320, 85231330, 85231340, 85231390, 85232010, 85232020, 85232030, 85232040, 85232090, 85239010, 85239020, 85239090, 85244000, 85249920 Bộ nâng cấp đa phương tiện sử dụng cho máy xử lý dữ liệu tự động, và các khối chức 84718070, 84733010, năng của chúng, đã đóng gói để bán lẻ, bao gồm, ít nhất có, loa và/hoặc mic-ro cũng như 84733090, 85175010, tấm mạch in đã lắp sẵn cho phép máy xử lý dữ liệu tự động (ADP) và các khối chức năng 85175020, 85175030, của chúng xử lý các tín hiệu âm thanh (cạc âm thanh) 85175040, 85175050, 85175090 Thiết bị giải mã và chọn kênh dùng trong truyền hình cáp: thiết bị dựa trên bộ vi xử lý kết 85175040, 85251040, hợp với bộ điều giả (modem) để truy cập internet, và có chức năng trao đổi thông tin tương 85252070, 85281210 tác
CÓ THỂ BẠN MUỐN DOWNLOAD
-
Thông báo Số: 191/TB-BGDĐT-ĐTVNN V/v: Thông báo về việc giao dịch điện tử đối với công tác tuyển sinh đi học nước ngoài
3 p | 195 | 34
-
Thông tư Số: 11/2010/TT-BTTTT
11 p | 196 | 26
-
Thông Tư Số: 14/2010/TT-BTTTT
13 p | 116 | 19
-
Quyết định Số: 15/2010/QĐ-UBND
7 p | 106 | 15
-
Thông tư Số: 08/2010/TT-BTTTT
5 p | 124 | 12
-
Cam kết số 314/WTO/CK của Cộng hoà Xã hội chủ nghĩa Việt Nam
8 p | 53 | 11
-
Thông tư Số: 10/2010/TT-BTTTT
9 p | 87 | 9
-
Thông Tư Số: 15/2010/TT-BTTTT
5 p | 74 | 8
-
Quyết Định Số: 12/2010/QĐ-UBND
7 p | 50 | 6
-
Quyết định Số: 09/2010/QĐ-UBND
3 p | 93 | 5
-
Luật số: 73/2014/QH13
22 p | 17 | 3
-
Quyết định số 1682/QĐ-VPCP
4 p | 43 | 3
-
Luật Công nghệ thông tin 2006
37 p | 29 | 2
-
Quyết định số 250/2005/QĐ-TTg
8 p | 57 | 2
-
Nghị quyết số: 84/2014/QH13
2 p | 22 | 1
-
Luật số: 61/2014/QH13
18 p | 8 | 0
-
Nghị quyết số: 83/2014/QH13
2 p | 23 | 0

markdown:
# Cam kết số 316/WTO/CK của Cộng hoà Xã hội chủ nghĩa Việt Nam
Chia sẻ: Phi Van | Ngày: | Loại File: PDF | Số trang:4
lượt xem 14
download
![](http://image.tlvnimg.com/document/thumbnail/2009/20091023/phithanhvan/80x100/448.jpg)
##
Cam kết số 316/WTO/CK của Cộng hoà Xã hội chủ nghĩa Việt Nam
[Vui lòng tải xuống để xem tài liệu đầy đủ](javascript:void(0);)
Download
![](http://static.tlvnimg.com/b2013az/templates/version1/default/images/down16x21.png)
Cam kết số 316/WTO/CK của Cộng hoà Xã hội chủ nghĩa Việt Nam về lộ trình xoá bỏ thuế nhập khẩu cho các sản phẩm ITA
Bình luận(0)
[Đăng nhập để gửi bình luận!](javascript:void(0);)
##
Nội dung Text: Cam kết số 316/WTO/CK của Cộng hoà Xã hội chủ nghĩa Việt Nam
- CỘNG HOÀ XÃ HỘI CHỦ NGHĨA VIỆT NAM Độc lập- Tự do – Hạnh phúc PHỤ LỤC B Đối với tất cả các sản phẩm được liệt kê trong hoặc theo Phụ lục B của Phụ lục kèm theo Tuyên bố cấp Bộ trưởng về thương mại đối với các Sản phẩm Công nghệ Thông tin (WT/MIN(96)/16), nếu chưa được nêu cụ thể trong Phụ lục này, thuế nhập khẩu đối với các sản phẩm đó dù được phân loại ởđâu trong biểu thuế, cũng như bất cứ các khoản phụ thu nhập khẩu nào (theo định nghĩa của Điều II:1(b) của Hiệp định chung về Thuế quan và Thương mại 1994), sẽ được ràng buộc và xoá bỏ, như nêu tại khoản 2(a) của Phụ lục kèm theo Tuyên bố nói trên. Mô tả hàng hoá Mã hàng èng phản ứng thạch anh và vòng kẹp được thiết kế để chèn vào lò luyện khuyếch tán hoặc 70171010, 70200020 lò ô xi hóa, để sản xuất tấm bán dẫn mỏng Thiết bị làm ngưng tụ khí hoá học để sản xuất sản phẩm bán dẫn 84198912 Bộ phận của thiết bị làm ngưng tụ khí hoá học để sản xuất sản phẩm bán dẫn 84199011 Thiết bị tẩy rửa hoặc làm sạch các tấm bán dẫn mỏng 84569100, 84569910 Máy cắt la-ze để cắt các đường tiếp xúc bằng các chùm tia la-ze trong các sản phẩm bán 84561010, 84569990 dẫn Máy cắt khối bán dẫn đơn tinh thể thành các lát cắt hoặc cưa miếng mỏng đơn tinh thể 84641011 thành các chip Bộ phận của máy cắt khối bán dẫn đơn tinh thể thành các lát cắt hoặc cưa miếng mỏng 84661020, 84662020, đơn tinh thể thành các chip 84663020, 84669110 Bộ phận của máy khắc để đánh dấu hoặc khắc vạch lên các tấm bán dẫn mỏng 84661020, 84662020, 84663020, 84669110 Bộ phận của máy cắt la-ze để cắt các đường rãnh trong chế tạo bán dẫn bằng chùm tia la- 84661020, 84662020, ze 84663020, 84669310 Bộ phận của thiết bị tẩy rửa hoặc làm sạch các tấm bán dẫn mỏng 84663020, 84669310 Thiết bị bọc nhựa để lắp ráp các chất bán dẫn 84771032, 84774021, 84775922, 84798910 Bộ phận của thiết bị bọc nhựa 84779031, 84799010 Máy tự động dùng để chuyên chở, xử lý và bảo quản các tấm bán dẫn mỏng, khung miếng 84283920, 84289010, mỏng, hộp mỏng và các vật liệu khác cho thiết bị bán dẫn. 84795010, 84798910 Máy kết tủa vật lý bằng phương pháp phun phủ trên tấm bán dẫn mỏng 84798910, 85438920 Thiết bị khắc a-xít ướt, máy hiện ảnh, tẩy rửa hoặc làm sạch các tấm bán dẫn mỏng và 84248930, 84649012, màn hình dẹt 84798910, 85433010 Thiết bị gắn khuôn, nối băng tự động, và nối dây để lắp ráp các chất bán dẫn 84798910, 85158020 Thiết bị bọc nhựa để lắp ráp các chất bán dẫn 84771032, 84774021, 84775922, 84798910 84622110, 84622911, Máy uốn, gấp và làm thẳng các đầu bán dẫn 84798930 Máy kết tủa vật lý dùng trong sản xuất bán dẫn 84798930, 85438920 Thiết bị lăn để phủ nhũ ảnh lên các tấm bán dẫn mỏng 84798910 Mô tả hàng hoá Mã hàng Bộ phận của máy kết tủa vật lý bằng phương pháp phun phủ trên tấm bán dẫn mỏng 84799010, 85439070 Bộ phận của thiết bị gắn khuôn, nối băng tự động, và nối dâyđể lắp ráp các chất bán dẫn 84799010, 85159030 Bộ phận của thiết bị lăn để phủ nhũ ảnh lên các tấm bán dẫn mỏng 84799010
- Bộ phận của thiết bị khắc a-xít ướt, máy hiện ảnh, tẩy rửa hoặc làm sạch các tấm bán dẫn 84249096, 84662030, mỏng và màn hình dẹt 84663030, 84669110, 84799010, 85439010 Bộ phận của máy tự động dùng để chuyên chở, xử lý và bảo quản các tấm bán dẫn mỏng, 84313930 khung miếng mỏng, hộp mỏng và các vật liệu khác cho thiết bị bán dẫn Bộ phận của thiết bị bọc nhựa để lắp ráp các chất bán dẫn 84779031, 84799010 Bộ phận của máy uốn, gấp và làm thẳng các đầu bán dẫn 84661020, 84662020, 84663020, 84669420, 84799030 Bộ phận của máy kết tủa vật lý dùng trong sản xuất bán dẫn 84799030, 85439070 Thiết bị làm nóng nhanh tấm bán dẫn mỏng 84198912, 85143011 Bộ phận của thiết bị làm nóng nhanh tấm bán dẫn mỏng 84199011, 85149010 Đầu dò dẹt dưới dạng miếng lát (wafer probers) 85369010, 90308210 Thiết bị khắc a-xít ướt, máy hiện ảnh, tẩy rửa hoặc làm sạch các tấm bán dẫn mỏng và 84248930, 84649012, màn hình dẹt 84798910, 85433010 Bộ phận của thiết bị khắc a-xít ướt, máy hiện ảnh, tẩy rửa hoặc làm sạch các tấm bán dẫn 84249096, 84662030, mỏng và màn hình dẹt 84663030, 84669110, 84799010, 85439010 Kính hiển vi quang học nhìn hình nổi (lập thể) có gắn thiết bị chuyên dụng để điều khiển và 90111010 di chuyển các miếng hoặc lưới bán dẫn Kính hiển vi để xem vi ảnh có gắn thiết bị chuyên dụng để điều khiển và di chuyển các 90112010 miếng hoặc lưới bán dẫn Bộ phận và phụ tùng của kính hiển vi quang học nhìn hình nổi (lập thể) có gắn thiết bị 90119010 chuyên dụng để điều khiển và di chuyển các miếng hoặc lưới bán dẫn Bộ phận và phụ tùng của kính hiển vi để xem vi ảnh có gắn thiết bị chuyên dụng để điều 90119010 khiển và di chuyển các miếng hoặc lưới bán dẫn Kính hiển vi tia electron có gắn thiết bị chuyên dụng để điều khiển và di chuyển các miếng 90121010, 90318091 hoặc lưới bán dẫn Bộ phận và phụ tùng của kính hiển vi tia electron có gắn thiết bị chuyên dụng để điều khiển 90129010, 90319014 và di chuyển các miếng hoặc lưới bán dẫn Thiết bị tạo mẫu dùng để sản xuất mặt nạ hoặc lưới caro từ chất nền phủ chất cản quang 90172020 Bộ phận và phụ tùng của thiết bị tạo mẫu dùng để sản xuất mặt nạ hoặc lưới caro từ chất 90179010 nền phủ chất cản quang Bộ phận của thiết bị tạo mẫu như thế 90179010 Máy tính: máy xử lý dữ liệu tự động có khả năng 1) lưu giữ chương trình hay các chương 84711000, 84713010, trình xử lý và ít nhất là dữ liệu trực tiếp cần thiết cho việc chạy chương trình; 2) được lập 84713020, 84713090, trình một cách tự do theo nhu cầu của người sử dụng 84714110, 84714190, 84714910, 84714990, 84715010, 84715090 Mô tả hàng hoá Mã hàng Bộ khuyếch đại được sử dụng như một bộ lặp trong điện thoại hữu tuyến theo Hiệp định 84715010, 84715090, này, và các bộ phận của nó 85175010, 85175020, 85175030, 85175040, 85175050, 85175090, 85178010, 85178020, 85178030, 85178040, 85178050, 85178060, 85178070, 85178091,
- 85178092, 85178099, 85179010, 85179020, 85179090, 85184020, 85189010 Màn hình dẹt (kể cả loại màn hình tinh thể lỏng LCD, loại công nghệ quang điện tử, plasma 84714910, 84714990, và công nghệ khác) dùng cho các sản phẩm thuộc Hiệp định này, và các bộ phận của nó 85312000, 85318020, 85319010, 85438920, 85489040, 90138020, 90139030 84711000, 84713010, 84713020, 84713090, 84714110, 84714190, 84714910, 84714990, 84716011, 84716012, 84716013, 84716019, 84716021, 84716029, Thiết bị mạng: Thiết bị mạng cục bộ (LAN) và mạng diện rộng (WAN), kể cả những sản 84716030, 84716040, phẩm được thiết kế chuyên dùng hoặc chủ yếu dùng để kết nối các máy xử lý dữ liệu tự 84716050, 84716060, động và các thiết bị mạng của nó chủ yếu dùng để chia sẻ các nguồn dữ liệu như bộ xử lý 84716090, 84717010, trung tâm, thiết bị lưu trữ dữ liệu và các bộ nhập hoặc bộ xuất, bao gồm bộ tiếp hợp, cổng 84717020, 84717030, kết nối, bộ lặp hữu tuyến, bộ chuyển đổi, bộ tập kết, cầu nối, bộ định tuyến, và tấm mạch in 84717040, 84717050, đã lắp ráp để kết hợp vật lý thành máy sử lý dữ liệu tự động và các thiết bị của nó 84717091, 84717 Màn hình: Thiết bị hiển thị của máy xử lý dữ liệu tự động có đèn điện tử tia ca tốt có điểm 84716021, 84716029, ảnh nhỏ hơn 0,4 mm, không có khả năng thu và xử lý các tín hiệu ti-vi hoặc các tín hiệu 84716040, 84716090, loại kỹ thuật tương tự hoặc tín hiệu âm thanh hay hình ảnh được số hoá mà không có sự 85404010, 85404090 trợ giúp của bộ xử lý trung tâm của máy tính như định nghĩa theo Hiệp định này. Hiệp định, do đó không bao gồm ti-vi, kể cả ti-vi có độ nét cao Bộ lưu giữ bằng đĩa quang học, dùng cho máy xử lý dữ liệu tự động (kể cả ổ đĩa CD và ổ 84714910, 84714990, đĩa DVD), có hoặc không có khả năng ghi cũng như đọc, có hoặc không có vỏ riêng của 84717040 chúng Thiết bị cảnh báo bằng nhắn tin, và các bộ phận của nó 85252010, 85252020, 85252030, 85252040, 85252050, 85252060, 85252070, 85252080, 85252091, 85252092, 85252099, 85279010, 85291010 Máy vẽ có bộ xuất hoặc bộ nhập thuộc nhóm HS 8471 hoặc máy vẽ hoặc vẽ phácthuộc 84714910, 84714990, nhóm HS 9017. 84716050, 90171010, 90172050 Mô tả hàng hoá Mã hàng Tấm mạch in đã lắp ráp dùng cho các sản phẩm thuộc Hiệp định này, kể cả loại để nối bên 84731010, 84732900, ngoài như cạc (cards) theo tiêu chuẩn của Hiệp hội quốc tế về cạc nhớ của máy tính cá 84733010, 84733090, nhân. TÊm m¹ch in nµy bao gåm mét hay nhiÒu m¹ch in thuéc nhãm 8534 g¾n kÌm víi mét 84734011, 84735011, hoÆc nhiÒu linh kiÖn tÝch cùc, cã hoÆc kh«ng cã c¸c linh kiÖn bÞ ®éng. "linh kiÖn tÝch 84735019, 84735021, cùc" lµ nh÷ng ®ièt, bãng b¸n dÉn vµ c¸c thiÕt bÞ b¸n dÉn t−¬ng tù, cã hoÆc kh«ng cã ®é 84735029, 85049020, c¶m quang thuéc nhãm 85.41, m¹ch tÝch hîp vµ vi linh kiÖn thuéc nhãm 8542 85149010, 85159030, 85175010, 85175020, 85175030, 85175040, 85175050, 85175090, 85179010, 85179020, 85179090, 85189010,
- 85189010, 85202000, 85229020, 85281 Các màn hình dẹt kiểu đèn chiếu được sử dụng cho máy xử lý dữ liệu tự động có thể hiển 84714910, 84714990, thị thông tin số do bộ xử lý trung tâm tạo ra 84716040, 84716060, 84716090, 85282110, 85283020 Các bộ lưu trữ được tạo định dạng riêng kể cả các vật mang tin dùng cho máy xử lý dữ liệu 84717050, 85231110, tự động, có hoặc không có các vật mang tin có thể thay đổi được là sản phẩm của công 85231190, 85231210, nghệ từ, quang, hay công nghệ khác, kể cả hộp Bermoulli, Syquest hoặc bộ lưu 85231220, 85231230, 85231290, 85231310, 85231320, 85231330, 85231340, 85231390, 85232010, 85232020, 85232030, 85232040, 85232090, 85239010, 85239020, 85239090, 85244000, 85249920 Bộ nâng cấp đa phương tiện sử dụng cho máy xử lý dữ liệu tự động, và các khối chức 84718070, 84733010, năng của chúng, đã đóng gói để bán lẻ, bao gồm, ít nhất có, loa và/hoặc mic-ro cũng như 84733090, 85175010, tấm mạch in đã lắp sẵn cho phép máy xử lý dữ liệu tự động (ADP) và các khối chức năng 85175020, 85175030, của chúng xử lý các tín hiệu âm thanh (cạc âm thanh) 85175040, 85175050, 85175090 Thiết bị giải mã và chọn kênh dùng trong truyền hình cáp: thiết bị dựa trên bộ vi xử lý kết 85175040, 85251040, hợp với bộ điều giả (modem) để truy cập internet, và có chức năng trao đổi thông tin tương 85252070, 85281210 tác
CÓ THỂ BẠN MUỐN DOWNLOAD
-
Thông báo Số: 191/TB-BGDĐT-ĐTVNN V/v: Thông báo về việc giao dịch điện tử đối với công tác tuyển sinh đi học nước ngoài
3 p |
195 |
34
-
Thông tư Số: 11/2010/TT-BTTTT
11 p |
196 |
26
-
Thông Tư Số: 14/2010/TT-BTTTT
13 p |
116 |
19
-
Quyết định Số: 15/2010/QĐ-UBND
7 p |
106 |
15
-
Thông tư Số: 08/2010/TT-BTTTT
5 p |
124 |
12
-
Cam kết số 314/WTO/CK của Cộng hoà Xã hội chủ nghĩa Việt Nam
8 p |
53 |
11
-
Thông tư Số: 10/2010/TT-BTTTT
9 p |
87 |
9
-
Thông Tư Số: 15/2010/TT-BTTTT
5 p |
74 |
8
-
Quyết Định Số: 12/2010/QĐ-UBND
7 p |
50 |
6
-
Quyết định Số: 09/2010/QĐ-UBND
3 p |
93 |
5
-
Luật số: 73/2014/QH13
22 p |
17 |
3
-
Quyết định số 1682/QĐ-VPCP
4 p |
43 |
3
-
Luật Công nghệ thông tin 2006
37 p |
29 |
2
-
Quyết định số 250/2005/QĐ-TTg
8 p |
57 |
2
-
Nghị quyết số: 84/2014/QH13
2 p |
22 |
1
-
Luật số: 61/2014/QH13
18 p |
8 |
0
-
Nghị quyết số: 83/2014/QH13
2 p |
23 |
0

WARC-Type: response

Content-Type: application/http; msgtype=response

WARC-Identified-Payload-Type: application/xhtml+xml

Connection: close

Set-Cookie: TLDEVNamespace=b91edtv441o64uk8m68spph365; path=/; domain=.tailieu.vn; HttpOnly

Vary: Accept-Encoding

Content-Type: text/html; charset=UTF-8


text:
Chapter 17: SẮP XẾP
Chia sẻ: Chao Hello | Ngày: | Loại File: DOC | Số trang:21
lượt xem 51
download
Chapter 17: SẮP XẾP
Sắp xếp là một quá trình biến đổi một danh sách các đối tượng thành một danh sách thoả mãn một thứ tự xác định nào đó. Sắp xếp đóng vai trò quan trọng trong tìm kiếm dữ liệu. Chẳng hạn, nếu danh sách đã được sắp xếp theo thứ tự tăng dần (hoặc giảm dần), ta có thể sử dụng kỹ thuật tìm kiếm nhị phân hiệu quả hơn nhiều tìm kiếm tuần tự…
Bình luận(0) Đăng nhập để gửi bình luận!
Nội dung Text: Chapter 17: SẮP XẾP
- CHƯƠNG 17 SẮP XẾP Sắp xếp là một quá trình biến đổi một danh sách các đối tượng thành một danh sách thoả mãn một thứ tự xác định nào đó. Sắp xếp đóng vai trò quan trọng trong tìm kiếm dữ liệu. Chẳng hạn, nếu danh sách đã được sắp xếp theo thứ tự tăng dần (hoặc giảm dần), ta có thể sử dụng kỹ thuật tìm kiếm nhị phân hiệu quả hơn nhiều tìm kiếm tuần tự… Trong thiết kế thuật toán, ta cũng thường xuyên cần đến sắp xếp, nhiều thuật toán được thiết kế dựa trên ý tưởng xử lý các đối tượng theo một thứ tự xác định. Các thuật toán sắp xếp được chia làm 2 loại: sắp xếp trong và sắp xếp ngoài. Sắp xếp trong được thực hiện khi mà các đối tượng cần sắp xếp được lưu ở bộ nhớ trong của máy tính dưới dạng mảng. Do đó sắp xếp trong còn được gọi là sắp xếp mảng. Khi các đối tượng cần sắp xếp quá lớn cần lưu ở bộ nhớ ngoài dưới dạng file, ta cần sử dụng các phương pháp sắp xếp ngoài, hay còn gọi là sắp xếp file. Trong chương này, chúng ta trình bày các thuật toán sắp xếp đơn giản, các thuật toán này dòi hỏi thời gian O(n2) để sắp xếp mảng n đối tượng. Sau đó chúng ta đưa ra các thuật toán phức tạp và tinh vi hơn, nhưng hiệu quả hơn, chỉ cần thời gian O(nlogn). Mảng cần được sắp xếp có thể là mảng số nguyên, mảng các số thực, hoặc mảng các xâu ký tự. Trong trường hợp tổng quát, các đối tượng cần được sắp xếp chứa một số thành phần dữ liệu, và ta cần sắp xếp mảng các đối tượng đó theo một thành phần dữ liệu nào đó. Thành phần dữ liệu đó được gọi là khoá sắp xếp. Chẳng hạn, ta có một mảng các đối tượng sinh viên, mỗi sinh viên gồm các thành phần dữ liệu: tên, tuổi, chiều cao,…, và ta muốn sắp xếp các sinh viên theo thứ tự chiều cao tăng, khi đó chiều cao là khoá sắp xếp. 187
- Từ đây về sau, ta giả thiết rằng, mảng cần được sắp xếp là mảng các đối tượng có kiểu Item, trong đó Item là cấu trúc sau: struct Item { keyType key; // Khoá sắp xếp // Các trường dữ liệu khác }; Vấn đề sắp xếp bây giờ được phát biểu chính xác như sau. Cho mảng A[0..n-1] chứa n Item, chúng ta cần sắp xếp lại các thành phần của mảng A sao cho: A[0].key
- A[0] A[1] A[2] A[3] A[4] A[5] I k 5 9 1 8 3 7 0 2 1 9 5 8 3 7 1 4 1 3 5 8 9 7 2 2 1 3 5 8 9 7 3 5 1 3 5 7 9 8 4 5 1 3 5 7 8 9 Sau đây là hàm sắp xếp lựa chọn: void SelectionSort(Item A[] , int n) // Sắp xếp mảng A[0..n-1] với n > 0 { (1) for (int i = 0 ; i < n-1 ; i++) { (2) int k = i; (3) for (int j = i + 1 ; j < n ; j++) (4) if (A[j].key < A[k].key) k = j; (5) swap(A[i],A[k]); } } Trong hàm trên, swap là hàm thực hiện trao đổi giá trị của hai biến. Phân tích sắp xếp lựa chọn. Thân của lệnh lặp (1) là các lệnh (2), (3) và (5). Các lệnh (2) và (5) có thời gian chạy là O(1). Ta đánh giá thời gian chạy của lệnh lặp (3). Số lần lặp là (n-1-i), thời gian thực hiện lệnh (4) là O(1), do đó thời gian chạy của lệnh (3) là (n-1-i)O(1). Như vậy, thân của lệnh lặp (1) có thời gian chạy ở lần lặp thứ i là (n-1-i)O(1). Do đó lệnh lặp (1) đòi hỏi thời gian n −2 ∑ i =0 (n-1-i)O(1) = O(1)(1 + 2 + …+ n-1) = O(1)n(n-1)/2 = O(n2) 189
- Vậy thời gian chạy của hàm sắp xếp lựa chọn là O(n2). 17.1.2 Sắp xếp xen vào Phương pháp sắp xếp xen vào là như sau. Giả sử đoạn đầu của mảng A[0..i-1] (với i >= 1) đã được sắp xếp, tức là ta đã có A[0].key
- { (1) for ( int i = 1 ; i < n ; i++) (2) for ( int k = i ; k > 0 ; k--) (3) if (A[k].key < A[k-1].key) swap(A[k],A[k-1]); else break; } Phân tích sắp xếp xen vào Số lần lặp tối đa của lệnh lặp (2) là i, thân của lệnh lặp (2) là lệnh (3) cần thời gian O(1). Do đó thời gian chạy của lệnh (2) là O(1)i. Thời gian thực hiện lệnh lặp (1) là n −1 ∑ O(1) i = O(1)(1 + 2 + ... + n − 1) = O(n i =1 2 ) 17.1.3 Sắp xếp nổi bọt Ý tưởng của sắp xếp nổi bọt là như sau. Cho chỉ số k chạy từ 0, 1 , …, n-1, nếu hai thành phần kề nhau không đúng trật tự, tức là A[k].key >A[k+1].key thì ta trao đổi hai thành phần A[k] và A[k+1]. Làm như vậy ta đẩy được dữ liệu có khoá lớn nhất lên vị trí sau cùng A[n-1]. Ví dụ. Giả sử ta có mảng số nguyên A[0..4]= (6,1,7,3,5).Kết quả thực hiện quá trình trên được cho trong bảng sau: A[0] A[1] A[2] A[3] A[4] 6 1 7 3 5 Trao đổi A[0] và A[1] 1 6 7 3 5 Trao đổi A[2] và A[3] 1 6 3 7 5 Trao đổi A[3] và A[4] 1 6 3 5 7 191
- Lặp lại quá trình trên đối với mảng A[0,…, n-2] để đẩy dữ liệu có khoá lớn nhất lên vị trí A[n-2]. Khi đó ta có A[n-2].key ≤ A[n-1].key. Tiếp tục lặp lại quá trình đã mô tả trên các đoạn đầu A[0..i], với i = n-3, …,1, ta sẽ thu được mảng được sắp . Ta có hàm sắp xếp nổi bọt như sau: void BubbleSort( Item A[] , int n) { (1) for (int i = n-1 ; i > 0 ; i--) (2) for (int k = 0 ; k < i ; k++) (3) if ( A[k].key > A[k+1].key) Swap(A[k],A[k+1]); } Tương tự như hàm sắp xếp xen vào ,ta có thể đánh giá thời gian chạy của hàm sắp xếp nổi bọt là O(n2 ). Trong hàm BubbleSort khi thực hiện lệnh lặp (1), nếu đến chỉ số i nào đó, n-1 ≥ i > 1, mà đoạn đầu A[0..i] đã được sắp, thì ta có thể dừng. Do đó ta có thể cải tiến hàm BubbleSort bằng cách đưa vào biến sorted, biến này nhận giá trị true nếu A[0..i] đã được sắp và nhận giá trị false nếu ngược lại. Khi sorted nhận giá trị true thì lệnh lặp (1) sẽ dừng lại. void BubbleSort (Item A[] , int n) { for (int i = n-1 ; i > 0 ; i -- ) { bool sorted = true; for( int k = 0 ; k < i ; k++) if (A[k].key > A[k+1].key) { swap (A[k], A[k+1]); sorted = false; } if (sorted) break; } } 192
- 17.2 SẮP XẾP HOÀ NHẬP Thuật toán sắp xếp hoà nhập (MergeSort) là một thuật toán được thết kế bằng kỹ thuật chia - để - trị. Giả sử ta cần sắp xếp mảng A[a..b], trong đó a, b là các số nguyên không âm, a b, a là chỉ số đầu và b là chỉ số cuối của mảng. Ta chia mảng thành hai mảng con bởi chỉ số c nằm giữa a và b ( c = ( a + b ) / 2). Các mảng con A[a..c] và A[c+1…b] được sắp xếp bằng cách gọi đệ quy thủ tục sắp xếp hoà nhập. Sau đó ta hoà nhập hai mảng con A[a…c] và A[c+1…b] đã được sắp thành mảng A[a…b] được sắp. Giả sử Merge(A,a,c,b) là hàm kết hợp hai mảng con đã được sắp A[a..c] và A[c+ 1..b] thành mảng A[a..b] được sắp. Thuật toán sắp xếp hoà nhập được biểu diễn bởi hàm đệ quy sau. void MergeSort( Item A[ ], int a, int b) { if (a < b) { int c = (a + b)/2; MergeSort ( A, a, c ); MergeSort ( A, c+1, b); Merge ( A, a, c, b); } } Công việc còn lại của ta là thiết kế hàm hoà nhập Merge ( A, a, c, b), nhiệm vụ của nó là kết hợp hai nửa mảng đã được sắp A[a…c] và A[ c+1…b] thành mảng được sắp. Ý tưởng của thuật toán hoà nhập là ta đọc lần lượt các thành phần của hai nửa mảng và chép vào mảng phụ B[0..b-a] theo đúng thứ tự tăng dần. Giả sử i là chỉ số chạy trên mảng con A[a…c], i được khởi tạo là a ; j là chỉ số chạy trên mảng con A[c+1..b], j được khởi tạo là c + 1. So sánh A[i] và A[j], nếu A[i].key < A[j].key thì ta chép A[i] vào mảng B và tăng i lên 1, còn nếu ngược lại thì ta chép A[j] vào mảng B va tăng j lên 1. Lặp lại hành động đó cho đến khi i vượt quá c hoặc j vượt quá b. Nếu chỉ số i chưa vượt quá c nhưng j đã vượt quá b 193
- thì ta cần phải chép phần còn lại A[i…c] vào mảng B. Tương tự, nếu i > c, nhưng j ≤ b thì ta cần chép phần còn lại A[j…b] vào mảng B. Chẳng hạn, xét mảng số nguyên A[ 5…14], trong đó A[5…9] và A[10…14] đã được sắp như sau: i j A 10 12 20 31 35 3 5 15 21 26 a=5 6 7 8 c=9 10 11 12 13 14 Bắt đầu i = 5 , j = 10. Vì A[5] > A[10] nên A[10] = 3 được chép vào mảng B và j = 11. Ta lại có A[5] > A[11], nên A[11] = 5 được chép vào mảng B và j = 12. Đến dây A[5] < A[12], ta chép A[5] = 10 vào mảng B và i = 6. Tiếp tục như thế ta nhận được mảng B như sau: B 3 5 10 12 15 20 21 26 0 1 2 3 4 5 6 7 8 9 Đến đây j = 15 > b = 14, còn i = 8 < c = 9, do đó ta chép nốt A[8] = 31 và A[9] = 35 sang B để nhận được mảng B được sắp. Bây giờ chỉ cần chép lại mảng B sang mảng A. Hàm Merge được viết như sau: void Merge( Item A[] , int a , int c , int b) // a, c, b là các số nguyên không âm, a ≤ c ≤ b. // Các mảng con A[a…c] và A[c+1…b] đã được sắp. { int i = a; int j = c + 1; 194
- int k = 0; int n = b – a + 1; Item * B = new Item[n]; (1) while (( i < c +1 ) && ( j < b +1 )) if ( A [i].key < A[j].key) B[k ++] = A[i ++]; else B[k ++] = A[j ++]; (2) while ( i < c + 1) B[k ++] = A[i++]; (3) while ( j < b +1) B[k ++] = A[ j ++]; i = a; (4) for ( k = 0 ; k < n ; k ++) A[i ++] = B [k]; delete [ ] B; } Phân tích sắp xếp hoà nhập. Giả sử mảng cần sắp xếp A[a…b] có độ dài n, n = b – a +1, và T(n) là thời gian chạy của hàm MergeSort (A, a, b). Khi đó thời gian thực hiện mỗi lời gọi đệ quy MergeSort (A, a, c) và MergeSort (A, c + 1, b) là T(n/2). Chúng ta cần đánh gía thời gian chạy của hàm Merge(A, a, c, b). Xem xét hàm Merge ta thấy rằng, các lệnh lặp (1), (2), (3) cần thực hiện tất cả là n lần lặp, mỗi lần lặp chỉ cần thực hiện một số cố định các phép toán. Do đó tổng thời gian của ba lệnh lặp (1), (2), (3) là O(n). Lệnh lặp (4) cần thời gian O(n). Khi thực hiện hàm MergeSort(A, a, b) với a = b, chỉ một phép so sánh phải thực hiện, do đó T(1) = O(1). Từ hàm đệ quy MergeSort và các đánh giá trên, ta có quan hệ đệ quy sau T(1) = O(1) T(n) = 2T(n/2) + O(n) với n>1 Giả sử thời gian thực hiện các phép toán trong mỗi lần lặp ở hàm Merge là hằng số d nào đó, ta có : T(1) ≤ d 195
- T(n) ≤ 2T(n/2) + nd Áp dụng phương pháp thế lặp vào bất đẳng thức trên ta nhận được T(n) ≤ 2T(n/2) + n d ≤ 22 T(n/22) + 2 (n/2)d + n d …… ≤ 2k T(n/2k) + n d + …+ n d (k lần nd) Giả sử k là số nguyên dương lớn nhất sao cho 1 ≤ n / 2k. Khi đó, ta có T(n) ≤ 2k T(1) + n d + … + n d ( k lần n d) T(n) ≤ (k + 1) n d T(n) ≤ (1 + log n) n d Vậy T(n) = O (n log n). 17.3 SẮP XẾP NHANH Trong mục này chúng ta trình bày thuật toán sắp xếp được đưa ra bởi Hoare, nổi tiếng với tên gọi là sắp xếp nhanh (QuickSort). Thời gian chạy của thuật toán này trong trường hợp xấu nhất là O(n2). Tuy nhiên thời gian chạy trung bình là O(n logn). Thuật toán sắp xếp nhanh được thiết kế bởi kỹ thuật chia-để-trị như thuật toán sắp xếp hòa nhập. Nhưng trong thuật toán sắp xếp hòa nhập, mảng A[a…b] cần sắp được chia đơn giản thành hai mảng con A[a..c] và A[c+1..b] bởi điểm chia ở giữa mảng, c = (a+b)/2. Còn trong thuật toán sắp xếp nhanh, việc “chia mảng thành hai mảng con” là một quá trình biến đổi phức tạp để từ mảng A[a..b] ta thu được hai mảng con A[a..k-1] và A[k+1..b] thỏa mãn các tính chất sau : A[i].key ≤ A[k].key với mọi i, a ≤ i ≤ k-1. A[j].key > A[k].key với mọi j, k+1 ≤ j ≤ b. 196
- Nếu thực hiện được sự phân hoạch mảng A[a..b] thành hai mảng con A[a..k-1] và A[k+1..b] thỏa mãn các tính chất trên, thì nếu sắp xếp được các mảng con đó ta sẽ có toàn bộ mảng A[a..b] được sắp xếp. Giả sử Partition(A, a, b, k) là hàm phân hoạch mảng A[a..b] thành hai mảng con A[a..k-1] và A[k+1..b]. Thuật toán sắp xếp nhanh là thuật toán đệ quy được biểu diễn bởi hàm đệ quy như sau : void QuickSort(Item A[] , int a , int b) //Sắp xếp mảng A[a..b] với a ≤ b. { if (a < b) { int k; Partition(A, a, b, k); if (a
- con bằng nhau. Điều này là có thể làm được, tuy nhiên nó đòi hỏi nhiều thời gian hơn sự cần thiết. Vì vậy, ta sẽ chọn ngay thành phần đầu tiên của mảng làm mốc, tức là pivot = A[a].key. Sau đó ta sử dụng hai chỉ số, chỉ số left chạy từ trái sang phải, ban đầu left = a + 1, chỉ số right chạy từ phải sang trái, ban đầu right = b. Biến left sẽ tăng và dừng tại vị trí mà A[left].key > pivot, còn biến right sẽ giảm và dừng lại tại vị trí mà A[right].key ≤ pivot. Khi đó nếu left < right thì ta trao đổi giá trị của A[left] với A[right]. Quá trình trên được lặp lại cho tới khi left > right. Lúc này ta dễ thấy rằng, mọi thành phần trong mảng A[a..right] có khóa nhỏ hơn hay bằng mốc, còn mọi thành phần trong mảng A[left..b] có khóa lớn hơn mốc. Cuối cùng ta trao đổi A[a] và A[right] để đặt mốc vào vị trí k = right. Hàm phân hoạch được viết như sau : void Partition( Item A[] , int a , int b , int & k) { keyType pivot = A[a].key; int left = a + 1; int right = b; do { while (( left
- Để thấy được hàm phân hoạch làm việc như thế nào, ta hãy xét ví dụ sau. Giả sử ta cần phân hoạch mảng số nguyên A[0..9] như sau : 8 3 17 12 6 14 7 5 13 15 left right Lấy mốc pivot = A[0] = 8, ban đầu left = 1, right = 9. Chỉ số left tăng và dừng lại tại vị trí left = 2, vì A[2] = 17 > 8, chỉ số right giảm và dừng lại tại vị trí right = 7, vì A[7] = 5 < 8. Trao đổi A[2] với A[7], đồng thời tăng left lên 1, giảm right đi 1, ta có : 8 3 5 12 6 14 7 1 13 15 7 left right Đến đây A[left] = 12 > 8 và A[right] = 7 < 8. Lại trao đổi A[left] với A[right], và tăng left lên 1, giảm right đi 1, ta có : 8 3 5 7 6 14 1 1 13 15 2 7 left right Tiếp tục, A[left] = 6 < 8 nên left được tăng lên và dừng lại tại left = 5 vì A[5] > 8. A[right] = 14 > 8 nên right được giảm đi và dừng lại tại right = 4, vì A[4] < 8. Ta có hoàn cảnh sau : 8 3 5 7 6 14 1 1 13 15 2 7 right left 199
- Đến đây right < left, ta dừng lại, trao đổi A[0] với A[4] ta thu được phân hoạch với k = right = 4. 6 3 5 7 8 14 1 1 13 15 2 7 k Phân tích sắp xếp nhanh Chúng ta cần đánh giá thời gian chạy T(n) của thuật toán sắp xếp nhanh trên mảng A[a..b] có n phần tử, n = b – a + 1. Trước hết ta cần đánh giá thời gian thực hiện hàm phân hoạch. Thời gian phân hoạch là thời gian đi qua mảng (hai biến left và right chạy từ hai đầu mảng cho tới khi chúng gặp nhau), tại mỗi vị trí mà left và right chạy qua ta cần so sánh thành phần ở vị trí đó với mốc và các trao đổi khi cần thiết. Do đó khi phân hoạch một mảng n phần tử ta chỉ cần thời gian O(n). Thời gian trong trường hợp tốt nhất. Trường hợp tốt nhất xảy ra khi mà sau mỗi lần phân hoạch ta nhận được hai mảng con bằng nhau. Trong trường hợp này, từ hàm đệ quy QuickSort, ta suy ra quan hệ đệ quy sau : T(1) = O(1) T(n) = 2 T(n/2) + O(n) với n > 1. Đây là quan hệ đệ quy mà ta đã gặp khi phân tích sắp xếp hòa nhập. Như vậy trong trường hợp tốt nhất thời gian chạy của QuickSort là O(n logn). Thời gian trong trường hợp xấu nhất. Trường hợp xấu nhất là trường hợp mà sau mỗi lần phân hoạch mảng n phần tử ta nhận được mảng con n – 1 phần tử ở một phía của mốc, còn phía kia không có phần 200
- tử nào. (Dễ thấy rằng trường hợp này xẩy ra khi ta phân hoạch một mảng đã được sắp). Khi đó ta có quan hệ đệ quy sau : T(1) = O(1) T(n) = T(n – 1) + O(n) với n > 1 Ta có : T(1) = C T(n) = T(n – 1) + nC với n > 1 Trong đó C là hằng số nào đó. Bằng cách thế lặp ta có : T(n) = T(1) + 2C + 3C + … + nC n = C ∑i i =1 = Cn(n+1)/2 Do đó trong trường hợp xấu nhất, thời gian chạy của sắp xếp nhanh là O(n2). Thời gian trung bình. Bây giờ ta đánh giá thời gian trung bình Ttb(n) mà QuickSort đòi hòi để sắp xếp một mảng có n phần tử. Giả sử mảng A[a..b] chứa n phần tử được đưa vào mảng một cách ngẫu nhiên. Khi đó hàm phân hoạch Partition(A, a, b, k) sẽ cho ra hai mảng con A[a..k – 1] và A[k + 1..b] với k là một trong các chỉ số từ a đến b với xác suất như nhau và bằng 1/n. Vì thời gian thực hiện hàm phân hoạch là O(n), từ hàm QuickSort ta suy ra quan hệ đệ quy sau : n Ttb(n) = 1 n ∑ k =1 [ Ttb(k - 1) + Ttb(n - k)] + O(n) Hay n Ttb(n) = 1 n ∑ k =1 [ Ttb(k - 1) + Ttb(n - k)] + nC (1) 201
- Trong đó C là hằng số nào đó. Chú ý rằng n n ∑k =1 Ttb(k - 1) = ∑ k =1 Ttb(n - k) Do đó có thể viết lại (1) như sau : n Ttb(n) = 2 n ∑k =1 Ttb(k - 1) + nC (2) Trong (2) thay n bới n – 1 ta có : n −1 Ttb(n - 1) = 2 n−1 ∑ k =1 Ttb(k - 1) + (n – 1)C (3) Nhân (2) với n, nhân (3) với n – 1 và trừ cho nhau ta nhận được n Ttb(n) = (n + 1) Ttb(n - 1) + (2n – 1)C Chia đẳng thức trên cho n(n + 1) ta nhận được quan hệ đệ quy sau : Ttb (n) Ttb (n - 1) 2n - 1 n+1 = n + n ( n+1) C (4) Sử dụng phép thế lặp, từ (4) ta có Ttb (n) Ttb (n - 1) 2n - 1 n+1 = n + n ( n+1) C Ttb (n - 2) 2n - 3 2n - 1 = n−1 + ( n −1) n + n ( n+1) C ... Ttb (n) Ttb (1) n 2i − 1 n+1 = 2 + c ∑ i(i + 1) i =1 (5) Ta có đánh giá 202
- n 2i − 1 n 2 n dx ∑ i(i + 1) ≤ k =1 ∑ i ≤ 2 ∫ x ≤ 2logn i =1 1 Do đó từ (5) ta suy ra Ttb (n) = O(logn) n+1 hay Ttb(n) = O(n logn). Trong trường hợp xấu nhất, QuickSort đòi hỏi thời gian O(n2), nhưng trường hợp này rất ít khi xảy ra. Thời gian trung bình của QuickSort là O(n logn), và thời gian trong trường hợp xấu nhất của MergeSort cũng là O(n logn). Tuy nhiên thực tiễn cho thấy rằng, trong phần lớn các trường hợp QuickSort chạy nhanh hơn các thuật toán sắp xếp khác. 17.4 SẮP XẾP SỬ DỤNG CÂY THỨ TỰ BỘ PHẬN Trong mục này chúng ta trình bày phương pháp sắp xếp sử dụng cây thứ tự bộ phận (heapsort). Trong mục 10.3, chúng ta biết rằng một cây thứ tự bộ phận n đỉnh có thể biểu diễn bởi mảng A[0..n-1], trong đó gốc cây được lưu trong A[0], và nếu một đỉnh được lưu trong A[i], thì đỉnh con trái (nếu có) của nó được lưu trong A[2*i + 1], còn đỉnh con phải nếu có của nó được lưu trong A[2*i + 2]. Mảng A thoả mãn tính chất sau (ta sẽ gọi là tính chất heap): A[i].key
- A[n-1]. Mảng A[0..n-2] bây giờ thoả mãn tính chất heap với mọi i >= 1, trừ i = 0. Biến đổi mảng A[0..n-2] để nó thoả mãn tính chất heap. Lại trao đổi A[0] và A[n-2]. Rồi lại biến đổi mảng A[0..n-3] trở thành mảng thoả mãn tính chất heap. Lặp lại quá trình trên, cuối cùng ta sẽ nhận được mảng A[0..n-1] được sắp theo thứ tự giảm dần: A[0].key >= A[1].key >= … >= A[n-1].key Trong quá trình trên, sau mỗi lần trao đổi A[0] với A[m] (với m=n-1, …,1), ta sẽ nhận được mảng A[0…m-1] thoả mãn tính chất heap với mọi i >= 1, trừ i = 0. Điều này có nghĩa là cây nhị phân được biểu diễn bởi mảng A[0..m-1] đã thoả mãn tính chất thứ tự bộ phận, chỉ trừ gốc. Để nó trở thành cây thứ tự bộ phận, ta chỉ cần đẩy dữ liệu lưu ở gốc xuống vị trí thích hợp trong cây, bằng cách sử dụng hàm ShiftDown (Xem mục 10.3.3). Còn một vấn đề cần giải quyết, đó là biến đổi mảng cần sắp xếp A[0..n-1] thành mảng thoả mãn tính chất heap. Điều này có nghĩa là ta phải biến đổi cây nhị phân được biểu diễn bởi mảng A[0..n-1] thành cây thứ tự bộ phận. Muốn vậy, với i chạy từ n/2-1 giảm xuống 0, ta chỉ cần sử dụng hàm SiftDown để đẩy dữ liệu lưu ở đỉnh i xuống vị trí thíc hợp trong cây. Đây là cách xây dựng cây thứ tự bộ phận mà chúng ta đã trình bày trong 10.3.2. Bây giờ ta viết lại hàm ShiftDown cho thích hợp với sự sử dụng nó trong thuật toán. Giả sử mảng A[a..b] (a < b) đã thoả mãn tính chất heap với mọi i >= a+1. Hàm ShiftDown(a,b) sau đây thực hiện việc đẩy A[a] xuống vị trí thích hợp trong mảng A[a..b] để mảng thoả mãn tính chất heap với mọi i >= a. void ShiftDown(int a, int b) { int i = a; int j = 2 * i + 1; while (j
- { int k = j + 1; if (k A[j].key) { swap(A[i],A[j]); i = j; j = 2 * i + 1; } else break; } } Sử dụng hàm ShiftDown, ta đưa ra thuật toán sắp xếp HeapSort sau đây. Cần lưu ý rằng, kết quả của thuật toán là mảng A[0..n-1] được sắp xếp theo thứ tự giảm dần. void HeapSort(Item A[] , int n) //Sắp xếp mảng A[0..n-1] với n > 1 { for (int i = n / 2 – 1 ; i >= 0 ; i--) ShiftDown(i,n-1); //Biến đổi mảng A[0..n-1] // thành mảng thoả mãn tính chất heap for (int i = n – 1 ; i >= 1 ; i--) { swap(A[0],A[i]); ShiftDown(0,i - 1); } } Phân tích HeapSort. Thời gian thực hiện lệnh lặp (1) là thời gian xây dựng cây thứ tự bộ phận mà chúng ta đã xét trong mục 10.3.2. Theo chứng minh đã đưa ra trong 10.3.2, lệnh lặp (1) chỉ đòi hỏi thời gian O(n). Trong lệnh lặp (2), số lần lặp là n-1. Thân vòng lặp (2), với i = n-1 là 205
- swap(A[0],A[n - 1]); ShiftDown(0,n - 2); Đây là các lệnh thực hiện DeleteMin trên cây thứ tự bộ phận được biểu diễn bởi mảng A[0..n-1], và dữ liêụ có khoá nhỏ nhất được lưu vào A[n- 1]. Trong mục 10.3.1, ta đã chứng tỏ rằng DeleteMin chỉ cần thời gian O(logn). Như vậy thân của lệnh lặp (2) cần thời gian nhiều nhất là O(logn). Do đó lệnh (2) cần thời gian O(nlogn). Vì vậy, thời gian thực hiện HeapSort là O(nlogn). BÀI TẬP. 1. Cho mảng các số nguyên (8, 1, 4, 1, 5, 2, 6, 5). Hãy sắp xếp mảng này bằng cách sử dụng: a. Sắp xếp lựa chọn. b. Sắp xếp xen vào. c. Sắp xếp nổi bọt. d. Sắp xếp nhanh. e. Sắp xếp hoà nhập. f. Sắp xếp sử dụng cây thứ tự bộ phận. Cần đưa ra kết quả thực hiện mỗi bước của thuật toán. 2. Hãy đánh giá thời gian chạy của các thuật toán sắp xếp: a. Sắp xếp lựa chọn. b. Sắp xếp xen vào. c. Sắp xếp nhanh. d. Sắp xếp hoà nhập. Trong các trường hợp sau: a. Mảng đầu vào có tất cả các phần tử có khoá bằng nhau. b. Mảng đầu vào đã được sắp. 3. Viết hàm phân hoạch mảng A[a …b] với phần tử được chọn làm mốc là phần tử đứng giữa mảng, tức là phần tử A[(a + b) / 2]. 206
CÓ THỂ BẠN MUỐN DOWNLOAD
-
Giáo trình cấu trúc dữ liệu và giải thuật_Chương 7: Sắp xếp
16 p | 379 | 253
-
Chương 3: Các phương pháp sắp xếp và tìm kiếm
11 p | 508 | 150
-
Giáo trình giải thuật - tìm kiếm và sắp xếp
0 p | 315 | 130
-
CHƯƠNG 17: SẮP XẾP
25 p | 371 | 125
-
Thuật toán sắp xếp chọn
3 p | 350 | 99
-
Bài giảng cách giải thuật sắp xếp
63 p | 248 | 91
-
Bài toán sắp xếp
7 p | 264 | 78
-
BÀI TẬP LẬP TRÌNH - DEMO CÁC PHƯƠNG PHÁP SẮP XẾP
37 p | 253 | 72
-
Chương 4. SẮP XẾP THỨ TỰ
37 p | 174 | 57
-
Bài toán về sắp xếp
22 p | 117 | 54
-
Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 6: Các thuật toán sắp xếp
54 p | 42 | 20
-
Bài giảng Cấu trúc dữ liệu và thuật toán - Chương 2: Tìm kiếm và sắp xếp
79 p | 27 | 15
-
Sắp xếp danh sách lien ket don
107 p | 72 | 14
-
Bài giảng Lập trình căn bản: Tuần 16 - Bài toán tìm kiếm, sắp xếp
23 p | 81 | 14
-
Bài giảng Các thuật toán sắp xếp
40 p | 20 | 6
-
2.9.Sắp xếp trang trong tập tin bản vẽ
3 p | 90 | 5
-
Bài giảng Các giải thuật tìm kiếm, sắp xếp
98 p | 31 | 4

markdown:
# Chapter 17: SẮP XẾP
Chia sẻ: Chao Hello | Ngày: | Loại File: DOC | Số trang:21
lượt xem 51
download
![](http://image.tlvnimg.com/document/thumbnail/2010/20100920/daodangson01041991/80x100/chuong_17_2107.jpg)
##
Chapter 17: SẮP XẾP
[Vui lòng tải xuống để xem tài liệu đầy đủ](javascript:void(0);)
Download
![](http://static.tlvnimg.com/b2013az/templates/version1/default/images/down16x21.png)
Sắp xếp là một quá trình biến đổi một danh sách các đối tượng thành một danh sách thoả mãn một thứ tự xác định nào đó. Sắp xếp đóng vai trò quan trọng trong tìm kiếm dữ liệu. Chẳng hạn, nếu danh sách đã được sắp xếp theo thứ tự tăng dần (hoặc giảm dần), ta có thể sử dụng kỹ thuật tìm kiếm nhị phân hiệu quả hơn nhiều tìm kiếm tuần tự…
Bình luận(0)
[Đăng nhập để gửi bình luận!](javascript:void(0);)
##
Nội dung Text: Chapter 17: SẮP XẾP
- CHƯƠNG 17 SẮP XẾP Sắp xếp là một quá trình biến đổi một danh sách các đối tượng thành một danh sách thoả mãn một thứ tự xác định nào đó. Sắp xếp đóng vai trò quan trọng trong tìm kiếm dữ liệu. Chẳng hạn, nếu danh sách đã được sắp xếp theo thứ tự tăng dần (hoặc giảm dần), ta có thể sử dụng kỹ thuật tìm kiếm nhị phân hiệu quả hơn nhiều tìm kiếm tuần tự… Trong thiết kế thuật toán, ta cũng thường xuyên cần đến sắp xếp, nhiều thuật toán được thiết kế dựa trên ý tưởng xử lý các đối tượng theo một thứ tự xác định. Các thuật toán sắp xếp được chia làm 2 loại: sắp xếp trong và sắp xếp ngoài. Sắp xếp trong được thực hiện khi mà các đối tượng cần sắp xếp được lưu ở bộ nhớ trong của máy tính dưới dạng mảng. Do đó sắp xếp trong còn được gọi là sắp xếp mảng. Khi các đối tượng cần sắp xếp quá lớn cần lưu ở bộ nhớ ngoài dưới dạng file, ta cần sử dụng các phương pháp sắp xếp ngoài, hay còn gọi là sắp xếp file. Trong chương này, chúng ta trình bày các thuật toán sắp xếp đơn giản, các thuật toán này dòi hỏi thời gian O(n2) để sắp xếp mảng n đối tượng. Sau đó chúng ta đưa ra các thuật toán phức tạp và tinh vi hơn, nhưng hiệu quả hơn, chỉ cần thời gian O(nlogn). Mảng cần được sắp xếp có thể là mảng số nguyên, mảng các số thực, hoặc mảng các xâu ký tự. Trong trường hợp tổng quát, các đối tượng cần được sắp xếp chứa một số thành phần dữ liệu, và ta cần sắp xếp mảng các đối tượng đó theo một thành phần dữ liệu nào đó. Thành phần dữ liệu đó được gọi là khoá sắp xếp. Chẳng hạn, ta có một mảng các đối tượng sinh viên, mỗi sinh viên gồm các thành phần dữ liệu: tên, tuổi, chiều cao,…, và ta muốn sắp xếp các sinh viên theo thứ tự chiều cao tăng, khi đó chiều cao là khoá sắp xếp. 187
- Từ đây về sau, ta giả thiết rằng, mảng cần được sắp xếp là mảng các đối tượng có kiểu Item, trong đó Item là cấu trúc sau: struct Item { keyType key; // Khoá sắp xếp // Các trường dữ liệu khác }; Vấn đề sắp xếp bây giờ được phát biểu chính xác như sau. Cho mảng A[0..n-1] chứa n Item, chúng ta cần sắp xếp lại các thành phần của mảng A sao cho: A[0].key
- A[0] A[1] A[2] A[3] A[4] A[5] I k 5 9 1 8 3 7 0 2 1 9 5 8 3 7 1 4 1 3 5 8 9 7 2 2 1 3 5 8 9 7 3 5 1 3 5 7 9 8 4 5 1 3 5 7 8 9 Sau đây là hàm sắp xếp lựa chọn: void SelectionSort(Item A[] , int n) // Sắp xếp mảng A[0..n-1] với n > 0 { (1) for (int i = 0 ; i < n-1 ; i++) { (2) int k = i; (3) for (int j = i + 1 ; j < n ; j++) (4) if (A[j].key < A[k].key) k = j; (5) swap(A[i],A[k]); } } Trong hàm trên, swap là hàm thực hiện trao đổi giá trị của hai biến. Phân tích sắp xếp lựa chọn. Thân của lệnh lặp (1) là các lệnh (2), (3) và (5). Các lệnh (2) và (5) có thời gian chạy là O(1). Ta đánh giá thời gian chạy của lệnh lặp (3). Số lần lặp là (n-1-i), thời gian thực hiện lệnh (4) là O(1), do đó thời gian chạy của lệnh (3) là (n-1-i)O(1). Như vậy, thân của lệnh lặp (1) có thời gian chạy ở lần lặp thứ i là (n-1-i)O(1). Do đó lệnh lặp (1) đòi hỏi thời gian n −2 ∑ i =0 (n-1-i)O(1) = O(1)(1 + 2 + …+ n-1) = O(1)n(n-1)/2 = O(n2) 189
- Vậy thời gian chạy của hàm sắp xếp lựa chọn là O(n2). 17.1.2 Sắp xếp xen vào Phương pháp sắp xếp xen vào là như sau. Giả sử đoạn đầu của mảng A[0..i-1] (với i >= 1) đã được sắp xếp, tức là ta đã có A[0].key
- { (1) for ( int i = 1 ; i < n ; i++) (2) for ( int k = i ; k > 0 ; k--) (3) if (A[k].key < A[k-1].key) swap(A[k],A[k-1]); else break; } Phân tích sắp xếp xen vào Số lần lặp tối đa của lệnh lặp (2) là i, thân của lệnh lặp (2) là lệnh (3) cần thời gian O(1). Do đó thời gian chạy của lệnh (2) là O(1)i. Thời gian thực hiện lệnh lặp (1) là n −1 ∑ O(1) i = O(1)(1 + 2 + ... + n − 1) = O(n i =1 2 ) 17.1.3 Sắp xếp nổi bọt Ý tưởng của sắp xếp nổi bọt là như sau. Cho chỉ số k chạy từ 0, 1 , …, n-1, nếu hai thành phần kề nhau không đúng trật tự, tức là A[k].key >A[k+1].key thì ta trao đổi hai thành phần A[k] và A[k+1]. Làm như vậy ta đẩy được dữ liệu có khoá lớn nhất lên vị trí sau cùng A[n-1]. Ví dụ. Giả sử ta có mảng số nguyên A[0..4]= (6,1,7,3,5).Kết quả thực hiện quá trình trên được cho trong bảng sau: A[0] A[1] A[2] A[3] A[4] 6 1 7 3 5 Trao đổi A[0] và A[1] 1 6 7 3 5 Trao đổi A[2] và A[3] 1 6 3 7 5 Trao đổi A[3] và A[4] 1 6 3 5 7 191
- Lặp lại quá trình trên đối với mảng A[0,…, n-2] để đẩy dữ liệu có khoá lớn nhất lên vị trí A[n-2]. Khi đó ta có A[n-2].key ≤ A[n-1].key. Tiếp tục lặp lại quá trình đã mô tả trên các đoạn đầu A[0..i], với i = n-3, …,1, ta sẽ thu được mảng được sắp . Ta có hàm sắp xếp nổi bọt như sau: void BubbleSort( Item A[] , int n) { (1) for (int i = n-1 ; i > 0 ; i--) (2) for (int k = 0 ; k < i ; k++) (3) if ( A[k].key > A[k+1].key) Swap(A[k],A[k+1]); } Tương tự như hàm sắp xếp xen vào ,ta có thể đánh giá thời gian chạy của hàm sắp xếp nổi bọt là O(n2 ). Trong hàm BubbleSort khi thực hiện lệnh lặp (1), nếu đến chỉ số i nào đó, n-1 ≥ i > 1, mà đoạn đầu A[0..i] đã được sắp, thì ta có thể dừng. Do đó ta có thể cải tiến hàm BubbleSort bằng cách đưa vào biến sorted, biến này nhận giá trị true nếu A[0..i] đã được sắp và nhận giá trị false nếu ngược lại. Khi sorted nhận giá trị true thì lệnh lặp (1) sẽ dừng lại. void BubbleSort (Item A[] , int n) { for (int i = n-1 ; i > 0 ; i -- ) { bool sorted = true; for( int k = 0 ; k < i ; k++) if (A[k].key > A[k+1].key) { swap (A[k], A[k+1]); sorted = false; } if (sorted) break; } } 192
- 17.2 SẮP XẾP HOÀ NHẬP Thuật toán sắp xếp hoà nhập (MergeSort) là một thuật toán được thết kế bằng kỹ thuật chia - để - trị. Giả sử ta cần sắp xếp mảng A[a..b], trong đó a, b là các số nguyên không âm, a b, a là chỉ số đầu và b là chỉ số cuối của mảng. Ta chia mảng thành hai mảng con bởi chỉ số c nằm giữa a và b ( c = ( a + b ) / 2). Các mảng con A[a..c] và A[c+1…b] được sắp xếp bằng cách gọi đệ quy thủ tục sắp xếp hoà nhập. Sau đó ta hoà nhập hai mảng con A[a…c] và A[c+1…b] đã được sắp thành mảng A[a…b] được sắp. Giả sử Merge(A,a,c,b) là hàm kết hợp hai mảng con đã được sắp A[a..c] và A[c+ 1..b] thành mảng A[a..b] được sắp. Thuật toán sắp xếp hoà nhập được biểu diễn bởi hàm đệ quy sau. void MergeSort( Item A[ ], int a, int b) { if (a < b) { int c = (a + b)/2; MergeSort ( A, a, c ); MergeSort ( A, c+1, b); Merge ( A, a, c, b); } } Công việc còn lại của ta là thiết kế hàm hoà nhập Merge ( A, a, c, b), nhiệm vụ của nó là kết hợp hai nửa mảng đã được sắp A[a…c] và A[ c+1…b] thành mảng được sắp. Ý tưởng của thuật toán hoà nhập là ta đọc lần lượt các thành phần của hai nửa mảng và chép vào mảng phụ B[0..b-a] theo đúng thứ tự tăng dần. Giả sử i là chỉ số chạy trên mảng con A[a…c], i được khởi tạo là a ; j là chỉ số chạy trên mảng con A[c+1..b], j được khởi tạo là c + 1. So sánh A[i] và A[j], nếu A[i].key < A[j].key thì ta chép A[i] vào mảng B và tăng i lên 1, còn nếu ngược lại thì ta chép A[j] vào mảng B va tăng j lên 1. Lặp lại hành động đó cho đến khi i vượt quá c hoặc j vượt quá b. Nếu chỉ số i chưa vượt quá c nhưng j đã vượt quá b 193
- thì ta cần phải chép phần còn lại A[i…c] vào mảng B. Tương tự, nếu i > c, nhưng j ≤ b thì ta cần chép phần còn lại A[j…b] vào mảng B. Chẳng hạn, xét mảng số nguyên A[ 5…14], trong đó A[5…9] và A[10…14] đã được sắp như sau: i j A 10 12 20 31 35 3 5 15 21 26 a=5 6 7 8 c=9 10 11 12 13 14 Bắt đầu i = 5 , j = 10. Vì A[5] > A[10] nên A[10] = 3 được chép vào mảng B và j = 11. Ta lại có A[5] > A[11], nên A[11] = 5 được chép vào mảng B và j = 12. Đến dây A[5] < A[12], ta chép A[5] = 10 vào mảng B và i = 6. Tiếp tục như thế ta nhận được mảng B như sau: B 3 5 10 12 15 20 21 26 0 1 2 3 4 5 6 7 8 9 Đến đây j = 15 > b = 14, còn i = 8 < c = 9, do đó ta chép nốt A[8] = 31 và A[9] = 35 sang B để nhận được mảng B được sắp. Bây giờ chỉ cần chép lại mảng B sang mảng A. Hàm Merge được viết như sau: void Merge( Item A[] , int a , int c , int b) // a, c, b là các số nguyên không âm, a ≤ c ≤ b. // Các mảng con A[a…c] và A[c+1…b] đã được sắp. { int i = a; int j = c + 1; 194
- int k = 0; int n = b – a + 1; Item * B = new Item[n]; (1) while (( i < c +1 ) && ( j < b +1 )) if ( A [i].key < A[j].key) B[k ++] = A[i ++]; else B[k ++] = A[j ++]; (2) while ( i < c + 1) B[k ++] = A[i++]; (3) while ( j < b +1) B[k ++] = A[ j ++]; i = a; (4) for ( k = 0 ; k < n ; k ++) A[i ++] = B [k]; delete [ ] B; } Phân tích sắp xếp hoà nhập. Giả sử mảng cần sắp xếp A[a…b] có độ dài n, n = b – a +1, và T(n) là thời gian chạy của hàm MergeSort (A, a, b). Khi đó thời gian thực hiện mỗi lời gọi đệ quy MergeSort (A, a, c) và MergeSort (A, c + 1, b) là T(n/2). Chúng ta cần đánh gía thời gian chạy của hàm Merge(A, a, c, b). Xem xét hàm Merge ta thấy rằng, các lệnh lặp (1), (2), (3) cần thực hiện tất cả là n lần lặp, mỗi lần lặp chỉ cần thực hiện một số cố định các phép toán. Do đó tổng thời gian của ba lệnh lặp (1), (2), (3) là O(n). Lệnh lặp (4) cần thời gian O(n). Khi thực hiện hàm MergeSort(A, a, b) với a = b, chỉ một phép so sánh phải thực hiện, do đó T(1) = O(1). Từ hàm đệ quy MergeSort và các đánh giá trên, ta có quan hệ đệ quy sau T(1) = O(1) T(n) = 2T(n/2) + O(n) với n>1 Giả sử thời gian thực hiện các phép toán trong mỗi lần lặp ở hàm Merge là hằng số d nào đó, ta có : T(1) ≤ d 195
- T(n) ≤ 2T(n/2) + nd Áp dụng phương pháp thế lặp vào bất đẳng thức trên ta nhận được T(n) ≤ 2T(n/2) + n d ≤ 22 T(n/22) + 2 (n/2)d + n d …… ≤ 2k T(n/2k) + n d + …+ n d (k lần nd) Giả sử k là số nguyên dương lớn nhất sao cho 1 ≤ n / 2k. Khi đó, ta có T(n) ≤ 2k T(1) + n d + … + n d ( k lần n d) T(n) ≤ (k + 1) n d T(n) ≤ (1 + log n) n d Vậy T(n) = O (n log n). 17.3 SẮP XẾP NHANH Trong mục này chúng ta trình bày thuật toán sắp xếp được đưa ra bởi Hoare, nổi tiếng với tên gọi là sắp xếp nhanh (QuickSort). Thời gian chạy của thuật toán này trong trường hợp xấu nhất là O(n2). Tuy nhiên thời gian chạy trung bình là O(n logn). Thuật toán sắp xếp nhanh được thiết kế bởi kỹ thuật chia-để-trị như thuật toán sắp xếp hòa nhập. Nhưng trong thuật toán sắp xếp hòa nhập, mảng A[a…b] cần sắp được chia đơn giản thành hai mảng con A[a..c] và A[c+1..b] bởi điểm chia ở giữa mảng, c = (a+b)/2. Còn trong thuật toán sắp xếp nhanh, việc “chia mảng thành hai mảng con” là một quá trình biến đổi phức tạp để từ mảng A[a..b] ta thu được hai mảng con A[a..k-1] và A[k+1..b] thỏa mãn các tính chất sau : A[i].key ≤ A[k].key với mọi i, a ≤ i ≤ k-1. A[j].key > A[k].key với mọi j, k+1 ≤ j ≤ b. 196
- Nếu thực hiện được sự phân hoạch mảng A[a..b] thành hai mảng con A[a..k-1] và A[k+1..b] thỏa mãn các tính chất trên, thì nếu sắp xếp được các mảng con đó ta sẽ có toàn bộ mảng A[a..b] được sắp xếp. Giả sử Partition(A, a, b, k) là hàm phân hoạch mảng A[a..b] thành hai mảng con A[a..k-1] và A[k+1..b]. Thuật toán sắp xếp nhanh là thuật toán đệ quy được biểu diễn bởi hàm đệ quy như sau : void QuickSort(Item A[] , int a , int b) //Sắp xếp mảng A[a..b] với a ≤ b. { if (a < b) { int k; Partition(A, a, b, k); if (a
- con bằng nhau. Điều này là có thể làm được, tuy nhiên nó đòi hỏi nhiều thời gian hơn sự cần thiết. Vì vậy, ta sẽ chọn ngay thành phần đầu tiên của mảng làm mốc, tức là pivot = A[a].key. Sau đó ta sử dụng hai chỉ số, chỉ số left chạy từ trái sang phải, ban đầu left = a + 1, chỉ số right chạy từ phải sang trái, ban đầu right = b. Biến left sẽ tăng và dừng tại vị trí mà A[left].key > pivot, còn biến right sẽ giảm và dừng lại tại vị trí mà A[right].key ≤ pivot. Khi đó nếu left < right thì ta trao đổi giá trị của A[left] với A[right]. Quá trình trên được lặp lại cho tới khi left > right. Lúc này ta dễ thấy rằng, mọi thành phần trong mảng A[a..right] có khóa nhỏ hơn hay bằng mốc, còn mọi thành phần trong mảng A[left..b] có khóa lớn hơn mốc. Cuối cùng ta trao đổi A[a] và A[right] để đặt mốc vào vị trí k = right. Hàm phân hoạch được viết như sau : void Partition( Item A[] , int a , int b , int & k) { keyType pivot = A[a].key; int left = a + 1; int right = b; do { while (( left
- Để thấy được hàm phân hoạch làm việc như thế nào, ta hãy xét ví dụ sau. Giả sử ta cần phân hoạch mảng số nguyên A[0..9] như sau : 8 3 17 12 6 14 7 5 13 15 left right Lấy mốc pivot = A[0] = 8, ban đầu left = 1, right = 9. Chỉ số left tăng và dừng lại tại vị trí left = 2, vì A[2] = 17 > 8, chỉ số right giảm và dừng lại tại vị trí right = 7, vì A[7] = 5 < 8. Trao đổi A[2] với A[7], đồng thời tăng left lên 1, giảm right đi 1, ta có : 8 3 5 12 6 14 7 1 13 15 7 left right Đến đây A[left] = 12 > 8 và A[right] = 7 < 8. Lại trao đổi A[left] với A[right], và tăng left lên 1, giảm right đi 1, ta có : 8 3 5 7 6 14 1 1 13 15 2 7 left right Tiếp tục, A[left] = 6 < 8 nên left được tăng lên và dừng lại tại left = 5 vì A[5] > 8. A[right] = 14 > 8 nên right được giảm đi và dừng lại tại right = 4, vì A[4] < 8. Ta có hoàn cảnh sau : 8 3 5 7 6 14 1 1 13 15 2 7 right left 199
- Đến đây right < left, ta dừng lại, trao đổi A[0] với A[4] ta thu được phân hoạch với k = right = 4. 6 3 5 7 8 14 1 1 13 15 2 7 k Phân tích sắp xếp nhanh Chúng ta cần đánh giá thời gian chạy T(n) của thuật toán sắp xếp nhanh trên mảng A[a..b] có n phần tử, n = b – a + 1. Trước hết ta cần đánh giá thời gian thực hiện hàm phân hoạch. Thời gian phân hoạch là thời gian đi qua mảng (hai biến left và right chạy từ hai đầu mảng cho tới khi chúng gặp nhau), tại mỗi vị trí mà left và right chạy qua ta cần so sánh thành phần ở vị trí đó với mốc và các trao đổi khi cần thiết. Do đó khi phân hoạch một mảng n phần tử ta chỉ cần thời gian O(n). Thời gian trong trường hợp tốt nhất. Trường hợp tốt nhất xảy ra khi mà sau mỗi lần phân hoạch ta nhận được hai mảng con bằng nhau. Trong trường hợp này, từ hàm đệ quy QuickSort, ta suy ra quan hệ đệ quy sau : T(1) = O(1) T(n) = 2 T(n/2) + O(n) với n > 1. Đây là quan hệ đệ quy mà ta đã gặp khi phân tích sắp xếp hòa nhập. Như vậy trong trường hợp tốt nhất thời gian chạy của QuickSort là O(n logn). Thời gian trong trường hợp xấu nhất. Trường hợp xấu nhất là trường hợp mà sau mỗi lần phân hoạch mảng n phần tử ta nhận được mảng con n – 1 phần tử ở một phía của mốc, còn phía kia không có phần 200
- tử nào. (Dễ thấy rằng trường hợp này xẩy ra khi ta phân hoạch một mảng đã được sắp). Khi đó ta có quan hệ đệ quy sau : T(1) = O(1) T(n) = T(n – 1) + O(n) với n > 1 Ta có : T(1) = C T(n) = T(n – 1) + nC với n > 1 Trong đó C là hằng số nào đó. Bằng cách thế lặp ta có : T(n) = T(1) + 2C + 3C + … + nC n = C ∑i i =1 = Cn(n+1)/2 Do đó trong trường hợp xấu nhất, thời gian chạy của sắp xếp nhanh là O(n2). Thời gian trung bình. Bây giờ ta đánh giá thời gian trung bình Ttb(n) mà QuickSort đòi hòi để sắp xếp một mảng có n phần tử. Giả sử mảng A[a..b] chứa n phần tử được đưa vào mảng một cách ngẫu nhiên. Khi đó hàm phân hoạch Partition(A, a, b, k) sẽ cho ra hai mảng con A[a..k – 1] và A[k + 1..b] với k là một trong các chỉ số từ a đến b với xác suất như nhau và bằng 1/n. Vì thời gian thực hiện hàm phân hoạch là O(n), từ hàm QuickSort ta suy ra quan hệ đệ quy sau : n Ttb(n) = 1 n ∑ k =1 [ Ttb(k - 1) + Ttb(n - k)] + O(n) Hay n Ttb(n) = 1 n ∑ k =1 [ Ttb(k - 1) + Ttb(n - k)] + nC (1) 201
- Trong đó C là hằng số nào đó. Chú ý rằng n n ∑k =1 Ttb(k - 1) = ∑ k =1 Ttb(n - k) Do đó có thể viết lại (1) như sau : n Ttb(n) = 2 n ∑k =1 Ttb(k - 1) + nC (2) Trong (2) thay n bới n – 1 ta có : n −1 Ttb(n - 1) = 2 n−1 ∑ k =1 Ttb(k - 1) + (n – 1)C (3) Nhân (2) với n, nhân (3) với n – 1 và trừ cho nhau ta nhận được n Ttb(n) = (n + 1) Ttb(n - 1) + (2n – 1)C Chia đẳng thức trên cho n(n + 1) ta nhận được quan hệ đệ quy sau : Ttb (n) Ttb (n - 1) 2n - 1 n+1 = n + n ( n+1) C (4) Sử dụng phép thế lặp, từ (4) ta có Ttb (n) Ttb (n - 1) 2n - 1 n+1 = n + n ( n+1) C Ttb (n - 2) 2n - 3 2n - 1 = n−1 + ( n −1) n + n ( n+1) C ... Ttb (n) Ttb (1) n 2i − 1 n+1 = 2 + c ∑ i(i + 1) i =1 (5) Ta có đánh giá 202
- n 2i − 1 n 2 n dx ∑ i(i + 1) ≤ k =1 ∑ i ≤ 2 ∫ x ≤ 2logn i =1 1 Do đó từ (5) ta suy ra Ttb (n) = O(logn) n+1 hay Ttb(n) = O(n logn). Trong trường hợp xấu nhất, QuickSort đòi hỏi thời gian O(n2), nhưng trường hợp này rất ít khi xảy ra. Thời gian trung bình của QuickSort là O(n logn), và thời gian trong trường hợp xấu nhất của MergeSort cũng là O(n logn). Tuy nhiên thực tiễn cho thấy rằng, trong phần lớn các trường hợp QuickSort chạy nhanh hơn các thuật toán sắp xếp khác. 17.4 SẮP XẾP SỬ DỤNG CÂY THỨ TỰ BỘ PHẬN Trong mục này chúng ta trình bày phương pháp sắp xếp sử dụng cây thứ tự bộ phận (heapsort). Trong mục 10.3, chúng ta biết rằng một cây thứ tự bộ phận n đỉnh có thể biểu diễn bởi mảng A[0..n-1], trong đó gốc cây được lưu trong A[0], và nếu một đỉnh được lưu trong A[i], thì đỉnh con trái (nếu có) của nó được lưu trong A[2*i + 1], còn đỉnh con phải nếu có của nó được lưu trong A[2*i + 2]. Mảng A thoả mãn tính chất sau (ta sẽ gọi là tính chất heap): A[i].key
- A[n-1]. Mảng A[0..n-2] bây giờ thoả mãn tính chất heap với mọi i >= 1, trừ i = 0. Biến đổi mảng A[0..n-2] để nó thoả mãn tính chất heap. Lại trao đổi A[0] và A[n-2]. Rồi lại biến đổi mảng A[0..n-3] trở thành mảng thoả mãn tính chất heap. Lặp lại quá trình trên, cuối cùng ta sẽ nhận được mảng A[0..n-1] được sắp theo thứ tự giảm dần: A[0].key >= A[1].key >= … >= A[n-1].key Trong quá trình trên, sau mỗi lần trao đổi A[0] với A[m] (với m=n-1, …,1), ta sẽ nhận được mảng A[0…m-1] thoả mãn tính chất heap với mọi i >= 1, trừ i = 0. Điều này có nghĩa là cây nhị phân được biểu diễn bởi mảng A[0..m-1] đã thoả mãn tính chất thứ tự bộ phận, chỉ trừ gốc. Để nó trở thành cây thứ tự bộ phận, ta chỉ cần đẩy dữ liệu lưu ở gốc xuống vị trí thích hợp trong cây, bằng cách sử dụng hàm ShiftDown (Xem mục 10.3.3). Còn một vấn đề cần giải quyết, đó là biến đổi mảng cần sắp xếp A[0..n-1] thành mảng thoả mãn tính chất heap. Điều này có nghĩa là ta phải biến đổi cây nhị phân được biểu diễn bởi mảng A[0..n-1] thành cây thứ tự bộ phận. Muốn vậy, với i chạy từ n/2-1 giảm xuống 0, ta chỉ cần sử dụng hàm SiftDown để đẩy dữ liệu lưu ở đỉnh i xuống vị trí thíc hợp trong cây. Đây là cách xây dựng cây thứ tự bộ phận mà chúng ta đã trình bày trong 10.3.2. Bây giờ ta viết lại hàm ShiftDown cho thích hợp với sự sử dụng nó trong thuật toán. Giả sử mảng A[a..b] (a < b) đã thoả mãn tính chất heap với mọi i >= a+1. Hàm ShiftDown(a,b) sau đây thực hiện việc đẩy A[a] xuống vị trí thích hợp trong mảng A[a..b] để mảng thoả mãn tính chất heap với mọi i >= a. void ShiftDown(int a, int b) { int i = a; int j = 2 * i + 1; while (j
- { int k = j + 1; if (k A[j].key) { swap(A[i],A[j]); i = j; j = 2 * i + 1; } else break; } } Sử dụng hàm ShiftDown, ta đưa ra thuật toán sắp xếp HeapSort sau đây. Cần lưu ý rằng, kết quả của thuật toán là mảng A[0..n-1] được sắp xếp theo thứ tự giảm dần. void HeapSort(Item A[] , int n) //Sắp xếp mảng A[0..n-1] với n > 1 { for (int i = n / 2 – 1 ; i >= 0 ; i--) ShiftDown(i,n-1); //Biến đổi mảng A[0..n-1] // thành mảng thoả mãn tính chất heap for (int i = n – 1 ; i >= 1 ; i--) { swap(A[0],A[i]); ShiftDown(0,i - 1); } } Phân tích HeapSort. Thời gian thực hiện lệnh lặp (1) là thời gian xây dựng cây thứ tự bộ phận mà chúng ta đã xét trong mục 10.3.2. Theo chứng minh đã đưa ra trong 10.3.2, lệnh lặp (1) chỉ đòi hỏi thời gian O(n). Trong lệnh lặp (2), số lần lặp là n-1. Thân vòng lặp (2), với i = n-1 là 205
- swap(A[0],A[n - 1]); ShiftDown(0,n - 2); Đây là các lệnh thực hiện DeleteMin trên cây thứ tự bộ phận được biểu diễn bởi mảng A[0..n-1], và dữ liêụ có khoá nhỏ nhất được lưu vào A[n- 1]. Trong mục 10.3.1, ta đã chứng tỏ rằng DeleteMin chỉ cần thời gian O(logn). Như vậy thân của lệnh lặp (2) cần thời gian nhiều nhất là O(logn). Do đó lệnh (2) cần thời gian O(nlogn). Vì vậy, thời gian thực hiện HeapSort là O(nlogn). BÀI TẬP. 1. Cho mảng các số nguyên (8, 1, 4, 1, 5, 2, 6, 5). Hãy sắp xếp mảng này bằng cách sử dụng: a. Sắp xếp lựa chọn. b. Sắp xếp xen vào. c. Sắp xếp nổi bọt. d. Sắp xếp nhanh. e. Sắp xếp hoà nhập. f. Sắp xếp sử dụng cây thứ tự bộ phận. Cần đưa ra kết quả thực hiện mỗi bước của thuật toán. 2. Hãy đánh giá thời gian chạy của các thuật toán sắp xếp: a. Sắp xếp lựa chọn. b. Sắp xếp xen vào. c. Sắp xếp nhanh. d. Sắp xếp hoà nhập. Trong các trường hợp sau: a. Mảng đầu vào có tất cả các phần tử có khoá bằng nhau. b. Mảng đầu vào đã được sắp. 3. Viết hàm phân hoạch mảng A[a …b] với phần tử được chọn làm mốc là phần tử đứng giữa mảng, tức là phần tử A[(a + b) / 2]. 206
CÓ THỂ BẠN MUỐN DOWNLOAD
-
Giáo trình cấu trúc dữ liệu và giải thuật_Chương 7: Sắp xếp
16 p |
379 |
253
-
Chương 3: Các phương pháp sắp xếp và tìm kiếm
11 p |
508 |
150
-
Giáo trình giải thuật - tìm kiếm và sắp xếp
0 p |
315 |
130
-
CHƯƠNG 17: SẮP XẾP
25 p |
371 |
125
-
Thuật toán sắp xếp chọn
3 p |
350 |
99
-
Bài giảng cách giải thuật sắp xếp
63 p |
248 |
91
-
Bài toán sắp xếp
7 p |
264 |
78
-
BÀI TẬP LẬP TRÌNH - DEMO CÁC PHƯƠNG PHÁP SẮP XẾP
37 p |
253 |
72
-
Chương 4. SẮP XẾP THỨ TỰ
37 p |
174 |
57
-
Bài toán về sắp xếp
22 p |
117 |
54
-
Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 6: Các thuật toán sắp xếp
54 p |
42 |
20
-
Bài giảng Cấu trúc dữ liệu và thuật toán - Chương 2: Tìm kiếm và sắp xếp
79 p |
27 |
15
-
Sắp xếp danh sách lien ket don
107 p |
72 |
14
-
Bài giảng Lập trình căn bản: Tuần 16 - Bài toán tìm kiếm, sắp xếp
23 p |
81 |
14
-
Bài giảng Các thuật toán sắp xếp
40 p |
20 |
6
-
2.9.Sắp xếp trang trong tập tin bản vẽ
3 p |
90 |
5
-
Bài giảng Các giải thuật tìm kiếm, sắp xếp
98 p |
31 |
4

Server: Apache/2.2.31 (CentOS)

Pragma: no-cache

Cache-Control: no-store, no-cache, must-revalidate, post-check=0, pre-check=0

Set-Cookie: TLDEVNamespace=2uopul8rrr0p3qe25np85s6v72; path=/; domain=.tailieu.vn; HttpOnly


text:
Quyết định số 131/QĐ-TTg
Chia sẻ: Son Pham | Ngày: | Loại File: PDF | Số trang:3
lượt xem 8
download
Quyết định số 131/QĐ-TTg
Quyết định số 131/QĐ-TTg về việc hỗ trợ lãi suất cho các tổ chức, cá nhân vay vốn ngân hàng để sản xuất – kinh doanh do Thủ tướng Chính phủ ban hành
Bình luận(0) Đăng nhập để gửi bình luận!
Nội dung Text: Quyết định số 131/QĐ-TTg
- TH TƯ NG CHÍNH PH C NG HÒA XÃ H I CH NGHĨA VI T NAM ------- c l p – T do – H nh phúc -------------- S : 131/Q -TTg Hà N i, ngày 23 tháng 01 năm 2009 QUY T NNH V VI C H TR LÃI SU T CHO CÁC T CH C, CÁ NHÂN VAY V N NGÂN HÀNG S N XU T – KINH DOANH TH TƯ NG CHÍNH PH Căn c Lu t T ch c Chính ph ngày 25 tháng 12 năm 2001; Căn c Lu t Ngân hàng nhà nư c ngày 12 tháng 12 năm 1997 và Lu t s a i, b sung m t s i u c a Lu t Ngân hàng nhà nư c ngày 17 tháng 6 năm 2003; Căn c Lu t Các t ch c tín d ng ngày 12 tháng 12 năm 1997 và Lu t s a i, b sung m t s i u c a Lu t các t ch c tín d ng ngày 15 tháng 6 năm 2004; Căn c Ngh quy t s 30/2008/NQ-CP ngày 11 tháng 12 năm 2008 c a Chính ph v nh ng gi i pháp c p bách nh m ngăn ch n suy gi m kinh t , duy trì tăng trư ng kinh t , m b o an sinh, xã h i; Xét ngh c a Th ng c Ngân hàng Nhà nư c Vi t Nam, B trư ng B Tài chính, B trư ng B K ho ch và u tư, QUY T NNH: i u 1. Trong năm 2009, Nhà nư c h tr lãi su t cho các t ch c, cá nhân vay v n ngân hàng s n xu t – kinh doanh, nh m gi m giá thành s n phNm hàng hóa, duy trì s n xu t, kinh doanh và t o vi c làm, trong i u ki n n n kinh t b tác ng c a kh ng ho ng tài chính và suy thoái kinh t th gi i. i u 2. i tư ng và ph m vi áp d ng 1. Các t ch c tín d ng cho vay v n i v i các t ch c, cá nhân (g i chung là khách hàng vay) theo quy nh c a pháp lu t, bao g m: các ngân hàng thương m i Nhà nư c, ngân hàng thương m i c ph n, ngân hàng liên doanh, chi nhánh ngân hàng nư c ngoài ho t ng t i Vi t Nam, ngân hàng 100% v n nư c ngoài và Qu Tín d ng nhân dân trung ương (dư i ây g i chung là ngân hàng thương m i). 2. Các kho n vay ng n h n ngân hàng b ng ng Vi t Nam theo các h p ng tín d ng ư c ký k t và gi i ngân trong năm 2009 c a các t ch c (doanh nghi p, h p tác xã, t h p tác, h gia ình …), cá nhân làm v n lưu ng s n xu t – kinh doanh, ư c th ng kê tín d ng theo quy nh c a Ngân hàng Nhà nư c Vi t Nam v ch báo cáo th ng kê; tr các kho n vay thu c ngành, lĩnh v c theo Ph l c kèm theo Quy t nh này. i u 3. Nguyên t c, th i h n, s ti n vay và m c lãi su t h tr 1. Nguyên t c h tr lãi su t là các ngân hàng thương m i cho vay các nhu c u v n lưu ng ho t ng s n xu t – kinh doanh theo cơ ch tín d ng thông thư ng và th c hi n h tr lãi su t theo úng quy nh c a Th tư ng Chính ph và hư ng d n c a Ngân hàng Nhà nư c Vi t Nam; không ư c t ch i h tr lãi su t, n u kho n vay thu c i tư ng ư c h tr lãi su t; nh kỳ báo cáo Ngân hàng Nhà nư c Vi t Nam ki m tra, giám sát tình hình h tr lãi su t. 2. Th i h n vay ư c h tr lãi su t t i a là 08 tháng i v i các kho n vay theo h p ng tín d ng ư c ký k t và gi i ngân trong kho ng th i gian t ngày 01 tháng 02 n ngày 31 tháng 12 năm 2009.
- 3. M c lãi su t h tr cho khách hàng vay là 4%/năm, tính trên s ti n vay và th i h n cho vay th c t n m trong kho ng th i gian quy nh t i kho n 2 i u này; khi thu lãi cho vay, các ngân hàng thương m i gi m tr s ti n lãi ph i tr cho khách hàng vay. i u 4. T ch c th c hi n 1. Quy t nh này có hi u l c thi hành k t ngày ký. 2. Ngân hàng Nhà nư c Vi t Nam ch trì, ph i h p v i B Tài chính hư ng d n và ki m tra, giám sát vi c th c hi n nghiêm Quy t nh này. 3. Trách nhi m c a ngân hàng thương m i và khách hàng vay a) i v i ngân hàng thương m i: - Th c hi n vi c h tr lãi su t cho khách hàng vay theo úng quy nh c a Th tư ng Chính ph và hư ng d n c a Ngân hàng Nhà nư c Vi t Nam; - Trong 10 ngày u tháng 02 năm 2009, g i gi y ăng ký và k ho ch h tr lãi su t cho Ngân hàng Nhà nư c Vi t Nam và th c hi n ngay vi c h tr lãi su t cho khách hàng vay; - Áp d ng cơ ch và lãi su t cho vay thông thư ng khi ký k t h p ng tín d ng; n kỳ h n thu lãi ti n vay c a khách hàng, các ngân hàng thương m i th c hi n vi c gi m tr s ti n lãi b ng 4%/năm tính trên s ti n vay và th i h n cho vay th c t phát sinh trong năm 2009; các ngân hàng thương m i ư c hoàn tr s ti n lãi gi m tr này t Ngân hàng Nhà nư c Vi t Nam trên cơ s báo cáo nh kỳ hàng quý; - Ngày 10 c a tháng u quý g i báo cáo s ti n h tr lãi su t và ăng ký s ti n h tr lãi su t c a quý ti p theo cho Ngân hàng Nhà nư c Vi t Nam. b) Khách hàng vay thu c i tư ng h tr lãi su t g i gi y ngh h tr lãi su t cho các ngân hàng thương m i nơi vay v n ư c h tr lãi su t. 4. Th ng c ngân hàng Nhà nư c Vi t Nam, các B trư ng, Th trư ng cơ quan ngang B , Th trư ng cơ quan thu c Chính ph , Ch t ch y ban nhân dân t nh, thành ph tr c thu c Trung ương, Ch t ch H i ng qu n tr , T ng Giám c các ngân hàng thương m i ch u trách nhi m thi hành Quy t nh này./. KT. TH TƯ NG PHÓ TH TƯ NG Nơi nh n: - Ban Bí thư Trung ương ng; - Th tư ng, các Phó Th tư ng Chính ph ; - Các B , cơ quan ngang B , cơ quan thu c Chính ph ; - Văn phòng BC TW v phòng, ch ng tham nhũng; - H ND, UBND các t nh, thành ph tr c thu c TW; Nguy n Sinh Hùng - Văn phòng Trung ương và các Ban c a ng; - Văn phòng Ch t ch nư c; - H i ng Dân t c và các y ban c a Qu c h i; - Văn phòng Qu c h i; - Tòa án nhân dân t i cao; - Vi n Ki m sát nhân dân t i cao; - Ki m toán Nhà nư c; - UB Giám sát tài chính Qu c gia; - Ngân hàng Chính sách Xã h i; - Ngân hàng Phát tri n Vi t Nam; - UBTW M t tr n T qu c Vi t Nam; - Cơ quan Trung ương c a các oàn th ; - VPCP: BTCN, các PCN, C ng TT T, các V , C c, ơn v tr c thu c, Công báo;
- - Lưu: Văn thư, KTTH (5b). PH L C CÁC KHO N VAY NGÂN HÀNG NG N H N (V N LƯU NG) B NG NG VI T NAM C A KHÁCH HÀNG VAY KHÔNG THU C I TƯ NG H TR LÃI SU T Ư C TH NG KÊ THEO NGÀNH, LĨNH V C (Ban hành kèm theo Quy t nh s 131/Q -TTg ngày 23 tháng 01 năm 2009 c a Th tư ng Chính ph ) 1. Ngành Công nghi p khai thác m . 2. Ho t ng tài chính. 3. Ngành qu n lý nhà nư c và an ninh qu c phòng, ng, oàn th , b o m xã h i b t bu c. 4. Giáo d c và ào t o. 5. Y t và ho t ng c u tr xã h i. 6. Ho t ng văn hóa, th thao. 7. Ho t ng liên quan n kinh doanh tài s n và d ch v tư v n (tr ho t ng u tư xây d ng nhà cho ngư i có thu nh p th p). 8. Ho t ng ph c v cá nhân và công c ng (bao g m c cho vay thông qua th tín d ng). 9. Ho t ng d ch v t i h gia ình. 10. Ho t ng các t ch c qu c t . 11. Nh p khNu nh ng m t hàng tiêu dùng. 12. u tư và kinh doanh ch ng khoán. 13. Kinh doanh b t ng s n dư i hình th c mua, bán quy n s d ng t.
CÓ THỂ BẠN MUỐN DOWNLOAD
-
Quyết định Số: 19/2006/QĐ-BTC Bộ Tài chính
61 p | 3763 | 1154
-
Quyết định số 02/2005/QĐ-NHNN của Ngân hàng Nhà nước
13 p | 300 | 72
-
Quyết định số 24/2006/QĐ-NHNN của Ngân hàng Nhà nước
42 p | 326 | 43
-
Quyết định số 1315/QĐ-TTg
11 p | 251 | 34
-
Quyết định 333/QĐ-TTg của Thủ tướng Chính phủ
2 p | 127 | 9
-
Quyết định số 1325/QĐ-TTg
1 p | 79 | 8
-
Quyết định số 673/QĐ-NHNN
3 p | 90 | 7
-
Quyết định số 596/QĐ-BTC
2 p | 53 | 6
-
Quyết định số 2376/QĐ-BNN-QLCL
10 p | 70 | 6
-
Quyết định số 131/2008/QĐ-BNN
11 p | 59 | 4
-
Công văn 13838/TC/NSNN của Bộ Tài chính đính chính Quyết định số 130/2003/QĐ-BTC ngày 18/8/2003 của Bộ Tài chính
4 p | 122 | 4
-
Quyết định số 131/QĐ-BXD
2 p | 32 | 4
-
Quyết định số 1095/QĐ-BLĐTBXH
2 p | 84 | 3
-
Quyết định số 333/QĐ-TTg
2 p | 53 | 3
-
Quyết định về việc sửa đổi, bổ sung một số điều của Quyết định số 71/1998/QĐ-NHNN21
3 p | 100 | 2
-
Quyết định 673/QĐ-NHNN của Ngân hàng Nhà nước
4 p | 49 | 1
-
Quyết định số: 131/QĐ-BKHĐT
4 p | 29 | 0

markdown:
# Quyết định số 131/QĐ-TTg
Chia sẻ: Son Pham | Ngày: | Loại File: PDF | Số trang:3
lượt xem 8
download
![](http://image.tlvnimg.com/document/thumbnail/2009/20091113/lawttnh11/80x100/3229.jpg)
##
Quyết định số 131/QĐ-TTg
[Vui lòng tải xuống để xem tài liệu đầy đủ](javascript:void(0);)
Download
![](http://static.tlvnimg.com/b2013az/templates/version1/default/images/down16x21.png)
Quyết định số 131/QĐ-TTg về việc hỗ trợ lãi suất cho các tổ chức, cá nhân vay vốn ngân hàng để sản xuất – kinh doanh do Thủ tướng Chính phủ ban hành
Bình luận(0)
[Đăng nhập để gửi bình luận!](javascript:void(0);)
##
Nội dung Text: Quyết định số 131/QĐ-TTg
- TH TƯ NG CHÍNH PH C NG HÒA XÃ H I CH NGHĨA VI T NAM ------- c l p – T do – H nh phúc -------------- S : 131/Q -TTg Hà N i, ngày 23 tháng 01 năm 2009 QUY T NNH V VI C H TR LÃI SU T CHO CÁC T CH C, CÁ NHÂN VAY V N NGÂN HÀNG S N XU T – KINH DOANH TH TƯ NG CHÍNH PH Căn c Lu t T ch c Chính ph ngày 25 tháng 12 năm 2001; Căn c Lu t Ngân hàng nhà nư c ngày 12 tháng 12 năm 1997 và Lu t s a i, b sung m t s i u c a Lu t Ngân hàng nhà nư c ngày 17 tháng 6 năm 2003; Căn c Lu t Các t ch c tín d ng ngày 12 tháng 12 năm 1997 và Lu t s a i, b sung m t s i u c a Lu t các t ch c tín d ng ngày 15 tháng 6 năm 2004; Căn c Ngh quy t s 30/2008/NQ-CP ngày 11 tháng 12 năm 2008 c a Chính ph v nh ng gi i pháp c p bách nh m ngăn ch n suy gi m kinh t , duy trì tăng trư ng kinh t , m b o an sinh, xã h i; Xét ngh c a Th ng c Ngân hàng Nhà nư c Vi t Nam, B trư ng B Tài chính, B trư ng B K ho ch và u tư, QUY T NNH: i u 1. Trong năm 2009, Nhà nư c h tr lãi su t cho các t ch c, cá nhân vay v n ngân hàng s n xu t – kinh doanh, nh m gi m giá thành s n phNm hàng hóa, duy trì s n xu t, kinh doanh và t o vi c làm, trong i u ki n n n kinh t b tác ng c a kh ng ho ng tài chính và suy thoái kinh t th gi i. i u 2. i tư ng và ph m vi áp d ng 1. Các t ch c tín d ng cho vay v n i v i các t ch c, cá nhân (g i chung là khách hàng vay) theo quy nh c a pháp lu t, bao g m: các ngân hàng thương m i Nhà nư c, ngân hàng thương m i c ph n, ngân hàng liên doanh, chi nhánh ngân hàng nư c ngoài ho t ng t i Vi t Nam, ngân hàng 100% v n nư c ngoài và Qu Tín d ng nhân dân trung ương (dư i ây g i chung là ngân hàng thương m i). 2. Các kho n vay ng n h n ngân hàng b ng ng Vi t Nam theo các h p ng tín d ng ư c ký k t và gi i ngân trong năm 2009 c a các t ch c (doanh nghi p, h p tác xã, t h p tác, h gia ình …), cá nhân làm v n lưu ng s n xu t – kinh doanh, ư c th ng kê tín d ng theo quy nh c a Ngân hàng Nhà nư c Vi t Nam v ch báo cáo th ng kê; tr các kho n vay thu c ngành, lĩnh v c theo Ph l c kèm theo Quy t nh này. i u 3. Nguyên t c, th i h n, s ti n vay và m c lãi su t h tr 1. Nguyên t c h tr lãi su t là các ngân hàng thương m i cho vay các nhu c u v n lưu ng ho t ng s n xu t – kinh doanh theo cơ ch tín d ng thông thư ng và th c hi n h tr lãi su t theo úng quy nh c a Th tư ng Chính ph và hư ng d n c a Ngân hàng Nhà nư c Vi t Nam; không ư c t ch i h tr lãi su t, n u kho n vay thu c i tư ng ư c h tr lãi su t; nh kỳ báo cáo Ngân hàng Nhà nư c Vi t Nam ki m tra, giám sát tình hình h tr lãi su t. 2. Th i h n vay ư c h tr lãi su t t i a là 08 tháng i v i các kho n vay theo h p ng tín d ng ư c ký k t và gi i ngân trong kho ng th i gian t ngày 01 tháng 02 n ngày 31 tháng 12 năm 2009.
- 3. M c lãi su t h tr cho khách hàng vay là 4%/năm, tính trên s ti n vay và th i h n cho vay th c t n m trong kho ng th i gian quy nh t i kho n 2 i u này; khi thu lãi cho vay, các ngân hàng thương m i gi m tr s ti n lãi ph i tr cho khách hàng vay. i u 4. T ch c th c hi n 1. Quy t nh này có hi u l c thi hành k t ngày ký. 2. Ngân hàng Nhà nư c Vi t Nam ch trì, ph i h p v i B Tài chính hư ng d n và ki m tra, giám sát vi c th c hi n nghiêm Quy t nh này. 3. Trách nhi m c a ngân hàng thương m i và khách hàng vay a) i v i ngân hàng thương m i: - Th c hi n vi c h tr lãi su t cho khách hàng vay theo úng quy nh c a Th tư ng Chính ph và hư ng d n c a Ngân hàng Nhà nư c Vi t Nam; - Trong 10 ngày u tháng 02 năm 2009, g i gi y ăng ký và k ho ch h tr lãi su t cho Ngân hàng Nhà nư c Vi t Nam và th c hi n ngay vi c h tr lãi su t cho khách hàng vay; - Áp d ng cơ ch và lãi su t cho vay thông thư ng khi ký k t h p ng tín d ng; n kỳ h n thu lãi ti n vay c a khách hàng, các ngân hàng thương m i th c hi n vi c gi m tr s ti n lãi b ng 4%/năm tính trên s ti n vay và th i h n cho vay th c t phát sinh trong năm 2009; các ngân hàng thương m i ư c hoàn tr s ti n lãi gi m tr này t Ngân hàng Nhà nư c Vi t Nam trên cơ s báo cáo nh kỳ hàng quý; - Ngày 10 c a tháng u quý g i báo cáo s ti n h tr lãi su t và ăng ký s ti n h tr lãi su t c a quý ti p theo cho Ngân hàng Nhà nư c Vi t Nam. b) Khách hàng vay thu c i tư ng h tr lãi su t g i gi y ngh h tr lãi su t cho các ngân hàng thương m i nơi vay v n ư c h tr lãi su t. 4. Th ng c ngân hàng Nhà nư c Vi t Nam, các B trư ng, Th trư ng cơ quan ngang B , Th trư ng cơ quan thu c Chính ph , Ch t ch y ban nhân dân t nh, thành ph tr c thu c Trung ương, Ch t ch H i ng qu n tr , T ng Giám c các ngân hàng thương m i ch u trách nhi m thi hành Quy t nh này./. KT. TH TƯ NG PHÓ TH TƯ NG Nơi nh n: - Ban Bí thư Trung ương ng; - Th tư ng, các Phó Th tư ng Chính ph ; - Các B , cơ quan ngang B , cơ quan thu c Chính ph ; - Văn phòng BC TW v phòng, ch ng tham nhũng; - H ND, UBND các t nh, thành ph tr c thu c TW; Nguy n Sinh Hùng - Văn phòng Trung ương và các Ban c a ng; - Văn phòng Ch t ch nư c; - H i ng Dân t c và các y ban c a Qu c h i; - Văn phòng Qu c h i; - Tòa án nhân dân t i cao; - Vi n Ki m sát nhân dân t i cao; - Ki m toán Nhà nư c; - UB Giám sát tài chính Qu c gia; - Ngân hàng Chính sách Xã h i; - Ngân hàng Phát tri n Vi t Nam; - UBTW M t tr n T qu c Vi t Nam; - Cơ quan Trung ương c a các oàn th ; - VPCP: BTCN, các PCN, C ng TT T, các V , C c, ơn v tr c thu c, Công báo;
- - Lưu: Văn thư, KTTH (5b). PH L C CÁC KHO N VAY NGÂN HÀNG NG N H N (V N LƯU NG) B NG NG VI T NAM C A KHÁCH HÀNG VAY KHÔNG THU C I TƯ NG H TR LÃI SU T Ư C TH NG KÊ THEO NGÀNH, LĨNH V C (Ban hành kèm theo Quy t nh s 131/Q -TTg ngày 23 tháng 01 năm 2009 c a Th tư ng Chính ph ) 1. Ngành Công nghi p khai thác m . 2. Ho t ng tài chính. 3. Ngành qu n lý nhà nư c và an ninh qu c phòng, ng, oàn th , b o m xã h i b t bu c. 4. Giáo d c và ào t o. 5. Y t và ho t ng c u tr xã h i. 6. Ho t ng văn hóa, th thao. 7. Ho t ng liên quan n kinh doanh tài s n và d ch v tư v n (tr ho t ng u tư xây d ng nhà cho ngư i có thu nh p th p). 8. Ho t ng ph c v cá nhân và công c ng (bao g m c cho vay thông qua th tín d ng). 9. Ho t ng d ch v t i h gia ình. 10. Ho t ng các t ch c qu c t . 11. Nh p khNu nh ng m t hàng tiêu dùng. 12. u tư và kinh doanh ch ng khoán. 13. Kinh doanh b t ng s n dư i hình th c mua, bán quy n s d ng t.
CÓ THỂ BẠN MUỐN DOWNLOAD
-
Quyết định Số: 19/2006/QĐ-BTC Bộ Tài chính
61 p |
3763 |
1154
-
Quyết định số 02/2005/QĐ-NHNN của Ngân hàng Nhà nước
13 p |
300 |
72
-
Quyết định số 24/2006/QĐ-NHNN của Ngân hàng Nhà nước
42 p |
326 |
43
-
Quyết định số 1315/QĐ-TTg
11 p |
251 |
34
-
Quyết định 333/QĐ-TTg của Thủ tướng Chính phủ
2 p |
127 |
9
-
Quyết định số 1325/QĐ-TTg
1 p |
79 |
8
-
Quyết định số 673/QĐ-NHNN
3 p |
90 |
7
-
Quyết định số 596/QĐ-BTC
2 p |
53 |
6
-
Quyết định số 2376/QĐ-BNN-QLCL
10 p |
70 |
6
-
Quyết định số 131/2008/QĐ-BNN
11 p |
59 |
4
-
Công văn 13838/TC/NSNN của Bộ Tài chính đính chính Quyết định số 130/2003/QĐ-BTC ngày 18/8/2003 của Bộ Tài chính
4 p |
122 |
4
-
Quyết định số 131/QĐ-BXD
2 p |
32 |
4
-
Quyết định số 1095/QĐ-BLĐTBXH
2 p |
84 |
3
-
Quyết định số 333/QĐ-TTg
2 p |
53 |
3
-
Quyết định về việc sửa đổi, bổ sung một số điều của Quyết định số 71/1998/QĐ-NHNN21
3 p |
100 |
2
-
Quyết định 673/QĐ-NHNN của Ngân hàng Nhà nước
4 p |
49 |
1
-
Quyết định số: 131/QĐ-BKHĐT
4 p |
29 |
0

Set-Cookie: TLDEVNamespace=d05hcrlmphmlscd0ebg10nulr4; path=/; domain=.tailieu.vn; HttpOnly