Հարթության վրա պատկերված ուղղանկյուն տիրույթների հատումների գրաֆում կարճագույն ճանապարհի որոնման ալգորիթմի մշակումը և ծրագրային

1. Հարթության վրա պատկերված ուղղանկյուն տիրույթների հատումների գրաֆում կարճագույն ճանապարհի որոնման ալգորիթմի մշակումը և ծրագրային իրական

ՀԱՅԱՍՏԱՆԻ ԱԶԳԱՅԻՆ
ՊՈԼԻՏԵԽՆԻԿԱԿԱՆ ՀԱՄԱԼՍԱՐԱՆ
Հարթության վրա պատկերված
ուղղանկյուն տիրույթների հատումների
գրաֆում կարճագույն ճանապարհի
որոնման ալգորիթմի մշակումը և
ծրագրային իրականացումը
Խումբ՝
Ուսանող՝
Ղեկավար՝
Հ119-1Ս
Արմինե Գևորգյան
Գարեգին Սարգսյան
Միկրոէլեկտրոնային սխեմաներ և
համակարգեր
միջֆակուլտետային ամբիոն
1
Synopsys Armenia

2. ԲՈՎԱՆԴԱԿՈՒԹՅՈՒՆ

Ներածություն
Խնդրի դրվածքը
Ուղղանկյուն պատկերների հատումների գրաֆ
Կարճագույն ճանապարհի որոնման ալգորիթմ
Ստացված արդյունքները
Եզրակացություն
Օգտագործված գրականություն
Միկրոէլեկտրոնային սխեմաներ և
համակարգեր
միջֆակուլտետային ամբիոն
2
Synopsys Armenia

3. ԻՍ նախագծման փուլերը

Ներածություն(1
)
ԻՍ նախագծման փուլերը
Տեխնիկական առաջադրանք
Ճարատարապետական
նախագծում
Տրամաբանական նախագծում
Սխեմայի նախագծում
Ֆիզիկական նախագծում
Ֆիզիկական ստուգում
Արտադրություն
Պատյանավորում և
տեստավորում
Ինտեգրալ սխեմա
Միկրոէլեկտրոնային սխեմաներ և
համակարգեր
միջֆակուլտետային ամբիոն
3
Synopsys Armenia

4. ԻՍ-ի ֆիզիկական նախագծում

Ներածություն(2
)
ԻՍ-ի ֆիզիկական նախագծում
Սխեմայի
ձևայնացված
նկարագիր
Մասնատում
Ֆիզիկակ
ան
նախագծո
ւմ
Հիերարխիկ
պլանավորում
Տեղաբաշխում
Ծրագծում
Միկրոէլեկտրոնային սխեմաներ և
համակարգեր
միջֆակուլտետային ամբիոն
4
Synopsys Armenia

5. Տեղաբաշխում

Ներածություն(3
)
Տեղաբաշխում
Նախագծման
տարրերը
հատակագիծ
Միկրոէլեկտրոնային սխեմաներ և
համակարգեր
միջֆակուլտետային ամբիոն
5
Տեղաբաշխման նախագիծ
Synopsys Armenia

6. Ծրագծում

Ներածություն(4
)
Ծրագծում
Տեղաբաշխման նախագիծ
Միկրոէլեկտրոնային սխեմաներ և
համակարգեր
միջֆակուլտետային ամբիոն
Ծրագծման նախագիծ
6
Synopsys Armenia

7. Խնդրի դրվածքը

 Տրված է՝
հարթության վրա A = {A1, A2, …, An} ուղղանկյուն
պատկերներ
Պահանջվում է`
Ստանալ A բազմության վրա որոշված կշռված կողերով
Ω(A) հատումների գրաֆը
Մշակել ալգորիթմ, որը կգտնի Ω(A) գրաֆում տրված A i, Aj
գագաթները միացնող կարճագույն ճանապարհը
Միկրոէլեկտրոնային սխեմաներ և
համակարգեր
միջֆակուլտետային ամբիոն
7
Synopsys Armenia

8. Ուղղանկյուն պատկերների հատումների գրաֆ

f8
B
f7
f6
A
f10
f9
f2
D
f7
f
4
E
f3
f5
f6
C
F
f9
f7
f4
f3
f8
f6
f5
f10
f
4
f2
f10
f8
f2
f5
f3
Միկրոէլեկտրոնային սխեմաներ և
համակարգեր
միջֆակուլտետային ամբիոն
8
Synopsys Armenia

9. Դեյկստրայի ալգորիթմը

Կարճագույն ճանապարհի որոնման ալգորիթմ
Դեյկստրայի ալգորիթմը
6
∞
2
∞
2
2
0
4
4
2
2
4
3
3
2
5
4
4∞
Հեռավորությունը = 6
6
Միկրոէլեկտրոնային սխեմաներ և
համակարգեր
միջֆակուլտետային ամբիոն
6
5
3
∞
4
1
6
∞
3
1
1
2
9
Synopsys Armenia

10. Ծրագրի աշխատանքի օրինակ

Ստացված արդյունքները
Ծրագրի աշխատանքի օրինակ
Միկրոէլեկտրոնային սխեմաներ և
համակարգեր
միջֆակուլտետային ամբիոն
10
Synopsys Armenia

11. ԵԶՐԱԿԱՑՈՒԹՅՈՒՆ

Դիպլոմային աշխատանքի ընթացքում
կատարվել է հարթության վրա
պատկերված ուղղանկյուն տիրույթների
հատումների գրաֆում կարճագույն
ճանապարհի որոնման ալգորիթմի
մշակումը և ծրագրային իրականացումը,
որը կարելի է օգտագործել ԻՍ-ի
ֆիզիկական նախագծման
տեղաբաշխման և ծրագծման փուլերում:
Միկրոէլեկտրոնային սխեմաներ և
համակարգեր
միջֆակուլտետային ամբիոն
11
Synopsys Armenia

12. Օգտագործված գրականություն

Keijo Ruohonen,Translation by Janne Tamminen, Kung-Chung Lee and
Robert Piché, 2013
http://en.wikipedia.org
L.S. Chandran, N. Sivadasan , Journal of Combinatorial Theory, Series B 97
, 2007
Жасмин Бланшет, Марк Саммерфилдt , Программирование GUI на С+
+, 2-е издание, 2008
Naveed A. Sherwani, Algorithms For VLSI Physical Design Automation
,Third Edition, 2002
Andreq B. Kahng, Jens Lienig, Igor L. Markov, Jin Hu, VLSI Physical Design.
From Graph to Timing Clouser, 2008
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Introduction to
Algoritms, 3rd Edition, 2009
Միկրոէլեկտրոնային սխեմաներ և
համակարգեր
միջֆակուլտետային ամբիոն
12
Synopsys Armenia

13.

ՇՆՈՐՀԱԿԱԼՈՒԹՅՈՒՆ
Միկրոէլեկտրոնային սխեմաներ և
համակարգեր
միջֆակուլտետային ամբիոն
13
Synopsys Armenia