markdown:
# Cấu trúc dữ liệu 2005 P9
Chia sẻ: Nhan Hoang | Ngày: | Loại File: PDF | Số trang:54
lượt xem 12
download
![](http://image1.tailieu.vn/document/thumbnail/2009/20091110/nguyen2/80x100/ctdl_2005_chuong_9_3045.jpg)
##
Cấu trúc dữ liệu 2005 P9
[Vui lòng tải xuống để xem tài liệu đầy đủ](javascript:void(0);)
Download
![](http://static1.tailieu.vn/b2013az/templates/version1/default/images/down16x21.png)
Tham khảo tài liệu 'cấu trúc dữ liệu 2005 p9', công nghệ thông tin, cơ sở dữ liệu 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: Cấu trúc dữ liệu 2005 P9
- Chöông 9 – Caây nhò phaân Chöông 9 – CAÂY NHÒ PHAÂN So vôùi hieän thöïc lieân tuïc cuûa caùc caáu truùc döõ lieäu, caùc danh saùch lieân keát coù nhöõng öu ñieåm lôùn veà tính meàm deûo. Nhöng chuùng cuõng coù moät ñieåm yeáu, ñoù laø söï tuaàn töï, chuùng ñöôïc toå chöùc theo caùch maø vieäc di chuyeån treân chuùng chæ coù theå qua töøng phaàn töû moät. Trong chöông naøy chuùng ta khaéc phuïc nhöôïc ñieåm naøy baèng caùch söû duïng caùc caáu truùc döõ lieäu caây chöùa con troû. Caây ñöôïc duøng trong raát nhieàu öùng duïng, ñaëc bieät trong vieäc truy xuaát döõ lieäu. 9.1. Caùc khaùi nieäm cô baûn veà caây Moät caây (tree) - hình 9.1- goàm moät taäp höõu haïn caùc nuùt (node) vaø moät taäp höõu haïn caùc caønh (branch) noái giöõa caùc nuùt. Caønh ñi vaøo nuùt goïi laø caønh vaøo (indegree), caønh ñi ra khoûi nuùt goïi laø caønh ra (outdegree). Soá caønh ra töø moät nuùt goïi laø baäc (degree) cuûa nuùt ñoù. Neáu caây khoâng roãng thì phaûi coù moät nuùt goïi laø nuùt goác (root), nuùt naøy khoâng coù caønh vaøo. Caây trong hình 9.1 coù M laø nuùt goác. Caùc nuùt coøn laïi, moãi nuùt phaûi coù chính xaùc moät caønh vaøo. Taát caû caùc nuùt ñeàu coù theå coù 0, 1, hoaëc nhieàu hôn soá caønh ra. M A D O N C Y E L S B T X (a) M - A - - N - - C - - - B M(A(NC(B))DO(Y(TX)ELS)) - D (c) - O - - Y - - - T - - - X - - E - - L - - S (b) Hình 9.1 – Caùc caùch bieåu dieãn cuûa caây Giaùo trình Caáu truùc Döõ lieäu vaø Giaûi thuaät 183
- Chöông 9 – Caây nhò phaân Nuùt laù (leaf) ñöôïc ñònh nghóa nhö laø nuùt cuûa caây maø soá caønh ra baèng 0. Caùc nuùt khoâng phaûi nuùt goác hoaëc nuùt laù thì ñöôïc goïi laø nuùt trung gian hay nuùt trong (internal node). Nuùt coù soá caønh ra khaùc 0 coù theå goïi laø nuùt cha (parent) cuûa caùc nuùt maø caønh ra cuûa noù ñi vaøo, caùc nuùt naøy cuõng ñöôïc goïi laø caùc nuùt con (child) cuûa noù. Caùc nuùt cuøng cha ñöôïc goïi laø caùc nuùt anh em (sibling) vôùi nhau. Nuùt treân nuùt cha coù theå goïi laø nuùt oâng (grandparent, trong moät soá baøi toaùn chuùng ta cuõng caàn goïi teân nhö vaäy ñeå trình baøy giaûi thuaät). Theo hình 9.1, caùc nuùt laù goàm: N, B, D, T, X, E, L, S; caùc nuùt trung gian goàm: A, C, O, Y. Nuùt Y laø cha cuûa hai nuùt T vaø X. T vaø X laø con cuûa Y, vaø laø nuùt anh em vôùi nhau. Ñöôøng ñi (path) töø nuùt n1 ñeán nuùt nk ñöôïc ñònh nghóa laø moät daõy caùc nuùt n1, n2, …, nk sao cho ni laø nuùt cha cuûa nuùt ni+1 vôùi 1≤ i< k. Chieàu daøi (length) ñöôøng ñi naøy laø soá caønh treân noù, ñoù laø k-1. Moãi nuùt coù ñöôøng ñi chieàu daøi baèng 0 ñeán chính noù. Trong moät caây, töø nuùt goác ñeán moãi nuùt coøn laïi chæ coù duy nhaát moät ñöôøng ñi. Ñoái vôùi moãi nuùt ni, ñoä saâu (depth) hay coøn goïi laø möùc (level) cuûa noù chính laø chieàu daøi ñöôøng ñi duy nhaát töø nuùt goác ñeán noù coäng 1. Nuùt goác coù möùc baèng 1. Chieàu cao (height) cuûa nuùt ni laø chieàu daøi cuûa ñöôøng ñi daøi nhaát töø noù ñeán moät nuùt laù. Moïi nuùt laù coù chieàu cao baèng 1. Chieàu cao cuûa caây baèng chieàu cao cuûa nuùt goác. Ñoä saâu cuûa caây baèng ñoä saâu cuûa nuùt laù saâu nhaát, noù luoân baèng chieàu cao cuûa caây. Neáu giöõa nuùt n1 vaø nuùt n2 coù moät ñöôøng ñi, thì n1 ñöôc goïi laø nuùt tröôùc (ancestor) cuûa n2 vaø n2 laø nuùt sau (descendant) cuûa n1. M laø nuùt tröôùc cuûa nuùt B. M laø nuùt goác, coù möùc laø 1. Ñöôøng ñi töø M ñeán B laø: M, A, C, B, coù chieàu daøi laø 3. B coù möùc laø 4. B laø nuùt laù, coù chieàu cao laø 1. Chieàu cao cuûa C laø 2, cuûa A laø 3, vaø cuûa M laø 4 chính baèng chieàu cao cuûa caây. Moät caây coù theå ñöôïc chia thaønh nhieàu caây con (subtree). Moät caây con laø baát kyø moät caáu truùc caây beân döôùi cuûa nuùt goác. Nuùt ñaàu tieân cuûa caây con laø nuùt goác cuûa noù vaø ñoâi khi ngöôøi ta duøng teân cuûa nuùt naøy ñeå goïi cho caây con. Caây con goác A (hay goïi taét laø caây con A) goàm caùc nuùt A, N, C, B. Moät caây con cuõng coù theå chia thaønh nhieàu caây con khaùc. Khaùi nieäm caây con daãn ñeán ñònh nghóa ñeä quy cho caây nhö sau: Giaùo trình Caáu truùc Döõ lieäu vaø Giaûi thuaät 184
- Chöông 9 – Caây nhò phaân Ñònh nghóa: Moät caây laø taäp caùc nuùt maø - laø taäp roãng, hoaëc - coù moät nuùt goïi laø nuùt goác coù khoâng hoaëc nhieàu caây con, caùc caây con cuõng laø caây Caùc caùch bieåu dieãn caây Thoâng thöôøng coù 3 caùch bieåu dieãn caây: bieåu dieãn baèng ñoà thò – hình 9.1a, bieåu dieãn baèng caùch canh leà – hình 9.1b, vaø bieåu dieãn baèng bieåu thöùc coù daáu ngoaëc – hình 9.1c. 9.2. Caây nhò phaân 9.2.1. Caùc ñònh nghóa Ñònh nghóa: Moät caây nhò phaân hoaëc laø moät caây roãng, hoaëc bao goàm moät nuùt goïi laø nuùt goác (root) vaø hai caây nhò phaân ñöôïc goïi laø caây con beân traùi vaø caây con beân phaûi cuûa nuùt goác. Löu yù raèng ñònh nghóa naøy laø ñònh nghóa toaùn hoïc cho moät caáu truùc caây. Ñeå ñaëc taû caây nhò phaân nhö moät kieåu döõ lieäu tröøu töôïng, chuùng ta caàn chæ ra caùc taùc vuï coù theå thöïc hieän treân caây nhò phaân. Caùc phöông thöùc cô baûn cuûa moät caây nhò phaân toång quaùt chuùng ta baøn ñeán coù theå laø taïo caây, giaûi phoùng caây, kieåm tra caây roãng, duyeät caây,… Ñònh nghóa naøy khoâng quan taâm ñeán caùch hieän thöïc cuûa caây nhò phaân trong boä nhôù. Chuùng ta seõ thaáy ngay raèng moät bieåu dieãn lieân keát laø töï nhieân vaø deã söû duïng, nhöng caùc hieän thöïc khaùc nhö maûng lieân tuïc cuõng coù theå thích hôïp. Ñònh nghóa naøy cuõng khoâng quan taâm ñeán caùc khoùa hoaëc caùch maø chuùng ñöôïc saép thöù töï. Caây nhò phaân ñöôïc duøng cho nhieàu muïc ñích khaùc hôn laø chæ coù tìm kieám truy xuaát, do ñoù chuùng ta caàn giöõ moät ñònh nghóa toång quaùt. Tröôùc khi xem xeùt xa hôn veà caùc ñaëc tính chung cuûa caây nhò phaân, chuùng ta haõy quay veà ñònh nghóa toång quaùt vaø nhìn xem baûn chaát ñeä quy cuûa noù theå hieän nhö theá naøo trong caáu truùc cuûa moät caây nhò phaân nhoû. Tröôøng hôïp thöù nhaát, moät tröôøng hôïp cô baûn khoâng lieân quan ñeán ñeä quy, ñoù laø moät caây nhò phaân roãng. Caùch duy nhaát ñeå xaây döïng moät caây nhò phaân coù moät nuùt laø cho nuùt ñoù laø goác vaø cho hai caây con traùi vaø phaûi laø hai caây roãng. Vôùi caây coù hai nuùt, moät trong hai seõ laø goác vaø nuùt coøn laïi seõ thuoäc caây con. Hoaëc caây con traùi hoaëc caây con phaûi laø caây roãng, vaø caây coøn laïi chöùa chính xaùc chæ Giaùo trình Caáu truùc Döõ lieäu vaø Giaûi thuaät 185
- Chöông 9 – Caây nhò phaân moät nuùt. Nhö vaäy coù hai caây nhò phaân khaùc nhau coù hai nuùt. Hai caây nhò phaân coù hai nuùt coù theå ñöôïc veõ nhö sau: vaø vaø ñaây laø hai caây khaùc nhau. Chuùng ta seõ khoâng bao giôø veõ baát kyø moät phaàn naøo cuûa moät caây nhò phaân nhö sau: do chuùng ta seõ khoâng theå noùi ñöôïc nuùt beân döôùi laø con traùi hay con phaûi cuûa nuùt treân. Ñoái vôùi tröôøng hôïp caây nhò phaân coù ba nuùt, moät trong chuùng seõ laø goác, vaø hai nuùt coøn laïi coù theå ñöôïc chia giöõa caây con traùi vaø caây con phaûi theo moät trong caùc caùch sau: 2+0 1+1 0+2 Do coù theå coù hai caây nhò phaân coù hai nuùt vaø chæ coù moät caây roãng, tröôøng hôïp thöù nhaát treân cho ra hai caây nhò phaân. Tröôøng hôïp thöù ba, töông töï, cho theâm hai caây khaùc. Tröôøng hôïp giöõa, caây con traùi vaø caây con phaûi moãi caây chæ coù moät nuùt, vaø chæ coù duy nhaát moät caây nhò phaân coù moät nuùt neân tröôøng hôïp naøy chæ coù moät caây nhò phaân. Taát caû chuùng ta coù naêm caây nhò phaân coù ba nuùt: Hình 9.2- Caùc caây nhò phaân coù ba nuùt Caùc böôùc ñeå xaây döïng caây naøy laø moät ñieån hình cho caùc tröôøng hôïp lôùn hôn. Chuùng ta baét ñaàu töø goác cuûa caây vaø xem caùc nuùt coøn laïi nhö laø caùc caùch phaân chia giöõa caây con traùi vaø caây con phaûi. Caây con traùi vaø caây con phaûi luùc naøy seõ laø caùc tröôøng hôïp nhoû hôn maø chuùng ta ñaõ bieát. Giaùo trình Caáu truùc Döõ lieäu vaø Giaûi thuaät 186
- Chöông 9 – Caây nhò phaân Goïi N laø soá nuùt cuûa caây nhò phaân, H laø chieàu cao cuûa caây thì, Hmax = N, Hmin = ⎣log2N⎦ +1 Nmin = H, Nmax = 2H-1 Khoaûng caùch töø moät nuùt ñeán nuùt goác xaùc ñònh chi phí caàn ñeå ñònh vò noù. Chaúng haïn moät nuùt coù ñoä saâu laø 5 thì chuùng ta phaûi ñi töø nuùt goác vaø qua 5 caønh treân ñöôøng ñi töø goác ñeán noù ñeå tìm ñeán noù. Do ñoù, neáu caây caøng thaáp thì vieäc tìm ñeán caùc nuùt seõ caøng nhanh. Ñieàu naøy daãn ñeán tính chaát caân baèng cuûa caây nhò phaân. Heä soá caân baèng cuûa caây (balance factor) laø söï cheânh leäch giöõa chieàu cao cuûa hai caây con traùi vaø phaûi cuûa noù: B = HL-HR Moät caây caân baèng khi heä soá naøy baèng 0 vaø caùc caây con cuûa noù cuõng caân baèng. Moät caây nhò phaân caân baèng vôùi chieàu cao cho tröôùc seõ coù soá nuùt laø lôùn nhaát coù theå. Ngöôïc laïi, vôùi soá nuùt cho tröôùc caây nhò phaân caân baèng coù chieàu cao nhoû nhaát. Thoâng thöôøng ñieàu naøy raát khoù xaûy ra neân ñònh nghóa coù theå nôùi loûng hôn vôùi caùc trò B = –1, 0, hoaëc 1 thay vì chæ laø 0. Chuùng ta seõ hoïc kyõ hôn veà caây caân baèng AVL trong phaàn sau. Moät caây nhò phaân ñaày ñuû (complete tree) laø caây coù ñöôïc soá nuùt toái ña vôùi chieàu cao cuûa noù. Ñoù cuõng chính laø caây coù B=0 vôùi moïi nuùt. Thuaät ngöõ caây nhò phaân gaàn nhö ñaày ñuû cuõng ñöôïc duøng cho tröôøng hôïp caây coù ñöôïc chieàu cao toái thieåu cuûa noù vaø moïi nuùt ôû möùc lôùn nhaát doàn heát veà beân traùi. Hình 9.3 bieåu dieãn caây nhò phaân ñaày ñuû coù 31 nuùt. Giaû söû loaïi ñi caùc nuùt 19, 21, 23, 25, 27, 29, 31 ta coù moät caây nhò phaân gaàn nhö ñaày ñuû. Hình 9.3 – Caây nhò phaân ñaày ñuû vôùi 31 nuùt. 9.2.2. Duyeät caây nhò phaân Moät trong caùc taùc vuï quan troïng nhaát ñöôïc thöïc hieän treân caây nhò phaân laø duyeät caây (traversal). Moät pheùp duyeät caây laø moät söï di chuyeån qua khaép caùc nuùt cuûa caây theo moät thöù töï ñònh tröôùc, moãi nuùt chæ ñöôïc xöû lyù moät Giaùo trình Caáu truùc Döõ lieäu vaø Giaûi thuaät 187
- Chöông 9 – Caây nhò phaân laàn duy nhaát. Cuõng nhö pheùp duyeät treân caùc caáu truùc döõ lieäu khaùc, haønh ñoäng maø chuùng ta caàn laøm khi gheù qua moät nuùt seõ phuï thuoäc vaøo öùng duïng. Ñoái vôùi caùc danh saùch, caùc nuùt naèm theo moät thöù töï töï nhieân töø nuùt ñaàu ñeán nuùt cuoái, vaø pheùp duyeät cuõng theo thöù töï naøy. Tuy nhieân, ñoái vôùi caùc caây, coù raát nhieàu thöù töï khaùc nhau ñeå duyeät qua caùc nuùt. Coù 2 caùch tieáp caän chính khi duyeät caây: duyeät theo chieàu saâu vaø duyeät theo chieàu roäng. Duyeät theo chieàu saâu (defth-first traversal): moïi nuùt sau cuûa moät nuùt con ñöôïc duyeät tröôùc khi sang moät nuùt con khaùc. Duyeät theo chieàu roäng (breadth-first traversal): moïi nuùt trong cuøng moät möùc ñöôïc duyeät tröôùc khi sang möùc khaùc. 9.2.2.1. Duyeät theo chieàu saâu Taïi moät nuùt cho tröôùc, coù ba vieäc maø chuùng ta muoán laøm: gheù nuùt naøy, duyeät caây con beân traùi, duyeät caây con beân phaûi. Söï khaùc nhau giöõa caùc phöông aùn duyeät laø chuùng ta quyeát ñònh gheù nuùt ñoù tröôùc hoaëc sau khi duyeät hai caây con, hoaëc giöõa khi duyeät hai caây con. Neáu chuùng ta goïi coâng vieäc gheù moät nuùt laø V, duyeät caây con traùi laø L, duyeät caây con phaûi laø R, thì coù ñeán saùu caùch keát hôïp giöõa chuùng: VLR LVR LRV VRL RVL RLV. Caùc thöù töï duyeät caây chuaån Theo quy öôùc chuaån, saùu caùch duyeät treân giaûm xuoáng chæ coøn ba bôûi chuùng ta chæ xem xeùt caùc caùch maø trong ñoù caây con traùi ñöôïc duyeät tröôùc caây con phaûi. Ba caùch coøn laïi roõ raøng laø töông töï vì chuùng chính laø nhöõng thöù töï ngöôïc cuûa ba caùch chuaån. Caùc caùch chuaån naøy ñöôïc ñaëït teân nhö sau: VLR LVR LRV preorder inorder postorder Caùc teân naøy ñöôïc choïn töông öùng vôùi böôùc maø nuùt ñaõ cho ñöôïc gheù ñeán. Trong pheùp duyeät preorder, nuùt ñöôïc gheù tröôùc caùc caây con; trong pheùp duyeät inorder, noù ñöôïc gheù ñeán giöõa khi duyeät hai caây con; vaø trong pheùp duyeät postorder, goác cuûa caây ñöôïc gheù sau hai caây con cuûa noù. Giaùo trình Caáu truùc Döõ lieäu vaø Giaûi thuaät 188
- Chöông 9 – Caây nhò phaân Pheùp duyeät inorder ñoâi khi coøn ñöôïc goïi laø pheùp duyeät ñoái xöùng (symmetric order), vaø postorder ñöôïc goïi laø endorder. Caùc ví duï ñôn giaûn Trong ví duï thöù nhaát, chuùng ta haõy xeùt caây nhò phaân sau: 1 2 3 Vôùi pheùp duyeät preorder, goác caây mang nhaõn 1 ñöôïc gheù ñaàu tieân, sau ñoù pheùp duyeät di chuyeån sang caây con traùi. Caây con traùi chæ chöùa moät nuùt coù nhaõn laø 2, nuùt naøy ñöôïc duyeät thöù hai. Sau ñoù pheùp duyeät chuyeån sang caây con phaûi cuûa nuùt goác, cuoái cuøng laø nuùt mang nhaõn 3 ñöôïc gheù. Vaäy pheùp duyeät preorder seõ gheù caùc nuùt theo thöù töï 1, 2, 3. Tröôùc khi goác cuûa caây ñöôïc gheù theo thöù töï inorder, chuùng ta phaûi duyeät caây con traùi cuûa noù tröôùc. Do ñoù nuùt mang nhaõn 2 ñöôïc gheù ñaàu tieân. Ñoù laø nuùt duy nhaát trong caây con traùi. Sau ñoù pheùp duyeät chuyeån ñeán nuùt goác mang nhaõn 1, vaø cuoái cuøng duyeät qua caây con phaûi. Vaäy pheùp duyeät inorder seõ gheù caùc nuùt theo thöù töï 2, 1, 3. Vôùi pheùp duyeät postorder, chuùng ta phaûi duyeät caùc hai caây con traùi vaø phaûi tröôùc khi gheù nuùt goác. Tröôùc tieân chuùng ta ñi ñeán caây con beân traùi chæ coù moät nuùt mang nhaõn 2, vaø noù ñöôïc gheù ñaàu tieân. Tieáp theo, chuùng ta duyeät qua caây con phaûi, gheù nuùt 3, vaø cuoái cuøng chuùng ta gheù nuùt 1. Pheùp duyeät postorder duyeät caùc nuùt theo thöù töï 2, 3, 1. Ví duï thöù hai phöùc taïp hôn, chuùng ta haõy xem xeùt caây nhò phaân döôùi ñaây: 1 2 3 4 5 Giaùo trình Caáu truùc Döõ lieäu vaø Giaûi thuaät 189
- Chöông 9 – Caây nhò phaân Töông töï caùch laøm treân chuùng ta coù pheùp duyeät preorder seõ gheù caùc nuùt theo thöù töï 1, 2, 3, 4, 5. Pheùp duyeät inorder seõ gheù caùc nuùt theo thöù töï 1, 4, 3, 5, 2. Pheùp duyeät postorder seõ gheù caùc nuùt theo thöù töï 4, 5, 3, 2, 1. Caây bieåu thöùc Caùch choïn caùc teân preorder, inorder, vaø postorder cho ba pheùp duyeät caây treân khoâng phaûi laø tình côø, noù lieân quan chaët cheõ ñeán moät trong nhöõng öùng duïng, ñoù laø caùc caây bieåu thöùc. Moät caây bieåu thöùc (expression tree) ñöôïc taïo neân töø caùc toaùn haïng ñôn giaûn vaø caùc toaùn töû (soá hoïc hoaëc luaän lyù) cuûa bieåu thöùc baèng caùch thay theá caùc toaùn haïng ñôn giaûn baèng caùc nuùt laù cuûa moät caây nhò phaân vaø caùc toaùn töû baèng caùc nuùt beân trong caây. Ñoái vôùi moãi toaùn töû hai ngoâi, caây con traùi chöùa moïi toaùn haïng vaø moïi toaùn töû thuoäc toaùn haïng beân traùi cuûa toaùn töû ñoù, vaø caây con phaûi chöùa moïi toaùn haïng vaø moïi toaùn töû thuoäc toaùn haïng beân phaûi cuûa noù. Hình 9.4 – Caây bieåu thöùc Ñoái vôùi toaùn töû moät ngoâi, moät trong hai caây con seõ roãng. Chuùng ta thöôøng vieát moät vaøi toaùn töû moät ngoâi phía beân traùi cuûa toaùn haïng cuûa chuùng, chaúng haïn daáu tröø (pheùp laáy soá aâm) hoaëc caùc haøm chuaån nhö log() vaø cos(). Caùc toaùn töû moät ngoâi khaùc ñöôïc vieát beân phaûi cuûa toaùn haïng, chaúng haïn haøm giai thöøa ()! hoaëc haøm bình phöông ()2. Ñoâi khi caû hai phía ñeàu hôïp leä, nhö pheùp laáy ñaïo haøm coù theå vieát d/dx phía beân traùi, hoaëc ()’ phía beân phaûi, hoaëc toaùn töû taêng ++ coù aûnh höôûng Giaùo trình Caáu truùc Döõ lieäu vaø Giaûi thuaät 190
- Chöông 9 – Caây nhò phaân khaùc nhau khi naèm beân traùi hoaëc naèm beân phaûi. Neáu toaùn töû ñöôïc ghi beân traùi, thì trong caây bieåu thöùc noù seõ coù caây con traùi roãng, nhö vaäy toaùn haïng seõ xuaát hieän beân phaûi cuûa noù trong caây. Ngöôïc laïi, neáu toaùn töû xuaát hieän beân phaûi, thì caây con phaûi cuûa noù seõ roãng, vaø toaùn haïng seõ laø caây con traùi cuûa noù. Moät soá caây bieåu thöùc cuûa moät vaøi bieåu thöùc ñôn giaûn ñöôïc minh hoïa trong hình 9.4. Hình 9.5 bieåu dieãn moät coâng thöùc baäc hai phöùc taïp hôn. Ba thöù töï duyeät caây chuaån cho caây bieåu thöùc naøy lieät keâ trong hình 9.6. Hình 9.5 – Caây bieåu thöùc cho coâng thöùc baäc hai. Caùc teân cuûa caùc pheùp duyeät lieân quan ñeán caùc daïng Balan cuûa bieåu thöùc: duyeät caây bieåu thöùc theo preorder laø daïng prefix, trong ñoù moãi toaùn töû naèm tröôùc caùc toaùn haïng cuûa noù; duyeät caây bieåu thöùc theo inorder laø daïng infix (caùch vieát bieåu thöùc quen thuoäc cuûa chuùng ta); duyeät caây bieåu thöùc theo postorder laø daïng postfix, moïi toaùn haïng naèm tröôùc toaùn töû cuûa chuùng. Nhö vaäy caùc caây con traùi vaø caây con phaûi cuûa moãi nuùt luoân laø caùc toaùn haïng cuûa noù, vaø vò trí töông ñoái cuûa moät toaùn töû so vôùi caùc toaùn haïng cuûa noù trong ba daïng Balan hoaøn toaøn gioáng vôùi thöù töï töông ñoái cuûa caùc laàn gheù caùc thaønh phaàn naøy theo moät trong ba pheùp duyeät caây bieåu thöùc. Giaùo trình Caáu truùc Döõ lieäu vaø Giaûi thuaät 191
- Chöông 9 – Caây nhò phaân Hình 9.6 – Caùc thöù tö duyeät cho caây bieåu thöùc Caây so saùnh Hình 9.7 – Caây so saùnh ñeå tìm nhò phaân Chuùng ta haõy xem laïi ví duï trong hình 9.7 vaø ghi laïi keát quaû cuûa ba pheùp duyeät caây chuaån nhö sau: preorder: Jim Dot Amy Ann Guy Eva Jan Ron Kay Jon Kim Tim Roy Tom inorder: Amy Ann Dot Eva Guy Jan Jim Jon Kay Kim Ron Roy Tim Tom postorder:Ann Amy Eva Jan Guy Dot Jon Kim Kay Roy Tom Tim Ron Jim Pheùp duyeät inorder cho caùc teân coù thöù töï theo alphabet. Caùch taïo moät caây so saùnh nhö hình 9.7 nhö sau: di chuyeån sang traùi khi khoùa cuûa nuùt caàn theâm nhoû hôn khoùa cuûa nuùt ñang xeùt, ngöôïc laïi thì di chuyeån sang phaûi. Nhö vaäy caây nhò phaân treân ñaõ ñöôïc xaây döïng sao cho moïi nuùt trong caây con traùi cuûa moãi nuùt coù thöù töï nhoû hôn thöù töï cuûa noù, vaø moïi nuùt trong caây con phaûi coù thöù töï lôùn hôn noù. Do ñoái vôùi moãi nuùt, pheùp duyeät inorder seõ duyeät qua caùc nuùt trong caây con traùi tröôùc, roài ñeán chính noù, vaø cuoái cuøng laø caùc nuùt trong caây con phaûi, neân chuùng ta coù ñöôïc caùc nuùt theo thöù töï. Giaùo trình Caáu truùc Döõ lieäu vaø Giaûi thuaät 192
- Chöông 9 – Caây nhò phaân Trong phaàn sau chuùng ta seõ tìm hieåu caùc caây nhò phaân vôùi ñaëc tính treân, chuùng coøn ñöôïc goïi laø caùc caây nhò phaân tìm kieám (binary search tree), do chuùng raát coù ích vaø hieäu quaû cho yeâu caàu tìm kieám. 9.2.2.2. Duyeät theo chieàu roäng Thöù töï duyeät caây theo chieàu roäng laø thöù töï duyeät heát möùc naøy ñeán möùc kia, coù theå töø möùc cao ñeán möùc thaáp hoaëc ngöôïc laïi. Trong moãi möùc coù theå duyeät töø traùi sang phaûi hoaëc töø phaûi sang traùi. Ví duï caây trong hình 9.7 neáu duyeät theo chieàu roäng töø möùc thaáp ñeán möùc cao, trong moãi möùc duyeät töø traùi sang phaûi, ta coù: Jim, Dot, Ron, Amy, Guy, Kay, Tim, Ann, Eva, Jan, Jon, Kim, Roy, Tom. 9.2.3. Hieän thöïc lieân keát cuûa caây nhò phaân Chuùng ta haõy xem xeùt caùch bieåu dieãn cuûa caùc nuùt ñeå xaây döïng neân caây. 9.2.3.1. Caáu truùc cô baûn cho moät nuùt trong caây nhò phaân Hình 9.8 – Caây nhò phaân lieân keát Moãi nuùt cuûa moät caây nhò phaân (cuõng laø goác cuûa moät caây con naøo ñoù) coù hai caây con traùi vaø phaûi. Caùc caây con naøy coù theå ñöôïc xaùc ñònh thoâng qua caùc con troû chæ ñeán caùc nuùt goác cuûa noù. Chuùng ta coù ñaëc taû sau: template struct Binary_node { // Caùc thaønh phaàn. Entry data; Binary_node *left; Binary_node *right; Giaùo trình Caáu truùc Döõ lieäu vaø Giaûi thuaät 193
- Chöông 9 – Caây nhò phaân // constructors: Binary_node(); Binary_node(const Entry &x); }; Binary_node chöùa hai constructor ñeàu khôûi gaùn caùc thuoäc tính con troû laø NULL moãi khi ñoái töôïng ñöôïc taïo ra. Trong hình 9.8, chuùng ta thaáy nhöõng tham chieáu NULL, tuy nhieân chuùng ta coù theå quy öôùc raèng caùc caây con roãng vaø caùc caønh ñeán noù coù theå boû qua khoâng caàn hieån thò khi veõ caây. 9.2.3.2. Ñaëc taû caây nhò phaân Moät caây nhò phaân coù moät hieän thöïc töï nhieân trong vuøng nhôù lieân keát. Cuõng nhö caùc caáu truùc lieân keát, chuùng ta seõ caáp phaùt ñoäng caùc nuùt, noái keát chuùng laïi vôùi nhau. Chuùng ta chæ caàn moät con troû chæ ñeán nuùt goác cuûa caây. template class Binary_tree { public: Binary_tree(); bool empty() const; void preorder(void (*visit)(Entry &)); void inorder(void (*visit)(Entry &)); void postorder(void (*visit)(Entry &)); int size() const; void clear(); int height() const; void insert(const Entry &); Binary_tree (const Binary_tree &original); Binary_tree & operator =(const Binary_tree &original); ~Binary_tree(); protected: // Caùc haøm ñeä quy phuï trôï: void recursive_inorder(Binary_node*sub_root, void (*visit)(Entry &)) void recursive_preorder(Binary_node*sub_root, void (*visit)(Entry &)) void recursive_postorder(Binary_node*sub_root, void (*visit)(Entry &)) Binary_node *root; }; Vôùi con troû root, coù theå deã daøng nhaän ra moät caây nhò phaân roãng bôûi bieåu thöùc root == NULL; vaø khi taïo moät caây nhò phaân môùi chuùng ta chæ caàn gaùn root baèng NULL. Giaùo trình Caáu truùc Döõ lieäu vaø Giaûi thuaät 194
- Chöông 9 – Caây nhò phaân template Binary_tree::Binary_tree() /* post: Caây nhò phaân roãng ñöôïc taïo ra. */ { root = NULL; } Phöông thöùc empty kieåm tra xem moät caây nhò phaân coù roãng hay khoâng: template bool Binary_tree::empty() const /* post: Traû veà true neáu caäy roãng, ngöôïc laïi traû veà false. */ { return root == NULL; } 9.2.3.3. Duyeät caây Baây giôø chuùng ta seõ xaây döïng caùc phöông thöùc duyeät moät caây nhò phaân lieân keát theo caû ba pheùp duyeät cô baûn. Cuõng nhö tröôùc kia, chuùng ta seõ giaû söû nhö chuùng ta ñaõ coù haøm visit ñeå thöïc hieän moät coâng vieäc mong muoán naøo ñoù cho moãi nuùt cuûa caây. Vaø nhö caùc haøm duyeät cho nhöõng caáu truùc döõ lieäu khaùc, con troû haøm visit seõ laø moät thoâng soá hình thöùc cuûa caùc haøm duyeät caây. Trong caùc haøm duyeät caây, chuùng ta caàn gheù ñeán nuùt goác vaø duyeät caùc caây con cuûa noù. Ñeä quy seõ laøm cho vieäc duyeät caùc caây con trôû neân heát söùc deã daøng. Caùc caây con ñöôïc tìm thaáy nhôø caùc con troû trong nuùt goác, do ñoù caùc con troû naøy caàn ñöôïc chuyeån cho caùc laàn goïi ñeä quy. Moãi phöông thöùc duyeät caàn goïi haøm ñeä quy coù moät thoâng soá con troû. Chaúng haïn, phöông thöùc duyeät inorder ñöôïc vieát nhö sau: template void Binary_tree::inorder(void (*visit)(Entry &)) /* post: Caây ñöôïc duyeät theo thöù töï inorder uses: Haøm recursive_inorder */ { recursive_inorder(root, visit); } Moät caùch toång quaùt, chuùng ta nhaän thaáy moät caùch toång quaùt raèng baát kyø phöông thöùc naøo cuûa Binary_tree maø baûn chaát laø moät quaù trình ñeä quy cuõng ñöôïc hieän thöïc baèng caùch goïi moät haøm ñeä quy phuï trôï coù thoâng soá laø goác cuûa caây. Haøm duyeät inorder phuï trôï ñöôïc hieän thöïc baèng caùch goïi ñeä quy ñôn giaûn nhö sau: Giaùo trình Caáu truùc Döõ lieäu vaø Giaûi thuaät 195
- Chöông 9 – Caây nhò phaân template void Binary_tree::recursive_inorder(Binary_node*sub_root, void (*visit)(Entry &)) /* pre: sub_root hoaëc laø NULL hoaëc chæ ñeán goác cuûa moät caây con. post: Caây con ñöôïc duyeät theo thöù töï inorder. uses: Haøm recursive_inorder ñöôïc goïi ñeä quy. */ { if (sub_root != NULL) { recursive_inorder(sub_root->left, visit); (*visit)(sub_root->data); recursive_inorder(sub_root->right, visit); } } Caùc phöông thöùc duyeät khaùc cuõng ñöôïc xaây döïng moät caùch töông töï baèng caùch goïi caùc haøm ñeä quy phuï trôï. caùc haøm ñeä quy phuï trôï coù hieän thöïc nhö sau: template void Binary_tree::recursive_preorder(Binary_node *sub_root, void (*visit)(Entry &)) /* pre: sub_root hoaëc laø NULL hoaëc chæ ñeán goác cuûa moät caây con. post: Caây con ñöôïc duyeät theo thöù töï preorder. uses: Haøm recursive_inorder ñöôïc goïi ñeä quy. */ { if (sub_root != NULL) { (*visit)(sub_root->data); recursive_preorder(sub_root->left, visit); recursive_preorder(sub_root->right, visit); } } template void Binary_tree::recursive_postorder(Binary_node *sub_root, void (*visit)(Entry &)) /* pre: sub_root hoaëc laø NULL hoaëc chæ ñeán goác cuûa moät caây con. post: Caây con ñöôïc duyeät theo thöù töï postorder. uses: Haøm recursive_inorder ñöôïc goïi ñeä quy. */ { if (sub_root != NULL) { recursive_postorder(sub_root->left, visit); recursive_postorder(sub_root->right, visit); (*visit)(sub_root->data); } } Chöông trình duyeät caây theo chieàu roäng luoân phaûi söû duïng ñeán CTDL haøng ñôïi. Neáu duyeät theo thöù töï töø möùc thaáp ñeán möùc cao, moãi möùc duyeät töø traùi sang phaûi, tröôùc tieân nuùt goác ñöôïc ñöa vaøo haøng ñôïi. Coâng vieäc ñöôïc laëp cho ñeán khi Giaùo trình Caáu truùc Döõ lieäu vaø Giaûi thuaät 196
- Chöông 9 – Caây nhò phaân haøng ñôïi roãng: laáy moät nuùt ra khoûi haøng ñôïi, xöû lyù cho noù, ñöa caùc nuùt con cuûa noù vaøo haøng ñôïi (theo ñuùng thöù töï töø traùi sang phaûi). Caùc bieán theå khaùc cuûa pheùp duyeät caây theo chieàu roäng cuõng voâ cuøng ñôn giaûn, sinh vieân coù theå töï suy nghó theâm. Chuùng ta ñeå phaàn hieän thöïc caùc phöông thöùc cuûa caây nhò phaân nhö height, size, vaø clear nhö laø baøi taäp. Caùc phöông thöùc naøy cuõng ñöôïc hieän thöïc deã daøng baèng caùch goïi caùc haøm ñeä quy phuï trôï. Trong phaàn baøi taäp chuùng ta cuõng seõ vieát phöông thöùc insert ñeå theâm caùc phaàn töû vaøo caây nhò phaân, phöông thöùc naøy caàn ñeå taïo moät caây nhò phaân, sau ñoù, keát hôïp vôùi caùc phöông thöùc neâu treân, chuùng ta seõ kieåm tra lôùp Binary_tree maø chuùng ta xaây döïng ñöôïc. Trong phaàn sau cuûa chöông naøy, chuùng ta seõ xaây döïng caùc lôùp daãn xuaát töø caây nhò phaân coù nhieàu ñaëc tính vaø höõu ích hôn (caùc lôùp daãn xuaát naøy seõ coù caùc phöông thöùc theâm hoaëc loaïi phaàn töû trong caây thích hôïp vôùi ñaëc tính cuûa töøng loaïi caây). Coøn hieän taïi thì chuùng ta khoâng neân theâm nhöõng phöông thöùc nhö vaäy vaøo caây nhò phaân cô baûn. Maëc duø lôùp Binary_tree cuûa chuùng ta xuaát hieän chæ nhö laø moät lôùp voû maø caùc phöông thöùc cuûa noù ñeàu ñaåy caùc coâng vieäc caàn laøm ñeán cho caùc haøm phuï trôï, baûn thaân noù laïi mang moät yù nghóa quan troïng. Lôùp naøy taäp trung vaøo noù nhieàu haøm khaùc nhau vaø cung caáp moät giao dieän thuaän tieän töông töï caùc kieåu döõ lieäu tröøu töôïng khaùc. Hôn nöõa, chính lôùp môùi coù theå cung caáp tính ñoùng kín: khoâng coù noù thì caùc döõ lieäu trong caây khoâng ñöôïc baûo veä moät caùch an toaøn vaø deã daøng bò thaâm nhaäp vaø söûa ñoåi ngoaøi yù muoán. Cuoái cuøng, chuùng ta coù theå thaáy lôùp Binary_tree coøn laøm moät lôùp cô sôû cho caùc lôùp khaùc daãn xuaát töø noù höõu ích hôn. 9.3. Caây nhò phaân tìm kieám Chuùng ta haõy xem xeùt vaán ñeà tìm kieám moät khoùa trong moät danh saùch lieân keát. Khoâng coù caùch naøo khaùc ngoaøi caùch di chuyeån treân danh saùch moãi laàn moät phaàn töû, vaø do ñoù vieäc tìm kieám treân danh saùch lieân keát luoân laø tìm tuaàn töï. Vieäc tìm kieám seõ trôû neân nhanh hôn nhieàu neáu chuùng ta söû duïng danh saùch lieân tuïc vaø tìm nhò phaân. Tuy nhieân, danh saùch lieân tuïc laïi khoâng phuø hôïp vôùi söï bieán ñoäng döõ lieäu. Giaû söû chuùng ta cuõng caàn thay ñoåi danh saùch thöôøng xuyeân, theâm caùc phaàn töû môùi hoaëc loaïi caùc phaàn töû hieän coù. Nhö vaäy danh saùch lieân tuïc seõ chaäm hôn nhieàu so vôùi danh saùch lieân keát, do vieäc theâm vaø loaïi phaàn töû trong danh saùch lieân tuïc moãi laàn ñeàu ñoøi hoûi phaûi di chuyeån nhieàu phaàn töû sang caùc vò trí khaùc. Trong danh saùch lieân keát chæ caàn thay ñoåi moät vaøi con troû maø thoâi. Vaán ñeà chuû choát trong phaàn naøy chính laø: Lieäu chuùng ta coù theå tìm moät hieän thöïc cho caùc danh saùch coù thöù töï maø trong ñoù chuùng ta coù theå tìm kieám, hoaëc theâm bôùt phaàn töû ñeàu raát nhanh? Giaùo trình Caáu truùc Döõ lieäu vaø Giaûi thuaät 197
- Chöông 9 – Caây nhò phaân Caây nhò phaân cho moät lôøi giaûi toát cho vaán ñeà naøy. Baèng caùch ñaët caùc entry cuûa moät danh saùch coù thöù töï vaøo trong caùc nuùt cuûa moät caây nhò phaân, chuùng ta seõ thaáy raèng chuùng ta coù theå tìm moät khoùa cho tröôùc qua O(log n) böôùc, gioáng nhö tìm nhò phaân, ñoàng thôøi chuùng ta cuõng coù giaûi thuaät theâm vaø loaïi phaàn töû trong O(log n) thôøi gian. Ñònh nghóa: Moät caây nhò phaân tìm kieám (binary search tree -BST) laø moät caây hoaëc roãng hoaëc trong ñoù moãi nuùt coù moät khoùa (naèm trong phaàn döõ lieäu cuûa noù) vaø thoûa caùc ñieàu kieän sau: 1. Khoùa cuûa nuùt goác lôùn hôn khoùa cuûa baát kyø nuùt naøo trong caây con traùi cuûa noù. 2. Khoùa cuûa nuùt goác nhoû hôn khoùa cuûa baát kyø nuùt naøo trong caây con phaûi cuûa noù. 3. Caây con traùi vaø caây con phaûi cuûa goác cuõng laø caùc caây nhò phaân tìm kieám. Hai ñaëc tính ñaàu tieân moâ taû thöù töï lieân quan ñeán khoùa cuûa nuùt goác, ñaëc tính thöù ba môû roäng chuùng ñeán moïi nuùt trong caây; do ñoù chuùng ta coù theå tieáp tuïc söû duïng caáu truùc ñeä quy cuûa caây nhò phaân. Chuùng ta ñaõ vieát ñònh nghóa naøy theo caùch maø noù baûo ñaûm raèng khoâng coù hai phaàn töû trong moät caây nhò phaân tìm kieám coù cuøng khoùa, do caùc khoùa trong caây con traùi chính xaùc laø nhoû hôn khoùa cuûa goác, vaø caùc khoùa cuûa caây con phaûi cuõng chính xaùc laø lôùn hôn khoùa cuûa goác. Chuùng ta coù theå thay ñoåi ñònh nghóa ñeå cho pheùp caùc phaàn töû truøng khoùa. Tuy nhieân trong phaàn naøy chuùng ta coù theå giaû söû raèng: Khoâng coù hai phaàn töû trong moät caây nhò phaân tìm kieám coù truøng khoùa. Caùc caây nhò phaân trong hình 9.7 vaø 9.8 laø caùc caây nhò phaân tìm kieám, do quyeát ñònh di chuyeån sang traùi hoaëc phaûi taïi moãi nuùt döïa treân caùch so saùnh caùc khoùa trong ñònh nghóa cuûa moät caây tìm kieám. 9.3.1. Caùc danh saùch coù thöù töï vaø caùc caùch hieän thöïc Ñaõ ñeán luùc baét ñaàu xaây döïng caùc phöông thöùc C++ ñeå xöû lyù cho caây nhò phaân tìm kieám, chuùng ta neân löu yù raèng coù ít nhaát laø ba quan ñieåm khaùc nhau döôùi ñaây: • Chuùng ta coù theå xem caây nhò phaân tìm kieám nhö moät kieåu döõ lieäu tröøu töôïng môùi vôùi ñònh nghóa vaø caùc phöông thöùc cuûa noù; • Do caây nhò phaân tìm kieám laø moät daïng ñaëc bieät cuûa caây nhò phaân, chuùng ta coù theå xem caùc phöông thöùc cuûa noù nhö caùc daïng ñaëc bieät cuûa caùc phöông thöùc cuûa caây nhò phaân; • Do caùc phaàn töû trong caây nhò phaân tìm kieám coù chöùa caùc khoùa, vaø do chuùng ñöôïc gaùn döõ lieäu ñeå truy xuaát thoâng tin theo caùch töông töï nhö caùc danh saùch coù thöù töï, chuùng ta coù theå nghieân cöùu caây nhò phaân tìm kieám nhö laø moät hieän thöïc môùi cuûa kieåu döõ lieäu tröøu töôïng danh saùch coù thöù töï (ordered list ADT). Giaùo trình Caáu truùc Döõ lieäu vaø Giaûi thuaät 198
- Chöông 9 – Caây nhò phaân Trong thöïc teá, ñoâi khi caùc laäp trình vieân chæ taäp trung vaøo moät trong ba quan ñieåm treân, vaø chuùng ta cuõng seõ nhö theá. Chuùng ta seõ ñaëc taû lôùp caây nhò phaân tìm kieám daãn xuaát töø caây nhò phaân. Nhö vaäy, lôùp caây nhò phaân cuûa chuùng ta laïi bieåu dieãn cho moät kieåu döõ lieäu tröøu töôïng khaùc. Tuy nhieân, lôùp môùi seõ thöøa keá caùc phöông thöùc cuûa lôùp caây nhò phaân tröôùc kia. Baèng caùch naøy, söï söû duïng lôùp thöøa keá nhaán maïnh vaøo hai quan ñieåm treân. Quan ñieåm thöù ba thöôøng ñöôïc nhìn thaáy trong caùc öùng duïng cuûa caây nhò phaân tìm kieám. Chöông trình cuûa ngöôøi söû duïng coù theå duøng lôùp cuûa chuùng ta ñeå giaûi quyeát caùc baøi toaùn saép thöù töï vaø tìm kieám lieân quan ñeán danh saùch coù thöù töï. Chuùng ta ñaõ ñöa ra nhöõng khai baùo C++ cho pheùp xöû lyù cho caây nhò phaân. Chuùng ta seõ söû duïng hieän thöïc naøy cuûa caây nhò phaân laøm cô sôû cho lôùp caây nhò phaân tìm kieám. template class Search_tree: public Binary_tree { public: Error_code insert(const Record &new_data); Error_code remove(const Record &old_data); Error_code tree_search(Record &target) const; private: // Caùc haøm ñeä quy phuï trôï. }; Do lôùp caây nhò phaân tìm kieám thöøa keá töø lôùp nhò phaân, chuùng ta coù theå duøng laïi caùc phöông thöùc ñaõ ñònh nghóa treân caây nhò phaân toång quaùt cho caây nhò phaân tìm kieám. Caùc phöông thöùc naøy laø constructor, destructor, clear, empty, size, height, vaø caùc phöông thöùc duyeät preorder, inorder, postorder. Ñeå theâm vaøo caùc phöông thöùc naøy, moät caây nhò phaân tìm kieám caàn theâm caùc phöông thöùc chuyeân bieät hoùa nhö insert, remove, vaø tree_search. 9.3.2. Tìm kieám treân caây Phöông thöùc môùi quan troïng ñaàu tieân cuûa caây nhò phaân tìm kieám laø: tìm moät phaàn töû vôùi moät khoùa cho tröôùc trong caây nhò phaân tìm kieám lieân keát. Ñaëc taû cuûa phöông thöùc nhö sau: Error_code Search_tree :: tree_search (Record &target) const; post: Neáu coù moät phaàn töû coù khoùa truøng vôùi khoùa trong target, thì target ñöôïc cheùp ñeø bôûi phaàn töû naøy, phöông thöùc traû veà success; ngöôïc laïi phöông thöùc traû veà not_present. ÔÛ ñaây chuùng ta duøng lôùp Record nhö ñaõ moâ taû trong chöông 7. Ngoaøi thuoäc tính thuoäc lôùp Key daønh cho khoùa, trong Record coù theå coøn nhieàu thaønh phaàn döõ lieäu khaùc. Trong caùc öùng duïng, phöông thöùc naøy thöôøng ñöôïc goïi vôùi thoâng soá target chæ chöùa trò cuûa thaønh phaàn khoùa. Neáu tìm thaáy khoùa caàn tìm, phöông thöùc seõ boå sung caùc döõ lieäu ñaày ñuû vaøo caùc thaønh phaàn khaùc coøn laïi cuûa Record. Giaùo trình Caáu truùc Döõ lieäu vaø Giaûi thuaät 199
- Chöông 9 – Caây nhò phaân 9.3.2.1. Chieán löôïc Ñeå tìm moät khoùa, tröôùc tieân chuùng ta so saùnh noù vôùi khoùa cuûa nuùt goác trong caây. Neáu so truøng, giaûi thuaät döøng. Ngöôïc laïi, chuùng ta ñi sang caây con traùi hoaëc caây con phaûi vaø laëp laïi vieäc tìm kieám trong caây con naøy. Ví duï, chuùng ta caàn tìm teân Kim trong caây nhò phaân tìm kieám hình 9.7 vaø 9.8. Chuùng ta so saùnh Kim vôùi phaàn töû taïi nuùt goác, Jim. Do Kim lôùn hôn Jim theo thöù töï alphabet, chuùng ta ñi sang phaûi vaø tieáp tuïc so saùnh Kim vôùi Ron. Do Kim nhoû hôn Jon, chuùng ta di chuyeån sang traùi, so saùnh Kim vôùi Kay. Chuùng ta laïi di chuyeån sang phaûi vaø gaëp ñöôïc phaàn töû caàn tìm. Ñaây roõ raøng laø moät quaù trình ñeä quy, cho neân chuùng ta seõ hieän thöïc phöông thöùc naøy baèng caùch goïi moät haøm ñeä quy phuï trôï. Lieäu ñieàu kieän döøng cuûa vieäc tìm kieám ñeä quy laø gì? Roõ raøng laø, neáu chuùng ta tìm thaáy phaàn töû caàn tìm, haøm seõ keát thuùc thaønh coâng. Neáu khoâng, chuùng ta seõ cöù tieáp tuïc tìm cho ñeán khi gaëp moät caây roãng, trong tröôøng hôïp naøy vieäc tìm kieám thaát baïi. Haøm ñeä quy tìm kieám phuï trôï seõ traû veà moät con troû chæ ñeán phaàn töû ñöôïc tìm thaáy. Maëc duø con troû naøy coù theå ñöôïc söû duïng ñeå truy xuaát ñeán döõ lieäu löu trong ñoái töôïng caây, nhöng chæ coù caùc haøm laø nhöõng phöông thöùc cuûa caây môùi coù theå goïi haøm tìm kieám phuï trôï naøy (vì chæ coù chuùng môùi coù theå gôûi thuoäc tính root cuûa caây laøm thoâng soá). Nhö vaäy, vieäc traû veà con troû ñeán moät nuùt seõ khoâng vi phaïm ñeán tính ñoùng kín cuûa caây khi nhìn töø öùng duïng beân ngoaøi. Chuùng ta coù ñaëc taû sau ñaây cuûa haøm tìm kieám phuï trôï. Binary_node *Search_tree :: search_for_node (Binary_node *sub_root, const Record &target) const; pre: sub_root hoaëc laø NULL hoaëc chæ ñeán moät caây con cuûa lôùp Search_tree. post:Neáu khoùa cuûa target khoâng coù trong caây con sub_tree, haøm traû veà NULL; ngöôïc laïi, haøm traû veà con troû ñeán nuùt chöùa target. 9.3.2.2. Phieân baûn ñeä quy Caùch ñôn giaûn nhaát ñeå vieát haøm tìm kieám treân laø duøng ñeä quy: template Binary_node *Search_tree::search_for_node( Binary_node* sub_root, const Record &target) const { if (sub_root == NULL || sub_root->data == target) return sub_root; else if (sub_root->data < target) return search_for_node(sub_root->right, target); else return search_for_node(sub_root->left, target); } Giaùo trình Caáu truùc Döõ lieäu vaø Giaûi thuaät 200
- Chöông 9 – Caây nhò phaân 9.3.2.3. Khöû ñeä quy Ñeä quy xuaát hieän trong haøm treân chæ laø ñeä quy ñuoâi, ñoù laø leänh cuoái cuøng ñöôïc thöïc hieän trong haøm. Baèng caùch söû duïng voøng laëp, ñeä quy ñuoâi luoân coù theå ñöôïc thay theá bôûi söï laëp laïi nhieàu laàn. Trong tröôøng hôïp naøy chuùng ta caàn vieát voøng laëp theá cho leänh if ñaàu tieân, vaø thay ñoåi thoâng soá sub_root ñeå noù di chuyeån xuoáng caùc caønh cuûa caây. template Binary_node *Search_tree::search_for_node( Binary_node *sub_root, const Record &target) const { while (sub_root != NULL && sub_root->data != target) if (sub_root->data < target) sub_root = sub_root->right; else sub_root = sub_root->left; return sub_root; } 9.3.2.4. Phöông thöùc tree_search Phöông thöùc tree_search ñôn giaûn chæ goïi haøm phuï trôï search_for_node ñeå tìm nuùt chöùa khoùa truøng vôùi khoùa caàn tìm trong caây tìm kieám nhò phaân. Sau ñoù noù trích döõ lieäu caàn thieát vaø traû veà Error_code töông öùng. template Error_code Search_tree::tree_search(Record &target) const /* post: Neáu tìm thaáy khoùa caàn tìm trong target, phöông thöùc seõ boå sung caùc döõ lieäu ñaày ñuû vaøo caùc thaønh phaàn khaùc coøn laïi cuûa target vaø traø veà success. Ngöôïc laïi traû veà not_present. Caû hai tröôøng hôïp caây ñeàu khoâng thay ñoåi. Uses: Haøm search_for_node */ { Error_code result = success; Binary_node *found = search_for_node(root, target); if (found == NULL) result = not_present; else target = found->data; return result; } 9.3.2.5. Haønh vi cuûa giaûi thuaät Chuùng ta thaáy raèng tree_search döïa treân cô sôû cuûa tìm nhò phaân. Neáu chuùng ta thöïc hieän tìm nhò phaân treân moät danh saùch coù thöù töï, chuùng ta thaáy raèng tìm nhò phaân thöïc hieän caùc pheùp so saùnh hoaøn toaøn gioáng nhö tree_search. Chuùng ta cuõng ñaõ bieát tìm nhò phaân thöïc hieän O(log n) laàn so saùnh ñoái vôùi danh saùch coù chieàu daøi n. Ñieàu naøy thöïc söï toát so vôùi caùc phöông phaùp tìm kieám khaùc, do log n taêng raát chaäm khi n taêng. Giaùo trình Caáu truùc Döõ lieäu vaø Giaûi thuaät 201
- Chöông 9 – Caây nhò phaân Caây trong hình 9.9a laø caây toát nhaát ñoái vôùi vieäc tìm kieám. Caây caøng “raäm raïp” caøng toát: noù coù chieàu cao nhoû nhaát ñoái vôùi soá nuùt cho tröôùc. Soá nuùt naèm giöõa nuùt goác vaø nuùt caàn tìm, keå caû nuùt caàn tìm, laø soá laàn so saùnh caàn thöïc hieän khi tìm kieám. Vì vaäy, caây caøng raäm raïp thì soá laàn so saùnh naøy caøng nhoû. Khoâng phaûi chuùng ta luoân coù theå döï ñoaùn tröôùc hình daïng cuûa moät caây nhò phaân tìm kieám tröôùc khi caây ñöôïc taïo ra, vaø caây ôû hình (b) laø moät caây ñieån hình thöôøng coù nhaát so vôùi caây ôû hình (a). Trong caây naøy, vieäc tìm phaàn töû c caàn boán laàn so saùnh, coøn hình (a) chæ caàn ba laàn so saùnh. Tuy nhieân, caây ôû hình (b) vaãn coøn töông ñoái raäm raïp vaø vieäc tìm kieám treân noù chæ dôû hôn moät ít so vôùi caây toái öu trong hình (a). Hình 9.9 – Moät vaøi caây nhò phaân tìm kieám coù caùc khoùa gioáng nhau Trong hình (c), caây ñaõ trôû neân suy thoaùi, vaø vieäc tìm phaàn töû c caàn ñeán 6 laàn so saùnh. Hình (d) vaø (e) caùc caây ñaõ trôû thaønh chuoãi caùc maéc xích. Khi tìm treân caùc chuoãi maéc xích nhö vaäy, tree_search khoâng theå laøm ñöôïc gì khaùc hôn laø duyeät töø phaàn töû naøy sang phaàn töû kia. Noùi caùch khaùc, tree_search khi thöïc hieän treân chuoãi caùc maéc xích nhö vaäy ñaõ suy thoaùi thaønh tìm tuaàn töï. Trong tröôøng hôïp xaáu Giaùo trình Caáu truùc Döõ lieäu vaø Giaûi thuaät 202
CÓ THỂ BẠN MUỐN DOWNLOAD
-
Đề thi cấu trúc dữ liệu và giải thuật có đáp án (2007-2008)
17 p |
3051 |
875
-
Chương 1: Nhập môn cấu trúc dữ liệu
33 p |
427 |
171
-
Các cấu trúc dữ liệu
7 p |
220 |
125
-
Cấu trúc dữ liệu 2005 P18
16 p |
92 |
23
-
Cấu trúc dữ liệu 2005 P15
10 p |
75 |
20
-
Cấu trúc dữ liệu 2005 P17
6 p |
74 |
17
-
Cấu trúc dữ liệu 2005 P16
8 p |
88 |
17
-
Cấu trúc dữ liệu 2005 P14
12 p |
72 |
17
-
Cấu trúc dữ liệu 2005 P12
34 p |
76 |
15
-
Cấu trúc dữ liệu 2005 P10
46 p |
68 |
13
-
Cấu trúc dữ liệu 2005 P11
22 p |
50 |
12
-
Cấu trúc dữ liệu 2005 P13
26 p |
82 |
9
-
Cấu trúc dữ liệu 2005 P5
16 p |
43 |
9
-
Cấu trúc dữ liệu 2005 P4
24 p |
39 |
9
-
Cấu trúc dữ liệu 2005 P6
46 p |
38 |
7
-
Cấu trúc dữ liệu 2005 P3
14 p |
28 |
7
-
Cấu trúc dữ liệu 2005 P7
12 p |
30 |
6

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


markdown:
# Đồ án tốt nghiệp : 'điều khiển logic '
Chia sẻ: Minh Tuan | Ngày: | Loại File: PDF | Số trang:30
lượt xem 308
download
![](http://image1.tailieu.vn/document/thumbnail/2009/20090720/minhtuan/80x100/do_an_hoang1_8993.jpg)
##
Đồ án tốt nghiệp : 'điều khiển logic '
[Vui lòng tải xuống để xem tài liệu đầy đủ](javascript:void(0);)
Download
![](http://static1.tailieu.vn/b2013az/templates/version1/default/images/down16x21.png)
Ngày nay tự động hoá điều khiển các quá trình sản xuất đã đi sâu vào từng ngõ nghách, vào trong tất cả các khâu của quá trình tạo ra sản phẩm. Một trong nhữnh ứng dụng đó mà đồ án này thiết kế là điều khiển công nghệ khoan. Tự động hoá điều khiển công nghệ khoan là quá trình tạo ra một lỗ thủng trên bề mặt vật thể có kích thước chiều sâu định trước. Trong công việc thiết kế, tự động hoá điều khiển được thể hiện qua hai quá trình sau...
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 : 'điều khiển logic '
- Đồ án điều khiển logic Triệu Tuyên Hoàng TĐH 3- K43 -------------------------------------------------------------------------------------- TRƯỜNG ĐẠI HỌC BÁCH KHOA HÀ NỘI THIẾT KẾ MÔN HỌC KHOA NĂNG LƯỢNG BỘ MÔN TỰ ĐỘNG HOÁ XNCN ĐIỀU KHIỂN LOGIC ĐỒ ÁN MÔN HỌC Sinh viên : TRIệU TUYÊN HOàNG Lớp : Tự động hoá 3 K43 1. NHIỆM VỤ THIẾT KẾ Thiết kế hệ thống điều khiển máy khoan có sơ đồ như hình vẽ bằng phương pháp ma trận trạng thái với mạch động lực dùng thiết bị khí nén và mạch điều khiển dùng thiết bị điện. 2. NỘI DUNG - Thiết kế sơ đồ nguyên lý. - Tính chọn thiết bị điều khiển. - Thiết kế sơ đồ lắp ráp. 3. THUYẾT MINH VÀ BẢN VẼ - 1 quyển thuyết minh. - 2 bản vẽ kỹ thuật khổ A0 cho sơ đồ nguyên lý và lắp ráp. CÁN BỘ HƯỚNG DẪN MỤC LỤC nhiệm vụ thiết kế 02 mục lục 03 Tài liệu tham khảo 04 ---------------------------------------- 1 ---------------------------------------
- Đồ án điều khiển logic Triệu Tuyên Hoàng TĐH 3- K43 -------------------------------------------------------------------------------------- Lời nói đầu 05 Chương I: giới thiệu chung về công nghệ 1. sơ đồ công nghệ 06 2. nguyên lý hoạt động của sơ đồ công nghệ 06 Chương II: tổng hợp hàm điều khiển 1. tổng hợp hàm điều khiển bằng phương pháp hàm tác động 08 1.1 xác định các biến điều khiển 08 1.2 tổng hợp hàm điều khiển 09 2. sơ đồ nguyên lý điều khiển hệ thống 11 2.1 các phần tử 11 2.2 sơ đồ nguyên lý 12 2.3 thuyết minh nguyên lý hoạt động của sơ đồ 13 Chương III: Tính chọn và thiết kế mạch lắp ráp 1. Chọn các thiết bị 14 1. chọn các phần tử logic 14 2. chọn công tắc 15 3. Chọn Van phân phối 16 4. Chọn thiết bị chấp hành 17 5. chọn nút ấn 17 2. SƠ Đồ LắP RáP 1. Lựa chọn vị trí lắp đặt thiết bị 17 2. Sơ đồ lắp ráp của mạch điều khiển hệ thống 18 MỞ ĐẦU Trong sự nghiệp công nghiệp hoá, hiện đại hoá đất nước, có thể nói một trong những tiêu chí để đánh giá sự phát triển kinh tế của mỗi quốc gia là mức độ tự động hoá trong các quá trình sản xuất mà trước hết đó là năng suất sản xuất và chất lượng sản phẩm làm ra. Sự phát triển rất nhanh ---------------------------------------- 2 ---------------------------------------
- Đồ án điều khiển logic Triệu Tuyên Hoàng TĐH 3- K43 -------------------------------------------------------------------------------------- chóng của máy tính điện tử , công nghệ thông tin và những thành tựu của lý thuyết Điều khiển tự động đã làm cở sở và hỗ trợ cho sự phát triển tương xứng của lĩnh vực tự động hoá. ở nước ta mặc dầu là một nước chậm phát triển, nhưng những năm gần đây cùng với những đòi hỏi của sản xuất cũng như sự hội nhập vào nền kinh tế thế giới thì việc áp dụng các tiến bộ khoa học kỹ thuật mà đặc biệt là sự tự động hoá các quá trình sản xuất đã có bước phát triển mới tạo ra sản phẩm có hàm lượng chất xám cao tiến tới hình thành một nền kinh tế tri thức. Ngày nay tự động hoá điều khiển các quá trình sản xuất đã đi sâu vào từng ngõ nghách, vào trong tất cả các khâu của quá trình tạo ra sản phẩm. Một trong nhữnh ứng dụng đó mà đồ án này thiết kế là điều khiển công nghệ khoan. Tự động hoá điều khiển công nghệ khoan là quá trình tạo ra một lỗ thủng trên bề mặt vật thể có kích thước chiều sâu định trước. Trong công việc thiết kế, tự động hoá điều khiển được thể hiện qua hai quá trình sau: - Tự động hoá điều khiển công việc đưa vật thể vào vị trí định trước (xác định vị trí lỗ khoan). - Tự động hoá đưa mũi khoan vào khoan vật thể sau đó quay về vị trí cũ đễ đảm bảo cho quy trình tiếp theo. Chất lượng mũi khoan và năng suất làm việc phụ thuộc rất nhiều vào công nghệ điều khiển. Quá trình làm việc được thực hiện theo một trật tự logic, theo trình tự thời gian xác định do đó để điều khiển được công nghệ ta phải tổng hợp được hàm điều khiển cho hệ thống. Có rất nhiều phương pháp để tổng hợp hàm điều khiển nhưng ở đây ta sử dụng phương pháp GRAPCET. So với các phương pháp khác thì phương pháp hàm tác động có ưu điểm đơn giản và đảm bảo sự chính xác về tuần tự thực hiện quá trình. Sinh viên . CHƯƠNG I : GIỚI THIỆU CÔNG NGHỆ Công nghệ : Khoan một lỗ hai giai đoạn ---------------------------------------- 3 ---------------------------------------
- Đồ án điều khiển logic Triệu Tuyên Hoàng TĐH 3- K43 -------------------------------------------------------------------------------------- Máy khoan được sử dụng rộng rãi trong các nhà máy cơ khí. Bên cạnh các máy móc cơ khí khác như các máy tiện, máy doa, máy bào giường, bào xọc ... dần dần được tự động hóa theo một dây chuyền ngày càng hiện đại. Các máy khoan cũng được tự động hoá theo dây chuyền nhằm nâng cao năng suất và giảm sự nặng nhọc cho người công nhân. Trong đó công nghệ khoan một lỗ hai giai đoạn cũng được sử dụng trong các nhà máy cơ khí, nhà máy sửa chữa và chế tạo máy. Trong môi trường làm việc nặng nhọc công nghệ yêu cầu : - Khoan làm việc ổn định, chắc chắn. - Tần số làm việc lớn. CHƯƠNG II : THIẾT KẾ THEO PHƯƠNG PHÁP GRAPCET ---------------------------------------- 4 ---------------------------------------
- Đồ án điều khiển logic Triệu Tuyên Hoàng TĐH 3- K43 -------------------------------------------------------------------------------------- 1. Grapcet - công cụ để mô tả mạch trình tự trong công nghiệp Trong dây chuyền sản xuất công nghiệp, các thiết bị máy móc thường hoạt động theo một trình tự lôgic chặt chẽ nhằm đảm bảo chất lượng sản phẩm, an toàn cho người và thiết bị. Cấu trúc làm việc trình tự của dây chuyền đã đưa ra yêu cầu cho điều khiển là điều khiển sự hoạt động chặt chẽ thống nhất của dây chuyền đồng thời cũng gợi ý cho ta sự phân nhóm lôgic của automat trình tự bởi các tập hợp con của máy móc và các thuật toán. Ta có sơ đồ khối : Tín hiệu Cấu trúc Quá trình vào điều khiển trình tự Quá trình công nghệ có thể bao gồm : - Hoàn toàn tự động ---------------------------------------- 5 ---------------------------------------
- Đồ án điều khiển logic Triệu Tuyên Hoàng TĐH 3- K43 -------------------------------------------------------------------------------------- - Bán tự động - Hoàn toàn bằng tay Khi thiết kế hệ thống phải tính toán đến các phương thức làm việc khác nhau để đảm bảo an toàn và xử lí kịp thời các hư hỏng trong hệ thống. Phải luôn có phương án can thiệp trực tiếp của người vân hành đến việc dừng máy khẩn cấp ... Grapcep là công cụ rất hữu ích để thiết kế và thực hiện đầy đủ các yêu cầu của công nghệ tự động hoá các quá trình công nghệ kể trên. 2.Phương pháp Grapcet ---------------------------------------- 6 ---------------------------------------
- Đồ án điều khiển logic Triệu Tuyên Hoàng TĐH 3- K43 -------------------------------------------------------------------------------------- Yêu cầu công nghệ : a, b, c, d là các công tắc hành trình cảm nhận vị trí của lưỡi khoan. Hoạt động : Khoan đi xuống với vận tốc v1 gặp ‘b’ (gặp vật liệu) giảm tốc độ khoan với vận tốc v2. Xuống gặp ‘c’ lưỡi khoan nhấc lên tháo phoi chuẩn bị cho giai đoạn khoan thứ hai. Đi lên với vận tốc V1 gặp ‘a’ khoan đảo chiều đi xuống với vận tốc V1 bắt đầu giai đoạn hai. Đi xuống gặp ‘c’ (gặp phôi) bắt đầu khoan xuống với vận tốc V2 . Gặp ‘d’ khoan hết một lỗ khoan được nhấc lên với vận tốc V1 . Đi lên gặp ‘a’ thì dừng lại kết thúc quá trình khoan. ---------------------------------------- 7 ---------------------------------------
- Đồ án điều khiển logic Triệu Tuyên Hoàng TĐH 3- K43 -------------------------------------------------------------------------------------- 3.Tín hiệu vào, trạng thái ra Tín hiệu vào : Các cảm biến vị trí a, b, c, d Tín hiệu ra : X : trạng thái đi xuống L : trạng thái đi lên V1 : chạy xuống với vận tốc v1 V2 : chạy xuống với vận tốc v2 4.Thành lập Grapcet 1 -Xác lập trạng thái ban đầu -Trạng thái ban đầu -Đã ở trạng thái ban đầu -Đi xuống với vận tốc v1 ---------------------------------------- 8 ---------------------------------------
- Đồ án điều khiển logic Triệu Tuyên Hoàng TĐH 3- K43 -------------------------------------------------------------------------------------- -Đã đi xuống với vân tốc v1 -Đi xuống với vận tốc v2 -Đã đi xuống với vận tốc v2 -Đi lên với vận tốc v1 -Đã đi lên với vận tốc v1 *Nhận xét : - Nếu Grapcet chỉ có vậy khoan sẽ đi xuống găp b giảm tốc, gặp c đi lên, gặp a lặp lại quá trình trên mà không khoan 2 giai đoạn. - Vì vậy, phải thêm 1 biến phụ nhận biết cho phép : . gặp b lần thứ nhất đi xuống với vận tốc v2 nhưng gặp b lần thứ hai vẫn duy trì vận tốc cũ. . đồng thời gặp c lần thứ nhất đi lên nhưng cấm đi lên lần thứ hai mà gặp c đi xuống với vận tốc v2. Chỉ khi gặp d mới đi lên. - Gọi biến P gặp c hàm đóng và gặp d thì cắt. Từ những điều trên Grapcet 2 có thể thành lập như sau ---------------------------------------- 9 ---------------------------------------
- Đồ án điều khiển logic Triệu Tuyên Hoàng TĐH 3- K43 -------------------------------------------------------------------------------------- 5.Thành lập Grapcet 2 ---------------------------------------- 10 ---------------------------------------
- Đồ án điều khiển logic Triệu Tuyên Hoàng TĐH 3- K43 -------------------------------------------------------------------------------------- Ta rút ra được hàm đóng cắt như sau : So+ = g + L.a So- = X.v1 X+ = m.a.So + a.L.P X- = L.v1 V1+ = m.a.So + (c+d).X.v2 + a.L.P V1- = v2 V2+ = c.v1 + b.v1.P V2- = L.v1 L+ = (c+d).X.v2 L- = So + X.v1 P+ = c ---------------------------------------- 11 ---------------------------------------
- Đồ án điều khiển logic Triệu Tuyên Hoàng TĐH 3- K43 -------------------------------------------------------------------------------------- P- = d “ + “ : hàm đóng “ – “ : hàm cắt Grapcet sử dụng các phần tử nhớ thực hiện công nghệ trên. Nhưng yêu cầu bài toán sử dụng phần tử tiếp điểm nên : - Viết hàm đóng có tiếp điểm tự duy trì để nhớ - Viết hàm cắt Ta có sơ đồ mạch điều khiển trang sau ---------------------------------------- 12 ---------------------------------------
- Đồ án điều khiển logic Triệu Tuyên Hoàng TĐH 3- K43 -------------------------------------------------------------------------------------- 6.Nguyên lí hoạt động sơ đồ như sau : - Khi có tín hiệu sẵn sàng của So tự duy trì theo đường 1-So-5- 4-2 Tiếp điểm So98, So12 15 đóng lại sẵn sàng làm việc. - Tại vị trí ban đầu a ấn nút mở máy m rơle trung gian X có điện và tự duy trì bởi tiếp điểm X1-8, X5-4 lúc này mở ra. - Đồng thời khi đó rơle V1 có điện và tự duy trì bởi tiếp điểm V1 1-12 tiếp điểm V1 5-4 mở ra làm mất điện So. Khoan chạy xuống với vận tốc v1. - Gặp b tiếp điểm V1 20-22 đang đóng nên V2 có điện và tự duy trì bởi V2 1-16 V2 có điện đồng thời tiếp điểm V2 12-10 mở ra cắt điện V1. Các rơle khác không bị ảnh hưởng. Khoan lúc này giảm tốc độ xuống vận tốc v2 (bắt đầu quá trình khoan giai đoạn một) ---------------------------------------- 13 ---------------------------------------
- Đồ án điều khiển logic Triệu Tuyên Hoàng TĐH 3- K43 -------------------------------------------------------------------------------------- - Gặp c rơle P có điện và tự duy trì bởi tiếp điểm P1-29 tiếp điểm P20-16 mở ra đồng thời P23-12 đóng lại sẵn sàng. - Cùng lúc đó bởi các tiếp diểm V2 25-27, X2 17-28 đang đóng nên rơle L có điện tự duy trì bởi L1-28. - Tiếp điểm X17-19, V2 19-12 đóng nên rơle V1 cũng có điện. Chúng cắt V2 và X do vậy khoan chạy lên với vận tốc v1. - Gặp b không chuyện gì xảy ra P20-16 đã mở . - Gặp a vì các tiếp điểm L11’-11, P11-8 đang duy trì nên rơle X có điện và duy trì bởi X1-8. Đồng thời V1 có điện và cắt L Khoan lại chạy xuống với vận tốc v1 (bắt đầu chu trình thứ hai) - Gặp b do P20-16 đã mở cho nên rơle V2 không thể có điện Khoan tiếp tục chạy xuống với vận tốc v1. - Đến khi gặp c do V2 25-27 đang mở nên rơle L không có điện - Vì V1 18-16 đang có điện nên V2 có điện và tự duy trì bởi V2 1-16. Có V2 thì V1 bị cắt bởi V210-12. ---------------------------------------- 14 ---------------------------------------
- Đồ án điều khiển logic Triệu Tuyên Hoàng TĐH 3- K43 -------------------------------------------------------------------------------------- Khoan tiếp tục chạy xuống với vận tốc mới v2. - Gặp d do V2 25-27, X27-28 đang đóng nên rơle L có điện. - Tương tự rơle V1 có điện. - V1, L có điện các tiếp điểm thường đóng của nó mở ra do đó cắt điện X, V1 - Đồng thời gặp d nên P mất điện. Khoan chạy lên với vận tốc v1 - Gặp a rơle So có điện và tự duy trì các tiếp điểm của nó đóng lại ở trạng thái sẵn sàng đợi lệnh mới. Kết thúc quá trình khoan một lỗ hai giai đoạn ---------------------------------------- 15 ---------------------------------------
- Đồ án điều khiển logic Triệu Tuyên Hoàng TĐH 3- K43 -------------------------------------------------------------------------------------- CHƯƠNG III : SƠ DỒ MẠCH LỰC – LỰA CHỌN THIẾT BỊ 1. Mạch lực - Công suất động cơ 2KW - Điện áp định mức 220V - Động cơ một chiều kích từ độc lập. Dòng điện định mức : Iđm = Pđm/Uđm = 2.103/220 =9,1 A - Đối với động cơ công suất nhỏ thế này có thể sử dụng phương pháp mở máy trực tiếp không cần qua ddiện trở hàn chế. - Đối với mạch bảo vệ ta có thể chọn phương án bảop vệ cầu chì đơn giản và rẻ tiền. ---------------------------------------- 16 ---------------------------------------
- Đồ án điều khiển logic Triệu Tuyên Hoàng TĐH 3- K43 -------------------------------------------------------------------------------------- - Khi đảo chiều thực hiện hãm ngược bằng tất cả các điện trở tham gia trong mạch phần ứng theo nguyên tắc dòng điện bởi rơle dòng điện cực đại RH. Sơ đồ nguyên lí mạch lực , mạch lực như hình bên : ---------------------------------------- 17 ---------------------------------------
- Đồ án điều khiển logic Triệu Tuyên Hoàng TĐH 3- K43 -------------------------------------------------------------------------------------- 2. Lựa chọn thiết bị a. Phần tử chấp hành Dòng điện định mức Iđm = 9,1 A Khi mở máy dòng điện Imm < 2,5. Iđm . Dòng cực đại khi mở máy là : Imm = 2,5.Iđm =2,5 . 9,1 =22,7 (A) Ta có thể chọn công tắc tơ có các thông số thoả mãn Loại Dòng điện Số lượng tiếp điểm Uđm CS Kích Iđm Imax Thường Thường đóng cuộn thước mở dây K∏1-0021 15 60 2 220 10 200x128 ---------------------------------------- 18 ---------------------------------------
- Đồ án điều khiển logic Triệu Tuyên Hoàng TĐH 3- K43 -------------------------------------------------------------------------------------- Chọn 4 công tắc tơ như trên cho các công tắc tơ X, L, V1, V2. Từ công suất cuộn hút có thể tính được dòng qua cuộn hút : Ih = P/U =10/220 = 0,05 (A) b. Phần tử điều khiển Từ dòng cuộn hút ta có thể chọn được các rơle trung gian có tiếp điểm thoả mãn. Chọn rơle trung gian : Loại Dòng điện Số lượng tiếp điểm Uđm CS cuộn Kích Thường Thường đóng hút thước mở RH101 5 4 4 220 2 92x128 c. Các thiết bị bảo vệ Bảo vệ bằng cầu chì ta chọn cầu chì : - Động lực - Điều khiển Mạch động lực Kiểu cầu Dòng đm Dòng cắt Điện áp Kích thước chung ---------------------------------------- 19 ---------------------------------------
- Đồ án điều khiển logic Triệu Tuyên Hoàng TĐH 3- K43 -------------------------------------------------------------------------------------- chì dây chảy giới hạn định mức A B C H∏H 15 8000 220 91 16 25 Cầu chì kiểu ống nên khi đứt rất an toàn. Mạch điều khiển Kiểu cầu Dòng đm Dòng cắt Điện áp Kích thước chung chì dây chảy giới hạn định mức A B C H∏H 6 1200 220 91 16 25 Chọn rơle dòng điện cực đại Bảng đấu dây có thể lập như sau : STT Tên thiết bị Điểm nối ---------------------------------------- 20 ---------------------------------------
CÓ THỂ BẠN MUỐN DOWNLOAD
-
Đồ án môn học: "Điều khiển logic "
24 p |
1440 |
433
-
Đồ án "điều khiển logic "
10 p |
2013 |
292
-
ĐỒ ÁN ĐỀ TÀI 'ĐIỀU KHIỂN LOGIC'
44 p |
951 |
254
-
PLC thiết kế mạch điều khiển động cơ đơn giản
20 p |
704 |
192
-
thiết kế phương pháp điều khiển robot tự hành dựa trên cơ sở logic mờ, chương 15
18 p |
267 |
158
-
THIẾT KẾ VÀ LẮP RÁP BỘ BIẾN TẦN NGUỒN ÁP ĐIỀU KHIỂN ĐỘNG CƠ KHÔNG ĐỒNG BỘ BA PHA RÔTO LỒNG SÓC. (DÙNG VI ĐIỀU KHIỂN - CHIP AT89C51)
17 p |
302 |
143
-
Thiết kế hệ điều khiển logic
14 p |
242 |
120
-
Đồ án bảo dưỡng công nghiệp Hệ thống Servo- Chương 1
20 p |
185 |
83
-
TỰ CHỈNH ĐỘ LỢI MỜ THÍCH NGHI ĐIỀU KHIỂN HỆ PHI TUYẾN RỜI RẠC
6 p |
201 |
79
-
Đồ án bảo dưỡng công nghiệp Hệ thống Servo- Chương 5
23 p |
155 |
78
-
Đồ án bảo dưỡng công nghiệp Hệ thống Servo- Chương 4
9 p |
141 |
66
-
Đồ án tốt nghiệp: "Toyota Hybrid System" - Chương IV: CÁC PHƯƠNG PHÁP BỐ TRÍ
6 p |
142 |
64
-
Đồ án môn học Kỷ thuật lạnh - GVHD Nguyễn Thành Văn
43 p |
131 |
59
-
ỨNG DỤNG BỘ ĐIỀU KHIỂN LOGIC MỜ (FUZZY LOGIC CONTROLLER) TRONG MÁY LÁI TỰ ĐỘNG TÀU BIỂN APPLICATION OF FUZZY LOGIC CONTROLLER TO SHIPS AUTOPILOT
5 p |
152 |
52
-
Những lưu ý khi làm đồ án công nghệ chế tạo máy
3 p |
144 |
40
-
Ebook Hướng dẫn đồ án môn học Thủy năng: Phần 1 - Vũ Hữu Hải, Nguyễn Thượng Bằng (ĐH Xây dựng)
29 p |
71 |
29
-
Ebook Hướng dẫn đồ án môn học Thủy năng: Phần 2 - Vũ Hữu Hải, Nguyễn Thượng Bằng (ĐH Xây dựng)
28 p |
60 |
20

WARC-Type: response

Content-Type: application/http; msgtype=response

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

Server: Apache/2.2.31 (CentOS)

Connection: close

Pragma: no-cache

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

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

Vary: Accept-Encoding

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


markdown:
# Quyết định 3772/QĐ-UBND của Ủy ban Nhân dân Thành phố Hà Nội
Chia sẻ: Tran Huu Tri | Ngày: | Loại File: DOC | Số trang:0
lượt xem 3
download
![](http://image1.tailieu.vn/document/thumbnail/2009/20090806/1huutri/80x100/09402599.jpg)
##
Quyết định 3772/QĐ-UBND của Ủy ban Nhân dân Thành phố Hà Nội
[Vui lòng tải xuống để xem tài liệu đầy đủ](javascript:void(0);)
Download
![](http://static1.tailieu.vn/b2013az/templates/version1/default/images/down16x21.png)
Quyết định 3772/QĐ-UBND của Ủy ban Nhân dân Thành phố Hà Nội về quy chế hoạt động của Ban Chỉ đạo phát triển hệ thống chợ và cửa hàng xăng dầu trên địa bàn Thành phố Hà Nội
Bình luận(0)
[Đăng nhập để gửi bình luận!](javascript:void(0);)
##
Nội dung Text: Quyết định 3772/QĐ-UBND của Ủy ban Nhân dân Thành phố Hà Nội
- ỦY BAN NHÂN DÂN CỘNG HÒA XÃ HỘI CHỦ NGHĨA VIỆT NAM THÀNH PHỐ HÀ NỘI Độc lập – Tự do – Hạnh phúc ----------------- ---------------------- Số: 3772/QĐ-UBND Hà Nội, ngày 24 tháng 07 năm 2009 QUYẾT ĐỊNH VỀ QUY CHẾ HOẠT ĐỘNG CỦA BAN CHỈ ĐẠO PHÁT TRIỂN HỆ THỐNG CHỢ VÀ CỬA HÀNG XĂNG DẦU TRÊN ĐỊA BÀN THÀNH PHỐ HÀ NỘI ---------------------- ỦY BAN NHÂN DÂN THÀNH PHỐ HÀ NỘI Căn cứ Luật tổ chức Hội đồng nhân dân và Ủy ban nhân dân ngày 26/11/2003; Căn cứ Quyết định số 559/QĐ-TTg ngày 31/05/2004 của Thủ tướng Chính phủ về việc phê duyệt Chương trình phát triển chợ đến năm 2010; Căn cứ Quyết định số 1287/2009/QĐ-UBND ngày 18/3/2009 của UBND Thành phố về việc thành lập Ban Chỉ đạo phát triển hệ thống chợ và cửa hàng xăng dầu trên địa bàn Thành phố Hà Nội; Xét đề nghị của Giám đốc Sở Công thương Hà Nội tại Tờ trình số 1801/TTr-SCT ngày 17/6/2009, QUYẾT ĐỊNH: Điều 1. Ban hành kèm theo Quyết định này Quy chế hoạt động của Ban Chỉ đạo phát triển hệ thống chợ và cửa hàng xăng dầu trên địa bàn Thành phố Hà Nội; Điều 2. Ban Chỉ đạo phát triển hệ thống chợ và cửa hàng xăng dầu trên địa bàn Thành phố Hà Nội được sử dụng con dấu của UBND Thành phố để phục vụ công tác chỉ đạo thực hiện. Quyết định này có hiệu lực kể từ ngày ký, các quyết định trước đây trái với Quyết định này đều được bãi bỏ. Điều 3. Chánh Văn phòng UBND Thành phố, các thành viên Ban Chỉ đạo phát triển hệ thống chợ và cửa hàng xăng dầu trên địa bàn Thành phố Hà Nội, các Sở, ngành có liên quan và UBND các quận, huyện, thị xã chịu trách nhiệm thi hành Quyết định này./. Nơi nhận: TM. ỦY BAN NHÂN DÂN - Như Điều 3; KT. CHỦ TỊCH - Bộ Công Thương; (để b/c) PHÓ CHỦ TỊCH - TT Thành ủy; (để b/c) - Đ/c CT UBND TP; (để b/c) - Các Phó CT UBND TP; (để b/c) - CPVP, các phòng: TH, KT, CT; - Các Sở, ngành liên quan; Nguyễn Huy Tưởng - UBND các quận, huyện, thị xã; - Lưu VT, SCT.
- QUY CHẾ HOẠT ĐỘNG CỦA BAN CHỈ ĐẠO PHÁT TRIỂN HỆ THỐNG CHỢ VÀ CỬA HÀNG XĂNG DẦU TRÊN ĐỊA BÀN THÀNH PHỐ HÀ NỘI (Ban hành theo Quyết định số 3772/QĐ-UBND ngày 24/7/2009 của UBND Thành phố Hà Nội) Điều 1. Ban Chỉ đạo phát triển hệ thống chợ và cửa hàng xăng dầu trên địa bàn Thành phố Hà Nội (sau đây gọi tắt là Ban chỉ đạo): 1. Ban chỉ đạo được thành lập theo Quyết định số 1287/QĐ-UBND ngày 18/3/2009 của UBND Thành phố Hà Nội là tổ chức phối hợp liên ngành, hoạt động theo chế độ kiêm nhiệm, thực hiện chỉ đạo thống nhất của các cơ quan, tổ chức thuộc Thành phố đối với công tác phát triển mạng lưới chợ và cửa hàng xăng dầu trên địa bàn Thành phố phù hợp với quy hoạch, kế hoạch phát triển kinh tế - xã hội Thủ đô, đáp ứng nhu cầu của nhân dân Thủ đô, đảm bảo văn minh thương mại và yêu cầu hội nhập kinh tế quốc tế. 2. Cơ quan Thường trực của Ban chỉ đạo là sở Công Thương Hà Nội. Lãnh đạo sở Công Thương là Phó trưởng ban Ban chỉ đạo đồng thời là Tổ trưởng Tổ công tác liên ngành của Ban chỉ đạo. Cơ quan Thường trực của Ban chỉ đạo chịu trách nhiệm chuẩn bị nội dung, tổ chức triển khai và tổng hợp kết quả thực hiện công tác của Ban chỉ đạo. Điều 2. Ban chỉ đạo có nhiệm vụ: 1. Chỉ đạo xây dựng kế hoạch ngắn hạn (hàng năm) và dài hạn về phát triển, quản lý hệ thống chợ và cửa hàng xăng dầu trên địa bàn Thành phố Hà Nội trên cơ sở quy hoạch được cấp có thẩm quyền phê duyệt. 2. Chỉ đạo các sở, ngành Thành phố, UBND các quận, huyện, thị xã tổ chức thực hiện chương trình phát triển chợ Hà Nội đến năm 2010, định hướng phát triển chợ đến năm 2020; đôn đốc, kiểm tra việc thực hiện của các đơn vị đảm bảo theo đúng kế hoạch, chương trình đề ra, đạt mục tiêu xây dựng hệ thống chợ, hệ thống cửa hàng xăng dầu văn minh, hiện đại. 3. Đề xuất, kiến nghị việc sửa đổi, bổ sung hoặc ban hành mới các cơ chế chính sách về phát triển, quản lý hệ thống chợ và cửa hàng xăng dầu với cơ quan có thẩm quyền. 4. Định kỳ 6 tháng, 1 năm báo cáo UBND Thành phố kết quả thực hiện quy hoạch, kế hoạch và chương trình phát triển hệ thống chợ và cửa hàng xăng dầu trên địa bàn Thành phố. Điều 3. Ban chỉ đạo có quyền hạn: 1. Kiểm tra tiến độ, kết quả thực hiện các dự án của chương trình phát triển hệ thống chợ và cửa hàng xăng dầu theo quy hoạch và việc thực hiện cơ chế, chính sách về phát triển, quản lý hệ thống chợ và cửa hàng xăng dầu trên địa bàn Thành phố Hà Nội. 2. Yêu cầu UBND các quận, huyện, Thị xã, chủ đầu tư, đơn vị quản lý, kinh doanh, khai thác chợ báo cáo định kỳ hoặc đột xuất tình hình phát triển, quản lý hệ thống chợ và cửa hàng xăng dầu cũng như tiến độ, kết quả thực hiện các dự án của Chương trình. 3. Báo cáo UBND Thành phố dừng triển khai xây dựng chợ, cửa hàng xăng dầu không phù hợp với quy hoạch, đề nghị giải tỏa các chợ cóc, chợ tạm trên địa bàn Thành phố. Điều 4. Trách nhiệm và quyền hạn của Trưởng Ban chỉ đạo: 1. Chịu trách nhiệm trước Chủ tịch UBND Thành phố về tiến độ, kết quả thực hiện quy hoạch, kế hoạch, chương trình và toàn bộ hoạt động của Ban chỉ đạo. 2. Phân công trách nhiệm cụ thể cho từng thành viên Ban chỉ đạo; kiểm tra, đôn đốc các thành viên Ban chỉ đạo thực hiện các nhiệm vụ được phân công. 3. Triệp tập và chủ trì các phiên họp của Ban chỉ đạo. 4. Giải quyết những kiến nghị, đề xuất của các thành viên Ban chỉ đạo.
- 5. Kiến nghị với cơ quan có thẩm quyền giải quyết những vấn đề vượt quá thẩm quyền của Ban chỉ đạo. 6. Trưởng ban Ban chỉ đạo được sử dụng con dấu của UBND Thành phố để phục vụ công tác chỉ đạo, điều hành. Điều 5. Trách nhiệm của các thành viên Ban chỉ đạo: 1. Phó Trưởng ban chỉ đạo: a. Giúp Trưởng ban chỉ đạo điều phối hoạt động của Ban chỉ đạo khi được Trưởng ban chỉ đạo ủy quyền; b. Trực tiếp chỉ đạo các nhiệm vụ sau: Kiểm tra, đôn đốc các quận, huyện thực hiện quy hoạch, kế hoạch phát triển mạng lưới chợ, mạng lưới cửa hàng xăng dầu. Triển khai điều chỉnh quy hoạch mạng lưới chợ, mạng lưới cửa hàng xăng dầu thành phố; xây dựng các cơ chế đầu tư quản lý, khai thác chợ; Triển khai thực hiện các dự án đầu tư xây dựng chợ và giải tỏa tụ điểm chợ tạm, chợ cóc trên địa bàn thuộc chương trình phát triển chợ Hà Nội văn minh, hiện đại; triển khai chuyển đổi mô hình tổ chức quản lý chợ trên địa bàn thành phố theo đúng tiến độ đề ra. 2. Các thành viên Ban chỉ đạo: a. Thực hiện các nhiệm vụ cụ thể được Trưởng ban chỉ đạo phân công trong kế hoạch của Ban chỉ đạo phát triển chợ hàng năm và kế hoạch của Ban chỉ đạo đến năm 2010. Đồng thời tham gia các hoạt động và các cuộc họp của Ban chỉ đạo nhằm thực hiện tốt nhiệm vụ của Ban chỉ đạo đã được quy định tại Điều 2 của Quy chế này. b. Thành viên Ban chỉ đạo đại diện các sở, ngành thành phố: căn cứ vào chức năng nhiệm vụ của sở, ngành do pháp luật quy định, có trách nhiệm tham mưu, đề xuất: điều chỉnh quy hoạch mạng lưới chợ, các cơ chế, chính sách, giải pháp liên quan đến phát triển, quản lý hệ thống chợ và cửa hàng xăng dầu, trình UBND Thành phố phê duyệt. Đối với những vấn đề lãnh đạo Bộ, ngành Trung ương có ý kiến khác với ý kiến của Ban chỉ đạo, cần báo cáo kịp thời Trưởng ban chỉ đạo để giải quyết. c. Thành viên Ban chỉ đạo đại diện UBND các quận, huyện, Thị xã: có trách nhiệm xây dựng kế hoạch, chương trình phát triển hệ thống chợ và cửa hàng xăng dầu, chuyển đổi mô hình tổ chức quản lý chợ trên địa bàn quận, huyện, Thị xã quản lý; tham gia xây dựng quy hoạch, cơ chế, chính sách, giải pháp liên quan đến phát triển, quản lý hệ thống chợ và cửa hàng xăng dầu; trực tiếp chỉ đạo việc thực hiện các dự án chợ và tổ chức giải tỏa tụ điểm chợ tạm, chợ cóc trên địa bàn quận, huyện, Thị xã theo đúng kế hoạch đề ra. Điều 6. Tổ công tác liên ngành của Ban chỉ đạo Tổ công tác liên ngành của Ban chỉ đạo gồm một số cán bộ phụ trách Phòng chức năng của các sở, ngành Thành phố. Tổ công tác liên ngành vừa là đầu mối tiếp nhận, tổng hợp và xử lý thông tin liên quan đến hoạt động của Ban chỉ đạo; vừa có trách nhiệm chuẩn bị nội dung, chương trình phục vụ các cuộc họp của Ban chỉ đạo; quản lý kinh phí hoạt động của Ban chỉ đạo theo quy định tại Điều 9 của Quy chế này. Điều 7. Chế độ họp của Ban chỉ đạo: 1. Trưởng ban chỉ đạo trực tiếp triệu tập và chủ tọa các phiên họp toàn thể Ban chỉ đạo thường kỳ 3 tháng một lần và các phiên họp bất thường (nếu có). Trưởng ban chỉ đạo có thể ủy quyền cho Phó Trưởng ban chủ tọa các phiên họp. Phó Trưởng ban chỉ đạo chủ trì các phiên họp của Tổ công tác liên ngành định kỳ 1 tháng một lần. Nội dung các phiên họp do Tổ công tác liên ngành chuẩn bị và gửi trước một tuần cho các thành viên. 2. Các phiên họp thường kỳ của Ban chỉ đạo nhằm đánh giá các mặt hoạt động của Ban chỉ đạo, kết quả thực hiện các mục tiêu của Chương trình, Kế hoạch đề ra; phối hợp tháo gỡ khó khăn, đề xuất và kiến nghị với cơ quan có thẩm quyền về cơ chế, chính sách, các giải pháp để thực hiện đạt được mục tiêu của Chương trình, Kế hoạch đề ra. Điều 8. Chế độ đi công tác
- 1. Kế hoạch làm việc với các Bộ, Ngành Trung ương liên quan và các quận, huyện, Thị xã do Trưởng Ban chỉ đạo quyết định và phân công trên cơ sở kế hoạch chung của Ban chỉ đạo. 2. Thành viên Ban chỉ đạo được sử dụng cán bộ, phương tiện, các trang thiết bị của đơn vị do mình quản lý để thực hiện nhiệm vụ công tác được giao theo chế độ hiện hành. Điều 9. Kinh phí hoạt động của Ban chỉ đạo Kinh phí hoạt động của Ban chỉ đạo được cấp từ ngân sách thành phố, được dự toán hàng năm, chuyển vào tài khoản sở Công Thương; Tổ công tác liên ngành của Ban chỉ đạo có trách nhiệm dự toán, sử dụng và thanh quyết toán kinh phí được cấp theo quy định hiện hành của nhà nước. Điều 10. Điều khoản thi hành Trong quá trình thực hiện Quy chế, nếu có vướng mắc nảy sinh, các cơ quan, tổ chức có ý kiến bằng văn bản gửi về cơ quan Thường trực của Ban chỉ đạo để tổng hợp, đề xuất trình Trưởng ban xem xét bổ sung, sửa đổi cho phù hợp./.
CÓ THỂ BẠN MUỐN DOWNLOAD
-
Quyết định 56/2008/QĐ-UBND của Uỷ ban Nhân dân Thành phố Hà Nội
2 p |
1358 |
130
-
Quyết định 57/2008/QĐ-UBND của Uỷ ban Nhân dân Thành phố Hà Nội
6 p |
658 |
83
-
Quyết định 55/2008/QĐ-UBND của Uỷ ban Nhân dân Thành phố Hà Nội
2 p |
335 |
60
-
Quyết định 54/2008/QĐ-UBND của Uỷ ban Nhân dân Thành phố Hà Nội
9 p |
184 |
39
-
Quyết định 52/2008/QĐ-UBND của Uỷ ban Nhân dân Thành phố Hà Nội
17 p |
340 |
38
-
Quyết định 91/2009/QĐ-UBND của Ủy ban Nhân dân Thành phố Hà Nội
11 p |
243 |
34
-
Quyết định 87/2009/QĐ-UBND của Ủy ban Nhân dân Thành phố Hà Nội
7 p |
447 |
31
-
Quyết định 63/2008/QĐ-UBND của Uỷ ban Nhân dân Thành phố Hà Nội
7 p |
196 |
27
-
Quyết định 3746/QĐ-UBND của Ủy ban Nhân dân Thành phố Hà Nội
5 p |
110 |
22
-
Quyết định 101/2007/QĐ-UBND của Ủy ban Nhân dân Thành phố Hà Nội
8 p |
103 |
15
-
Quyết định 3753/QĐ-UBND của Ủy ban Nhân dân Thành phố Hà Nội
0 p |
89 |
11
-
Quyết định 28/2009/QĐ-UBND của Uỷ ban Nhân dân Thành phố Hà Nội
3 p |
114 |
10
-
Chỉ thị 20/CT-UBND của Uỷ ban Nhân dân Thành phố Hà Nội
5 p |
114 |
8
-
Quyết định 24/2008/QĐ-UBND của Ủy ban Nhân dân Thành phố Hà Nội
2 p |
102 |
6
-
Quyết định 82/2009/QĐ-UBND của Uỷ ban Nhân dân Thành phố Hà Nội
2 p |
200 |
6
-
Quyết định 3753/QĐ-UBND của Ủy ban Nhân dân Thành phố Hà Nội
1 p |
76 |
2
-
Quyết định 10/2008/QĐ-UBND của Ủy ban Nhân dân Thành phố Hà Nội
8 p |
74 |
2
-
Quyết định 129/2007/QĐ-UBND của Ủy ban Nhân dân Thành phố Hà Nội
2 p |
97 |
1

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