Bai01 - Tong Quan

  • Published on
    09-Nov-2015

  • View
    217

  • Download
    3

Embed Size (px)

Transcript

<ul><li><p>27/01/2015</p><p>1</p><p>Phn tch v Thit kTHUT TON</p><p>H i Dng</p><p>duonghd@mta.edu.vn</p><p>Web: fit.mta.edu.vn/~duonghd</p><p>Bi 1 - Gii thiuPHN TCH V THIT K THU TON</p></li><li><p>27/01/2015</p><p>2</p><p>NI DUNG</p><p>I. Gii thiu1. Mc ch</p><p>2. Ni dung mn hc</p><p>3. Hnh thc Kim tra, Thi v nh gi kt qu</p><p>4. Ti liu tham kho</p><p>II. Thut ton1. nh ngha</p><p>2. Tnh cht</p><p>3. Biu din</p><p>NI DUNG</p><p>III. phc tp thut ton1. Gii tiu</p><p>2. Hng tip cn</p><p>3. Phn lp phc tp</p><p>IV. Bi tp</p></li><li><p>27/01/2015</p><p>3</p><p>I. Gii thiu</p><p>1. MC CH Cung cp kin thc v vic nh gi thut ton</p><p> L thuyt Thc nghim</p><p> Kin thc, k thut v gii quyt bi ton trn my tnh: Trc tip Gin tip</p><p> Thit k thut gii Chia tr Quy hoch ng Tm kim cc b </p><p>I. Gii thiu</p><p>2. NI DUNG</p><p> Tng quan v thut ton v phc tp ca thut ton</p><p> nh gi thut ton: L thuyt (ton hc s cp)</p><p> Thc nghim</p><p> quy v phng php nh gi</p><p> nh gi mt s thut ton thng dng Thut ton tm kim</p><p> Thut ton sp xp</p></li><li><p>27/01/2015</p><p>4</p><p>I. Gii thiu</p><p>2. NI DUNG</p><p> Cc phng php gii quyt bi ton trn my tnh Trc tip</p><p> Gin tip</p><p> K thut thit k thut ton Chia tr</p><p> Gii thut tham lam</p><p> Quy hoch ng</p><p> Tm kim cc b</p><p>I. Gii thiu</p><p>3. HNH THC KIM TRA</p><p> 10% Chuyn cn</p><p> 20% Thng xuyn (bi tp, bi kim tra)</p><p> 70% Thi cui k (vn p): Sinh vin thc hin 1 bi tp ln vi yucu: Ci t thut ton cho bi ton t ra, </p><p> Chy vi d liu pht sinh ngu nhin, m s php gn v so snh, v th, tnh phng sai, lch chun -&gt; c lng phc tp ca thut ton</p><p> Tnh ton bng l thuyt v so snh vi thc nghim.</p><p> Vit bo co, vn p tr li cc cu hi t ra.</p></li><li><p>27/01/2015</p><p>5</p><p>I. Gii thiu</p><p>4. TI LIU THAM KHO</p><p> Slide bi ging.</p><p> Bi ging Thit k v nh gi Thut ton, Trn Xun Sinh, NXB, HQG, 2010.</p><p> Cm nang thut ton, Robert Sedgewich - Trn an Th dch (ti bnln 2), NXB KHKT, 2006.</p><p> Cu trc d liu v gii thut, Trn Xun Li, NXB H Quc Gia, 2006.</p><p> Gii mt bi ton trn my tnh nh th no (3 tp), Hong Kim, NXB Gio dc, 2005.</p><p>I. Gii thiu</p><p>4. TI LIU THAM KHO</p><p> Gii thut v lp trnh (bi ging chuyn ), L Minh Hong, HSP, 2002.</p><p> Computer Algorithms Introduction to Design and Analysis, Addison-Wesley, 1988.</p><p> Algorithms and Complexity, Herbert S. Wilf, University of Pennsylvania, Philadelphia 1999.</p><p> Algorithm Design, Jon Kleinberg, Eva Tardos Pearson, 2006.</p></li><li><p>27/01/2015</p><p>6</p><p>II. Thut ton</p><p>1. NH NGHA</p><p>C nhiu cch pht biu c chp nhn, trong :</p><p>1)</p><p>2)</p><p>II. Thut ton</p><p>2. TNH CHT</p></li><li><p>27/01/2015</p><p>7</p><p>II. Thut ton</p><p>2. TNH CHT</p><p>II. Thut ton</p><p>2. TNH CHT</p></li><li><p>27/01/2015</p><p>8</p><p>II. Thut ton</p><p>2. TNH CHT</p><p>II. Thut ton</p><p>3. BIU DIN THUT TON</p></li><li><p>27/01/2015</p><p>9</p><p>II. Thut ton</p><p>4. THUT GII</p><p>III. phc tp thut ton</p><p>1. GII THIU</p><p> Kch thc ca bi ton n (c th hiu l s phn t cn phi x l ca biton) V d: Sp xp mt danh sch n sinh vin</p><p> Tm phn t X trong mt mng c n phn t</p><p> Vi 1 bi ton c th c nhiu thut gii (chng trnh) Chng trnh 1</p><p> Chng trnh 2</p><p> Chng trnh (thut gii) no tt?</p></li><li><p>27/01/2015</p><p>10</p><p>III. phc tp thut ton</p><p>1. GII THIU nh gi phc tp thi gian tnh ton</p><p>(V thi gian cn ph thuc vo mt my tnh c th)</p><p> nh gi theo tng s cc php ton c bn (gn, so snh)</p><p> V vic nh gi ph thuc vo n nn phc tp thut ton c hiunh mt hm ph thuc vo n, f(n)</p><p>III. phc tp thut ton</p><p>2. HNG TIP CN</p><p> nh gi f(n) nh th no?</p></li><li><p>27/01/2015</p><p>11</p><p>III. phc tp thut ton</p><p>2. HNG TIP CN</p><p> Hng tip cn thc nghim</p><p>III. phc tp thut ton</p><p>2. HNG TIP CN</p><p> c lng tim cn(l thuyt):</p><p> ngha:</p><p> nh ngha:</p></li><li><p>27/01/2015</p><p>12</p><p>III. phc tp thut ton</p><p>2. HNG TIP CN</p><p> c lng tim cn(l thuyt): </p><p>III. phc tp thut ton</p><p>2. HNG TIP CN</p><p> c lng tim cn(l thuyt): </p></li><li><p>27/01/2015</p><p>13</p><p>III. phc tp thut ton</p><p>2. HNG TIP CN</p><p> c lng tim cn(l thuyt): </p><p>III. phc tp thut ton</p><p>2. HNG TIP CN</p><p> c lng tim cn(l thuyt): </p></li><li><p>27/01/2015</p><p>14</p><p>III. phc tp thut ton</p><p>2. HNG TIP CN</p><p> c lng tim cn(l thuyt): </p><p>III. phc tp thut ton</p><p>2. HNG TIP CN</p><p> c lng tim cn(l thuyt): </p></li><li><p>27/01/2015</p><p>15</p><p>III. phc tp thut ton</p><p>2. HNG TIP CN</p><p> c lng tim cn(l thuyt): </p><p>III. phc tp thut ton</p><p>3. PHN LP CC HM</p></li><li><p>27/01/2015</p><p>16</p><p>III. phc tp thut ton</p><p>3. PHN LP CC HM</p><p>III. phc tp thut ton</p><p>3. PHN LP CC HM</p></li><li><p>27/01/2015</p><p>17</p><p>III. phc tp thut ton</p><p>4. MT S VN KHC</p><p> S ph thuc/khng ph thuc vo phn b d liu</p><p>III. phc tp thut ton</p><p>4. MT S VN KHC</p><p> Tnh O (ln) da trn quy tc Cng/Nhn</p></li><li><p>27/01/2015</p><p>18</p><p>NI DUNG BI HC</p><p>I. Gii thiu</p><p>II. Thut ton</p><p>III. phc tp thut ton</p><p>IV. Bi tp</p><p>1. Nu nh ngha, tnh cht v cc cch thc biu din thut ton</p><p>2. Cho cc bi ton sau:a) Tnh nghim phng trnh bc 2: ax2+bx+c=0, a0.</p><p>b) Tnh tng bnh phng ca n s t nhin u tin.</p><p>c) Tm s c gi tr x trong dy x1, x2,,xn.</p><p>d) Tm s c gi tr ln nht trong dy x1, x2,,xn.</p><p>Hy tm thut ton gii bi ton trn, m t cc thut ton s dng ngnng t nhin v ch ra cc tnh cht ca thut ton .</p><p>3. M t cc thut ton trong bi 2 dng s khi.</p><p>4. M t cc thut ton trong bi 2 dng gi m.</p></li></ul>