Algorithmics (ºtºâªk) 2018

Lecturer: ¦¿®¶·ç
Teaching Assistants (TAs): ·¨©y©÷ ­S®¶­Û Áª÷¨k °ª°·»«
Time: ¶g¤T 14:00~16:50
Place: E6-A306 and E6-A303 (Audio and Slides)

TA Class: ¶g¤T 13:00~13:50 (E6-A306)
Scoring¡G
TextBook:
Reference Books:
Programming:
  • ¦w¸Ë½Òµ{¬ÛÃö³nÅé¤Î­ì©lµ{¦¡½X: Jeep6 (for JAVA platform on Windows)(¤U¸ü: Jeep6Setup&SourceCode.exe)
  • 1 ¦w¸ËJava Development Kit (JDK): http://java.sun.com/javase/downloads/index.jsp
    2 ¦w¸ËMinGW C++ Compiler (G++): http://prdownloads.sf.net/mingw/MinGW-3.0.0-1.exe?download
    3 ¦w¸Ë³Ì·sPython 3 Interpreter: https://www.anaconda.com/
    4 ¦w¸ËJeep6(Java editor for Chineseprogrammers v6.0) (¤U¸ü: Jeep6Setup&SourceCode.exe)
    5 ³]©w¸ô®|°Ñ¼Æ: ª`·N¡A³o·|¦]¬°§A¦w¸Ë¤W¦C¤£¦P³nÅ骺¤£¦Pª©¥»¦Ó¤£¦P¡A¤]·|¦]¬°§A¦w¸Ëªº§@·~¨t²Îª©¥»¤£¦P¦Ó¤£¦P¡C¥H¤U¬°°w¹ïWin7 64¦ì¤¸§@·~¨t²Î¡A¦w¸Ë¥Ñ¥»ºô¯¸°Ï°ì¤U¸ü³nÅ骺³]©w:

    ¿ï¾Ü [±±¨î¥x][¨t²Î¤Î¦w¥þ©Ê][¨t²Î][¶i¶¥¨t²Î³]©w][Àô¹ÒÅܼÆ]¡A§ä¥X[path]Åܼƨëö¤U[½s¿è]¡A¥H¦b¨äÅܼƭȥ½ºÝ¥[¤J


    ;JDK¦w¸Ë¥Ø¿ý\bin;MinGW¦w¸Ë¥Ø¿ý\ bin;Python¦w¸Ë¥Ø¿ý;Jeep6¦w¸Ë¥Ø¿ý 
    (¨Ò¦p:   ;C:\Program Files\Java\jdk-9.0.4\bin;C:\MinGW\bin;C:\Users\yourname\Anaconda3;C:\Jeep6)


    6 ¤U¸ü½d¨Òµ{¦¡(Sample.c)(Sample.cpp)(Sample.java)(Sample.py)Àx ¦s©óC:\Jeep6¥Ø¿ý¤¤¡A«ö¤U®à­±Jeep6¹Ï¥Ü°õ¦æJeep6³nÅé¡A¨Ã¨Ï¥Î [¶}ÂÂÀÉ]¿ï¶µ¸ü¤J½d¨Òµ{¦¡¶i¦æ[½sĶ][°õ¦æ]¡C

  • ACM°ê»Ú¤j¾Ç¥Íµ{¦¡³]­p ÄvÁÉ (ACM International Collegiate Programming Contest, ACM-ICPC) (ACM-ICPC&EPC.ppt)
  • Syllabus:  
    A. µ¹©w¤@­Ó0/1­I¥]°ÝÃD¦p¤U¡F­I¥]²ü­«W=12¡A¥B4­Óª««~¨ä­«¶q¦U¬°6¡B4¡B5¡B3¡A¨ä»ù­È¦U¬°20¡B30¡B40¡B10¡A»¡©úÂǥѰʺA³W¹ººtºâªk¸Ñ¨M¦¹0/1­I¥]°ÝÃDªº¹Lµ{¡C
    B. ¥H¤l¶°¦X¥[Á`°ÊºA³W¹ººtºâªk¸Ñ¨M¥H¤U¤l¶°¦X¥[Á`°ÝÃD: µ¹©w¾ã¼Æ¶°¦XS={1, 2, 4, 7}¤Î¾ã¼Æc=10¡C
    C. ­×§ï¤l¶°¦X¥[Á`°ÊºA³W¹ººtºâªk¨Ï¨ä¶Ç¦^¥[Á`­È¬°cªº¤l¶°¦X­Y¦¹¤l¶°¦X¦s¦b¡F§_«h¶Ç¦^ªÅ¶°¦X¡C
    D. ¥OS = (-2, 1, -3, 4, -1, 2, 1, -5, 4), ¨Ï¥Î
    °ÊºA³W¹ººtºâªk¨D¥X³Ì¤j³sÄò«DªÅ¤l§Ç¦C©M¡C
    E. ³]­p
    ³Ì¤j³sÄò¥iªÅ¤l§Ç¦C©M°ÊºA³W¹ººtºâªk¡C
    F. »¡©úX=ABCBA»PY=BDCA¨â­Ó¦r¦êÂǥѰʺA³W¹ººtºâªk¨D¥X³Ìªø¦@¦P¤l§Ç¦Cªº¹Lµ{¡C
    G. ÂǥѰʺA³W¹ººtºâªk¨Ó´À¤@¯x°}Ãì(¨äºû«×§Ç¦C¬° <5, 20, 10, 12> )¥[¤W¬A¸¹¨Ó³Ì¨Î¤Æ¯x°}¬Û­¼¦¸¼Æ¡C
    H. µ¹©wp1=0.2, p2=0.15, p3=0.3; q0=0.1, q1=0.08, q2=0.07, q3=0.1,¥H³Ì¨Î¤G¤¸·j´M¾ð°ÊºA³W¹ººtºâªk«Øºc¥X³Ì¨Î¤G¤¸·j´M¾ð¡C
    I. µe¹Ï»¡©ú§Q¥Î§Q¥ÎFloyd-Warshallºtºâªk¨D¥H¤U¹Ï(graph)¥þ¹ï³Ìµu¸ô®|(all-pair shortest path)¶ZÂ÷(¦¨¥»)(¦¹¹Ïªº±Ò©l¶ZÂ÷¯x°}¦p¤U¡A¥H¸g¹Lªº¤¤¶¡¸`ÂI¬°s, a, b, c, dªº¶¶§Ç¼g¥X¶ZÂ÷¯x°}ªº§ïÅܹLµ{¡C)
    (d->bªº¥[Åv¦b¹Ï§Î»Pªí®æ¤¤»~´Ó¬°¤£¤@­Pªº­È¡A¦P¾Ç¥i¥H±N¤§§ï¬°5©Î6Åý¹Ï§Î»Pªí®æ¤@­P«á¸ÑÃD³£ºâµª¹ï¡C)

     
    J. ¨D¥X¥H¤Uµ¹©w¹Ï(graph)ªºFloyd-Warshallºtºâªkªº±Ò©l«e¸`ÂI¯x°}(°}¦C)¡A¨Ã¨D¥X³Ì«áªº«e¸`ÂI¯x°}(°}¦C)¡C
    A graph
    L. °w¹ï¥H¤Uªºµ¹©w¹Ï¡A¦C¥XBellman-Ford³Ìµu¸ô®|ºtºâ ªk°õ¦æ¹Lµ{¡A »¡©úBellman -Ford³Ìµu¸ô®|ºtºâªk¦p¦óÀˬd¥X¤@µ¹©w¹Ï¨ã¦³­t´`Àô(negative-weight cycle)¡C


    Links¡G

    Back to My Home