Tài liệu Chương trình đào tạo tiến sĩ - Chuyên ngành Khoa học máy tính

Bꢀ GIÁO DꢁC VÀ ðÀO TꢂO

TRƯꢃNG ðꢂI HꢄC BÁCH KHOA HÀ NꢀI

CHƯƠNG TRÌNH ðÀO TꢂO

TIꢅN SĨ

CHUYÊN NGÀNH

KHOA HꢄC MÁY TÍNH

MÃ Sꢀ: 62480101

ðã ñưꢆc Hꢇi ñꢈng Xây dꢉng Chương trình ñào tꢊo bꢋc Tiꢌn sĩ thông qua

ngày ....... tháng 06 năm 2012

HÀ NꢁI 2012

MꢁC LꢁC

Trang

PHꢍN I

1

TꢎNG QUAN Vꢏ CHƯƠNG TRÌNH ðÀO TꢂO

Mꢂc tiêu ñào tꢃo

1.1

1.2

2

Mꢂc tiêu chung

Mꢂc tiêu cꢂ thꢄ

Thꢅi gian ñào tꢃo

3

Khꢆi lưꢇng kiꢈn thꢉc

4

ðꢆi tưꢇng tuyꢄn sinh

4.1

4.2

5

ðꢊnh nghĩa

Phân loꢃi ñꢆi tưꢇng

Quy trình ñào tꢃo, ñiꢋu kiꢌn công nhꢍn ñꢃt

Thang ñiꢄm

6

7

Nꢎi dung chương trình

Cꢏu trúc

Hꢐc phꢑn bꢒ sung

7.1

7.2

7.3

7.3.1

7.3.2

7.3.3

7.4

8

Hꢐc phꢑn Tiꢈn sĩ

Danh mꢂc hꢐc phꢑn Tiꢈn sĩ

Mô tꢓ tóm tꢔt hꢐc phꢑn Tiꢈn sĩ

Kꢈ hoꢃch hꢐc tꢍp các hꢐc phꢑn Tiꢈn sĩ

Chuyên ñꢋ Tiꢈn sĩ

Danh sách Tꢃp chí / Hꢎi nghꢊ Khoa hꢐc

PHꢍN II ðꢏ CƯƠNG CHI TIꢅT CÁC HꢄC PHꢍN

9

Danh mꢂc hꢐc phꢑn chi tiꢈt cꢕa chương trình ñào tꢃo

Danh mꢂc hꢐc phꢑn bꢒ sung, chuyꢄn ñꢒi

Danh mꢂc hꢐc phꢑn Tiꢈn sĩ

9.1

9.2

10

ðꢋ cương chi tiꢈt các hꢐc phꢑn Tiꢈn sĩ

2

PHꢍN I

TꢎNG QUAN Vꢏ CHƯƠNG TRÌNH ðÀO TꢂO

3

TRƯꢃNG ðꢂI HꢄC BÁCH KHOA HÀ NꢀI CꢀNG HÒA XÃ HꢀI CHꢑ NGHĨA VIꢐT NAM

VIꢐN CNTT VÀ TRUYꢏN THÔNG ðꢇc lꢋp - Tꢉ do - Hꢊnh phúc

CHƯƠNG TRÌNH ðÀO TꢀO TIꢁN SĨ

CHUYÊN NGÀNH “KHOA HꢂC MÁY TÍNH”

Tên chương trình:

Trình ñꢇ ñào tꢊo:

Chương trình ñào tꢃo Tiꢈn sĩ chuyên ngành “Khoa hꢐc Máy tính”

Tiꢈn sĩ

Chuyên ngành ñào tꢊo: Khoa hꢐc Máy tính – Computer Science

Mã chuyên ngành: 62480101

(Ban hành theo Quyꢈt ñꢊnh sꢆ ......... / Qð-ðHBK-SðH ngày ....... tháng ....... năm ...........

cꢕa Hiꢌu trưꢖng trưꢅng ðH Bách Khoa Hà Nꢎi)

1. Mꢒc tiêu ñào tꢊo

1.1 Mꢒc tiêu chung

ðào tꢃo Tiꢈn sĩ chuyên ngành “Khoa hꢀc Máy tính” có trình ñꢎ chuyên môn sâu cao, có khꢓ

năng nghiên cꢉu và lãnh ñꢃo nhóm nghiên cꢉu các lĩnh vꢗc cꢕa chuyên ngành, có tư duy khoa

hꢐc, có khꢓ năng tiꢈp cꢍn và giꢓi quyꢈt các vꢏn ñꢋ khoa hꢐc chuyên ngành, có khꢓ năng trình bày

- giꢘi thiꢌu các nꢎi dung khoa hꢐc, ñꢙng thꢅi có khꢓ năng ñào tꢃo các bꢍc ðꢃi hꢐc và Cao hꢐc.

1.2 Mꢒc tiêu cꢒ thꢓ

Sau khi ñã kꢈt thúc thành công chương trình ñào tꢃo, Tiꢈn sĩ chuyên ngành Khoa hꢐc Máy tính:

Có khꢓ năng phát hiꢌn và trꢗc tiꢈp giꢓi quyꢈt các vꢏn ñꢋ khoa hꢐc thuꢎc các lĩnh vꢗc Khoa hꢐc

Máy tính.

Có khꢓ năng dꢚn dꢔt, lãnh ñꢃo nhóm nghiên cꢉu thuꢎc các lĩnh vꢗc Khoa hꢐc Máy tính.

Có khꢓ năng nghiên cꢉu, ñꢋ xuꢏt và áp dꢂng các giꢓi pháp công nghꢌ thuꢎc lĩnh vꢗc Khoa hꢐc

máy tính trong thꢗc tiꢛn.

Có khꢓ năng cao ñꢄ trình bꢑy, giꢘi thiꢌu (bꢜng các hình thꢉc bài viꢈt, báo cáo hꢎi nghꢊ, giꢓng

dꢃy ñꢃi hꢐc và sau ñꢃi hꢐc) các vꢏn ñꢋ khoa hꢐc thuꢎc lĩnh vꢗc Khoa hꢐc Máy tính.

2. Thꢔi gian ñào tꢊo

• Hꢁ tꢂp trung liên tꢃc: 3 năm liên tꢂc ñꢆi vꢘi NCS có bꢜng ThS, 4 năm ñꢆi vꢘi NCS có

bꢜng ðH.

• Hꢁ không tꢂp trung liên tꢃc: NCS có văn bꢜng ThS ñăng ký thꢗc hiꢌn trong vòng 4 năm

ñꢓm bꢓo tꢒng thꢅi gian hꢐc tꢍp, nghiên cꢉu tꢃi Trưꢅng là 3 năm và 12 tháng ñꢑu tiên tꢍp

trung liên tꢂc tꢃi Trưꢅng.

3. Khꢕi lưꢆng kiꢌn thꢖc

Khꢆi lưꢇng kiꢈn thꢉc bao gꢙm khꢆi lưꢇng cꢕa các hꢀc phꢄn Tiꢅn sĩ và khꢆi lưꢇng cꢕa các

