introduction to algorithms

PPT 29 sahifa 523,0 KB Bepul yuklash

29 sahifa

FaylHub.uz

Telegram orqali yuklab olish

Hajm 523,0 KB

Fayl turi PPT

Sahifalar 29

Yangilangan Dek 2025

Sahifa ko'rinishi (5 sahifa)

Pastga aylantiring 👇

1 / 29

algorithms and data structures algorithms and data structures * september 10, 2001 * administration people simonas šaltenis anders b. christensen daniel povlsen home page http://www.cs.auc.dk/~simas/ad01 check the homepage frequently! course book “ introduction to algorithms”, 2.ed cormen et al. lectures, fib 15, a, 8:15-10:00, mondays and thursdays * september 10, 2001 * administration (2) exercises: every week after the lecture exam: se course, written troubles simonas šaltenis e1-215 simas@cs.auc.dk september 10, 2001 * syllabus introduction (1) correctness, analysis of algorithms (2,3,4) sorting (1,6,7) elementary data structures, adts (10) searching, advanced data structures (11,12,13,18) dynamic programming (15) graph algorithms (22,23,24) computational geometry (33) np-completeness (34) september 10, 2001 * what is it all about? solving problems get me from home to work balance my checkbook simulate a jet engine graduate from spu using a computer to help solve problems designing programs (architecture, algorithms) writing programs verifying programs documenting programs september 10, …

2 / 29

0-300 b.c. 19th century – charles babbage, ada lovelace. 20th century – alan turing, alonzo church, john von neumann september 10, 2001 * algorithmic problem infinite number of input instances satisfying the specification. for example: a sorted, non-decreasing sequence of natural numbers. the sequence is of non-zero, finite length: 1, 20, 908, 909, 100000, 1000000000. 3. specification of input ? specification of output as a function of input september 10, 2001 * algorithmic solution algorithm describes actions on the input instance infinitely many correct algorithms for the same algorithmic problem input instance, adhering to the specification algorithm output related to the input as required september 10, 2001 * sort example: sorting input sequence of numbers a1, a2, a3,….,an b1,b2,b3,….,bn output a permutation of the sequence of numbers 2 5 4 10 7 2 4 5 7 10 correctness for any given input the algorithm halts with the output: b1 0 …

3 / 29

adratic time average case: tj=j/2, running time = f(n2), i.e., quadratic time september 10, 2001 * best/worst/average case (2) for a specific size of input n, investigate running times for different input instances: 1n 2n 3n 4n 5n 6n september 10, 2001 * best/worst/average case (3) for inputs of all sizes: 1n 2n 3n 4n 5n 6n input instance size running time 1 2 3 4 5 6 7 8 9 10 11 12 ….. best-case average-case worst-case september 10, 2001 * best/worst/average case (4) worst case is usually used: it is an upper-bound and in certain application domains (e.g., air traffic control, surgery) knowing the worst-case time complexity is of crucial importance for some algorithms worst case occurs fairly often the average case is often as bad as the worst case finding the average case can be very difficult september 10, 2001 * growth functions september 10, 2001 * …

4 / 29

2 512 512 512 512 1024 1024 1024 1024 1024 1024 1024 n log n sqrt n n log n 100n n^2 n^3 n t(n) 2 0.3010299957 1.4142135624 0.6020599913 200 4 8 4 0.6020599913 2 2.4082399653 400 16 64 8 0.903089987 2.8284271247 7.2247198959 800 64 512 16 1.2041199827 4 19.2659197225 1600 256 4096 32 1.5051499783 5.6568542495 48.1647993062 3200 1024 32768 64 1.806179974 8 115.595518335 6400 4096 262144 128 2.1072099696 11.313708499 269.7228761149 12800 16384 2097152 256 2.4082399653 16 616.5094311198 25600 65536 16777216 512 2.709269961 22.627416998 1387.1462200196 51200 262144 134217728 1024 3.0102999566 32 3082.5471555992 102400 1048576 1073741824 all-2^n 2 2 2 2 2 2 2 4 4 4 4 4 4 4 4 16 8 8 8 8 8 8 8 256 16 16 16 16 16 16 16 65536 32 32 32 32 32 32 32 4294967296 64 64 64 64 64 64 64 1.84467440737096e+19 128 128 128 128 128 128 …

5 / 29

8761149 12800 16384 2097152 3.40282366920938e+38 256 2.4082399653 16 616.5094311198 25600 65536 16777216 1.15792089237316e+77 512 2.709269961 22.627416998 1387.1462200196 51200 262144 134217728 1.34078079299426e+154 1024 3.0102999566 32 3082.5471555992 102400 1048576 1073741824 1,8e+308 all 2 2 2 2 2 2 2 4 4 4 4 4 4 4 8 8 8 8 8 8 8 16 16 16 16 16 16 16 32 32 32 32 32 32 32 64 64 64 64 64 64 64 128 128 128 128 128 128 128 256 256 256 256 256 256 256 512 512 512 512 512 512 512 1024 1024 1024 1024 1024 1024 1024 n log n sqrt n n log n 100n n^2 n^3 n t(n) growth functions 2 0.3010299957 1.4142135624 0.6020599913 200 4 8 4 0.6020599913 2 2.4082399653 400 16 64 8 0.903089987 2.8284271247 7.2247198959 800 64 512 16 1.2041199827 4 19.2659197225 1600 256 4096 32 1.5051499783 5.6568542495 48.1647993062 3200 1024 32768 …

Ko'proq o'qimoqchimisiz?

Barcha 29 sahifani Telegram orqali bepul yuklab oling.

To'liq faylni yuklab olish

"introduction to algorithms" haqida

algorithms and data structures algorithms and data structures * september 10, 2001 * administration people simonas šaltenis anders b. christensen daniel povlsen home page http://www.cs.auc.dk/~simas/ad01 check the homepage frequently! course book “ introduction to algorithms”, 2.ed cormen et al. lectures, fib 15, a, 8:15-10:00, mondays and thursdays * september 10, 2001 * administration (2) exercises: every week after the lecture exam: se course, written troubles simonas šaltenis e1-215 simas@cs.auc.dk september 10, 2001 * syllabus introduction (1) correctness, analysis of algorithms (2,3,4) sorting (1,6,7) elementary data structures, adts (10) searching, advanced data structures (11,12,13,18) dynamic programming (15) graph algorithms (22,23,24) computational geometry (33) np-completeness ...

Bu fayl PPT formatida 29 sahifadan iborat (523,0 KB). "introduction to algorithms"ni yuklab olish uchun chap tomondagi Telegram tugmasini bosing.

Teglar: introduction to algorithms PPT 29 sahifa Bepul yuklash Telegram