markdown:
# Cấu trúc dữ liệu ( chương 13)
Chia sẻ: Nguyễn Thị Giỏi | Ngày: | Loại File: PDF | Số trang:26
lượt xem 66
download
![](http://image.tlvnimg.com/document/thumbnail/2009/20091105/ntgioi120403/80x100/ctdl_2005_chuong_13_9477.jpg)
##
Cấu trúc dữ liệu ( chương 13)
[Vui lòng tải xuống để xem tài liệu đầy đủ](javascript:void(0);)
Download
![](images/down16x21.png)
Chương này trình bày về các cấu trúc toán học quan trong được gọi là đồ thị. Đồ thị thường được ứng dụng trong rất nhiều lĩnh vực, điều tra xã hội, hóa học, địa lý, kỹ thuật điện.
Bình luận(0)
[Đăng nhập để gửi bình luận!](javascript:void(0);)
##
Nội dung Text: Cấu trúc dữ liệu ( chương 13)
- Chöông 13 – Ñoà thò Chöông 13 – ÑOÀ THÒ Chöông naøy trình baøy veà caùc caáu truùc toaùn hoïc quan troïng ñöôïc goïi laø ñoà thò. Ñoà thò thöôøng ñöôïc öùng duïng trong raát nhieàu lónh vöïc: ñieàu tra xaõ hoäi, hoùa hoïc, ñòa lyù, kyõ thuaät ñieän,…. Chuùng ta seõ tìm hieåu caùc phöông phaùp bieåu ñieãn ñoà thò baèng caùc caáu truùc döõ lieäu vaø xaây döïng moät soá giaûi thuaät tieâu bieåu lieân quan ñeán ñoà thò. 13.1. Neàn taûng toaùn hoïc 13.1.1. Caùc ñònh nghóa vaø ví duï Moät ñoà thò (graph) G goàm moät taäp V chöùa caùc ñænh cuûa ñoà thò, vaø taäp E chöùa caùc caëp ñænh khaùc nhau töø V. Caùc caëp ñænh naøy ñöôïc goïi laø caùc caïnh cuûa G. Neáu e = (ν, µ) laø moät caïnh coù hai ñænh ν vaø µ, thì chuùng ta goïi ν vaø µ naèm treân e, vaø e noái vôùi ν vaø µ. Neáu caùc caëp ñænh khoâng coù thöù töï, G ñöôïc goïi laø ñoà thò voâ höôùng (undirected graph), ngöôïc laïi, G ñöôïïc goïi laø ñoà thò coù höôùng (directed graph). Thoâng thöôøng ñoà thò coù höôùng ñöôïc goïi taét laø digraph, coøn töø graph thöôøng mang nghóa laø ñoà thò voâ höôùng. Caùch töï nhieân ñeå veõ ñoà thò laø bieåu dieãn caùc ñænh baèng caùc ñieåm hoaëc voøng troøn, vaø caùc caïnh baèng caùc ñöôøng thaúng hoaëc caùc cung noái caùc ñænh. Ñoái vôùi ñoà thò coù höôùng thì caùc ñöôøng thaúng hay caùc cung caàn coù muõi teân chæ höôùng. Hình 13.1 minh hoïa moät soá ví duï veà ñoà thò. Ñoà thò thöù nhaát trong hình 13.1 coù caùc thaønh phoá laø caùc ñænh, vaø caùc tuyeán bay laø caùc caïnh. Trong ñoà thò thöù hai, caùc nguyeân töû hydro vaø carbon laø caùc ñænh, caùc lieân keát hoùa hoïc laø caùc caïnh. Hình thöù ba laø moät ñoà thò coù höôùng cho bieát khaû naêng truyeàn nhaän döõ lieäu treân maïng, caùc nuùt cuûa maïng (A, B, …, F) laø caùc ñænh vaø caùc ñöôøng noái caùc nuùt laø coù höôùng. Ñoâi khi caùch choïn taäp ñænh vaø taäp caïnh cho ñoà thò phuï thuoäc vaøo giaûi thuaät maø chuùng ta duøng ñeå giaûi baøi toaùn, chaúng haïn baøi toaùn lieân quan ñeán quy trình coâng vieäc, baøi toaùn xeáp thôøi khoùa bieåu,… Ñoà thò ñöôïc söû duïng ñeå moâ hình hoùa raát nhieàu daïng quaù trình cuõng nhö caáu truùc khaùc nhau. Ñoà thò coù theå bieåu dieãn maïng giao thoâng giöõa caùc thaønh phoá, hoaëc caùc thaønh phaàn cuûa moät maïch in ñieän töû vaø caùc ñöôøng noái giöõa chuùng, hoaëc caáu truùc cuûa moät phaân töû goàm caùc nguyeân töû vaø caùc lieân keát hoùa hoïc. Nhöõng ngöôøi daân trong moät thaønh phoá cuõng coù theå ñöôïc bieåu dieãn bôûi caùc ñænh cuûa ñoà thò maø caùc caïnh laø caùc moái quan heä giöõa hoï. Nhaân vieân trong moät coâng ty coù theå ñöôïc bieåu dieãn trong moät ñoà thò coù höôùng maø caùc caïnh coù höôùng cho bieát moái quan heä cuûa hoï vôùi nhöõng ngöôøi quaûn lyù. Nhöõng ngöôøi naøy cuõng coù theå coù nhöõng moái quan heä “cuøng laøm vieäc” bieåu dieãn bôûi caùc caïnh khoâng höôùng trong moät ñoà thò voâ höôùng. Giaùo trình Caáu truùc döõ lieäu vaø Giaûi thuaät 339
- Chöông 13 – Ñoà thò Hình 13.1 – Caùc ví duï veà ñoà thò 13.1.2. Ñoà thò voâ höôùng Moät vaøi daïng cuûa ñoà thò voâ höôùng ñöôïc minh hoïa trong hình 13.2. Hai ñænh trong moät ñoà thò voâ höôùng ñöôïc goïi laø keà nhau (adjacent) neáu toàn taïi moät caïnh noái töø ñænh naøy ñeán ñænh kia. Trong ñoà thò voâ höôùng trong hình 13.2 a, ñænh 1 vaø 2 laø keà nhau, ñænh 3 vaø 4 laø keà nhau, nhöng ñænh 1 vaø ñænh 4 khoâng keà nhau. Moät ñöôøng ñi (path) laø moät daõy caùc ñænh khaùc nhau, trong ñoù moãi ñænh keà vôùi ñænh keá tieáp. Hình (b) cho thaáy moät ñöôøng ñi. Moät chu trình (cycle) laø moät ñöôøng ñi chöùa ít nhaát ba ñænh sao cho ñænh cuoái cuøng keà vôùi ñænh ñaàu tieân. Hình (c) laø moät chu trình. Moät ñoà thò ñöôïc goïi laø lieân thoâng (connected) neáu luoân coù moät ñöôøng ñi töø moät ñænh baát kyø ñeán moät ñænh baát kyø naøo khaùc. Hình (a), (b), vaø (c) laø caùc ñoà thò lieân thoâng. Hình (d) khoâng phaûi laø ñoà thò lieân thoâng. Neáu moät ñoà thò laø khoâng lieân thoâng, chuùng ta xem moãi taäp con lôùn nhaát caùc ñænh lieân thoâng nhau nhö moät thaønh phaàn lieân thoâng. Ví duï, ñoà thò khoâng lieân thoâng ôû hình (d) coù hai thaønh phaàn lieân thoâng: moät thaønh phaàn chöùa caùc ñænh 1,2 vaø 4; moät thaønh phaàn chæ coù ñænh 3. Hình 13.2 – Caùc daïng cuûa ñoà thò voâ höôùng Giaùo trình Caáu truùc döõ lieäu vaø Giaûi thuaät 340
- Chöông 13 – Ñoà thò Phaàn (e) laø moät ñoà thò lieân thoâng khoâng coù chu trình. Chuùng ta coù theå nhaän thaáy ñoà thò cuoái cuøng naøy thöïc söï laø moät caây, vaø chuùng ta duøng ñaëc tính naøy ñeå ñònh nghóa: Moät caây töï do (free tree) ñöôïc ñònh nghóa laø moät ñoà thò voâ höôùng lieân thoâng khoâng coù chu trình. 13.1.3. Ñoà thò coù höôùng Ñoái vôùi caùc ñoà thò coù höôùng, chuùng ta coù theå coù nhöõng ñònh nghóa töông töï. Chuùng ta yeâu caàu moïi caïnh trong moät ñöôøng ñi hoaëc moät chu trình ñeàu coù cuøng höôùng, nhö vaäy vieäc laàn theo moät ñöôøng ñi hoaëc moät chu trình coù nghóa laø phaûi di chuyeån theo höôùng chæ bôûi caùc muõi teân. Nhöõng ñöôøng ñi (hay chu trình) nhö vaäy ñöôïc goïi laø ñöôøng ñi coù höôùng (hay chu trình coù höôùng). Moät ñoà thò coù höôùng ñöôïc goïi laø lieân thoâng maïnh (strongly connected) neáu noù luoân coù moät ñöôøng ñi coù höôùng töø moät ñænh baát kyø ñeán moät ñænh baát kyø naøo khaùc. Trong moät ñoà thò coù höôùng khoâng lieân thoâng maïnh, neáu boû qua chieàu cuûa caùc caïnh maø chuùng ta coù ñöôïc moät ñoà thò voâ höôùng lieân thoâng thì ñoà thò coù höôùng ban ñaàu ñöôïc goïi laø ñoà thò lieân thoâng yeáu (weakly connected). Hình 13.3 minh hoïa moät chu trình coù höôùng, moät ñoà thò coù höôùng lieân thoâng maïnh vaø moät ñoà thò coù höôùng lieân thoâng yeáu. Hình 13.3 – Caùc ví duï veà ñoà thò coù höôùng Caùc ñoà thò coù höôùng trong phaàn (b) vaø (c) hình 13.3 coù caùc caëp ñænh coù caùc caïnh coù höôùng theo caû hai chieàu giöõa chuùng. Caùc caïnh coù höôùng laø caùc caëp coù thöù töï vaø caùc caëp coù thöù töï (ν, µ) vaø (µ,ν) laø khaùc nhau neáu ν ≠ µ. Trong ñoà thò voâ höôùng, chæ coù theå coù nhieàu nhaát moät caïnh noái hai ñænh khaùc nhau. Töông töï, do caùc ñænh treân moät caïnh theo ñònh nghóa laø phaûi khaùc nhau, khoâng theå coù moät caïnh noái moät ñænh vôùi chính noù. Tuy nhieân, cuõng coù nhöõng tröôøng hôïp môû roäng ñònh nghóa, ngöôøi ta cho pheùp nhieàu caïnh noái moät caëp ñænh, vaø moät caïnh noái moät ñænh vôùi chính noù. 13.2. Bieåu dieãn baèng maùy tính Neáu chuùng ta chuaån bò vieát chöông trình ñeå giaûi quyeát moät baøi toaùn coù lieân quan ñeán ñoà thò, tröôùc heát chuùng ta phaûi tìm caùch ñeå bieåu dieãn caáu truùc toaùn hoïc cuûa ñoà thò nhö laø moät daïng naøo ñoù cuûa caáu truùc döõ lieäu. Coù nhieàu phöông phaùp Giaùo trình Caáu truùc döõ lieäu vaø Giaûi thuaät 341
- Chöông 13 – Ñoà thò ñöôïc duøng phoå bieán, veà cô baûn chuùng khaùc nhau trong vieäc löïa choïn kieåu döõ lieäu tröøu töôïng ñeå bieåu dieãn ñoà thò, cuõng nhö nhieàu caùch hieän thöïc khaùc nhau cho moãi kieåu döõ lieäu tröøu töôïng. Noùi caùch khaùc, chuùng ta baét ñaàu töø moät ñònh nghóa toaùn hoïc, ñoù laø ñoà thò, sau ñoù chuùng ta tìm hieåu caùch moâ taû noù nhö moät kieåu döõ lieäu tröøu töôïng (taäp hôïp, baûng, hay danh saùch ñeàu coù theå duøng ñöôïc), vaø cuoái cuøng chuùng ta löïa choïn caùch hieän thöïc cho kieåu döõ lieäu tröøu töôïng maø chuùng ta choïn. 13.2.1. Bieåu dieãn cuûa taäp hôïp Ñoà thò ñöôïc ñònh nghóa baèng moät taäp hôïp, nhö vaäy moät caùch heát söùc töï nhieân laø duøng taäp hôïp ñeå xaùc ñònh caùch bieåu dieãn noù nhö laø döõ lieäu. Tröôùc tieân, chuùng ta coù moät taäp caùc ñænh, vaø thöù hai, chuùng ta coù caùc caïnh nhö laø taäp caùc caëp ñænh. Thay vì thöû bieåu dieãn taäp caùc caëp ñænh naøy moät caùch tröïc tieáp, chuùng ta chia noù ra thaønh nhieàu phaàn nhoû baèng caùch xem xeùt taäp caùc caïnh lieân quan ñeán töøng ñænh rieâng reõ. Noùi moät caùch khaùc, chuùng ta coù theå bieát ñöôïc taát caû caùc caïnh trong ñoà thò baèng caùch naém giöõ taäp Eν caùc caïnh coù chöùa ν ñoái vôùi moãi ñænh ν trong ñoà thò, hoaëc, moät caùch töông ñöông, taäp Aν goàm taát caû caùc ñænh keà vôùi ν. Thaät vaäy, chuùng ta coù theå duøng yù töôûng naøy ñeå ñöa ra moät ñònh nghóa môùi töông ñöông cho ñoà thò: Ñònh nghóa: Moät ñoà thò coù höôùng G bao goàm taäp V, goïi laø caùc ñænh cuûa G, vaø, ñoái vôùi moïi ν ∈ V, coù moät taäp con Aν , goïi laø taäp caùc ñænh keà cuûa ν. Töø caùc taäp con Aν chuùng ta coù theå taùi taïo laïi caùc caïnh nhö laø caùc caëp coù thöù töï theo quy taéc sau: caëp (ν, w) laø moät caïnh neáu vaø chæ neáu w∈ Aν. Xöû lyù cho taäp caùc ñænh deã hôn laø taäp caùc caïnh. Ngoaøi ra, ñònh nghóa môùi naøy thích hôïp vôùi caû ñoà thò coù höôùng vaø ñoà thò voâ höôùng. Moät ñoà thò laø voâ höôùng khi noù thoûa tính chaát ñoái xöùng sau: w∈ Aν keùo theo ν∈ Aw vôùi moïi ν, w∈V. Tính chaát naøy coù theå ñöôïc phaùt bieåu laïi nhö sau: Moät caïnh khoâng coù höôùng giöõa ν vaø w coù theå ñöôïc xem nhö hai caïnh coù höôùng, moät töø ν ñeán w vaø moät töø w ñeán ν. 13.2.1.1. Hieän thöïc caùc taäp hôïp Coù nhieàu caùch ñeå hieän thöïc taäp caùc ñænh trong caáu truùc döõ lieäu vaø giaûi thuaät. Caùch thöù nhaát laø bieåu dieãn taäp caùc ñænh nhö laø moät danh saùch caùc phaàn töû cuûa noù, chuùng ta seõ tìm hieåu phöông phaùp naøy sau. Caùch thöù hai, thöôøng goïi laø chuoãi caùc bit (bit string), löu moät trò Boolean cho moãi phaàn töû cuûa taäp hôïp ñeå chæ ra raèng noù coù hay khoâng coù trong taäp hôïp. Ñeå ñôn giaûn, chuùng ta seõ xem caùc phaàn töû coù theå coù cuûa taäp hôïp ñöôïc ñaùnh chæ soá töø 0 ñeán max_set-1, vôùi max_set laø soá phaàn töû toái ña cho pheùp. Ñieàu naøy coù theå ñöôïc hieän thöïc moät caùch deã daøng baèng caùch söû duïng thö vieän chuaån (Standard Template Library- STL) Giaùo trình Caáu truùc döõ lieäu vaø Giaûi thuaät 342
- Chöông 13 – Ñoà thò std::bitset, hoaëc lôùp coù söû duïng template cho kích thöôùc taäp hôïp cuûa chuùng ta nhö sau: template struct Set { bool is_element[max_set]; }; Ñaây chæ laø moät caùch hieän thöïc ñôn giaûn nhaát cuûa khaùi nieäm taäp hôïp. Sinh vieân coù theå thaáy raèng khoâng coù gì ngaên caûn chuùng ta ñaëc taû vaø hieän thöïc moät CTDL taäp hôïp vôùi caùc phöông thöùc hoäi, giao, hieäu, xeùt thaønh vieân cuûa noù,…, moät caùch hoaøn chænh neáu nhö caàn söû duïng taäp hôïp trong nhöõng baøi toaùn lôùn naøo ñoù. Giôø chuùng ta ñaõ coù theå ñaëc taû caùch bieåu dieãn thöù nhaát cho ñoà thò cuûa chuùng ta: // Töông öùng hình 13.4-b template class Digraph { // Soá ñænh cuûa ñoà thò, nhieàu nhaát laø max_size int count; Set neighbors[max_size]; }; Trong caùch hieän thöïc naøy, caùc ñænh ñöôïc ñaët teân baèng caùc soá nguyeân töø 0 ñeán count-1. Neáu ν laø moät soá nguyeân thì phaàn töû neighbors[ν] cuûa maûng laø moät taäp caùc ñænh keà vôùi ñænh ν. 13.2.1.2. Baûng keà Trong caùch hieän thöïc treân ñaây, caáu truùc Set ñöôïc hieän thöïc nhö moät maûng caùc phaàn töû kieåu bool. Moãi phaàn töû chæ ra raèng ñænh töông öùng coù laø thaønh phaàn cuûa taäp hôïp hay khoâng. Neáu chuùng ta thay theá taäp caùc ñænh keà naøy baèng moät maûng, chuùng ta seõ thaáy raèng maûng neighbors trong ñònh nghóa cuûa lôùp Graph coù theå ñöôïc bieán ñoåi thaønh maûng caùc maûng (maûng hai chieàu) nhö sau ñaây, vaø chuùng ta goïi laø baûng keà (adjacency table): // Töông öùng hình 13.4-c template class Digraph { // Soá ñænh cuûa ñoà thò, nhieàu nhaát laø max_size. int count; bool adjacency[max_size][max_size]; }; Giaùo trình Caáu truùc döõ lieäu vaø Giaûi thuaät 343
- Chöông 13 – Ñoà thò Baûng keà chöùa caùc thoâng tin moät caùch töï nhieân nhö sau: adjacency[v][w] laø true neáu vaø chæ neáu ñænh v laø ñænh keà cuûa w. Neáu laø ñoà thò coù höôùng, adjacency[v][w] cho bieát caïnh töø v ñeán w coù trong ñoà thò hay khoâng. Neáu ñoà thò voâ höôùng, baûng keà phaûi ñoái xöùng, nghóa laø adjacency[v][w]= adjacency[v][w] vôùi moïi v vaø w. Bieåu dieãn ñoà thò bôûi taäp caùc ñænh keà vaø bôûi baûng keà ñöôïc minh hoïa trong hình 13.4. (a) (b) (c) Hình 13.4 – Taäp caùc ñænh keà vaø baûng keà. 13.2.2. Danh saùch keà Moät caùch khaùc ñeå bieåu dieãn moät taäp hôïp laø duøng danh saùch caùc phaàn töû. Chuùng ta coù moät danh saùch caùc ñænh, vaø, ñoái vôùi moãi ñænh, coù moät danh saùch caùc ñænh keà. Chuùng ta coù theå xem xeùt caùch hieän thöïc cho ñoà thò baèng danh saùch lieân tuïc hoaëc danh saùch lieân keát ñôn. Tuy nhieân, ñoái vôùi nhieàu öùng duïng, ngöôøi ta thöôøng söû duïng caùc hieän thöïc khaùc cuûa danh saùch phöùc taïp hôn nhö caây nhò phaân tìm kieám, caây nhieàu nhaùnh tìm kieám, hoaëc laø heap. Löu yù raèng, baèng caùch ñaët teân caùc ñænh theo caùc chæ soá trong caùc caùch hieän thöïc tröôùc ñaây, chuùng ta cuõng coù ñöôïc caùch hieän thöïc cho taäp caùc ñænh nhö laø moät danh saùch lieân tuïc. 13.2.2.1. Hieän thöïc döïa treân cô sôû laø danh saùch Chuùng ta coù ñöôïc hieän thöïc cuûa ñoà thò döïa treân cô sôû laø danh saùch baèng caùch thay theá caùc taäp hôïp ñænh keà tröôùc kia baèng caùc danh saùch. Hieän thöïc naøy coù theå söû duïng hoaëc danh saùch lieân tuïc hoaëc danh saùch lieân keát. Phaàn (b) vaø (c) cuûa hình 13.5 minh hoïa hai caùch hieän thöïc naøy. // Toång quaùt cho caû danh saùch lieân tuïc laãn lieân keát (hình 13.5-b vaø c). typedef int Vertex; template class Digraph { // Soá ñænh cuûa ñoà thò, nhieàu nhaát laø max_size. int count; List neighbors[max_size]; }; Giaùo trình Caáu truùc döõ lieäu vaø Giaûi thuaät 344
- Chöông 13 – Ñoà thò 13.2.2.2. Hieän thöïc lieân keát Baèng caùch söû duïng caùc ñoái töôïng lieân keát cho caû caùc ñænh vaø cho caû caùc danh saùch keà, ñoà thò seõ coù ñöôïc tính linh hoaït cao nhaát. Hieän thöïc naøy ñöôïc minh hoïa trong hình 13.5-a vaø coù caùc ñònh nghóa nhö sau: Hình 13.5 – Hieän thöïc ñoà thò baèng caùc danh saùch class Edge; class Vertex { Chæ ñeán phaàn töû ñaàu cuûa DSLK caùc ñænh keà. Edge *first_edge; // Chæ ñeán phaàn töû keá trong DSLK caùc ñænh coù trong ñoà thò. Vertex *next_vertex; // }; class Edge { Chæ ñeán moät ñænh keà vôùi ñænh maø danh saùch naøy thuoäc veà. Vertex *end_point; // Chæ ñeán phaàn töû bieåu dieãn ñænh keà keá tieáp trong danh saùch caùc Edge *next_edge; // ñænh keà vôùi moät ñænh maø danh saùch naøy thuoäc veà. }; Giaùo trình Caáu truùc döõ lieäu vaø Giaûi thuaät 345
- Chöông 13 – Ñoà thò class Digraph { Chæ ñeán phaàn töû ñaàu tieân trong danh saùch caùc ñænh cuûa ñoà thò. Vertex *first_vertex;// }; 13.2.3. Caùc thoâng tin khaùc trong ñoà thò Nhieàu öùng duïng veà ñoà thò khoâng nhöõng caàn nhöõng thoâng tin veà caùc ñænh keà cuûa moät ñænh maø coøn caàn theâm moät soá thoâng tin khaùc lieân quan ñeán caùc ñænh cuõng nhö caùc caïnh. Trong hieän thöïc lieân keát, caùc thoâng tin naøy coù theå ñöôïc löu nhö caùc thuoäc tính boå sung beân trong caùc baûn ghi töông öùng, vaø trong hieän thöïc lieân tuïc, chuùng coù theå ñöôïc löu trong caùc maûng caùc phaàn töû beân trong caùc baûn ghi. Laáy ví duï tröôøng hôïp maïng caùc maùy tính, noù ñöôïc ñònh nghóa nhö moät ñoà thò trong ñoù moãi caïnh coù theâm thoâng tin laø taûi troïng cuûa ñöôøng truyeàn töø maùy naøy qua maùy khaùc. Ñoái vôùi nhieàu giaûi thuaät treân maïng, caùch bieåu dieãn toát nhaát laø duøng baûng keà, trong ñoù caùc phaàn töû seõ chöùa taûi troïng thay vì moät trò kieåu bool. Chuùng ta seõ quay laïi vaán ñeà naøy sau trong chöông naøy. 13.3. Duyeät ñoà thò 13.3.1. Caùc phöông phaùp Trong nhieàu baøi toaùn, chuùng ta mong muoán ñöôïc khaûo saùt caùc ñænh trong ñoà thò theo moät thöù töï naøo ñoù. Töïa nhö ñoái vôùi caây nhò phaân chuùng ta ñaõ phaùt trieån moät vaøi phöông phaùp duyeät qua caùc phaàn töû moät caùch coù heä thoáng. Khi duyeät caây, chuùng ta thöôøng baét ñaàu töø nuùt goác. Trong ñoà thò, thöôøng khoâng coù ñænh naøo laø ñænh ñaëc bieät, neân vieäc duyeät qua ñoà thò coù theå baét ñaàu töø moät ñænh baát kyø naøo ñoù. Tuy coù nhieàu thöù töï khaùc nhau ñeå duyeät qua caùc ñænh cuûa ñoà thò, coù hai phöông phaùp ñöôïc xem laø ñaëc bieät quan troïng. Phöông phaùp duyeät theo chieàu saâu (depth-first traversal) treân moät ñoà thò gaàn gioáng vôùi pheùp duyeät preorder cho moät caây coù thöù töï. Giaû söû nhö pheùp duyeät vöøa duyeät xong ñænh ν, vaø goïi w1, w2,...,wk laø caùc ñænh keà vôùi ν, thì w1 laø ñænh ñöôïc duyeät keá tieáp, trong khi caùc ñænh w2,...,wk seõ naèm ñôïi. Sau khi duyeät qua ñænh w1 chuùng ta seõ duyeät qua taát caû caùc ñænh keà vôùi w1, tröôùc khi quay laïi vôùi w2,...,wk. Phöông phaùp duyeät theo chieàu roäng (breadth-first traversal) treân moät ñoà thò gaàn gioáng vôùi pheùp duyeät theo möùc (level by level) cho moät caây coù thöù töï. Neáu pheùp duyeät vöøa duyeät xong ñænh ν, thì taát caû caùc ñænh keà vôùi ν seõ ñöôïc duyeät tieáp sau ñoù, trong khi caùc ñænh keà vôùi caùc ñænh naøy seõ ñöôïc ñaët vaøo moät danh saùch chôø, chuùng seõ ñöôïc duyeät tôùi chæ sau khi taát caû caùc ñænh keà vôùi ν ñaõ ñöôïc duyeät xong. Giaùo trình Caáu truùc döõ lieäu vaø Giaûi thuaät 346
- Chöông 13 – Ñoà thò Hình 13.6 minh hoïa hai phöông phaùp duyeät treân, caùc con soá taïi caùc ñænh bieåu dieãn thöù töï maø chuùng ñöôïc duyeät ñeán. Hình 13.6 - Duyeät ñoà thò 13.3.2. Giaûi thuaät duyeät theo chieàu saâu Phöông phaùp duyeät theo chieàu saâu thöôøng ñöôïc xaây döïng nhö moät giaûi thuaät ñeä quy. Caùc coâng vieäc caàn laøm khi gaëp moät ñænh ν laø: visit(v); for (moãi ñænh w keà vôùi ñænh v) traverse(w); Tuy nhieân, trong pheùp duyeät ñoà thò, coù hai ñieåm khoù khaên maø trong pheùp duyeät caây khoâng coù. Thöù nhaát, ñoà thò coù theå chöùa chu trình, vaø giaûi thuaät cuûa chuùng ta coù theå gaëp laïi moät ñænh laàn thöù hai. Ñeå ngaên chaën ñeä quy voâ taän, chuùng ta duøng moät maûng caùc phaàn töû kieåu bool visited, visited[v] seõ laø true khi v vöøa ñöôïc duyeät xong, vaø chuùng ta luoân xeùt trò cuûa visited[w] tröôùc khi xöû lyù cho w, neáu trò naøy ñaõ laø true thì w khoâng caàn xöû lyù nöõa. Ñieàu khoù khaên thöù hai laø, ñoà thò coù theå khoâng lieân thoâng, vaø giaûi thuaät duyeät coù theå khoâng ñaït ñöôïc ñeán taát caû caùc ñænh cuûa ñoà thò neáu chæ baét ñaàu ñi töø moät ñænh. Do ñoù chuùng ta caàn thöïc hieän moät voøng laëp ñeå coù theå baét ñaàu töø moïi ñænh trong ñoà thò, nhôø vaäy chuùng ta seõ khoâng boû soùt moät ñænh naøo. Vôùi nhöõng phaân tích treân, chuùng ta coù phaùc thaûo cuûa giaûi thuaät duyeät ñoà thò theo chieàu saâu döôùi ñaây. Chi tieát hôn cho giaûi thuaät coøn phuï thuoäc vaøo caùch choïn löïa hieän thöïc cuûa ñoà thò vaø caùc ñænh, vaø chuùng ta ñeå laïi cho caùc chöông trình öùng duïng. template void Digraph::depth_first(void (*visit)(Vertex &)) const /* post: Haøm *visit ñöôïc thöïc hieän taïi moãi ñænh cuûa ñoà thò moät laàn, theo thöù töï duyeät theo chieàu saâu. uses: Haøm traverse thöïc hieän duyeät theo chieàu saâu. */ Giaùo trình Caáu truùc döõ lieäu vaø Giaûi thuaät 347
- Chöông 13 – Ñoà thò { bool visited[max_size]; Vertex v; for (all v in G) visited[v] = false; for (all v in G) if (!visited[v]) traverse(v, visited, visit); } Vieäc ñeä quy ñöôïc thöïc hieän trong haøm phuï trôï traverse. Do haøm naøy caàn truy nhaäp vaøo caáu truùc beân trong cuûa ñoà thò, noù phaûi laø haøm thaønh vieân cuûa lôùp Digraph. Ngoaøi ra, do traverse laø moät haøm phuï trôï vaø chæ ñöôïc söû duïng trong phöông thöùc depth_first, noù neân ñöôïc khai baùo private beân trong lôùp. template void Digraph::traverse(Vertex &v, bool visited[], void (*visit)(Vertex &)) const /* pre: v laø moät ñænh cuûa ñoà thò Digraph. post: Duyeät theo chieàu saâu, haøm *visit seõ ñöôïc thöïc hieän taïi v vaø taïi taát caû caùc ñænh coù theå ñeán ñöôïc töø v. uses: Haøm traverse moät caùch ñeä quy. */ { Vertex w; visited[v] = true; (*visit)(v); for (all w adjacent to v) if (!visited[w]) traverse(w, visited, visit); } 13.3.3. Giaûi thuaät duyeät theo chieàu roäng Do söû duïng ñeä quy vaø laäp trình vôùi ngaên xeáp veà baûn chaát laø töông ñöông, chuùng ta coù theå xaây döïng giaûi thuaät duyeät theo chieàu saâu baèng caùch söû duïng ngaên xeáp. Khi moät ñænh ñang ñöôïc duyeät thì caùc ñænh keà cuûa noù ñöôïc ñaåy vaøo ngaên xeáp, khi moät ñænh vöøa ñöôïc duyeät xong thì ñænh keá tieáp caàn duyeät laø ñænh ñöôïc laáy ra töø ngaên xeáp. Giaûi thuaät duyeät theo chieàu roäng cuõng töông töï nhö giaûi thuaät vöøa ñöôïc ñeà caäp ñeán trong vieäc duyeät theo chieàu saâu, tuy nhieân haøng ñôïi caàn ñöôïc söû duïng thay cho ngaên xeáp. template void Digraph::breadth_first(void (*visit)(Vertex &)) const /* post: Haøm *visit ñöôïc thöïc hieän taïi moãi ñænh cuûa ñoà thò moät laàn, theo thöù töï duyeät theo chieàu roäng. uses: Caùc phöông thöùc cuûa lôùp Queue. */ { Queue q; bool visited[max_size]; Vertex v, w, x; for (all v in G) visited[v] = false; Giaùo trình Caáu truùc döõ lieäu vaø Giaûi thuaät 348
- Chöông 13 – Ñoà thò for (all v in G) if (!visited[v]) { q.append(v); while (!q.empty()){ q.retrieve(w); if (!visited[w]) { visited[w] = true; (*visit)(w); for (all x adjacent to w) q.append(x); } q.serve(); } } } 13.4. Saép thöù töï topo 13.4.1. Ñaët vaán ñeà Neáu G laø moät ñoà thò coù höôùng khoâng coù chu trình, thì thöù töï topo (topological order) cuûa G laø moät caùch lieät keâ tuaàn töï moïi ñænh trong G sao cho, vôùi moïi ν, µ∈G, neáu coù moät caïnh töø ν ñeán µ, thì ν naèm tröôùc µ. Trong suoát phaàn naøy, chuùng seõ chæ xem xeùt caùc ñoà thò coù höôùng khoâng coù chu trình. Thuaät ngöõ acyclic coù nghóa laø moät ñoà thò khoâng coù chu trình. Caùc ñoà thò nhö vaäy xuaát hieän trong raát nhieàu baøi toaùn. Nhö moät ví duï ñaàu tieân veà thöù töï topo, chuùng ta haõy xem xeùt caùc moân hoïc trong moät tröôøng ñaïi hoïc nhö laø caùc ñænh cuûa ñoà thò, trong ñoù moät caïnh noái töø moân naøy ñeán moân kia coù nghóa laø moân thöù nhaát laø moân tieân quyeát cuûa moân thöù hai. Nhö vaäy thöù töï topo seõ lieät keâ taát caû caùc moân sao cho moïi moân tieân quyeát cuûa moät moân seõ naèm tröôùc moân ñoù. Ví duï thöù hai laø töø ñieån caùc thuaät ngöõ kyõ thuaät. Caùc töø trong töø ñieån ñöôïc saép thöù töï sao cho khoâng coù töø naøo ñöôïc söû duïng trong moät ñònh nghóa cuûa töø khaùc tröôùc khi chính noù ñöôïc ñònh nghóa. Töông töï, caùc taùc giaû cuûa caùc saùch söû duïng thöù töï topo cho caùc ñeà muïc trong saùch. Hai thöù töï topo khaùc nhau cuûa moät ñoà thò coù höôùng ñöôïc minh hoïa trong hình 13.7. Chuùng ta seõ xaây döïng haøm ñeå sinh ra thöù töï topo cho caùc ñænh cuûa moät ñoà thò khoâng coù chu trình theo hai caùch: söû duïng pheùp duyeät theo chieàu saâu vaø pheùp duyeät theo chieàu roäng. Caû hai phöông phaùp ñöôïc duøng cho moät ñoái töôïng cuûa lôùp Digraph söû duïng hieän thöïc döïa treân cô sôû laø danh saùch. Chuùng ta coù ñaëc taû lôùp nhö sau: typedef int Vertex; template class Digraph { public: Digraph(); void read(); void write(); Giaùo trình Caáu truùc döõ lieäu vaø Giaûi thuaät 349
- Chöông 13 – Ñoà thò Caùc phöông thöùc saép thöù töï topo. // void depth_sort(List &topological_order); void breadth_sort(List &topological_order); private: int count; List neighbors[graph_size]; void recursive_depth_sort(Vertex v, bool visited[], List &topological_order); }; Haøm phuï trôï recursive_depth_sort ñöôïc söû duïng bôûi phöông thöùc depth_sort. Caû hai phöông phaùp saép thöù töï ñeàu seõ taïo ra moät danh saùch caùc ñænh cuûa ñoà thò theo thöù töï topo töông öùng. Hình 13.7 – Caùc thöù tö topo cuûa moät ñoà thò coù höôùng 13.4.2. Giaûi thuaät duyeät theo chieàu saâu Trong thöù töï topo, moãi ñænh phaûi xuaát hieän tröôùc moïi ñænh keà cuûa noù trong ñoà thò. Giaûi thuaät duyeät theo chieàu saâu naøy ñaët daàn caùc ñænh vaøo maûng thöù töï topo töø phaûi sang traùi. Baét ñaàu töø moät ñænh chöa töøng ñöôïc duyeät ñeán, chuùng ta caàn goïi ñeä quy ñeå ñeán ñöôïc caùc ñænh maø khoâng coøn ñænh keà, caùc ñænh naøy seõ ñöôïc ñaët vaøo maûng thöù töï topo ôû caùc vò trí cuoái maûng. Tính töø phaûi sang traùi trong maûng thöù töï topo naøy, khi caùc ñænh keà cuûa moät ñænh ñaõ ñöôïc duyeät xong, thì chính ñænh ñoù Giaùo trình Caáu truùc döõ lieäu vaø Giaûi thuaät 350
- Chöông 13 – Ñoà thò coù theå coù maët trong maûng. Ñoù chính laø luùc caùc laàn goïi ñeä quy beân trong luøi veà laàn goïi ñeä quy beân ngoaøi. Phöông phaùp naøy laø moät caùch hieän thöïc tröïc tieáp cuûa thuû tuïc duyeät theo chieàu saâu moät caùch toång quaùt ñaõ ñöôïc trình baøy ôû treân. Ñieåm khaùc bieät laø vieäc xöû lyù taïi moãi ñænh (ghi vaøo maûng thöù töï topo) chæ ñöôïc thöïc hieän sau khi caùc ñænh keà cuûa noù ñaõ ñöôïc xöû lyù. template void Digraph::depth_sort(List &topological_order) /* post: Caùc ñænh cuûa moät ñoà thò coù höôùng khoâng coù chu trình ñöôïc xeáp theo thöù töï topo töông öùng caùch duyeät ñoà thò theo chieàu saâu. uses: Caùc phöong thöùc cuûa lôùp List, haøm ñeä quy recursive_depth_sort. */ { bool visited[graph_size]; Vertex v; for (v = 0; v < count; v++) visited[v] = false; topological_order.clear(); for (v = 0; v < count; v++) if (!visited[v]) // Theâm caùc ñænh keà cuûa v vaø sau ñoù laø v vaøo maûng töù töï topo töø phaûi sang traùi. recursive_depth_sort(v, visited, topological_order); } Haøm phuï trôï recursive_depth_sort thöïc hieän vieäc ñeä quy, döïa treân phaùc thaûo cuûa haøm traverse toång quaùt, tröôùc heát ñaët taát caû caùc ñænh sau cuûa moät ñænh v vaøo caùc vò trí cuûa chuùng trong thöù töï topo, sau ñoù môùi ñaët v vaøo. template void Digraph::recursive_depth_sort(Vertex v, bool *visited, List &topological_order) /* pre: Ñænh v chöa coù trong maûng thöù töï topo. post: Theâm caùc ñænh keà cuûa v vaø sau ñoù laø v vaøo maûng töù töï topo töø phaûi sang traùi. uses: Caùc phöông thöùc cuûa lôùp List vaø haøm ñeä quy recursive_depth_sort. */ { visited[v] = true; int degree = neighbors[v].size(); for (int i = 0; i < degree; i++) { Vertex w; neighbors[v].retrieve(i, w); // Moät ñænh keà cuûa v. // Duyeät tieáp xuoáng ñænh w. if (!visited[w]) recursive_depth_sort(w, visited, topological_order); } // Ñaët v vaøo maûng thöù töï topo. topological_order.insert(0, v); } Do giaûi thuaät naøy duyeät qua moãi ñænh cuûa ñoà thò chính xaùc moät laàn vaø xem xeùt moãi caïnh cuõng moät laàn, ñoàng thôøi noù khoâng heà thöïc hieän vieäc tìm kieám naøo, neân thôøi gian chaïy laø O(n+e), vôùi n laø soá ñænh vaø e laø soá caïnh cuûa ñoà thò. Giaùo trình Caáu truùc döõ lieäu vaø Giaûi thuaät 351
- Chöông 13 – Ñoà thò 13.4.3. Giaûi thuaät duyeät theo chieàu roäng Trong thöù töï topo theo chieàu roäng cuûa moät ñoà thò coù höôùng khoâng coù chu trình, chuùng ta baét ñaàu baèng caùch tìm caùc ñænh coù theå laø caùc ñænh ñaàu tieân trong thöù töï topo vaø sau ñoù chuùng ta aùp duïng nguyeân taéc raèng, moïi ñænh caàn phaûi xuaát hieän tröôùc taát caû caùc ñænh sau cuûa noù trong thöù töï topo. Giaûi thuaät naøy seõ laàn löôït ñaët caùc ñænh cuûa ñoà thò vaøo maûng thöù töï topo töø traùi sang phaûi. Caùc ñænh coù theå laø ñænh ñaàu tieân chính laø caùc ñænh khoâng laø ñænh sau cuûa baát kyø ñænh naøo trong ñoà thò. Ñeå tìm ñöôïc chuùng, chuùng ta taïo moät maûng predecessor_count, moãi phaàn töû taïi chæ soá v chöùa soá ñænh ñöùng ngay tröôùc ñænh v. Caùc ñænh caàn tìm chính laø caùc ñænh maø khoâng coù ñænh naøo ñöùng ngay tröôùc noù, trò trong phaàn töû töông öùng cuûa maûng baèng 0. Caùc ñænh nhö vaäy ñaõ saün saøng ñöôïc ñaët vaøo maûng thöù tö topo. Nhö vaäy chuùng ta seõ khôûi ñoäng quaù trình duyeäït theo chieàu roäng baèng caùch ñaët caùc ñænh naøy vaøo moät haøng caùc ñænh seõ ñöôïc xöû lyù. Khi moät ñænh caàn ñöôïc xöû lyù, noù seõ ñöôïc laáy ra töø haøng vaø ñaët vaøo vò trí keá tieáp trong maûng topo, luùc naøy, vieäc xem xeùt noù xem nhö keát thuùc vaø ñöôïc ñaùnh daáu baèng caùch cho caùc phaàn töû trong maûng predecessor_count töông öùng vôùi caùc ñænh laø ñænh sau cuûa noù giaûm ñi 1. Khi moät phaàn töû naøo trong maûng naøy ñaït ñöôïc trò 0, thì cuõng coù nghóa laø ñænh töông öùng vôùi noù coù caùc ñænh tröôùc ñaõ ñöôïc duyeät xong, vaø ñænh naøy ñaõ saün saøng ñöôïc duyeät neân ñöôïc ñöa vaøo haøng ñôïi. template void Digraph::breadth_sort(List &topological_order) /* post: Caùc ñænh cuûa moät ñoà thò coù höôùng khoâng coù chu trình ñöôïc xeáp theo thöù töï topo töông öùng caùch duyeät ñoà thò theo chieàu roäng. uses: Caùc phöông thöùc cuûa caùc lôùp List, Queue. */ { topological_order.clear(); Vertex v, w; int predecessor_count[graph_size]; for (v = 0; v < count; v++) predecessor_count[v] = 0; for (v = 0; v < count; v++) for (int i = 0; i < neighbors[v].size(); i++) { // Caäp nhaät soá ñænh ñöùng tröôùc cho moãi ñænh. neighbors[v].retrieve(i, w); predecessor_count[w]++; } Queue ready_to_process; for (v = 0; v < count; v++) if (predecessor_count[v] == 0) ready_to_process.append(v); while (!ready_to_process.empty()) { ready_to_process.retrieve(v); topological_order.insert(topological_order.size(), v); for (int j = 0; j < neighbors[v].size(); j++) { // Giaûm soá ñænh ñöùng tröôùc // cuûa moãi ñænh keà cuûa v ñi 1 neighbors[v].retrieve(j, w); predecessor_count[w]--; Giaùo trình Caáu truùc döõ lieäu vaø Giaûi thuaät 352
- Chöông 13 – Ñoà thò if (predecessor_count[w] == 0) ready_to_process.append(w); } ready_to_process.serve(); } } Giaûi thuaät naøy caàn ñeán moät trong caùc hieän thöïc cuûa lôùp Queue. Queue coù theå coù hieän thöïc theo baát kyø caùch naøo ñaõ ñöôïc moâ taû trong chöông 3. Do caùc phaàn töû trong Queue laø caùc ñænh. Cuõng nhö duyeät theo chieàu saâu, thôøi gian caàn cho haøm breadth_first laø O(n+e), vôùi n laø soá ñænh vaø e laø soá caïnh cuûa ñoà thò. 13.5. Giaûi thuaät Greedy: Tìm ñöôøng ñi ngaén nhaát 13.5.1. Ñaët vaán ñeà Nhö moät öùng duïng khaùc cuûa ñoà thò, chuùng ta xem xeùt moät baøi toaùn hôi phöùc taïp sau ñaây. Chuùng ta coù moät ñoà thò coù höôùng G, trong ñoù moãi caïnh ñöôïc gaùn moät con soá khoâng aâm goïi laø taûi troïng (weight). Baøi toaùn cuûa chuùng ta laø tìm moät ñöôøng ñi töø moät ñænh ν ñeán moät ñænh w sao cho toång taûi troïng treân ñöôøng ñi laø nhoû nhaát. Chuùng ta goïi ñöôøng ñi nhö vaäy laø ñöôøng ñi ngaén nhaát (shortest path), maëc duø taûi troïng coù theå bieåu dieãn cho giaù caû, thôøi gian, hoaëc moät vaøi ñaïi löôïng naøo khaùc thay vì khoaûng caùch. Chuùng ta coù theå xem G nhö moät baûn ñoà caùc tuyeán bay, chaúng haïn, moãi ñænh cuûa ñoà thò bieåu dieãn moät thaønh phoá vaø taûi troïng treân moãi caïnh bieåu dieãn chi phí bay töø thaønh phoá naøy sang thaønh phoá kia. Baøi toaùn cuûa chuùng ta laø tìm loä trình bay töø thaønh phoá ν ñeán thaønh phoá w sao cho toång chi phí laø nhoû nhaát. Chuùng ta haõy xem xeùt ñoà thò ôû hình 13.8. Ñöôøng ngaén nhaát töø ñænh 0 ñeán ñænh 1 ñi ngang qua ñænh 2 coù toång taûi troïng laø 4, so vôùi taûi troïng laø 5 ñoái vôùi caïnh noái tröïc tieáp töø 0 sang 1, vaø toång taûi troïng laø 8 neáu ñi ngang qua ñænh 4. Hình 13.8 – Ñoà thò coù höôùng vôùi caùc taûi troïng Coù theå deã daøng giaûi baøi toaùn moät caùch toång quaùt nhö sau: baét ñaàu töø moät ñænh, goïi laø ñænh nguoàn, tìm ñöôøng ñi ngaén nhaát ñeán moïi ñænh coøn laïi, thay vì chæ tìm ñöôøng ñeán moät ñænh ñích. Chuùng ta caàn taûi troïng phaûi laø nhöõng soá khoâng aâm. Giaùo trình Caáu truùc döõ lieäu vaø Giaûi thuaät 353
- Chöông 13 – Ñoà thò 13.5.2. Phöông phaùp Giaûi thuaät seõ ñöôïc thöïc hieän baèng caùch naém giöõ moät taäp S caùc ñænh maø ñöôøng ñi ngaén nhaát töø ñænh nguoàn ñeán chuùng ñaõ ñöôïc bieát. Môùi ñaàu, ñænh nguoàn laø ñænh duy nhaát trong S. Taïi moãi böôùc, chuùng ta theâm vaøo S caùc ñænh coøn laïi maø ñöôøng ñi ngaén nhaát töø nguoàn ñeán chuùng vöøa ñöôïc tìm thaáy. Baøi toaùn baây giôø trôû thaønh baøi toaùn xaùc ñònh ñænh naøo ñeå theâm vaøo S taïi moãi böôùc. Chuùng ta haõy xem nhöõng ñænh ñaõ coù trong S nhö ñaõ ñöôïc toâ moät maøu naøo ñoù, vaø caùc caïnh naèm trong caùc ñöôøng ñi ngaén nhaát töø ñænh nguoàn ñeán caùc ñænh coù maøu cuõng ñöôïc toâ maøu. Chuùng ta seõ naém giöõ moät maûng distance cho bieát raèng, ñoái vôùi moãi ñænh ν, khoaûng caùch töø ñænh nguoàn doïc theo ñöôøng ñi coù caùc caïnh ñaõ coù maøu, coù theå tröø caïnh cuoái cuøng. Nghóa laø, neáu ν thuoäc S, thì distance[v] chöùa khoaûng caùch ngaén nhaát ñeán ν, vaø moïi caïnh naèm treân ñöôøng ñi töông öùng ñeàu coù maøu. Neáu ν khoâng thuoäc S, thì distance[v] chöùa chieàu daøi cuûa ñöôøng ñi töø ñænh nguoàn ñeán moät ñænh w naøo ñoù coäng vôùi taûi troïng cuûa caïnh noái töø w ñeán ν, vaø moïi caïnh naèm treân ñöôøng ñi naøy, tröø caïnh cuoái, ñeàu coù maøu. Maûng distance ñöôïc khôûi taïo baèng caùch gaùn töøng distance[v] vôùi trò cuûa taûi troïng cuûa caïnh noái töø ñænh nguoàn ñeán ν neáu toàn taïi caïnh naøy, ngöôïc laïi noù ñöôïc gaùn baèng voâ cöïc. Hình 13.9 – Tìm moät ñöôøng ñi ngaén Ñeå xaùc ñònh ñænh ñöôïc theâm vaøo S taïi moãi böôùc, chuùng ta aùp duïng moät “tieâu chí tham lam” (greedy criterion) trong vieäc choïn ra moät ñænh ν coù khoaûng caùch nhoû nhaát töø trong maûng distance sao cho ν chöa coù trong S. Chuùng ta caàn chöùng minh raèng, ñoái vôùi ñænh ν naøy, khoaûng caùch chöùa trong maûng distance thöïc söï laø chieàu daøi cuûa ñöôøng ñi ngaén nhaát töø ñænh nguoàn ñeán ν. Giaû söû coù moät ñöôøng ñi ngaén hôn töø nguoàn ñeán ν, nhö hình 13.9. Ñöôøng ñi naøy ñi ngang moät ñænh x naøo ñoù chöa thuoäc S roài môùi ñeán ν (coù theå laïi qua moät soá ñænh khaùc coù naèm trong S tröôùc khi gaëp ν). Nhöng neáu ñöôøng ñi naøy ngaén hôn ñöôøng ñi ñaõ ñöôïc toâ maøu ñeán ν, thì ñoaïn ñöôøng ban ñaàu trong noù töø nguoàn ñeán x coøn ngaén hôn nöõa, nghóa laø distance[x] < distance[v], vaø nhö vaäy tieâu chí tham lam ñaõ phaûi choïn x thay vì ν laø ñænh keá tieáp ñöôïc theâm vaøo S. Giaùo trình Caáu truùc döõ lieäu vaø Giaûi thuaät 354
- Chöông 13 – Ñoà thò Khi theâm ν vaø S, chuùng ta seõ toâ maøu ν vaø toâ maøu luoân ñöôøng ñi ngaén nhaát töø ñænh nguoàn ñeán ν (moïi caïnh trong noù tröø caïnh cuoái thöïc söï ñaõ ñöôïc toâ maøu tröôùc Hình 12.10 - Ví duï veà caùc ñöôøng ñi ngaén nhaát ñoù). Keá tieáp, chuùng ta caàn caäp nhaät laïi caùc phaàn töû cuûa maûng distance baèng caùch xem xeùt ñoái vôùi moãi ñænh w naèm ngoaøi S, ñöôøng ñi töø nguoàn qua ν roài ñeán w coù ngaén hôn khoaûng caùch töø nguoàn ñeán w ñaõ ñöôïc ghi nhaän tröôùc ñoù hay khoâng. Neáu ñieàu naøy xaûy ra coù nghóa laø chuùng ta vöøa phaùt hieän ñöôïc moät ñöôøng ñi môùi cho ñænh w coù ñi ngang qua ν ngaén hôn caùch ñi ñaõ xaùc ñònh tröôùc ñoù, vaø nhö vaäy chuùng ta caàn caäp nhaät laïi distance[w] baèng distance[v] coäng vôùi taûi troïng cuûa caïnh noái töø ν ñeán w. Giaùo trình Caáu truùc döõ lieäu vaø Giaûi thuaät 355
- Chöông 13 – Ñoà thò 13.5.3. Ví duï Tröôùc khi vieát moät haøm cho phöông phaùp naøy, chuùng ta haõy xem qua ví duï ôû hình 13.10. Ñoái vôùi ñoà thò coù höôùng ôû hình (a), traïng thaùi ban ñaàu ñöôïc chæ ra ôû hình (b): taäp S (caùc ñænh ñaõ ñöôïc toâ maøu) chæ goàm coù nguoàn laø ñænh 0, caùc phaàn töû cuûa maûng distance chöùa caùc con soá ñöôïc ñaët caïnh moãi ñænh coøn laïi. Khoaûng caùch ñeán ñænh 4 ngaén nhaát, neân 4 ñöôïc theâm vaøo S nhö ôû hình (c), vaø distance[3] ñöôïc caäp nhaät thaønh 6. Do khoaûng caùch ñeán 1 vaø 2 ngang qua 4 lôùn hôn khoaûng caùch ñaõ chöùa trong maûng distance, neân caùc khoaûng caùch naøy trong distance ñöôïc giöõ khoâng ñoåi. Ñænh keá tieáp gaàn nhaát ñoái vôùi nguoàn laø ñænh 2, noù ñöôïc theâm vaøo S nhö hình (d), khoaûng caùch ñeán caùc ñænh 1 vaø 3 ñöôïc caäp nhaät laïi ngang qua ñænh naøy. Hai böôùc cuoái cuøng, trong hình (e) vaø (f), ñænh 1 vaø 3 ñöôïc theâm vaøo vaø caùc ñöôøng ñi ngaén nhaát töø ñænh nguoàn ñeán caùc ñænh coøn laïi ñöôïc chæ ra trong sô ñoà cuoái. 13.5.4. Hieän thöïc Ñeå hieän thöïc giaûi thuaät tìm ñöôøng ngaén nhaát treân, chuùng ta caàn choïn caùch hieän thöïc cho ñoà thò coù höôùng. Vieäc duøng baûng keà cho pheùp truy xuaát ngaãu nhieân ñeán moïi ñænh cuûa ñoà thò. Hôn nöõa, chuùng ta coù theå söû duïng baûng vöøa ñeå chöùa caùc taûi troïng vöøa ñeå chöùa thoâng tin veà caùc ñænh keà. Trong ñaëc taû döôùi ñaây cuûa ñoà thò coù höôùng, chuùng ta theâm thoâng soá template cho pheùp ngöôøi söû duïng choïn löïa kieåu cuûa taûi troïng theo yù muoán. Laáy ví duï, ngöôøi söû duïng khi duøng lôùp Digraph ñeå moâ hình hoùa maïng caùc tuyeán bay, hoï coù theå chöùa giaù veù laø moät soá nguyeân hay moät soá thöïc. template class Digraph { public: // Theâm constructor vaø caùc phöông thöùc nhaäp vaø xuaát ñoà thò. void set_distances(Vertex source, Weight distance[]) const; protected: int count; Weight adjacency[graph_size][graph_size]; }; Thuoäc tính count chöùa soá ñænh cuûa moät ñoái töôïng ñoà thò. Trong caùc öùng duïng, chuùng ta caàn boå sung caùc phöông thöùc ñeå nhaäp hay xuaát caùc thoâng tin cuûa moät ñoái töôïng ñoà thò, nhöng do chuùng khoâng caàn thieát trong vieäc hieän thöïc phöông thöùc distance ñeå tìm caùc ñöôøng ñi ngaén nhaát, chuùng ta xem chuùng nhö laø baøi taäp. Chuùng ta seõ giaû söû raèng lôùp Weight ñaõ coù caùc taùc vuï so saùnh. Ngoaøi ra, ngöôøi söû duïng seõ phaûi khai baùo trò lôùn nhaát coù theå coù cuûa Weight, goïi laø infinity. Chaúng haïn, chöông trình cuûa ngöôøi söû duïng vôùi taûi troïng laø soá nguyeân coù theå söû duïng thö vieän chuaån ANSI C++ vôùi ñònh nghóa toaøn cuïc nhö sau: const Weight infinity = numeric_limits::max(); Giaùo trình Caáu truùc döõ lieäu vaø Giaûi thuaät 356
- Chöông 13 – Ñoà thò Chuùng ta seõ ñaët trò cuûa infinity vaøo caùc phaàn töû cuûa maûng distance töông öùng vôùi caùc caïnh töø khoâng toàn taïi nguoàn ñeán moãi ñænh. Phöông thöùc set_distance seõ tìm caùc ñöôøng ñi ngaén nhaát vaø caùc khoaûng caùch ngaén nhaát naøy seõ ñöôïc traû veà qua tham bieán distance[]. template void Digraph::set_distances(Vertex source, Weight distance[]) const /* post: Maûng distance chöùa ñöôøng ñi coù taûi troïng ngaén nhaát töø ñænh nguoàn ñeán moãi ñænh trong ñoà thò. */ { Vertex v, w; // Bieåu dieãn caùc ñænh trong S. bool found[graph_size]; for (v = 0; v < count; v++) { found[v] = false; distance[v] = adjacency[source][v]; } found[source]=true;// Khôûi taïo baèng caùch boû ñænh nguoàn vaøo S. distance[source] = 0; for(int i = 0; i < count; i++){ // Moãi laàn laëp boû theâm moät ñænh vaøo S. Weight min = infinity; for (w = 0; w < count; w++) if (!found[w]) if (distance[w] < min) { v = w; min = distance[w]; } found[v] = true; for (w = 0; w < count; w++) if (!found[w]) if (min + adjacency[v][w] < distance[w]) distance[w] = min + adjacency[v][w]; } } Ñeå öôùc ñoaùn thôøi gian caàn ñeå chaïy haøm naøy, chuùng ta thaáy raèng voøng laëp chính thöïc hieän n-1 laàn, trong ñoù n laø soá ñænh, vaø beân trong voøng laëp chính coù hai voøng laëp khaùc, moãi voøng laëp naøy thöïc hieän n-1 laàn. Vaäy caùc voøng laëp thöïc hieän (n-1)2 laàn. Caùc leänh beân ngoaøi voøng laëp chæ heát O(n), neân thôøi gian chaïy cuûa haøm laø O(n2). 13.6. Caây phuû toái tieåu 13.6.1. Ñaët vaán ñeà Giaûi thuaät tìm ñöôøng ñi ngaén nhaát cuûa phaàn treân coù theå ñöôïc aùp duïng vôùi maïng hay ñoà thò coù höôùng cuõng nhö maïng hay ñoà thò khoâng coù höôùng. Ví duï, hình 13.11 minh hoïa öùng duïng tìm caùc ñöôøng ñi ngaén nhaát töø ñænh nguoàn 0 ñeán caùc ñænh khaùc trong maïng. Giaùo trình Caáu truùc döõ lieäu vaø Giaûi thuaät 357
- Chöông 13 – Ñoà thò Hình 13.11 – Tìm ñöôøng ñi ngaén nhaát trong moät maïng Neáu maïng döïa treân cô sôû laø moät ñoà thò lieân thoâng G, thì caùc ñöôøng ñi ngaén nhaát töø moät ñænh nguoàn naøo ñoù seõ noái nguoàn naøy vôùi taát caû caùc ñænh khaùc trong G. Töø ñoù, nhö trong hình 13.11, neáu chuùng ta keát hôïp caùc ñöôøng ñi ngaén nhaát tính ñöôïc laïi vôùi nhau, chuùng ta coù moät caây noái taát caû caùc ñænh cuûa G. Noùi caùch khaùc, ñoù laø caây ñöôïc taïo bôûi taát caû caùc ñænh vaø moät soá caïnh cuûa ñoà thò G. Chuùng ta goïi nhöõng caây nhö vaäy laø caây phuû (spanning tree) cuûa G. Cuõng nhö phaàn tröôùc, chuùng ta coù theå xem moät maïng treân moät ñoà thò G nhö laø moät baûn ñoà caùc tuyeán bay, vôùi moãi ñænh bieåu dieãn moät thaønh phoá vaø taûi troïng treân moät caïnh laø giaù veù bay töø thaønh phoá naøy sang thaønh phoá kia. Moät caây phuû cuûa G bieåu dieãn moät taäp caùc ñöôøng bay cho pheùp caùc haønh khaùch hoaøn taát moät chuyeán du lòch qua khaép caùc thaønh phoá. Dó nhieân raèng, haønh khaùch caàn phaûi thöïc hieän moät soá tuyeán bay naøo ñoù moät vaøi laàn môùi hoaøn taát ñöôïc chuyeán du lòch. Ñieàu baát tieän naøy ñöôïc buø ñaép bôûi chi phí thaáp. Neáu chuùng ta hình dung maïng trong hình 13.11 nhö moät heä thoáng ñieàu khieån taäp trung, thì ñænh nguoàn töông öùng vôùi saân bay trung taâm, vaø caùc ñöôøng ñi töø ñænh naøy laø nhöõng haønh trình bay. Moät ñieàu quan troïng ñoái vôùi moät saân bay theo heä thoáng ñieàu khieån taäp trung laø giaûm toái ña chi phí baèng caùch choïn löïa moät heä thoáng caùc ñöôøng bay maø toång chi phí nhoû nhaát. Ñònh nghóa: Moät caây phuû toái tieåu (minimal spanning tree) cuûa moät maïng lieân thoâng laø caây phuû maø toång caùc taûi troïng treân caùc caïnh cuûa noù laø nhoû nhaát. Maëc duø vieäc so saùnh hai caây phuû trong hình 13.12 laø khoâng khoù khaên, nhöng cuõng khoù maø bieát ñöôïc coøn coù caây phuû naøo coù trò nhoû hôn nöõa hay khoâng. Baøi toaùn cuûa chuùng ta laø xaây döïng moät phöông phaùp xaùc ñònh moät caây phuû toái tieåu cuûa moät maïng lieân thoâng. Giaùo trình Caáu truùc döõ lieäu vaø Giaûi thuaät 358
CÓ THỂ BẠN MUỐN DOWNLOAD
-
Kỹ thuật lập trình - Chương 4: Khái quát về cấu trúc dữ liệu
32 p |
273 |
134
-
Cấu trúc dữ liệu và giải thuật - Chương 2 - Tìm kiếm và sắp xếp
204 p |
280 |
124
-
Cấu trúc dữ liệu (chương 8)
34 p |
175 |
89
-
Cấu trúc dữ liệu (chương 9)
54 p |
134 |
86
-
Cấu trúc dữ liệu - Chương 1 Các khái niệm cơ bản
4 p |
336 |
82
-
Cấu trúc dữ liệu (chương 10)
46 p |
145 |
68
-
Giáo trình CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT - Chương 1
5 p |
199 |
60
-
Cấu trúc dữ liệu và giải thuật - chương 5
27 p |
109 |
27
-
Cấu trúc dữ liệu và giải thuật - chương 1
20 p |
107 |
19
-
Cấu trúc dữ liệu và giải thuật - chương 3
22 p |
125 |
18
-
CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT - CHƯƠNG 7: CÂY NHỊ PHÂN TÌM KIẾM
19 p |
80 |
17
-
CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT (501040) - Chương 1: Tổng quan
20 p |
50 |
14
-
CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT - CHƯƠNG 6: CÂY VÀ CÂY NHỊ PHÂN
14 p |
64 |
11
-
Bài giảng cấu trúc dữ liệu - Chương 2 Cấu trúc dữ liệu danh sách Phần 2
41 p |
49 |
5
-
Bài giảng cấu trúc dữ liệu - Chương 1 Nhập môn cấu trúc dữ liệu
33 p |
37 |
4
-
Bài giảng cấu trúc dữ liệu - Chương 2 Cấu trúc dữ liệu danh sách Phần 1
25 p |
37 |
3
-
Bài giảng Cấu trúc dữ liệu và thuật toán: Chương 1 - ThS. Phạn Nguyệt Thuần
31 p |
2 |
2

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


markdown:
# Công văn 10786/TC/CSTcủa Bộ Tài chính
Chia sẻ: Chánh Sơn | Ngày: | Loại File: DOC | Số trang:1
lượt xem 3
download
![](http://image.tlvnimg.com/document/thumbnail/2009/20090819/chanhson/80x100/03001048.jpg)
##
Công văn 10786/TC/CSTcủa Bộ Tài chính
[Vui lòng tải xuống để xem tài liệu đầy đủ](javascript:void(0);)
Download
![](images/down16x21.png)
Công văn 10786/TC/CST của Bộ Tài chính về việc hướng dẫn quản lý và sử dụng tiền thu từ xử phạt vi phạm hành chính
Bình luận(0)
[Đăng nhập để gửi bình luận!](javascript:void(0);)
##
Nội dung Text: Công văn 10786/TC/CSTcủa Bộ Tài chính
- phßng èc éi ¬ ë ÷ iÖu luËtviÖtnam qu h c s d l v¨n LAWDATA c«ng v¨n c ñ a b é t µi h Ý n h è 10786/TCC S T n g µ y 17 c s th¸ng 10 n¨ m 2003 v Ò Ö c h í ng d É n u ¶ n lý µ s ö ô n g ti Ò n thu vi q v d t õ x ö p h ¹t vi p h ¹ m h µ n h c h Ý n h K Ý nh öi: U û g ban © n © n nh d c¸c tØnh, µnh è ùc éc th ph tr thu Trung ng ¬ C ôc Õ thu c¸c tØnh, thµnh è ùc thuéc ph tr Trung ng ¬ TriÓn khai thùc Ön hi Ph¸p Önh ö ý vi ph¹m µnh Ýnh l x l h ch n¨m 2002, theo chØ o ña Ýnh ñ, Bé µi chÝnh ang ©y ùng µ µn Ön ®¹ c Ch ph T ® xd v ho thi c¸c v¨n b¶n quy nh ã ªnquan ®Þ c li trong ã ù ®ã c d th¶o NghÞ nh ña ®Þ c ChÝnh ñ Ò ö ¹t vi ph¹m µnh Ýnh ph v x ph h ch trong Ünh ùc Õ, ù l v thu d th¶o quyÕt nh ña ñ íng Ch Ýnh ñ Ò Öc ®Þ c Th t ph v vi ban µnh h Quy Õ Ých lËp, ch tr qu¶n ývµ ö ông ü èng l s d Qu ch kinh doanh tr¸ph¸p luËt. i Trong êigian chê th c¸c v¨n b¶n îcban µnh, ®Ó trªn® h kh«ng ¶nh ëng h ®Õ n c«ng ö ýviph¹m µnh Ýnh,® Æc Ötlµchèng t¸cx l h ch bi bu«n Ëu,chèng l trèn thuÕ, chèng kinh doanh tr¸ ph¸p Ët,Bé µi chÝnh ∙ ã i lu T ® c c¸c C«ng v¨n sè 14353/TC CSTC ngµy 30/12/2002, C«ng v¨n sè 2492/TCCSTC ngµy 19/3/2003 µ v C«ng è v¨n s 8376/TC CSTC µy ng 14/8/2003 íng dÉn Õp tôc h ti ¸p ông d c¸c quy nh ∙ ã õ tr c khiPh¸p Önh ö ýviph¹m µnh Ýnh ®Þ ® c t í l x l h ch n¨m 2002 ã Öu ùcthi µnh Ò c hi l h v qu¶n ývµ ö ông Òn thu tõxö ¹thµnh l s d ti ph chÝnh i víi Ünh ùc.Trong , i víi Ünh ùc Õ Én ông ®è lc¸c v ®ã ®è l v thu v ¸p d quy ®Þnh ¹ Th«ng è ti ts 128/1998/TT BTC µy ng 22/9/1998 cña é µichÝnh öa BT s ® æi, bæ sung Th«ng sè t 45/TC TCT µy ng 1/8/1996 íng Én ùc Ön h d th hi NghÞ nh è ®Þ s 22/CP µy ng 17/4/1996 ña Ýnh ñ Ò Öc ö ¹t vi c Ch ph v vi x ph ph¹m µnh Ýnh h ch tronglÜnh ùc Õ. v thu Theo quy nh ¹ Ó m ôc ®Þ ti §i 2, M IITh«ng è t s 30/2001/TT BTC ña é cB Tµi chÝnh µy ng 16/5/2001 × hµnh Õm o¹ttiÒn hoµn Õ Þ gia th vichi ® thu gi¸tr t¨ng ® îcx¸c ®Þnh µ hµnh l vikhaiman èn thuÕ. Do , Öc tr ®ã vi qu¶n ývµ ö l s dông Òn tõ xö ¹thµnh Ýnh i íic¸c viph¹m ti thu ph ch ®è v gian Ën l trong hoµn thuÕ Þ gia t¨ng ® îc¸p ông gi¸tr d theo quy nh ¹ ®Þ tiTh«ng è t s 128/1998/TT BTC. §Ò Þ û ngh U ban ©n ©n nh d c¸c tØnh, thµnh è ùc thuéc ph tr Trung ng ¬ chØ o µnh ®¹ c¸c ng chøc n¨ng ¹ a ¬ng ùc Ön ö ý vi ph¹m µnh ti ®Þ ph th hi x l h chÝnh, ® Æc Öt lµ trong lÜnh ùc Õ Þ gia t¨ng theo bi v thu gi¸tr c¸c quy nh ®Þ ph¸p ËthiÖn µnh. Trong lu h qu¸ ×nh ùc hiÖn, n Õu ã Ên íng ¾ c tr th c v ®Ò v m n¶y sinh,®Ò Þ ngh ph¶n Þp êivÒ é µichÝnh ¸nh k th B T ®Ó xem Ðt,xö ý. x l
CÓ THỂ BẠN MUỐN DOWNLOAD
-
Thông tư 59/2008/TT-BTC của Bộ Tài chính
6 p |
699 |
40
-
Thông tư liên tịch 46/2009/TTLT-BTC-BCA của Bộ Tài chính, Bộ Công an
6 p |
161 |
12
-
Thông tư liên tịch 100/2008/TTLT-BTC-BGTVT-BCA-BTP-NHNNVN của Bộ Tài chính, Bộ Giao thông vận tải, Bộ Công an, Bộ Tư pháp và Ngân hàng Nhà nước
5 p |
172 |
12
-
Thông tư 72/2004/TT-BTC của Bộ Tài chính
26 p |
134 |
7
-
Thông tư 14/2005/TT-BTC của Bộ Tài chính
125 p |
162 |
6
-
Công văn 69-TC/VP của Bộ Tài chính
1 p |
69 |
5
-
Thông tư số 130/2004/TT-BTC của Bộ Tài chính
8 p |
116 |
5
-
Thông tư 38/2008/TT-BTC của Bộ Tài chính
5 p |
171 |
5
-
Công văn 3645-TC/TCT của Bộ Tài chính
2 p |
51 |
3
-
Thông tư 24/2001/TT-BTC của Bộ Tài chính
4 p |
64 |
3
-
Quyết định 122/2002/QĐ-BTC của Bộ Tài chính
6 p |
62 |
3
-
Quyết định 58/2003/QĐ-BTC của Bộ Tài chính
2 p |
80 |
3
-
Thông tư liên tịch 04/2003/TTLT-BCN-BTC của Bộ Công nghiệp và Bộ Tài chính
3 p |
61 |
3
-
Thông tư 31/2004/TT-BTC của Bộ Tài chính
17 p |
64 |
3
-
Thông tư 110/2004/TT-BTC của Bộ Tài chính
23 p |
103 |
2
-
Thông tư 48/1999/TT-BTC của Bộ Tài chính
3 p |
46 |
2
-
Thông tư liên tịch 29TT/LB của Bộ Tài chính và Bộ Lao động, Thương binh và Xã hội
6 p |
119 |
2

WARC-Type: response

Content-Type: application/http; msgtype=response

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

Connection: close

Server: Apache/2.2.31 (CentOS)

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

Pragma: no-cache

Vary: Accept-Encoding

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


markdown:
# Đề thi học kỳ 1 môn Hóa lớp 11
Chia sẻ: Việt Anh Việt Anh | Ngày: | Loại File: DOC | Số trang:1
851
lượt xem 237
download
lượt xem 237
download
![](http://image.tlvnimg.com/document/thumbnail/2010/20101218/demon_a1/80x100/thi_hoa_11_1345.jpg)
##
Đề thi học kỳ 1 môn Hóa lớp 11
Mô tả tài liệu
[Vui lòng tải xuống để xem tài liệu đầy đủ](javascript:void(0);)
Download
![](images/down16x21.png)
Tài liệu tham khảo Đề thi học kỳ 1 môn Hóa lớp 11
Chủ đề:
Bình luận(0)
[Đăng nhập để gửi bình luận!](javascript:void(0);)
CÓ THỂ BẠN MUỐN DOWNLOAD

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


markdown:
# Đồ án tốt nghiệp Một số giải pháp và kiến nghị nhằm nâng cao hiệu quả công tác đấu thầu
Chia sẻ: Pham Tien Dung | Ngày: | Loại File: DOC | Số trang:74
lượt xem 93
download
![](http://image.tlvnimg.com/document/thumbnail/2010/20100309/tiendungtb3003/80x100/8011338002271.jpg)
##
Đồ án tốt nghiệp Một số giải pháp và kiến nghị nhằm nâng cao hiệu quả công tác đấu thầu
[Vui lòng tải xuống để xem tài liệu đầy đủ](javascript:void(0);)
Download
![](images/down16x21.png)
Tham khảo luận văn - đề án 'đồ án tốt nghiệp một số giải pháp và kiến nghị nhằm nâng cao hiệu quả công tác đấu thầu', luận văn - báo cáo phục vụ nhu cầu học tập, nghiên cứu và làm việc hiệu quả
Bình luận(0)
[Đăng nhập để gửi bình luận!](javascript:void(0);)
##
Nội dung Text: Đồ án tốt nghiệp Một số giải pháp và kiến nghị nhằm nâng cao hiệu quả công tác đấu thầu
- LuËn v¨n tèt nghiÖp NguyÔn M¹nh Cêng QLKT 39B Đồ án tốt nghiệp Một số giải pháp và kiến nghị nhằm nâng cao hiệu quả công tác đấu thầu 1
- LuËn v¨n tèt nghiÖp NguyÔn M¹nh Cêng QLKT 39B Mục lục Trang Lời nói đầu 5 Chương I: Những vấn đề cơ bản về hoạt động đấu thầu................................................ 6 I. Một số Khái niệm chung ........................................................................................... 6 1. Khái niệm đấu thầu nói chung ............................................................................... 6 2. Khái niệm về đấu thầu xây dựng ........................................................................... 6 3. ý nghĩa của công tác đấu thầu ................................................................................ 7 4. Vai trò của đấu thẩu trong đấu thầu xây dựng ........................................................ 7 4.1. Đối với các nhà thầu ..................................................................................... 7 4.2 Đối với chủ đầu tư ......................................................................................... 7 4.3. Đối với Nhà nước ......................................................................................... 8 II. Một số vấn đề về quy chế đấu thầu .......................................................................... 8 1. Phạm vi và đối tượng áp dụng ............................................................................... 8 1. 1. Phạm vi áp dụng .......................................................................................... 8 1. 2. Đối tượng áp dụng ....................................................................................... 8 2. Nguyên tắc đấu thầu .............................................................................................. 9 2. 1. Nguyên tắc cạnh tranh với điều kiện ngang nhau ......................................... 9 2. 2. Nguyên tắc dữ liệu đầy đủ ........................................................................... 9 2. 3. Nguyên tắc đánh giá công bằng ................................................................... 9 2. 4. Nguyên tắc trách nhiệm phân minh .............................................................. 9 2. 5. Nguyên tắc "ba chủ thể "............................................................................ 10 2. 6. Nguyên tắc tuân thủ nghiêm ngặt sự quản lý thống nhất của nhà nước ....... 10 2. 7. Nguyên tắc bảo lãnh, bảo hành và bảo hiểm thích đáng.............................. 10 3. Hình thức lựa chọn nhà thầu và phương thức áp dụng ......................................... 11 3. 1. Hình thức lựa chọn nhà thầu ...................................................................... 11 3. 2 Phương thức đấu thầu ................................................................................. 13 III. Trình tự tổ chức đấu thầu xây lắp ......................................................................... 13 1. Điều kiện thực hiện đấu thầu ............................................................................... 13 1. 1. Điều kiện mời thầu .................................................................................... 13 1. 2. Điều kiện dự thầu ...................................................................................... 14 1. 3. Bên mời thầu không được tham gia với tư cách là nhà thầu đối với gói thầu do mình tổ chức. ....................................................................................... 14 2. Điều kiện đấu thầu quốc tế và ưu đãi nhà thầu ..................................................... 14 3. Trình tự tổ chức đấu thầu xây lắp ........................................................................ 15 4. Trình tự dự thầu xây lắp của các doanh nghiệp xây dựng ..................................... 21 5. Những nhân tố ảnh hưởng đến việc thắng thầu của tổ chức xây dựng .................. 23 5. 1. Năng lực của tổ chức xây dựng .................................................................. 23 5. 2. Khả năng cạnh tranh của tổ chức xây dựng ................................................ 25 5. 3. Những nhân tố bên ngoài tổ chức................................................................ 27 6. Tiêu chuẩn đánh giá hiệu quả công tác đấu thầu với các doanh nghiệp xây lắp .... 28 6. 1. Chỉ tiêu số lượng công trình trúng thầu và giá trị trúng thầu hàng năm ....... 28 6. 2. Chỉ tiêu xác suất chúng thầu ...................................................................... 28 6. 3. Chỉ tiêu thị phần và uy tín của doanh nghiệp xây dựng trên thị trường xây dựng. ........................................................................................................ 29 Chương II: Tình hình thực hiện công tác đấu thầu tại công ty xây dựng Sông Đà II . 30 I. Giới thiệu chung về công ty xây dựng Sông Đà II ................................................... 30 2
- LuËn v¨n tèt nghiÖp NguyÔn M¹nh Cêng QLKT 39B 1. Quá trình hình thành và phát triển........................................................................ 30 1. 1. Giai đoạn từ khi thành lập (1960) đến khi được xắp xếp lại(1993) ............. 30 1. 2. Giai đoạn sau khi sắp xếp lại (3/1993) đến nay. ......................................... 31 2. Đặc điểm về cơ cấu tổ chức quản lý và cơ cấu tổ chức sản xuất .......................... 32 2.1. Cơ cấu tổ chức quản lý. .............................................................................. 32 2.2. Cơ cấu tổ chức sản xuất. ............................................................................. 35 II. Năng lực hiện tại của công ty................................................................................. 36 1. Đặc điểm ngành nghề kinh doanh ........................................................................ 36 2. Đặc điểm về máy móc thiết bị và nguyên vật liệu: ............................................... 36 3. Đặc điểm về lao động .......................................................................................... 40 4. Năng lực tài chính ............................................................................................... 42 III. Tình hình thực hiện công tác đấu thầu của công ty xây dựng Sông Đà II trong những năm gần đây .............................................................................................. 43 1. Tình hình chung .................................................................................................. 43 2.Trình tự tham gia dự thầu của công ty .................................................................. 47 2.1.Tìm kiếm thông tin về công trình cần đấu thầu .................................................. 47 2. 2. Tiếp xúc ban đầu với bên chủ đầu tư và tham gia sơ tuyển (nếu có) ........... 48 2. 3 Chuẩn bị và lập hồ sơ dự thầu ..................................................................... 48 2. 4 Nộp hồ sơ dự thầu và tham gia mở thầu ...................................................... 49 2.5 Ký kết hợp đồng kinh doanh (nếu trúng thầu) và theo dõi thực hiện hợp đồng. ................................................................................................................. 49 3. Đánh giá tình hình thực hiện đâú thầu của công ty trong những năm qua ............. 49 3.1. Những thành tích ........................................................................................ 49 3. 2. Những tồn tại trong công tác dự thầu tại công ty ........................................ 50 3. 3. Nguyên nhân chủ yếu của những tồn tại trên .............................................. 51 4. Tổ chức quản lý và phối hợp giữa các bộ phận thực hiên công tác dự thầu tại công ty....................................................................................................................... 51 Chương III :Một số giải pháp và kiến nghị nhằm nâng cao hiệu quả công tác đấu thầu tại công ty xây dựng Sông Đà II .......................................................... 55 I. Định hướng kế hoạch sản xuất kinh doanh 5 năm 2001- 2005 của công ty xây dựng Sông Đà II ............................................................................................................ 55 1. Định hướng phát triển ......................................................................................... 55 2. Một số mục tiêu chính ......................................................................................... 55 2.1.Cơ cấu sản lượng ......................................................................................... 55 2.2. Về cơ cấu các công trình trong thi công xây lắp .......................................... 56 2.3.Về cơ cấu địa bàn hoạt động ........................................................................ 56 II. Một số giải pháp nhằm nâng cao hiệu quả công tác đấu thầu tại công ty xây dựng Sông Đà II ............................................................................................................ 57 Biện pháp 1: Vận dụng phương pháp dùng chỉ tiêu tổng hợp để ra quyết định tranh thầu ................................................................................................................... 57 Biện pháp 2: Tổ chức bộ máy đấu thầu của công ty cho phù hợp với yêu cầu của thị trường ............................................................................................................... 60 Biện pháp 3 : Phát huy các biện pháp cải tiến kỹ thuật và thực hiện đầu tư có trọng điểm,tập trung vào thiết bị xe máy thi công. ...................................................... 64 Biện pháp 4 : Điều tra nghiên cứu thị trường và xây dựng các chính sách, chiến lược tranh thầu phù hợp ............................................................................................. 65 Biện pháp 5: Quản lý nhân công .............................................................................. 69 3
- LuËn v¨n tèt nghiÖp NguyÔn M¹nh Cêng QLKT 39B III. Một số kiến nghị nhằm nâng cao hiệu quả công tác đấu thầu của công ty xây dựng Sông Đà II. ........................................................................................................... 69 1. ý kiến đề nghị Tổng Công Ty .............................................................................. 69 2. Kiến nghị với Nhà nước ...................................................................................... 70 Kết luận........ .............................................................................................................. 70 Danh mục Tài liệu tham khảo ....................................................................................... 71 4
- LuËn v¨n tèt nghiÖp NguyÔn M¹nh Cêng QLKT 39B Lời nói đầu Trong một vài năm gần đây hoạt động đấu thầu xây lắp đối với các dự án có vốn đầu tư nước ngoài, các công trình trọng điểm của Nhà nước trong lĩnh vực xây dựng cơ sở hạ tầng, các công trình xây dựng với quy mô lớn trở nên sôi động hơn bao giờ hết. Cùng với quá trình đó, các doanh nghiệp xây dựng Việt Nam đang từng bước tiếp cận dần với các hình thức kinh nghiệm mới, với thực tiễn về kỹ thuật kinh doanh quốc tế và nhiều vấn đề có liên quan đến hoạt động đấu thầu. Tuy nhiên, ở Việt Nam hoạt động đấu thầu còn là vấn đề mới mẻ chỉ tiến hành một vài năm trở lại đây và chưa hoàn chỉnh về nhiều mặt. Cùng với điều này, nhiều doanh nghiệp xây dựng cũng đang phải tự điều chỉnh tiến tới thích ứng hoàn toàn với phương thức cạnh tranh mới. Vì thế, hoạt động đấu thầu tại các doanh nghiệp này không tránh khỏi bất cập và gặp những khó khăn dẫn đến hiệu quả hoạt động đấu thầu xây lắp chưa cao, ảnh hưởng trực tiếp tới đời sống, việc làm của người lao động cũng như tình hình sản xuất kinh doanh của đơn vị. Là một đơn vị hoạt động trong lĩnh vực kinh doanh xây lắp Công ty xây dựng Sông Đà II cũng không tránh khỏi những khó khăn vướng mắc như trên. Qua thời gian thực tập tại Công ty Sông Đà II kết hợp với những kiến thức đã học trên ghế nhà trường em mạnh dạn đi sâu tìm hiểu và nghiên cứu đề tài “Một số giải pháp và kiến nghị nhằm nâng cao hiệu quả công tác đấu thầu” với mong muốn góp phần giải quyết những khó khăn, vướng mắc trên. Về mặt kết cấu, ngoài phần mở đầu và kết luận, luận văn được chia thành 3 chương chính sau: Chương I: Những vấn đề cơ bản về hoạt động đấu thầu Chương II: Tình hình thực hiện công tác đấu thầu tại Công ty xây dựng Sông Đà II Chương III: Một số giải pháp và kiến nghị nhằm nâng cao hiệu quả công tác đấu thầu tại Công ty xây dựng Sông Đà II Vì trình độ và thời gian có hạn, luận văn này khó có thể tránh được những thiếu sót em rất mong nhận được những ý kiến đóng góp của thầy cô giáo cũng như các cán bộ Công ty xây dựng Sông Đà II để đề tài được hoàn thiện tốt hơn. Qua bài viết này cho phép em gửi lời cảm ơn tới các cô chú trong phòng KTKH - Công ty xây dựng Sông Đà II - Tổng công ty xây dựng Sông Đà, chú Nguyễn Văn Sinh Thạc sỹ- Phó giám đốc công ty xây dựng Sông Đà II, chú Nguyễn Trọng Hiến trưởng phòng KTKH và đặc biệt là cô giáo T.S Đoàn Thị Thu Hà -Khoa khoa học quản lý-Trường ĐHKTQD đã tận tình hướng dẫn, chỉ bảo và giúp đỡ em trong quá trình nghiên cứu hoàn thành luận văn tốt nghiệp. 5
- LuËn v¨n tèt nghiÖp NguyÔn M¹nh Cêng QLKT 39B Chương I Những vấn đề cơ bản về hoạt động đấu thầu I. Một số Khái niệm chung 1. Khái niệm đấu thầu nói chung Đấu thầu là quá trình lựa chọn nhà thầu đáp ứng được các yêu cầu của bên mời thầu trên cơ sở cạnh tranh giữa các nhà thầu. "Bên mời thầu" là chủ dự án, chủ đầu tư hoặc pháp nhân đại diện hợp pháp của chủ dự án, chủ đầu tư được giao trách nhiệm thực hiện công việc đấu thầu. "Nhà thầu" là tổ chức kinh tế có đủ tư cách pháp nhân tham gia đấu thầu. Trong trường hợp đấu thầu tuyển chọn tư vấn, nhà thầu có thể là cá nhân. Nhà thầu là nhà xây dựng trong đấu thầu xây lắp; là nhà cung cấp trong đấu thầu mua sắm hàng hoá; là nhà tư vấn trong đấu thầu tuyển chọn tư vấn; là nhà đầu tư trong đấu thầu lựa chọn đối tác đầu tư. Nhà thầu trong nước là nhà thầu có tư cách pháp nhân Việt Nam và hoạt động hợp pháp tại Việt Nam. 2. Khái niệm về đấu thầu xây dựng Đấu thầu xây dựng là quá trình lựa chọn các nhà thầu đáp ứng được các yêu cầu về xây dựng, lắp đặt thiết bị các công trình, hạng mục công trình, của bên mời thầu trên cơ sở cạnh tranh giữa các nhà thầu xây dựng. 6
- LuËn v¨n tèt nghiÖp NguyÔn M¹nh Cêng QLKT 39B 3. ý nghĩa của công tác đấu thầu Trong sự nghiệp công nghiệp hoá, hiện đại hoá nền kinh tế nước nhà, ngày càng có nhiều các dự án đầu tư và xây dựng trong nước cũng như đầu tư nước ngoài. Các công trình đòi hỏi ngày càng cao về chất lượng, kỹ thuật, tiến độ và giá cả. Vì vậy, câu hỏi đặt ra với các chủ đầu tư là làm thế nào để lựa chọn được các tổ chức và cá nhân có khả năng thực hiện tốt nhất những công việc trong chu trình của dự án ? Lịch sử phát triển và quản lý dự án trong nước và quốc tế đã khẳng định, đấu thầu là phương pháp có hiệu quả cao nhất thực hiện mục tiêu này, đảm bảo cho sự thành công của chủ đầu tư. Đấu thầu được xem như một phương pháp quản lý dự án có hiệu quả nhất hiện nay trên cơ sở chống độc quyền, tăng cường khả năng cạnh tranh giữa các nhà thầu. 4. Vai trò của đấu thầu trong xây dựng 4.1. Đối với các nhà thầu - Đối với nhà thầu xây dựng, thắng thầu đồng nghĩa với việc mang lại công ăn việc làm cho cán bộ công nhân viên, nâng cao uy tín của nhà thầu trên thương trường, thu được lợi nhuận, tích luỹ thêm được nhiều kinh nghiệm trong thi công và quản lý, đào tạo được đội ngũ cán bộ, công nhân kỹ thuật vững tay nghề, máy móc thiết bị thi công được tăng cường. - Hoạt động đấu thầu được tổ chức theo nguyên tắc công khai và bình đẳng, nhờ đó các nhà thầu sẽ có điều kiện để phát huy đến mức cao nhất cơ hội tìm kiếm công trình và khả năng của mình để trúng thầu. 4.2. Đối với chủ đầu tư - Thông qua đấu thầu, chủ đầu tư sẽ lựa chọn được các nhà thầu có khả năng đáp ứng được tốt nhất các yêu cầu kinh tế, kỹ thuật, tiến độ đặt ra của công trình. Trên cơ sở đó giúp cho chủ đầu tư vừa sử dụng hiệu quả, tiết kiệm vốn đầu tư, đồng thời vẫn đảm bảo được chất lượng cũng như tiến độ công trình. - Thông qua đấu thầu, chủ đầu tư cũng sẽ nắm bắt được quyền chủ động, quản lý có hiệu quả và giảm thiểu được các rủi ro phát sinh trong quá trình thực hiện dự án đầu tư do toàn bộ quá trình tổ chức đấu thầu và thực hiện kết quả đấu thầu được tuân thủ chặt chẽ theo quy định của pháp luật và sau khi chủ đầu tư đã có sự chuẩn bị kỹ lưỡng, đầy đủ về mọi mặt. - Để đánh giá đúng các hồ sơ dự thầu đòi hỏi đội ngũ cán bộ thực hiện công tác đấu thầu của chủ đầu tư phải tự nâng cao trình độ của mình về các mặt nên việc áp dụng phương thức đấu thầu còn giúp cho chủ đầu tư nâng cao trình độ và năng lực của cán bộ công nhân viên. 7
- LuËn v¨n tèt nghiÖp NguyÔn M¹nh Cêng QLKT 39B 4.3. Đối với Nhà nước - Đấu thầu góp phần nâng cao hiệu quả của công tác quản lý Nhà nước về đầu tư và xây dựng, quản lý sử dụng vốn một cách có hiệu quả, hạn chế và loại trừ được các tình trạng như: thất thoát lãng phí vốn đầu tư đặc biệt là vốn ngân sách, các hiện tượng tiêu cực phát sinh trong xây dựng cơ bản. - Đấu thầu tạo nên sự cạnh tranh mới và lành mạnh trong lĩnh vực xây dựng cơ bản, thúc đẩy sự phát triển của nền kinh tế hàng hoá trong ngành cũng như trong nền kinh tế quốc dân. II. Một số vấn đề về quy chế đấu thầu 1. Phạm vi và đối tượng áp dụng 1. 1. Phạm vi áp dụng Quy chế đấu thầu áp dụng để lựa chọn nhà thầu cho các dự án đầu tư tại Việt Nam phải được tổ chức đấu thầu và thực hiện tại Việt Nam. 1. 2. Đối tượng áp dụng Các dự án đầu tư thực hiện theo Quy chế Quản lý đầu tư và xây dựng có quy định phải thực hiện Quy chế đấu thầu là các dự án có sử dụng vốn ngân sách nhà nước, vốn tín dụng do nhà nước bảo lãnh, vốn tín dụng đầu tư phát triển của nhà nước, vốn đầu tư phát triển, bao gồm: a. Các dự án đầu tư xây dựng mới, cải tạo, sửa chữa lớn, nâng cấp các dự án đã đầu tư xây dựng. b. Các dự án đầu tư để mua sắm tài sản kể cả thiết bị, máy móc không cần lắp đặt và sản phẩm công nghệ khoa học mới. c. Các dự án sử dụng vốn ngân sách nhà nước quy hoạch vùng, lãnh thổ, quy hoạch phát triển ngành, quy hoạch xây dựng đô thị nông thôn. Các dự án liên doanh, hợp đồng hợp tác kinh doanh hoặc cổ phần có sự tham gia của các tổ chức kinh tế nhà nước (các doanh nghiệp nhà nước) từ 30% trở lên vào vốn pháp định, vốn kinh doanh hoặc vốn cổ phần. Các dự án sử dụng nguồn vốn tài trợ của các tổ chức quốc tế hoặc của tổ chức nước ngoài được thực hiện trên cơ sở nội dung Điều ước được các bên ký kết (các bên tài trợ và các bên Việt Nam). Trường hợp có những nội dung trong dự thảo Điều ước khác với 8
- LuËn v¨n tèt nghiÖp NguyÔn M¹nh Cêng QLKT 39B Quy chế này thì cơ quan được giao trách nhiệm đàm phán ký kết điều ước phải trình Thủ tướng chính phủ xem xét, quyết định trước khi ký kết. Các dự án cần lựa chọn đối tác đầu tư để thực hiện: a. Đối với dự án đầu tư trong nước, chỉ thực hiện khi có từ hai nhà đầu tư trở lên cùng muốn tham gia một dự án. b. Đối với dự án có vốn đầu tư nước ngoài, chỉ tổ chức đấu thầu theo quy chế này khi có từ hai nhà đầu tư trở lên cùng muốn tham gia một dự án hoặc Thủ tướng Chính phủ có yêu cầu phải đấu thầu để lựa chọn đối tác đầu tư thực hiện dự án. Đấu thầu khi có từ hai nhà đầu tư trở lên cùng muốn tham gia bao gồm: + Các dự án liên doanh + Các dự án thực hiện theo hình thức hợp đồng hợp tác kinh doanh + Các dự án BOT, BT, BTO. + Các dự án khác cần lựa chọn đối tác đầu tư. 2. Nguyên tắc đấu thầu Nhằm đảm bảo tính đúng đắn, khách quan, công bằng và hiệu quả trong đấu thầu, chủ thể quản lý dự án phải đảm bảo nghiêm túc các nguyên tắc sau: 2. 1. Nguyên tắc cạnh tranh với điều kiện ngang nhau Mỗi cuộc đấu thầu đều phải dược thực hiện với sự tham gia của một số nhà thầu có đủ năng lực để hình thành một cuộc cạnh tranh mạnh mẽ. Điều kiện đặt ra với các đơn vị ứng thầu và thông tin cung cấp cho họ phải ngang nhau, nhất thiết không có sự phân biệt đối xử. 2. 2. Nguyên tắc dữ liệu đầy đủ Các nhà thầu phải nhận được đầy đủ tài liệu đấu thầu với các thông tin chi tiết, rõ ràng và có hệ thống về quy mô, khối lượng, quy cách, yêu cầu chất lượng của công trình hay hàng hoá dịch vụ cần cung ứng, về tiến độ và điều kiện thực hiện. Để đảm bảo nguyên tắc này, chủ thể quản lý dự án phải nghiên cứu, tính toán, cân nhắc thấu đáo để tiên liệu rất kỹ và rất chắc chắn về mọi yếu tố có liên quan, phải cố gắng tránh tình trạng chuẩn bị sơ sài, tắc trách. 2. 3. Nguyên tắc đánh giá công bằng Các hồ sơ phải được đánh giá một cách không thiên vị theo cùng một chuẩn mực và được đánh giá bởi một hội đồng xét thầu có đủ năng lực và phẩm chất. Lý do để ''được chọn " hay 'bị loại " phải dược giải thích đầy đủ để tránh ngờ vực. 2. 4. Nguyên tắc trách nhiệm phân minh Theo nguyên tắc này không chỉ nghĩa vụ, quyền lợi của các bên liên quan được đề cập và chi tiết hoá trong hợp đồng, mà phạm vi trách nhiệm của mỗi bên ở từng phần việc đều được 9
- LuËn v¨n tèt nghiÖp NguyÔn M¹nh Cêng QLKT 39B phân định rõ ràng để không một sai sót nào không có người chịu trách nhiệm. Mỗi bên có liên quan đều phải biết rõ mình phải gánh chịu những hậu quả gì nếu có sơ xuất và do đó mỗi bên đều phải nỗ lực tối đa trong việc kiểm soát bất trắc và phòng ngừa rủi ro. 2. 5. Nguyên tắc "ba chủ thể " Trong quá trình thực hiện dự án luôn luôn có sư hiện diện đồng thời của ba chủ thể; chủ công trình, nhà thầu và kỹ sư tư vấn. Trong đó, "kỹ sư tư vấn " hiện diện như một nhân tố đảm bảo cho hợp đồng luôn được thực hiện một cách nghiêm túc đến từng chi tiết, mọi sự bất cập về kỹ thuật hoặc về tiến độ được phát hiện kịp thời, những biện pháp điều chỉnh thích hợp được đưa ra đúng lúc. Đồng thời, "kỹ sư tư vấn" cũng là nhân tố hạn chế tối đa với những mưu toan, thông đồng hoặc thoả hiệp, "châm chước" gây thiệt hại cho những chủ đích thực sự của dự án (Nhiều điều khoản được thi hành để buộc "kỹ sư tư vấn" phải là chuyên gia có đủ trình độ, năng lực phẩm chất và phải làm đúng vai trò của người trọng tài công minh, mẫn cảm, được cử ra bởi một công ty tư vấn chuyên ngành, công ty này cũng phải được lựa chọn thông qua đấu thầu theo một quy trình chặt chẽ) 2. 6. Nguyên tắc tuân thủ nghiêm ngặt sự quản lý thống nhất của nhà nước Theo nguyên tắc này mọi hoạt động trong quá trình đấu thầu các bên liên quan nhất thiết phải tuân theo Quy chế quản lý đấu thầu do Chính phủ ban hành nhằm đảm bảo tính đúng đắn, khách quan, công bằng và có tính cạnh tranh trong đấu thầu. 2. 7. Nguyên tắc bảo lãnh, bảo hành và bảo hiểm thích đáng Các khoản về bảo lãnh, bảo hành và bảo hiểm phải được đề cập trong túi hồ sơ dự thầu của các nhà thầu và phải được sự chấp nhận của chủ dự án. Với các dự án sử dụng vốn Ngân sách Nhà nước, vốn tín dụng do Nhà nước bảo lãnh, vốn tín dụng đầu tư phát triển của Nhà nước, vốn đầu tư phát triển của doanh nghiệp Nhà nước phải mua bảo hiểm công trình xây dựng để ứng phó với thiệt hại do những rủi ro bất ngờ và không lường trước. Đối tượng bảo hiểm bắt buộc cũng bao gồm cả các sản phẩm tư vấn, vật tư thiết bị, nhà xưởng phục vụ thi công và người lao động của các tổ chức tư vấn và nhà thầu xây lắp trong quá trình thực hiện dự án. Như vậy, chính sự tuân thủ các nguyên tắc nói trên đã kích thích sự cố gắng nghiêm túc của các bên và thúc đẩy sự hợp tác giữa các bên nhằm vào mục tiêu đáp ứng tốt nhất các yêu cầu về chất lượng, kỹ thuật, tài chính, tiến độ của dự án và do đó đảm bảo lợi ích thích đáng của cả chủ dự án và nhà thầu, góp phần tiết kiệm các nguồn lực xã hội. Đối với các đơn vị dự thầu, việc 10
- LuËn v¨n tèt nghiÖp NguyÔn M¹nh Cêng QLKT 39B làm quen với hoạt động đấu thầu là cách hữu hiệu giúp họ tích luỹ kiến thức và kinh nghiệm, tăng cường năng lực cạnh tranh trong đấu thầu. 3. Hình thức lựa chọn nhà thầu và phương thức áp dụng 3. 1. Hình thức lựa chọn nhà thầu a. Đấu thầu rộng rãi Đấu thầu rộng rãi là hình thức đấu thầu không hạn chế số lượng các nhà thầu tham gia. Bên mời thầu phải thông báo công khai về các điều kiện, thời gian dự thầu trên các phương tiện thông tin đại chúng tối thiểu 10 ngày trước khi phát hành hồ sơ mời thầu. Đấu thầu rộng rãi là hình thức chủ yếu được áp dụng trong đấu thầu. b. Đấu thầu hạn chế Đấu thầu hạn chế là hình thức đấu thầu mà bên mời thầu mời một số nhà thầu (tối thiểu là 5) có đủ năng lực tham dự. Danh sách nhà thầu tham dự phải được người có thẩm quyền hoặc cấp có thẩm quyền chấp thuận. Hình thức này chỉ được xem xét áp dụng khi có một trong các điều kiện sau : + Chỉ có một số nhà thầu có khả năng đáp ứng được yêu cầu của gói thầu. + Các nguồn vốn sử dụng yêu cầu phải tiến hành đấu thầu hạn chế. + Do tình hình cụ thể của gói thầu mà việc đấu thầu hạn chế có lợi thế. c. Chỉ định thầu Chỉ định thầu là hình thức chọn trực tiếp nhà thầu đáp ứng yêu cầu của gói thầu để thương thảo hoàn thiện hợp đồng. Hình thức này chỉ được áp dụng trong các trường hợp đặc biệt sau : +Trường hợp bất khả kháng do thiên tai, địch hoạ, sự cố cần khắc phục ngay thì chủ dự án (người được người có thẩm quyền giao trách nhiệm quản lý và thực hiện dự án) được phép chỉ định ngay đơn vị có đủ năng lực để thực hiện công việc kịp thời. Trong thời gian 10 ngày kể từ ngày quyết định chỉ định thầu, chủ dự án phải báo cáo người có thẩm quyền hoặc cấp có thẩm quyền về nội dung chỉ định thầu, người có thẩm quyền hoặc cấp có thẩm quyền nếu phát hiện chỉ định thầu sai với quy định phải kịp thời xử lý. + Gói thầu có tính chất nghiên cứu thử nghiệm, bí mật quốc gia, bí mật an ninh, bí mật quốc phòng do Thủ tướng chính phủ quyết định. + Gói thầu có giá trị dưới 1 tỷ đồng đối với mua sắm hàng hoá, xây lắp; dưới 500 triệu đồng đối với tư vấn. Bộ tài chính quy định cụ thể về chỉ định thầu mua sắm đồ dùng, vật tư, trang thiết bị, phương tiện làm việc thường xuyên của cơ quan Nhà nước, đoàn thể, doanh nghiệp Nhà nước; đồ dùng, vật tư, trang thiết bị phương tiện làm việc thông thường của lực lượng vũ trang. 11
- LuËn v¨n tèt nghiÖp NguyÔn M¹nh Cêng QLKT 39B + Gói thầu có tính chất đặc biệt khác do yêu cầu của cơ quan tài trợ vốn, do tính chất phức tạp về kỹ thuật và công nghệ hoặc do yêu cầu đột xuất của dự án, do người có thẩm quyền quyết định đầu tư chỉ định thầu trên cơ sở báo cáo thẩm định của Bộ kế hoạch và Đầu tư, ý kiến bằng văn bản của cơ quan tài trợ vốn và các cơ quan liên quan khác. + Phần vốn Ngân sách dành cho dự án của các cơ quan sự nghiệp để thực hiện nhiệm vụ nghiên cứu về quy hoạch phát triển kinh tế, quy hoạch phát triển ngành, quy hoạch chung xây dựng đô thị và nông thôn, đã được cơ quan Nhà nước có thẩm quyền giao nhiệm vụ thực hiện thì không phải đấu thầu, nhưng phải có hợp đồng cụ thể và giao nộp sản phẩm theo đúng quy định. +Gói thầu tư vấn lập báo cáo nghiên cứu tiền khả thi, khả thi của dự án đầu tư thì không phải đấu thầu, nhưng chủ đầu tư phải chọn nhà tư vấn phù hợp với yêu cầu của dự án. Khi áp dụng hình thức chỉ định thầu thì phải xác định rõ 3 nội dung sau: - Lý do chỉ định thầu - Kinh nghiệm và năng lực về mặt kỹ thuật, tài chính của nhà thầu được đề nghị chỉ định thầu. - Giá trị và khối lượng đã được người có thẩm quyền phê duyệt làm căn cứ cho chỉ định thầu (riêng gói thầu xây lắp phải có thiết kế và dự toán được phê duyệt theo quy định) d. Chào hàng cạnh tranh Hình thức này áp dụng cho những gói thầu mua sắm hàng hoá có giá trị dưới 2 tỷ đồng. Mỗi gói thầu phải có ít nhất 3 chào hàng của 3 nhà thầu khác nhau trên cơ sở chào hàng của bên mời thầu. Việc chào hàng có thể được thực hiện bằng cách gửi trực tiếp, bằng Fax, bằng đường bưu điện hoặc bằng các phương tiện khác. e. Mua sắm trực tiếp Hình thức mua sắm đặc biệt được áp dụng trong trường hợp bổ xung hợp đồng cũ đã thực hiện xong (dưới 1 năm) hoặc hợp đồng đang thực hiện với điều kiện chủ đầu tư có nhu cầu tăng thêm số lượng hàng hoá hoặc khối lượng công việc mà trước đó đã được tiến hành đấu thầu, nhưng phải đảm bảo không được vượt mức giá hoặc đơn giá trong hợp đồng đã ký trước đó. Trước khi ký hợp đồng, nhà thầu phải chứng minh có đủ năng lực về kỹ thuật và tài chính để thực hiện gói thầu. g. Mua sắm đặc biệt Hình thức này được áp dụng với các ngành hết sức đặc biệt mà nếu không có những quy định riêng thì không thể đấu thầu được. Cơ quan quản lý ngành phải xây dựng quy trình thực hiện đảm bảo các mục tiêu của quy chế đấu thầu và có ý kiến thoả thuận của Bộ kế hoạch và Đầu tư để trình Thủ tướng Chính phủ quyết định. 12
- LuËn v¨n tèt nghiÖp NguyÔn M¹nh Cêng QLKT 39B 3. 2 Phương thức đấu thầu a. Đấu thầu một túi hồ sơ Là phương thức mà nhà thầu nộp hồ sơ dự thầu trong một túi hồ sơ. Phương thức này được áp dụng đối với đấu thầu mua sắm hàng hoá và xây lắp. b. Đấu thầu 2 túi hồ sơ Là phương thức mà nhà thầu nộp đề xuất về mặt kỹ thuật và đề xuất về giá trong từng túi hồ sơ riêng vào cùng một thời điểm. Túi hồ sơ đề xuất kỹ thuật sẽ được xem xét trước để đánh giá. Các nhà thầu đạt số điểm kỹ thuật từ 70% trở lên sẽ được mở tiếp túi hồ sơ đề xuất về giá để đánh giá. Phương thức nầy chỉ được áp dụng đối với đấu thầu tuyển chọn tư vấn c. Đấu thầu hai giai đoạn Phương thức này áp dụng cho những trường hợp sau : + Các gói thầu mua sắm hàng hoá và xây lắp có giá trị từ 500 tỷ đồng trở lên + Các gói thầu mua sắm hàng hoá có tính chất lựa chọn công nghệ thiết bị toàn bộ, phức tạp về công nghệ và kỹ thuật hoặc gói thầu xây lắp đặc biệt phức tạp. +Dự án thực hiện hợp đồng chìa khoá trao tay ( là hợp đồng bao gồm toàn bộ các công việc, thiết kế, cung cấp thiết bị và xây lắp của một gói thầu được thực hiện thông qua một nhà thầu. Chủ đầu tư có trách nhiệm tham gia giám sát quá trình thực hiện, nghiệm thu và nhận bàn giao khi nhà thầu hoàn thành toàn bộ công trình theo hợp đồng đã ký) Quá trình thực hiện phương thức này như sau : Giai đoạn thứ nhất :Các nhà thầu nộp hồ sơ dự thầu sơ bộ gồm đề xuất về kỹ thuật và phương án tài chính (chưa có giá) để bên mời thầu xem xét và thảo luận cụ thể với từng nhà thầu nhằm thống nhất về yêu cầu và tiêu chuẩn kỹ thuật để nhà thầu chuẩn bị nộp hồ sơ dự thầu chính thức của mình Giai đoạn thứ hai : Bên mời thầu mời các nhà thầu tham gia trong giai đoạn thứ nhất nộp hồ sơ dự thầu chính thức với đề xuất về kỹ thuật đã được bổ xung hoàn chỉnh trên cùng một mặt bằng kỹ thuật và đề xuất chi tiết về tài chính với đầy đủ nội dung về tiến độ thực hiện, điều kiện thực hiện hợp đồng, giá dự thầu. III. TRình tự tổ chức đấu thầu xây lắp 1. Điều kiện thực hiện đấu thầu 1. 1. Điều kiện mời thầu Để cuộc đấu thầu đạt kết quả tốt, bên mời thầu cần chuẩn bị đủ các hồ sơ sau : 13
- LuËn v¨n tèt nghiÖp NguyÔn M¹nh Cêng QLKT 39B + Văn bản quyết định đầu tư hoặc giấy uỷ quyền cho phép đầu tư của cấp có thẩm quyền (Trường hợp cần đấu thầu tuyển chọn tư vấn lập báo cáo nghiên cứu khả thi phải có văn bản chấp thuận của "Người có thẩm quyền quyết định đầu tư " + Kế hoạch đấu thầu được phê duyệt + Hồ sơ mời thầu (Trường hợp sơ tuyển phải có hồ sơ sơ tuyển ) 1. 2. Điều kiện dự thầu Để được tham gia dự thầu, nhà thầu cần có những điều kiện sau: + Có giấy đăng ký kinh doanh. + Có đủ năng lực về kỹ thuật và tài chính đáp ứng yêu cầu của gói thầu. +Chỉ được tham gia một đơn dự thầu trong một gói thầu, dù là đơn phương hay liên doanh dự thầu. Trường hợp Tổng công ty đứng tên dự thầu thì các đơn vị trực thuộc nhưng hạch toán phụ thuộc không được phép tham dự với tư cách là nhà thầu độc lập trong cùng một gói thầu dưới hình thức là nhà thầu chính (liên danh hoặc đơn phương) 1. 3. Bên mời thầu không được tham gia với tư cách là nhà thầu đối với gói thầu do mình tổ chức. 2. Điều kiện đấu thầu quốc tế và ưu đãi nhà thầu Chỉ được tổ chức đấu thầu quốc tế trong các trường hợp sau: a. Đối với các gói thầu mà không có nhà thầu nào trong nước có khả năng đáp ứng yêu cầu của gói thầu. b. Đối với các dự án sử dụng nguồn vốn tài trợ của các tổ chức quốc tế hoặc của người nước ngoài có quy định trong điều ước là phải đấu thầu quốc tế. Nhà thầu nước ngoài khi tham dự đấu thầu quốc tế tại Việt Nam về xây lắp phải liên danh với nhà thầu Việt Nam hoặc phải cam kết sử dụng thầu phụ Việt Nam, nhưng phải nêu rõ sự phân chia giữa các bên về phạm vi, khối lượng và đơn giá tương ứng. Nhà thầu nước ngoài trúng thầu phải thực hiện cam kết về tỷ lệ % khối lượng công việc cùng với đơn giá tương ứng dành cho phía Việt Nam là liên doanh hoặc thầu phụ như đã nêu trong hồ sơ dự thầu. Trong khi thương thảo hoàn thiện hợp đồng, nếu nhà thầu nước ngoài trúng thầu không thực hiện các cam kết nêu trong hồ sơ dự thầu thì kết qủa đấu thầu sẽ bị huỷ bỏ. Các nhà thầu nước ngoài tham gia đấu thầu ở Việt Nam phải cam kết mua sắm và sử dụng các vật tư thiết bị phù hợp về chất lượng và giá cả đang sản xuất, gia công và hiện có tại Việt Nam. Nếu trong nước không có hoặc không có khả năng sản xuất, gia công thì nhà thầu được chào từ nguồn ngoại nhập trên cơ sở đảm bảo chất lượng và giá cả hợp lý. 14
- LuËn v¨n tèt nghiÖp NguyÔn M¹nh Cêng QLKT 39B Trong trường hợp hai hồ sơ dự thầu của nhà thầu nước ngoài được đánh giá ngang nhau, hồ sơ dự thầu có tỷ lệ công việc dành cho phía Việt Nam (là liên danh hoặc thầu phụ) cao hơn sẽ được chấp nhận. Nhà thầu trong nước tham dự đấu thầu quốc tế (đơn phương hoặc liên danh) được xét ưu tiên khi hồ sơ dự thầu được đánh giá tương đương với các hồ sơ dự thầu của nhà thầu nước ngoài. Trường hợp hai hồ sơ dự thầu được đánh giá ngang nhau, sẽ ưu tiên hồ sơ dự thầu có tỷ lệ nhân công nhiều hơn. Nhà thầu trong nước tham gia đấu thầu quốc tế sẽ được hưởng chế độ ưu đãi theo quy định của pháp luật. 3. Trình tự tổ chức đấu thầu xây lắp Việc tổ chức đấu thầu xây lắp được thực hiện theo trình tự sau: Bước 1: Sơ tuyển nhà thầu (nếu có) Việc sơ tuyển nhà thầu phải được tiến hành đối với các gói thầu có giá trị từ 200 tỷ đồng trở lên nhằm lựa chọn các nhà thầu có đủ năng lực và kinh nghiệm thực hiện, đáp ứng yêu cầu của hồ sơ mời thầu. Sơ tuyển nhà thầu được thực hiện theo các bước sau a. Lập hồ sơ sơ tuyển, bao gồm: + Thư mời sơ tuyển. + Chỉ dẫn sơ tuyển. + Tiêu chuẩn đánh giá. + Phụ lục kèm theo. b. Thông báo mời sơ tuyển c. Nhận và quản lý hồ sơ dự sơ tuyển d. Đánh giá hồ sơ dự sơ tuyển e. Trình duyệt kết quả sơ tuyển f. Thông báo kết quả sơ tuyển Bước 2 : Lập hồ sơ mời thầu Hồ sơ mời thầu bao gồm: a. Thư mời thầu b. Mẫu đơn dự thầu c. Chỉ dẫn đối với nhà thầu d. Các điều kiện ưu đãi (nếu có) 15
- LuËn v¨n tèt nghiÖp NguyÔn M¹nh Cêng QLKT 39B e. Các loại thuế theo quy định của pháp luật f. Hồ sơ thiết kế kỹ thuật kèm theo bản tiên lượng và chỉ dẫn kỹ thuật g. Tiến độ thi công h. Tiêu chuẩn đánh giá ( bao gồm cả phương pháp và cách thức quy đổi về cùng mặt bằng để xác định giá đánh giá ) i. Điều kiện chung và điều kiện cụ thể của hợp đồng j. Mẫu bảo lãnh dự thầu k. Mẫu thoả thuận hợp đồng l. Mẫu bảo lãnh thực hiện hợp đồng Bước 3: Gửi thư mời thầu hoặc thông báo mời thầu Gửi thư mời thầu được thực hiện đối với các gói thầu thực hiện hình thức đấu thầu hạn chế, đối với các gói thầu đã qua sơ tuyển, các gói thầu tư vấn đã có danh sách ngắn được chọn. Thông báo mời thầu áp dụng trong trường hợp đấu thầu rộng rãi. Nội dung thư hoặc thông báo mời thầu bao gồm : a. Tên và địa chỉ bên mời thầu b.Khái quát dự án, địa điểm, thời gian xây dựng và các nội dung khác c. Chỉ dẫn việc tìm hiểu hồ sơ mời thầu d.Các điều kiện tham gia dự thầu e. Thời gian, địa điểm nhận hồ sơ dự thầu Bước 4 : Nhận và quản lý hồ sơ dự thầu a. Nhận hồ sơ dự thầu Bên mời thầu tiếp nhận hồ sơ dự thầu của nhà thầu nộp trực tiếp hoặc gửi qua đường bưu điện theo địa chỉ và thời gian quy định trong hồ sơ mời thầu. Bên mời thầu không nhận hồ sơ dự thầu hoặc tài liệu bổ sung nào, kể cả thư giảm giá sau thời điểm đóng thầu. Các hồ sơ dự thầu nộp sau thời điểm đóng thầu được xem là không hợp lệ và được gửi trả lại cho nhà thầu theo nguyên trạng. b. Quản lý hồ sơ dự thầu Việc quản lý hồ sơ dự thầu được quản lý theo chế độ quản lý hồ sơ ‘Mật’. Bước 5 : Mở thầu Việc mở thầu được tiến hành theo trình tự sau: 1. Chuẩn bị mở thầu 16
- LuËn v¨n tèt nghiÖp NguyÔn M¹nh Cêng QLKT 39B Bên mời thầu mời đại diện của từng nhà thầu và có thể mời đại diện của các cơ quan quản lý có liên quan đến tham dự mở thầu để chứng kiến. Việc mở thầu được tiến hành theo địa điểm, thời gian ghi trong hồ sơ mời thầu, không phụ thuộc vào sự có mặt hay vắng mặt của nhà thầu được mời. 2. Trình tự mở thầu a. Thông báo thành phần tham dự b. Thông báo số lượng và tên nhà thầu nộp hồ sơ dự thầu. c. Kiểm tra niêm phong các hồ sơ dự thầu d. Mở lần lượt các túi hồ sơ dự thầu, đọc và ghi lại thông tin chủ yếu (Tên nhà thầu, số lượng bản chính, bản chụp hồ sơ dự thầu, giá trị thầu trong đó giảm giá, bảo lãnh dự thầu ( nếu có) và những vấn đề khác). đ. Thông qua biên bản mở thầu. e. Đại diện bên mời thầu, đại diện nhà thầu và đại diên của các cơ quan quản lý có liên quan ( nếu có mặt) ký xác nhận vào biên bản mở thầu. f. Tổ chuyên gia hoặc bên mời thầu ký xác nhận vào bản chính hồ sơ dự thầu trước khi tiến hành đánh giá hồ sơ dự thầu. Bản chính hồ sơ dự thầu được bảo quản theo chế độ bảo mật và việc đánh giá được tiến hành theo bản chụp. Bước 6: Đánh giá xếp hạng nhà thầu A. Việc đánh giá hồ sơ dự thầu xây lắp thực hiện theo trình tự sau 1. Đánh giá sơ bộ hồ sơ dự thầu Việc đánh giá sơ bộ là nhằm loại bỏ các hồ sơ dự thầu không đáp ứng yêu cầu,bao gồm: a. Kiểm tra tính hợp lệ và sự đáp ứng cơ bản của hồ sơ dự thầu. b. Xem xét sự đáp ứng cơ bản của hồ sơ dự thầu đối với hồ sơ mời thầu. c. Làm rõ hồ sơ dự thầu 2 Đánh giá chi tiết hồ sơ dự thầu. Việc đánh giá chi tiết hồ sơ dự thầu được thực hiện theo phương pháp đánh giá gồm hai bước sau : Bước1. Đánh giá về mặt kỹ thuật để chọn danh sách ngắn Việc đánh giá về mặt kỹ thuật để chọn danh sách ngắn được dựa trên các yêu cầu và tiêu chuẩn đánh giá đã quy định trong hồ sơ mời thầu và tiêu chuẩn đánh giá chi tiết được người 17
- LuËn v¨n tèt nghiÖp NguyÔn M¹nh Cêng QLKT 39B có thẩm quyền hoặc cấp có thẩm quyền phê duyệt trước thời điểm mở thầu.Các nhà thầu đạt số điểm tối thiểu từ 70% tổng số điểm về kỹ thuật trở lên sẽ được chọn vào danh sách ngắn. Bước 2. Đánh giá về tài chính, thương mại để xác định giá Tiến hành đánh giá tài chính, thương mại các nhà thầu thuộc danh sách ngắn trên cùng một mặt bằng theo tiêu chuẩn đánh giá được phê duyệt . Việc đánh giá về mặt tài chính, thương mại nhằm xác định giá đánh giá bao gồm các nội dung sau: - Sửa lỗi Sửa lỗi là việc sửa chữa những sai sót bao gồm lỗi số học, lỗi đánh máy, lỗi nhầm đơn vị. Nếu có sai lệch giữa đơn giá và tổng giá do việc nhân đơn giá với số lượng thì đơn giá dự thầu sẽ là cơ sở pháp lý. - Hiệu chỉnh các sai lệch Hồ sơ dự thầu có tổng giá trị các sai lệch vượt quá10% (tính theo giá trị tuyệt đối, không phụ thuộc vào việc làm tăng hay giảm giá dự thầu khi xác định giá đánh giá) so với giá dự thầu sẽ bị loại không xem xét tiếp. - Chuyển đổi giá trị dự thầu sang một đồng tiền chung. Đồng tiền dự thầu do bên mời thầu quy định trong hồ sơ mời thầu theo nguyên tắc một đồng tiền cho một khối lượng chào hàng. - Đưa về một mặt hàng để xác định giá đánh giá. - Xác định giá đánh giá của các hồ sơ dự thầu B. Xếp hạng nhà thầu Xếp hạng hồ sơ dự thầu thuộc danh sách ngắn theo giá đánh giá. Nhà thầu có giá đánh giá thấp nhất sẽ được xếp thứ nhất và được kiến nghị trúng thầu. Bước 7:Trình duyệt kết quả đấu thầu 1. Trách nhiệm trình duyệt kết quả đấu thầu Chủ đầu tư hoặc chủ dự án có trách nhiệm trình kết quả đấu thầu lên người có thẩm quyền hoặc cấp có thẩm quyền để xem xét xin phê duyệt. 2. Hồ sơ trình duyệt kết quả đấu thầu. a. Văn bản trình duyệt kết quả đấu thầu. 18
- LuËn v¨n tèt nghiÖp NguyÔn M¹nh Cêng QLKT 39B Trong thành phần này cần nêu được các nội dung sau. - Nội dung gói thầu và cơ sở pháp lý của việc tổ chức đấu thầu. - Quá trình tổ chức đấu thầu. - Kết quả đánh giá hồ sơ dự thầu. - Đề nghị phê duyệt kết quả đấu thầu. b. Tài liệu kèm theo văn bản trình duyệt Tài liệu kèm theo văn bản trình duyệt kết quả đấu thầu bao gồm bản chụp các tài liệu sau đây: - Báo cáo đánh giá hồ sơ dự thầu của tổ chuyên gia tư vấn. - Quyết định đầu tư hoặc văn bản pháp lý tương đương, điều ước quốc tế và tài trợ (nếu có) - Văn bản phê duyệt các nội dung cơ bản của quá trình đấu thầu bao gồm: - Kế hoạnh đấu thầu của dự án. - Danh sách các nhà thầu tham gia hạn chế - Danh sách ngắn tư vấn tham gia dự thầu. - Hồ sơ mời sơ tuyển, đánh giá sơ tuyển và kết quả sơ tuyển nhà thầu. - Hồ sơ mời thầu. - Tiêu chuẩn đánh giá hồ sơ dự thầu. - Quyết định thành lập tổ chuyên gia tư vấn. - Biên bản mở thầu, các văn bản liên quan đến việc bên mời thầu yêu cầu nhà thầu làm rõ hồ sơ dự thầu (nếu có). - Dự thảo hợp đồng (nếu có). - Hồ sơ mời thầu và hồ sơ dự thầu của các nhà thầu. - ý kiến sơ bộ về kết quả đấu thầu của tổ chức tài trợ nước ngoài (nếu có). - Các tài liệu có liên quan khác. Bước 8: Công bố kết quả đấu thầu, thương thảo hoàn thiện và ký hợp đồng 19
- LuËn v¨n tèt nghiÖp NguyÔn M¹nh Cêng QLKT 39B 1. Công bố kết quả đấu thầu a. Nguyên tắc chung Ngay sau khi có quyết định của người có thẩm quyền hoặc cấp có thẩm quyền, bên mời thầu tiến hành công bố kết quả đấu thầu qua việc thông báo bằng văn bản cho các nhà thầu tham dự, bao gồm nhà thầu trúng thầu và nhà thầu không trúng thầu về kết quả đấu thầu. Trong trường hợp không có nhà thầu nào trúng thầu hoặc huỷ đấu thầu bên mời thầu phải tiến hành thông báo cho các nhà thầu biết. b. Cập nhật thông tin về năng lực nhà thầu Trước khi ký hợp đồng chính thức, bên mời thầu cần cập nhật những thay đổi về năng lực của nhà thầu cũng như những thông tin thay đổi làm ảnh hưởng tới khả năng thực hiện hợp đồng cũng như năng lực tài chính suy giảm, nguy cơ phá sản, bên mời thầu phải kịp thời báo cáo người có thẩm quyền hoặc cấp có thẩm quyền xem xét quyết định. c. Yêu cầu đối với thông báo trúng thầu Bên mời thầu phải gửi thư thông báo trúng thầu bằng văn bản tới nhà thầu kèm theo dự thảo hợp đồng và những điểm lưu ý cần trao đổi khi thương thảo hoàn thiện hợp đồng. Đồng thời bên mời thầu cũng phải thông báo cho nhà thầu lịch biểu nêu rõ yêu cầu về thời gian thương thảo hoàn thiện hợp đồng, nộp bảo lãnh thực hiện hợp đồng và ký hợp đồng. 2. Thương thảo hoàn thiện và ký kết hợp đồng a. Khi nhận được thông báo trúng thầu nhà thầu phải gửi cho bên mời thầu thư chấp thuận thương thảo, hoàn thiện hợp đồng. b. Theo lịch biểu đã được thống nhất, hai bên sẽ tiến hành thương thảo hoàn thiện hợp đồng để tiến tới ký hợp đồng chính thức. Thương thảo hoàn thiện hợp đồng bao gồm những nội dung cần giải quyết các vấn để còn tồn tại chưa hoàn chỉnh được hợp đồng với các nhà thầu trúng thầu, đặc biệt là duyệt áp giá đối với những sai lệch so với yêu cầu của hồ sơ mời thầu trên nguyên tắc giá trị hợp đồng không vượt giá trúng thầu cần duyệt. Việc thương thảo hoàn thiện hợp đồng cũng bao gồm cả việc nghiên cứu các sáng kiến, giải pháp ưu việt do nhà thầu đề xuất. c. Bên mời thầu nhận bảo lãnh thực hiện hợp đồng của nhà thầu trúng thầu trước khi ký hợp đồng. Trường hợp nhà thầu đã ký hợp đồng và nộp bảo lãnh thực hiện hợp đồng nhưng không thực hiện hợp đồng thì bên mời thầu có quyền không hoàn trả lại bảo lãnh thực hiện hợp đồng cho nhà thầu. 20
CÓ THỂ BẠN MUỐN DOWNLOAD
-
Luận văn tốt nghiệp: Một số giải biện pháp nhằm nâng cao hiệu quả sử dụng Vốn cố định tại công ty chè Long Phú
33 p |
804 |
407
-
Luận văn tốt nghiệp “Một số giải pháp và kiến nghị nhằm nâng cao hiệu quả công tác đấu thầu”
80 p |
503 |
394
-
Đề tài “Một số giải pháp để áp dụng hoạt động Marketing – Mix tại Công ty Điện tử Công nghiệp – CDC"
51 p |
502 |
316
-
Luận văn tốt nghiệp “Một số giải pháp chủ yếu góp phần nâng cao khả năng thắng thầu của Công ty xây dựng 319”
72 p |
354 |
247
-
Đồ án tốt nghiệp Một số biện pháp hoàn thiện công tác quản trị nhân lực ở Viện luyện kim đen
43 p |
371 |
120
-
báo cáo tốt nghiệp "Một số giải pháp chủ yếu góp phần nâng cao khả năng thắng thầu của Công ty xây dựng 319"
71 p |
165 |
86
-
Chuyên đề tốt nghiệp: Nâng cao hiệu quả sử dụng tài sản lưu động tại Công ty vận tải biển Vinalines
67 p |
165 |
79
-
Chuyên đề tốt nghiệp: Giải pháp nâng cao hiệu quả công tác quản trị bán hàng tại Công ty TNHH Việt Thiên
69 p |
103 |
53
-
Đồ án tốt nghiệp Một số biện pháp để nâng cao hiệu quả sử dụng vốn cố định ở Công ty dệt kim đông xuân Hà Nội
12 p |
144 |
48
-
Đồ án tốt nghiệp: Một số giải pháp nhằm giảm chi phí sản xuất để hạ giá thành sản phẩm của Xí nghiệp khai thác công trình thủy lợi huyện Gia Lộc - Hải Dương
33 p |
85 |
27
-
Đồ án tốt nghiệp “Một số giải pháp và kiến nghị nhằm nâng cao hiệu quả công tác đấu thầu”
78 p |
80 |
27
-
Khóa luận tốt nghiệp: Một số giải pháp về quản trị lực lượng bán hàng ở Công ty TNHH Phương Tùng
91 p |
53 |
23
-
Chuyên đề tốt nghiệp: Một số giải pháp để áp dụng hoạt động Marketing – Mix tại Công ty Điện tử Công nghiệp – CDC
52 p |
43 |
20
-
Luận văn: Một số giải pháp tài chính chủ yếu nâng cao hiệu quả tổ chức sử dụng vốn kinh doanh tại công ty cổ phần Thiờn Tõn
52 p |
58 |
15
-
Chuyên đề tốt nghiệp: Một số giải pháp marketing nhằm nâng cao hiệu quả sản xuất kinh doanh của Nhà xuất bản Giao thông vận tải
51 p |
37 |
15
-
Đề tài: Một số đề xuất và kiến nghị nhằm nâng cao hiệu quả sản xuất kinh doanh của xí nghiệp khai thác công trình thủy lợi tỉnh Hải Dương
51 p |
24 |
12
-
Khóa luận tốt nghiệp: Một số giải pháp nâng cao hiệu quả công tác đấu thầu xây lắp tại công ty Cổ Phần Thành Đạt
87 p |
1 |
0

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