hꢀc phꢄn bꢆ sung ñưꢇc xác ñꢊnh cꢂ thꢄ cho tꢝng loꢃi ñꢆi tưꢇng tꢃi mꢂc 4.

NCS ñã có bꢜng ThS: tꢆi thiꢄu 8 tín chꢞ + khꢆi lưꢇng bꢒ sung (nꢈu có).

NCS mꢘi có bꢜng ðH: tꢆi thiꢄu 8 tín chꢞ + 28 tín chꢞ (không kꢄ luꢍn văn) cꢕa Chương trình Thꢃc

sĩ Khoa hꢐc ngành “Công nghꢌ thông tin”, trưꢅng ðꢃi hꢐc Bách Khoa Hà Nꢎi. ðꢆi vꢘi NCS có

4

bꢜng ðH cꢕa các hꢌ 4 hoꢟc 4,5 năm (theo quy ñꢊnh) sꢠ phꢓi thêm các hꢐc phꢑn bꢒ sung cꢕa

Chương trình Thꢃc sĩ Khoa hꢐc ngành “Công nghꢌ Thông tin” Trưꢅng ðH Bách Khoa Hà Nꢎi.

4. ðꢕi tưꢆng tuyꢓn sinh

ðꢆi tưꢇng tuyꢄn sinh là các thí sinh ñã có bꢜng Thꢃc sĩ vꢘi chuyên ngành tꢆt nghiꢌp phù hꢇp

(ñúng ngành) hoꢟc gꢑn phù hꢇp vꢘi chuyên ngành Khoa hꢐc Máy tính. Chꢞ tuyꢄn sinh mꢘi có

bꢜng ðH vꢘi ngành tꢆt nghiꢌp phù hꢇp. Mꢉc ñꢎ “phù hꢇp hoꢈc gꢄn phù hꢇp” vꢘi chuyên

ngành Khoa hꢐc Máy tính, ñưꢇc ñꢊnh nghĩa cꢂ thꢄ ꢖ mꢂc 4.1 sau ñây.

4.1 ðꢗnh nghĩa

Ngành phù hꢇp (ñúng ngành): Là nhꢡng hưꢘng ñào tꢃo chuyên sâu thuꢎc ngành “Công nghꢌ

Thông tin” và ngành “Kꢢ thuꢍt máy tính và Truyꢋn thông” cꢕa chương trình ñào tꢃo thꢃc sꢢ

trưꢅng ðHBK HN, các chuyên ngành thuꢎc ngành Công nghꢌ thông tin cꢕa các trưꢅng ñꢃi hꢐc

khác (như Khoa hꢐc máy tính, Hꢌ thꢆng thông tin, Công nghꢌ phꢑn mꢋm, Truyꢋn thông và

mꢃng, Kꢢ thuꢍt máy tính).

Ngành gꢑn phù hꢇp: Ngành „Toán tin“ (các chuyên ngành sâu Cơ sꢖ toán hꢐc cho tin hꢐc, Toán

Tin ꢉng dꢂng) cꢕa chương trình ñào tꢃo thꢃc sꢢ trưꢅng ðHBK HN và các trưꢅng ñꢃi hꢐc khác;

ngành SPKT CNTT cꢕa chương trình ñào tꢃo thꢃc sꢢ trưꢅng ðHBK HN.

4.2 Phân loꢊi ñꢕi tưꢆng

• Có bꢜng ThS Khoa hꢐc cꢕa ðH Bách Khoa Hà Nꢎi vꢘi ngành tꢆt nghiꢌp cao hꢐc ñúng vꢘi

chuyên ngành Tiꢈn sĩ. ðây là ñꢆi tưꢇng không phꢓi tham gia hꢐc bꢒ sung, gꢐi tꢔt là ñꢆi

tưꢇng A1.

• Có bꢜng tꢆt nghiꢌp ðꢃi hꢐc loꢃi xuꢏt sꢔc vꢘi ngành tꢆt nghiꢌp ñúng vꢘi chuyên ngành Tiꢈn

sĩ. ðây là ñꢆi tưꢇng phꢓi tham gia hꢐc bꢒ sung, gꢐi tꢔt là ñꢆi tưꢇng A2.

• Có bꢜng ThS ñúng ngành, nhưng không phꢓi là ThS Khoa hꢐc cꢕa ðH Bách Khoa Hà Nꢎi

hoꢟc có bꢜng ThS tꢆt nghiꢌp ngành gꢑn phù hꢇp. ðây là ñꢆi tưꢇng phꢓi tham gia hꢐc bꢒ

sung, gꢐi tꢔt là ñꢆi tưꢇng A3.

5. Quy trình ñào tꢊo, ñiꢘu kiꢙn công nhꢋn ñꢊt

Quy trình ñào tꢃo ñưꢇc thꢗc hiꢌn theo hꢐc chꢈ tín chꢞ, tuân thꢕ Quy ñꢊnh 1035/2011 vꢋ tꢒ chꢉc

và quꢓn lý ñào tꢃo sau ñꢃi hꢐc cꢕa ðH Bách Khoa Hà Nꢎi.

Các hꢐc phꢑn bꢒ sung, hꢐc phꢑn chuyꢄn ñꢒi phꢓi ñꢃt mꢉc ñiꢄm C trꢖ lên (xem mꢂc 6).

Các hꢐc phꢑn Tiꢈn sĩ phꢓi ñꢃt mꢉc ñiꢄm B trꢖ lên (xem mꢂc 6).

6. Thang ñiꢓm

Khoꢓn 6a ðiꢋu 62 cꢕa Quy ñꢊnh 1035/2011 quy ñꢊnh:

Viꢌc chꢏm ñiꢄm kiꢄm tra - ñánh giá hꢐc phꢑn (bao gꢙm các ñiꢄm kiꢄm tra và ñiꢄm thi kꢈt thúc

hꢐc phꢑn) ñưꢇc thꢗc hiꢌn theo thang ñiꢄm tꢝ 0 ñꢈn 10, làm tròn ñꢈn mꢎt chꢡ sꢆ thꢍp phân sau

dꢏu phꢣy. ðiꢄm hꢐc phꢑn là ñiꢄm trung bình có trꢐng sꢆ cꢕa các ñiꢄm kiꢄm tra và ñiꢄm thi kꢈt

thúc (tꢒng cꢕa tꢏt cꢓ các ñiꢄm kiꢄm tra, ñiꢄm thi kꢈt thúc ñã nhân vꢘi trꢐng sꢆ tương ꢉng cꢕa

tꢝng ñiꢄm ñưꢇc quy ñꢊnh trong ñꢋ cương chi tiꢈt hꢐc phꢑn).

ðiꢄm hꢐc phꢑn ñưꢇc làm tròn ñꢈn mꢎt chꢡ sꢆ thꢍp phân sau dꢏu phꢣy, sau ñó ñưꢇc chuyꢄn thành

ñiꢄm chꢡ vꢘi mꢉc như sau:

ðiꢄm sꢆ tꢝ

ðiꢄm sꢆ dưꢘi

8,5 – 10 chuyꢄn thành ñiꢄm A (Giꢤi)

7,0 – 8,4 chuyꢄn thành ñiꢄm B (Khá)

5,5 – 6,9 chuyꢄn thành ñiꢄm C (Trung bình)

4,0 – 5,4 chuyꢄn thành ñiꢄm D (Trung bình yꢈu)

4,0

chuyꢄn thành ñiꢄm F (Kém)

7. Nꢇi dung chương trình

7.1 Cꢚu trúc

Cꢏu trúc chương trình ñào tꢃo trình ñꢎ Tiꢈn sĩ gꢙm có 3 phꢑn như bꢓng sau ñây.

5

Phꢑn

Nꢎi dung ñào tꢃo

HP bꢒ sung

HP TS

A1

A2

CT ThS KH (28TC)

8TC

A3

0

≥ 4TC

1

TLTQ

Thꢗc hiꢌn và báo cáo trong năm hꢐc ñꢑu tiên

Tꢒng cꢎng 3 CðTS, mꢥi CðTS 2TC

2

CðTS

NC khoa hꢐc

Luꢍn án TS

3

Lưu ý:

- Sꢆ TC qui ñꢊnh cho các ñꢆi tưꢇng trong là sꢆ TC tꢆi thiꢄu NCS phꢓi hoàn thành.

- ðꢆi tưꢇng A2 phꢓi thꢗc hiꢌn toàn bꢎ các hꢐc phꢑn qui ñꢊnh trong chương trình ThS Khoa hꢐc

cꢕa ngành tương ꢉng, không cꢑn thꢗc hiꢌn luꢍn văn ThS.

- Các HP bꢒ sung ñưꢇc lꢗa chꢐn tꢝ chương trình ñào tꢃo Thꢃc sĩ cꢕa ngành ñúng chuyên ngành

Tiꢈn sĩ.

- Viꢌc qui ñꢊnh sꢆ TC cꢕa HP bꢒ sung cho ñꢆi tưꢇng A3 do ngưꢅi hưꢘng dꢚn (NHD) quyꢈt

ñꢊnh dꢗa trên cơ sꢖ ñꢆi chiꢈu các hꢐc phꢑn trong bꢓng kꢈt quꢓ hꢐc tꢍp ThS cꢕa thí sinh vꢘi

chương trình ThS hiꢌn tꢃi cꢕa ngành ñúng chuyên ngành Tiꢈn sĩ nhưng phꢓi ñꢓm bꢓo sꢆ TC

tꢆi thiꢄu trong bꢓng.

- Các HP TS ñưꢇc NHD ñꢋ xuꢏt tꢝ chương trình ñào tꢃo Thꢃc sĩ và Tiꢈn sĩ cꢕa trưꢅng nhꢜm

trang bꢊ kiꢈn cꢑn thiꢈt phꢂc vꢂ cho ñꢋ tài nghiên cꢉu cꢂ thꢄ cꢕa LATS.

7.2 Hꢛc phꢜn bꢝ sung

Các hꢐc phꢑn bꢒ sung ñưꢇc mô tꢓ trong quyꢄn “Chương trình ñào tꢉo Thꢉc sĩ” ngành “Công

nghꢁ Thông tin” hiꢌn hành cꢕa trưꢅng ðH Bách Khoa Hà Nꢎi.

NCS phꢓi hoàn thành các hꢐc phꢑn bꢒ sung trong thꢅi hꢃn 2 năm kꢄ tꢝ ngày có quyꢈt ñꢊnh

công nhꢍn là NCS.

7.3 Hꢛc phꢜn Tiꢌn sĩ

7.3.1 Danh mꢒc hꢛc phꢜn Tiꢌn sĩ

TÍN KHꢀI

CHꢩ LƯꢪNG

TT MÃ Sꢀ

TÊN HꢦC PHꢧN

GIꢨNG VIÊN

Tꢆi ưu hoá tꢒ hꢇp

Combinatorial

Optimization

Lꢍp trình song song cho

các hꢌ thꢆng ña lõi

Parallel programming for

multicore systems

1. PGS. Nguyꢛn ðꢉc

Nghĩa.

2. TS. ðꢥ Phan Thuꢍn

1

2

IT7110

IT7121

3

3(2-2-0-6)

1. TS. Nguyꢛn Hꢡu

ðꢉc.

2. TS. Cao Tuꢏn Dũng

Các chꢕ ñꢋ nâng cao trong 1. TS. Nguyꢛn Khanh

lý thuyꢈt hꢌ ñiꢋu hành

Advanced Topics in

Operating Systems

Tìm kiꢈm ñꢊa phương dꢗa

trên ràng buꢎc

Văn

3

4

IT7131

IT7141

3

3(2-2-0-6)

2.PGS. Huỳnh Quyꢈt

Thꢔng

1. PGS. Nguyꢛn ðꢉc

Nghĩa.

2. TS. ðꢥ Phan Thuꢍn

Constraint-Based Local

Search

6

Ghi chú: Theo yêu cꢑu cꢕa ñꢊnh hưꢘng nghiên cꢉu trong luꢍn án, tꢍp thꢄ giáo sư hưꢘng dꢚn,

nghiên cꢉu sinh có thꢄ quyꢈt ñꢊnh hꢐc hꢐc phꢑn tꢝ các hꢐc phꢑn trình ñꢎ tiꢈn sꢢ cꢕa chương

trình ñào tꢃo tiꢈn sꢢ Công nghꢌ phꢑn mꢋm, Hꢌ thꢆng thông tin, Kꢢ thuꢍt máy tính.

7.3.2 Mô tꢞ tóm tꢟt hꢛc phꢜn Tiꢌn sĩ

IT7110 Tꢕi ưu hoá tꢝ hꢆp

Hꢐc phꢑn cung cꢏp cho NCS nhꢡng hưꢘng tiꢈp cꢍn phát triꢄn thuꢍt toán và các phương pháp

hiꢌn ñꢃi cꢕa tꢆi ưu hoá tꢒ hꢇp. NCS sꢠ làm chꢕ ñưꢇc các kiꢈn thꢉc vꢋ qui hoꢃch nguyên, các sơ

ñꢙ phát triꢄn thuꢍt toán dꢗa trên phân rã, sinh cꢎt, các sơ ñꢙ thuꢍt toán gꢑn ñúng và ngꢚu nhiên

trong tꢆi ưu tꢒ hꢇp.

Nꢎi dung môn hꢐc bao gꢙm: Quy hoꢃch tuyꢈn tính (phương pháp ñơn hình, phương pháp ñiꢄm

trong, lý thuyꢈt ñꢆi ngꢚu và phương pháp ñơn hình mꢃng); Quy hoꢃch nguyên tuyꢈn tính

(phương pháp siêu phꢫng cꢔt, phương pháp nhánh cꢍn, phương pháp nhánh và cꢔt, phương pháp

nhánh và ñꢊnh giá); Phương pháp phân rã trong tꢆi ưu tꢒ hꢇp (Phân rã và Sinh cꢎt); Các thuꢍt

toán gꢑn ñúng (Sơ ñꢙ PTAS và FPTAS); Các phương pháp ngꢚu nhiên.

IT7110 Combinatorial Optimization

This course provides Ph.D students with algorithm development approaches and modern

metheods in combinatorial optimization. Ph.D students are expected to own knowledge on linear

programming, algorithm development schemas based on decomposition, column generation,

aproximative and heuristic algorithm schemas in combinatorial optimization.

This course includes: Linear Programming (Simplex Method, Interior Point Method, Dual

Theory and Network Simplex Method); Linear Interger Programming (Hyper-plan Cutting

Method, Brand and Bound Method, Branch and Cut Method, Branch and Price Method);

Decomposition Method in Combinatorial Optimization (Decomposition and Column

Generation); Approximation Algorithms (PTAS and FPTAS Schemas); Randomized Methods.

IT7121 Lꢋp trình song song cho các hꢙ thꢕng ña lõi

Hꢐc phꢑn này tꢍp trung giꢘi thiꢌu các kꢢ thuꢍt lꢍp trình song song phù hꢇp các kiꢈn trúc ña lõi

ñang phꢒ biꢈn hiꢌn nay. Nhꢡng chꢕ ñꢋ chính cꢕa hꢐc phꢑn là: lꢍp trình ña luꢙng, chia sꢬ bꢎ nhꢘ

chung, lꢍp trình song song dꢡ liꢌu, lꢍp trình ña dꢂng trên các bꢎ xꢭ lý ñꢙ hꢐa ña lõi. Trong nꢎi

dung cꢕa hꢐc phꢑn cũng giꢘi thiꢌu mꢎt sꢆ công cꢂ ñiꢄn hình như vꢘi ngôn ngꢡ Cilk; vꢘi ngôn

ngꢡ NESL; Ngoài ra hꢐc phꢑn cũng ñꢋ cꢍp tꢘi mô hình lꢍp trình mꢉc cao vꢘi mꢎt sꢆ thư viꢌn

khung song song như SkeTo.

IT7121 Parallel programming for multicore systems

This course focuses introduce parallel programming techniques suitable multi-core architectures

are popular today. The main theme of course is multi-threaded programming, shared common

memory, data parallel programming, programming on multi-processor multi-core graphics.

During the course content also introduces some typical tools such as Cilk language, the language

NESL; The course also addresses high-level programming model with a frame of parallel

libraries such as SkeTo.

IT7131 Các chꢠ ñꢘ nâng cao trong lý thuyꢌt hꢙ ñiꢘu hành

Hꢐc phꢑn này tꢍp trung giꢘi thiꢌu mꢎt sꢆ các chꢕ ñꢋ tiên tiꢈn trong lý thuyꢈt hꢌ ñiꢋu hành: khái

niꢌm vꢋ vꢋ Processes và Threads; các phương pháp tiên tiꢈn lꢍp lꢊch CPU và thꢗc thi chương

trình; chương trình tương tranh và ñꢙng bꢎ; các kꢢ thuꢍt tiên tiꢈn quꢓn lý bꢎ nhꢘ; hꢌ ñiꢋu hành

trong các hꢌ thꢆng phân tán; hꢌ ñiꢋu hành trong các hꢌ nhúng.

IT7131 Advanced Topics in Operating Systems

This course focuses introduce some advanced topics in operating systems theory: the concept of

the Processes and Threads, and other advanced methods CPU scheduling and program execution;

7

program concurrency and synchronization ; the advanced techniques of memory management,

operating system in distributed systems, operating systems in embedded systems.

IT7141 Tìm kiꢌm ñꢗa phương dꢉa trên ràng buꢇc

Hꢐc phꢑn này cung cꢏp cho NCS các kiꢈn thꢉc nꢋn tꢓng cꢕa Tìm kiꢈm ñꢊa phương dꢗa trên ràng

buꢎc – mꢎt hưꢘng tiꢈp cꢍn có triꢄn vꢐng ñꢄ giꢓi quyꢈt nhiꢋu bài toán ꢉng dꢂng thꢗc tiꢛn quan

trꢐng. Hꢐc xong hꢐc phꢑn này NCS có thꢄ tiꢈp tꢂc nghiên cꢉu ꢉng dꢂng cách tiꢈp cꢍn này trong

viꢌc nghiên cꢉu phát triꢄn thuꢍt toán giꢓi quyꢈt các vꢏn ñꢋ ꢉng dꢂng.

Hꢐc phꢑn bao gꢙm: Sơ ñꢙ tìm kiꢈm ñꢊa phương; Tìm kiꢈm ñꢊa phương dꢗa trên ràng buꢎc; Các

ꢉng dꢂng cꢕa tìm kiꢈm ñꢊa phương trong viꢌc phát triꢄn các thuꢍt toán metaheuristic; ꢮng dꢂng

cꢕa tìm kiꢈm ñꢊa phương trong lý thuyꢈt lꢍp lꢊch.

IT7141 Constraint-Based Local Search

This course provides Ph.D students basic knowledge of Constraint-based Local search - one

promising approach for solving important pratical problems. After this course, Ph.D students are

expected to use this knowledge in order to do their research on algorithm development for

pratical problems.

This course includes: Local Search Schema; Constraint-Based Local Search; Local Search

Applications in the Development of Meta-Heuristic Algorithms; Local Search Applications in

the Scheduling Theory.

7.3.3 Kꢌ hoꢊch hꢛc tꢋp các hꢛc phꢜn Tiꢌn sĩ

Các hꢐc phꢑn Tiꢈn sĩ ñưꢇc thꢗc hiꢌn linh hoꢃt, tùy theo các ñiꢋu kiꢌn thꢅi gian cꢂ thꢄ cꢕa giꢓng

viên. Tuy nhiên, nghiên cꢉu sinh phꢓi hoàn thành các hꢐc phꢑn Tiꢈn sĩ trong vòng 24 tháng kꢄ tꢝ

ngày có quyꢈt ñꢊnh công nhꢍn NCS.

7.4 Chuyên ñꢘ Tiꢌn sĩ

Mꢥi nghiên cꢉu sinh phꢓi hoàn thành 3 chuyên ñꢋ Tiꢈn sĩ có thꢄ chꢐn tꢝ danh sách hưꢘng

chuyên sâu. Mꢥi hưꢘng chuyên sâu ñꢋu có ngưꢅi hưꢘng dꢚn do Hꢎi ñꢙng Xây dꢗng chương

trình ñào tꢃo chuyên ngành cꢕa Viꢌn Công nghꢌ thông tin và truyꢋn thông xác ñꢊnh.

Ngưꢅi hưꢘng dꢚn khoa hꢐc luꢍn án cꢕa nghiên cꢉu sinh sꢠ ñꢋ xuꢏt ñꢋ tài cꢂ thꢄ. Ưu tiên ñꢋ

xuꢏt ñꢋ tài gꢔn liꢋn, thiꢈt thꢗc vꢘi ñꢋ tài cꢕa luꢍn án Tiꢈn sĩ.

Sau khi ñã có ñꢋ tài cꢂ thꢄ, NCS thꢗc hiꢌn ñꢋ tài ñó dưꢘi sꢗ hưꢘng dꢚn khoa hꢐc cꢕa ngưꢅi

hưꢘng dꢚn chuyên ñꢋ.

Danh mꢂc hưꢘng chuyên sâu cho Chuyên ñꢋ Tiꢈn sĩ

TT MÃ Sꢀ HƯꢯNG CHUYÊN SÂU

NGƯꢰI HƯꢯNG DꢱN

1. PGS. Nguyꢛn ðꢉc Nghĩa.

2. TS. ðꢥ Phan Thuꢍn

1. TS. Nguyꢛn Hꢡu ðꢉc.

2. TS. Cao Tuꢏn Dũng

TÍN CHꢩ

1

2

IT7210 Network Optimization

2

Parallel process and Multicore

IT7221

IT7231

2

systems

Các giꢓit thuꢍt và môi trương tính

toán tiên tiꢈn

3

1. PGS. Nguyꢛn ðꢉc Nghĩa.

Innovative Computing Algorithms 2. TS. ðꢥ Phan Thuꢍn

and Platforms

Công nghꢌ ða phương tiꢌn, mô

phꢤng và hiꢄn thꢊ

Multimedia, Visualization and

Simulation

1. TS. Nguyꢛn Linh Giang.

2. TS. Nguyꢛn Hꢡu ðꢉc

4

IT7241

2

8

Sinh tin hꢐc

Bioinformatics

Information Retrieval and

Searching

Combinatorial Enumeration and

Design

1.TS. ðꢥ Phan Thuꢍn

2.TS. Tꢃ Tuꢏn Anh

1. TS. Tꢃ Tuꢏn Anh.

2. TS. Cao Tuꢏn Dũng

1. PGS. Nguyꢛn ðꢉc Nghĩa.

2. TS. ðꢥ Phan Thuꢍn

5

6

7

IT7251

IT7261

IT7271

2

8 Danh sách Tꢊp chí / Hꢇi nghꢗ khoa hꢛc

Các diꢛn ñàn khoa hꢐc trong nưꢘc trong bꢓng dưꢘi ñây là nơi NCS có thꢄ chꢐn công bꢆ các kꢈt

quꢓ nghiên cꢉu khoa hꢐc phꢂc vꢂ hoàn thành luꢍn án Tiꢈn sĩ.

ðꢊnh kỳ

Sꢆ

TT

Tên diꢛn ñàn

ðꢊa chꢞ liên hꢌ

xuꢏt bꢓn / hꢐp

ðH Bách Khoa Hà Nꢎi; Sꢆ 1,

phꢆ ðꢃi Cꢙ Viꢌt, Hai Bà

Trưng, Hà Nꢎi

1

2

3

Tꢃp chí Khoa hꢐc và Công nghꢌ

Hai tháng 1 lꢑn

Tꢃp chí Khoa hꢐc và Công nghꢌ

trưꢅng ðꢃi hꢐc quꢆc gia Hà nꢎi

Trưꢅng ðꢃi hꢐc Quꢆc Gia Hà

Nꢎi

Tꢃp chí Khoa hꢐc và Công nghꢌ

trưꢅng ðꢃi hꢐc quꢆc gia thành

phꢆ Hꢙ Chí Minh

Trưꢅng ðꢃi hꢐc Quꢆc Gia

Thành phꢆ Hꢙ Chí Minh

Tꢃp chí Bưu chính viꢛn thông,

Viꢌn Khoa hꢐc và Công nghꢌ

Viꢌt Nam; ñưꢅng Hoàng

Quꢆc Viꢌt, Hà Nꢎi

Chuyên san Các nghiên cꢉu và

triꢄn khai ꢉng dꢂng trong viꢛn

thông và Công nghꢌ thông tin

4

Ba tháng 1 lꢑn

Viꢌn Khoa hꢐc và Công nghꢌ

Viꢌt Nam; sꢆ 18 ñưꢅng

Hoàng Quꢆc Viꢌt, Hà Nꢎi

Tꢃp chí Công nghꢌ thông tin 3

tháng 1 lꢑn

5

6

Ba tháng 1 lꢑn

Hàng năm

Hꢎi thꢓo khoa hꢐc quꢆc gia vꢋ

nghiên cꢉu, phát triꢄn và ꢉng

dꢂng CNTT và Truyꢋn thông ICT

RDA

Ban chương trình quꢆc gia

Hꢎi nghꢊ khoa hꢐc “Mꢎt sꢆ vꢏn

ñꢋ chꢐn lꢐc trong CNTT”

7

8

9

Hàng năm

Hꢎi thꢓo Khoa hꢐc Quꢆc gia –

"Nghiên cꢉu cơ bꢓn và ꢉng dꢂng Ban chương trình quꢆc gia

Công nghꢌ thông tin” FAIR

Các Hꢎi nghꢊ quꢆc tꢈ tꢒ chꢉc tꢃi

Ban chương trình quꢆc gia

Viꢌt Nam

9

PHꢍN II

ðꢏ CƯƠNG CHI TIꢅT CÁC HꢄC PHꢍN

10

9

Danh mꢒc hꢛc phꢜn chi tiꢌt cꢠa chương trình ñào tꢊo

9.1 Danh mꢒc hꢛc phꢜn bꢝ sung

Danh mꢂc hꢐc phꢑn bꢒ sung có thꢄ xem chi tiꢈt trong quyꢄn “Chương trình ñào tꢉo Thꢉc sĩ

Công nghꢁ thông tin” cꢕa Trưꢅng ðHBK Hà Nꢎi.

9.2 Danh mꢒc hꢛc phꢜn Tiꢌn sĩ

Sꢆ MÃ

TT Sꢀ

TÊN TIꢲNG

ANH

KHꢀI

LƯꢪNG

Khoa/Viꢌn Bꢎ

môn

ðánh

giá

TÊN HꢦC PHꢧN

KT0,3-

Combinatorial

Optimization

1

3(2-2-0-6) Bm KHMT

IT7110 Tꢆi ưu hoá tꢒ hꢇp

T0,7

Liên BM

3(2-2-0-6) KHMT+HTTT

+CNPM

Lꢍp trình song song Parallel

IT7121 cho các hꢌ thꢆng ña programming for

KT0,3-

T0,7

2

lõi

multicore systems

Liên BM

Các chꢕ ñꢋ nâng

IT7131 cao trong lý thuyꢈt

hꢌ ñiꢋu hành

Advanced Topics

in Operating

Systems

KT0,3-

T0,7

3

4

3(2-2-0-6) KHMT+HTTT

+CNPM

Tìm kiꢈm ñꢊa

phương dꢗa trên

ràng buꢎc

KT0,3-

T0,7

Constraint-Based

Local Search

3(2-2-0-6) Bm KHMT

IT7141

10 ðꢘ cương chi tiꢌt các hꢛc phꢜn Tiꢌn sĩ

IT7110 Tꢕi ưu hoá tꢝ hꢆp

Combinatorial Optimization

1. Tên hꢛc phꢜn: Tꢆi ưu hoá tꢒ hꢇp

2. Mã hꢛc phꢜn: IT7110

3. Tên tiꢌng Anh: Combinatorial Optimization

4. Khꢕi lưꢆng: 3(2-2-0-6)

- Lý thuyꢈt:30 tiꢈt

- Bài tꢍp:

30 tiꢈt

- Thí nghiꢌm:

5. ðꢕi tưꢆng tham dꢉ: Tꢏt cꢓ NCS thuꢎc chuyên ngành Khoa hꢐc Máy tính

6. Mꢒc tiêu cꢠa hꢛc phꢜn: Hꢐc phꢑn cung cꢏp cho NCS nhꢡng hưꢘng tiꢈp cꢍn phát triꢄn thuꢍt

toán và các phương pháp hiꢌn ñꢃi cꢕa tꢆi ưu hoá tꢒ hꢇp. NCS sꢠ làm chꢕ ñưꢇc các kiꢈn thꢉc vꢋ

qui hoꢃch nguyên, các sơ ñꢙ phát triꢄn thuꢍt toán dꢗa trên phân rã, sinh cꢎt, các sơ ñꢙ thuꢍt toán

gꢑn ñúng và ngꢚu nhiên trong tꢆi ưu tꢒ hꢇp.

7. Nꢇi dung tóm tꢟt: Quy hoꢃch tuyꢈn tính (phương pháp ñơn hình, phương pháp ñiꢄm trong,

lý thuyꢈt ñꢆi ngꢚu và phương pháp ñơn hình mꢃng); Quy hoꢃch nguyên tuyꢈn tính (phương pháp

siêu phꢫng cꢔt, phương pháp nhánh cꢍn, phương pháp nhánh và cꢔt, phương pháp nhánh và ñꢊnh

giá); Phương pháp phân rã trong tꢆi ưu tꢒ hꢇp (Phân rã và Sinh cꢎt); Các thuꢍt toán gꢑn ñúng

(Sơ ñꢙ PTAS và FPTAS); Các phương pháp ngꢚu nhiên.

8. Nhiꢙm vꢒ cꢠa NCS:

11

- Dꢗ lꢘp:

- Bài tꢍp:

- Thí nghiꢌm:

9. ðánh giá kꢌt quꢞ: (cách cho ñiꢄm giꢆng như quy ñꢊnh ñꢆi vꢘi Cao hꢐc)

- Mꢉc ñꢎ dꢗ giꢅ giꢓng: 0.2

- Kiꢄm tra ñꢊnh kỳ:

0.3

- Thi kꢈt thúc hꢐc phꢑn: 0.5

10. Nꢇi dung chi tiꢌt hꢛc phꢜn:

Chương 1. Mꢡ ñꢜu

1.1. Bài toán tꢆi ưu tꢒ hꢇp

1.2. Các mô hình thꢗc tꢈ cꢕa tꢆi ưu hoá tꢒ hꢇp

Chương 2. Qui hoꢊch tuyꢌn tính

2.1. Bài toán qui hoach tuyꢈn tính

2.2. Thuꢍt toán ñơn hình

2.3. Thuꢍt toán ñiꢄm trong

2.4. Lý thuyꢈt ñꢆi ngꢚu

2.5. Thuꢍt toán gꢆc-ñꢆi ngꢚu

Chương 3. Qui hoꢊch nguyên

3.1. Bài toán qui hoꢃch nguyên

3.2. Phương pháp siêu phꢫng cꢔt

3.3. Phương pháp nhánh cꢍn

3.4. Phương pháp nhánh và cꢔt

3.5. Phương pháp nhánh và ñꢊnh giá

Chương 4. Phân rã và sinh cꢇt Decomposition and Column Generation)

4.1. Nguyên lí phân rã

4.2. Giꢓi bài toán con

4.3. Giꢓi bài toán chꢕ

4.4. Phương pháp sinh cꢎt

4.5. ꢮng dꢂng vào mꢎt sꢆ bài toán tꢆi ưu tꢒ hꢇp

Chương 5. Các phương pháp gꢜn ñúng

5.1. Cꢍn sai sꢆ tꢳ lꢌ và sơ ñꢙ xꢏp xꢞ ña thꢉc

5.2. Mꢎt sꢆ kꢢ thuꢍt phát triꢄn thuꢍt toán vꢘi ñánh giá cꢍn sai sꢆ tꢳ lꢌ

12

5.3. Ví dꢂ ꢉng dꢂng

Chương 6. Các thuꢋt toán ngꢢu nhiên

6.1. Nhꢍp môn thuꢍt toán ngꢚu nhiên

6.2. Phát triꢄn thuꢍt toán ngꢚu nhiên cho mꢎt sꢆ lꢘp bài toán tꢆi ưu tꢒ hꢇp

11. Tài liꢙu hꢛc tꢋp: ðꢋ cương và Slides bài giꢓng môn hꢐc

12. Tài liꢙu tham khꢞo:

[1] Korte B., Vygen J. Combinatorial Optimization Theory and Algorithms.

Springer, 2008.

[2] John K. Karlof (Ed.). Integer programming. Theory and Practice. CRC Press, 2006.

IT7121

Lꢋp trình song song cho các hꢙ thꢕng ña lõi

Parallel programming for multicore systems

1. Tên hꢛc phꢜn: Lꢍp trình song song cho các hꢌ thꢆng ña lõi

2. Mã hꢛc phꢜn: IT7121

3. Tên tiꢌng Anh: Parallel programming for multicore systems

4. Khꢕi lưꢆng: 3(2-2-0-6)

- Lý thuyꢈt: 30 tiꢈt

- Bài tꢍp:

30 tiꢈt

- Thí nghiꢌm:

5. ðꢕi tưꢆng tham dꢉ: Tꢏt cꢓ NCS thuꢎc chuyên ngành Khoa hꢐc máy tính

6. Mꢒc tiêu cꢠa hꢛc phꢜn:

Hꢐc phꢑn này nhꢜm mang lꢃi cho NCS: Các kiꢈn thꢉc nâng cao vꢋ lý luꢍn chuyên ngành khoa

hꢐc máy tính; Rèn luyꢌn khꢓ năng tư duy lꢍp trình theo mô hình song song, áp dꢂng cho các kiꢈn

trúc tính toán hiꢌn ñꢃi; Rèn kꢢ năng công nghꢌ cꢕa chuyên ngành khoa hꢐc máy tính

7. Nꢇi dung tóm tꢟt:

Hꢐc phꢑn này tꢍp trung giꢘi thiꢌu các kꢢ thuꢍt lꢍp trình song song phù hꢇp các kiꢈn trúc ña lõi

ñang phꢒ biꢈn hiꢌn nay. Nhꢡng chꢕ ñꢋ chính cꢕa hꢐc phꢑn là: lꢍp trình ña luꢙng, chia sꢬ bꢎ nhꢘ

chung vꢘi ngôn ngꢡ Cilk; lꢍp trình song song dꢡ liꢌu vꢘi ngôn ngꢡ NESL; lꢍp trình ña dꢂng trên

các bꢎ xꢭ lý ñꢙ hꢐa ña lõi. Ngoài ra hꢐc phꢑn cũng ñꢋ cꢍp tꢘi mô hình lꢍp trình mꢉc cao vꢘi mꢎt

sꢆ thư viꢌn khung song song như SkeTo.

8. Nhiꢙm vꢒ cꢠa NCS:

- Dꢗ lꢘp:

- Bài tꢍp:

- Thí nghiꢌm:

9. ðánh giá kꢌt quꢞ:

- Mꢉc ñꢎ dꢗ giꢅ giꢓng: 0.2

13

- Kiꢄm tra ñꢊnh kỳ:

0.3

- Thi kꢈt thúc hꢐc phꢑn: 0.5

10. Nꢇi dung chi tiꢌt hꢛc phꢜn:

Mꢡ ñꢜu

Giꢘi thiꢌu môn hꢐc

Giꢘi thiꢌu ñꢋ cương môn hꢐc

Giꢘi thiꢌu tài liꢌu tham khꢓo

Chương 1:Tꢝng quan vꢘ lꢋp trình song song cho các hꢙ thꢕng ña lõi

1.1 Giꢘi thiꢌu chung

1.2 Các hꢌ thꢆng tính toán song song ña lõi

1.3 Các mô hình lꢍp trình song song trên nhꢡng hꢌ thꢆng ña lõi

Chương 2:Song song ñiꢘu khiꢓn

2.1 Lꢍp trình ña luꢙng

2.2 Các kꢢ thuꢍt chia sꢬ bꢎ nhꢘ chung

2.3 Lꢍp trình ña luꢙng ñꢎng vꢘi Cilk

Chương 3:Song song dꢣ liꢙu

3.1 Các phép toán song song dꢡ liꢌu

3.2 Lꢍp trình song song dꢡ liꢌu vꢘi NESL

Chương 4:Tính toán ña dꢒng trên các bꢇ xꢤ lý ñꢈ hꢛa (GPU)

4.1 Kiꢈn trúc GPU

4.2 Lꢍp trình ña dꢂng trên các bꢎ xꢭ lý ñꢙ hꢐa ña lõi

4.3 Tꢆi ưu hóa truy nhꢍp bꢎ nhꢘ

Chương 5:Lꢋp trình mꢖc cao vꢥi khung song song (parallel skeletal)

5.1 Khái niꢌm khung song song

5.2 Các khung song song cơ bꢓn

5.3 Các khung song song mꢖ rꢎng

11. Tài liꢙu hꢛc tꢋp: ðꢋ cương và Slides bài giꢓng môn hꢐc

12. Tài liꢙu tham khꢞo:

[1]. Thomas Rauber , Gudula Rünger. Parallel programming for multicore and cluster system.

Springer, 2010, ISBN: 364204817X, 450 pages

[2]. Daryl Gove. Multicore Application Programming: for Windows, Linux, and Oracle Solaris.

Developer's Library, 2010

IT7131

Các chꢠ ñꢘ nâng cao trong lý thuyꢌt hꢙ ñiꢘu hành

Advanced Topics in Operating Systems

1. Tên hꢛc phꢜn: Lꢍp trình song song cho các hꢌ thꢆng ña lõi

2. Mã hꢛc phꢜn: Các chꢕ ñꢋ nâng cao trong lý thuyꢈt hꢌ ñiꢋu hành

3. Tên tiꢌng Anh: Advanced Topics in Operating Systems

14

4. Khꢕi lưꢆng: 3(2-2-0-6)

- Lý thuyꢈt: 30 tiꢈt

- Bài tꢍp:

30 tiꢈt

- Thí nghiꢌm:

5. ðꢕi tưꢆng tham dꢉ: Tꢏt cꢓ NCS thuꢎc chuyên ngành Khoa hꢐc máy tính

6. Mꢒc tiêu cꢠa hꢛc phꢜn:

Hꢐc phꢑn này nhꢜm mang lꢃi cho NCS: Các kiꢈn thꢉc nâng cao vꢋ lý luꢍn chuyên ngành khoa

hꢐc máy tính; Rèn luyꢌn khꢓ năng tư duy hꢌ thꢆng, áp dꢂng cho các kiꢈn trúc và kꢢ thuꢍt tính

toán hiꢌn ñꢃi; Rèn kꢢ năng công nghꢌ cꢕa chuyên ngành khoa hꢐc máy tính

7. Nꢇi dung tóm tꢟt:

Hꢐc phꢑn này tꢍp trung giꢘi thiꢌu mꢎt sꢆ các chꢕ ñꢋ tiên tiꢈn trong lý thuyꢈt hꢌ ñiꢋu hành: khái

niꢌm vꢋ vꢋ Processes và Threads; các phương pháp tiên tiꢈn lꢍp lꢊch CPU và thꢗc thi chương

trình; chương trình tương tranh và ñꢙng bꢎ; các kꢢ thuꢍt tiên tiꢈn quꢓn lý bꢎ nhꢘ; hꢌ ñiꢋu hành

trong các hꢌ thꢆng phân tán; hꢌ ñiꢋu hành trong các hꢌ nhúng.

8. Nhiꢙm vꢒ cꢠa NCS:

- Dꢗ lꢘp:

- Bài tꢍp:

- Thí nghiꢌm:

9. ðánh giá kꢌt quꢞ:

- Mꢉc ñꢎ dꢗ giꢅ giꢓng:

- Kiꢄm tra ñꢊnh kỳ:

0.2

0.3

- Thi kꢈt thúc hꢐc phꢑn: 0.5

10. Nꢇi dung chi tiꢌt hꢛc phꢜn:

PHꢍN Mꢦ ðꢍU

Giꢘi thiꢌu môn hꢐc

Giꢘi thiꢌu ñꢋ cương môn hꢐc

Giꢘi thiꢌu tài liꢌu tham khꢓo

Chương 1: Tꢝng quan vꢘ lý thuyꢌt hꢙ ñiꢘu hành

1.1.Tꢒng quan vꢋ hꢌ ñiꢋu hành

1.2. Nhꢡng khái niꢌm và kꢢ thuꢍt tiêu biꢄu trong lý thuyꢈt hꢌ ñiꢋu hành

1.3. Các ñꢊnh hưꢘng phát triꢄn trong lý thuyꢈt hꢌ ñiꢋu hành

Chương 2: Các kꢧ thuꢋt hiꢙn ñꢊi quꢞn lý tiꢌn trình

2.1. Khái niꢌm vꢋ tiꢈn trình

2.2. Các kꢢ thuꢍt quꢓn lý tiꢈn trình

2.3. Các kꢢ thuꢍt lꢍp lꢊch cho tiꢈn trình

2.4. Các kꢢ thuꢍt ñꢙng bꢎ và trao ñꢒi (Synchronization and communication)

2.5. Quꢓn lý tiꢈn trình và lꢍp lꢊch trong mꢎt sꢆ hꢌ ñiꢋu hành tiêu biꢄu

Chương 3: Các kꢧ thuꢋt hiꢙn ñꢊi quꢞn lý bꢇ nhꢥ

15

3.1.Quꢓn lý bꢎ nhꢘ thꢗc

3.2. Quꢓn lý bꢎ nhꢘ ꢓo

3.3. Quꢓn lý bꢎ nhꢘ trong mꢎt sꢆ hꢌ ñiꢋu hành tiêu biꢄu

Chương 4: Công nghꢙ ꢞo hóa (Virtualization Technology)

4.1. Các khái niꢌm cơ bꢓn

4.2. Kꢢ thuꢍt ꢓo hóa

4.3. ꢨo hóa bꢎ vi xꢭ lý (CPU Virtualization)

Chương 5: Các kꢧ thuꢋt bꢞo mꢋt và chꢗu lꢨi

5.1 Tꢒng quan vꢋ bꢓo mꢍt, xác thꢗc và chꢊu lꢥi

5.2 Các kꢢ thuꢍt bꢓo mꢍt dꢡ liꢌu

5.3 Các kꢢ thuꢍt xác thꢗc

5.4 Các kꢢ thuꢍt chꢊu lꢥi

11. Tài liꢙu hꢛc tꢋp: ðꢋ cương và Slides bài giꢓng môn hꢐc

12. Tài liꢙu tham khꢞo:

[1]Andrew S. Tanenbaum (2007). Modern Operating Systems (3rd Edition), Prentice Hall; 3

edition (December 21, 2007)

[2]Thomas W. Doeppner (2010). Operating Systems In Depth: Design and Programming. Wiley

(November 2, 2010)

IT7141 Tìm kiꢌm ñꢗa phương dꢉa trên ràng buꢇc

Constraint-Based Local Search

1. Tên hꢛc phꢜn: Tìm kiꢈm ñꢊa phương dꢗa trên ràng buꢎc

2. Mã hꢛc phꢜn: IT7141

3. Tên tiꢌng Anh: Constraint-Based Local Search

4. Khꢕi lưꢆng: 3(2-2-0-6)

- Lý thuyꢈt:30 tiꢈt

- Bài tꢍp: 30 tiꢈt

- Thí nghiꢌm:

5. ðꢕi tưꢆng tham dꢉ: Tꢏt cꢓ NCS thuꢎc chuyên ngành Khoa hꢐc Máy tính

6. Mꢒc tiêu cꢠa hꢛc phꢜn: Hꢐc phꢑn này cung cꢏp cho NCS các kiꢈn thꢉc nꢋn tꢓng cꢕa Tìm

kiꢈm ñꢊa phương dꢗa trên ràng buꢎc – mꢎt hưꢘng tiꢈp cꢍn có triꢄn vꢐng ñꢄ giꢓi quyꢈt nhiꢋu bài

toán ꢉng dꢂng thꢗc tiꢛn quan trꢐng. Hꢐc xong hꢐc phꢑn này NCS có thꢄ tiꢈp tꢂc nghiên cꢉu ꢉng

dꢂng cách tiꢈp cꢍn này trong viꢌc nghiên cꢉu phát triꢄn thuꢍt toán giꢓi quyꢈt các vꢏn ñꢋ ꢉng

dꢂng.

16

7. Nꢇi dung tóm tꢟt: Sơ ñꢙ tìm kiꢈm ñꢊa phương; Tìm kiꢈm ñꢊa phương dꢗa trên ràng buꢎc;

Các ꢉng dꢂng cꢕa tìm kiꢈm ñꢊa phương trong viꢌc phát triꢄn các thuꢍt toán metaheuristic; ꢮng

dꢂng cꢕa tìm kiꢈm ñꢊa phương trong lý thuyꢈt lꢍp lꢊch. Giꢘi thiꢌu ngôn ngꢡ lꢍp trình chuyên

dꢂng (COMET) ñꢄ mô hình hoá và giꢓi các bài toán tꢆi ưu.

8. Nhiꢙm vꢒ cꢠa NCS:

- Dꢗ lꢘp:

- Bài tꢍp:

- Thí nghiꢌm:

9. ðánh giá kꢌt quꢞ: (cách cho ñiꢄm giꢆng như quy ñꢊnh ñꢆi vꢘi Cao hꢐc)

- Mꢉc ñꢎ dꢗ giꢅ giꢓng: 0.2

- Kiꢄm tra ñꢊnh kỳ:

0.3

- Thi kꢈt thúc hꢐc phꢑn: 0.5

10. Nꢇi dung chi tiꢌt hꢛc phꢜn:

Chương 1. Tìm kiꢌm ñꢗa phương (Local Search)

1.1. Lân cꢍn tìm kiꢈm

1.2. Tꢆi ưu ñꢊa phương

1.3. Các heuristics và toán hꢐc

Chương 2. Tìm kiꢌm ñꢗa phương dꢉa trên ràng buꢇc

2.1. Mô hình hoá

2.2. Tìm kiꢈm

Chương 3. COMET

3.1. Bꢏt biꢈn

3.2. Phân nhꢤ ñꢆi tưꢇng

3.3. ðiꢋu khiꢄn

3..4 ðiꢋu khiꢄn bꢍc 1

Chương 4. ꢩng dꢒng

4.1. ꢮng dꢂng trong tìm kiꢈm Tabu

4.2. Tìm kiꢈm vꢘi lân cꢍn biꢈn ñꢒi

4.3. ꢮng dꢂng trong phꢤng tôi luyꢌn

4.4. Tìm kiꢈm ñꢊa phương dꢚn ñưꢅng

4.5. Tìm kiꢈm tiꢈn hoá lai

4.6. Tìm kiꢈm ñꢊa phương ñꢎc lꢍp vꢘi miꢋn

17

4.7. ꢮng dꢂng trong sơ ñꢙ tꢆi ưu bày kiꢈn

Chương 5. Bài toán lꢋp lꢗch

5.1 Lꢍp lꢊch dãy công viꢌc

5.2 Các ñꢆi tưꢇng lꢍp lꢊch

5.3 Bài toán lꢍp lꢊch cꢗc tiꢄu thꢅi gian trꢛ

5.4 Bài toán lꢍp lꢊch cꢗc tiꢄu thꢅi gian hoàn thành

5.6 Lꢍp lꢊch tích luꢢ

11. Tài liꢙu hꢛc tꢋp: ðꢋ cương và Slides bài giꢓng môn hꢐc

12. Tài liꢙu tham khꢞo:

[1] Pascal Van Hentenryck, Laurent Michel, Constraint-Based Local Search. MIT Press, 2005.

[2] W. Michiels, E. Aarts, J. Korst, Theoretical Aspects of Local Search. Springer, 2007.

[3] F. Rossi, P. van Beek, T. Walsh (Edit), Handbook of Constraint Programming. Elsevier,

2006.

[4] Krzysztof R. Apt, Principles of Constraint Programming, Cambridge University Press 2003.

18