国际信息学奥林匹克竞赛所需的知识和能力

International Information Science Olympiad the necessary knowledge and ability
国际信息学奥林匹克竞赛所需的知识和能力
由于信息奥林匹克竞赛没有统一的大纲,所以教师普遍感到指导起来特别困难。指导信息学奥林匹克竞赛的教师必须了解所涉及的基本知识,不断扩充新的知识。

信息学奥林匹克竞赛的比赛方式是让选手在限定的时间内,用计算机编程的方法解决给定的任务。优胜者将是具有创新能力、对信息科学技术领域的知识有较广博涉猎的选手。

信息学奥林匹克竞赛所需要的知识和能力包括:
1. 数学建模的知识和能力
既要有常用的数学知识,如代数、几何、组合数学(主要包括加法原理、乘法原理、排列与组合、递推关系、鸽巢原理、容斥原理、母函数、Polya原理、拉丁方)、数论(主要包括整除和同余等)等,又要有把实际问题转化为数学模型的能力。
2. 算法分析与设计的知识和能力
建好数学模型后必须用相关的算法来解决数学问题,由于程序的计算时间也是检查的范围,所以必须有优化算法的能力,要掌握时间的复杂性分析的相关知识。
常用的算法设计方法有:
(1) 递归方法。递归是通过调用自身来完成与自身要求相同但规模较小的子问题的求解,可以简化程序,但功能强大,能求解许多问题,如阶乘函数、Fibonacci数、Hanoi塔问题等。所以,应用算法解决实际问题时,递归方法是非常有效的。
(2) 分治策略。分治策略是“分而治之”的意思,即把原问题分解成若干个子问题,用求解子问题来解决原问题,往往比较简单。利用分治策略可以解决涉及二分查找、整数乘法、矩阵乘法等的实际问题。
(3) 动态规划问题。动态规划方法是将要求解的问题逐层分解成一级一级、规模逐步缩小的子问题,知道可以直接求出其解的子问题为止。分解成的所有子问题按层次关系构成一棵树,树根就是原问题。动态规划方法可以解决涉及最短路劲问题、旅行商问题、矩阵链乘问题、最长公共子序列问题、图的任意两点间的最短距离问题、整数规划问题、可靠性问题、同顺序流水作业的任务安排问题、设备更新问题等的实际问题。
常用的算法有:
(1) 排序算法。包括冒泡排序、堆排序、归并排序、递归排序、插入排序、Shell排序、基数排序、下溢排序、插入归并排序等。但要注意,对任意n个数的排序,基于比较的排序算法,理论上已经证明其时间复杂性的下界约为nlog2^n-1.44n+0.5log2^n+1.325。目前最好的排序算法是Ford-Johnson归并插入分类法,其时间复杂性为nlog2^n-4n/3+0.5log2^n+(15+(-1)^m)/12(其中n=2^m),已接近理论下界。任何比它好的算法,一般都是对特殊的问题而言的。
(2) 最短路径有关的算法。包括最短路径问题、旅行商问题、Kruskal算法、Prim算法、Dijkstra算法、遗传算法等。
(3) 矩阵乘积算法。包括Strassen算法、Winograd算法、“三个苏联人算法”。
(4) 数据压缩算法。包括Huffman编码、FFT算法等。
(5) 作业调度算法。包括同顺序的Flowshop问题、带时间期限的Flowshop问题、并行机问题等。
(6) 线性规划和整数规划问题。
(7) 关于树的算法。包括二分树、AVL树、2-3树、2-3-4树等。
(8) 分支界定法。
(9) 并行算法。
(10) 深度优先搜索(DFS)算法和广度优先搜索(BFS)算法。
(11) 网络流算法。包括最大流和最小费用流算法。
(12) Greed算法。
(13) 随机化和近似算法。
3. 数据结构和程序设计的知识和能力
利用算法解决了数学问题后必须用程序来实现,所以必须有相关的数据结构知识(主要包括线性表、串、数组、树、图、指针和链表)和程序设计能力、学生必须掌握一种程序设计语言。

苏打绿 《陪我歌唱》

这几天一直都在听的一首歌,却不知道苏打绿是谁,上了他们的网站看看发现他们的网站蛮有意思的。

[audio:http://box.i-to.org/i_keep_singing.mp3]

以下是这首歌的歌词:

歌曲:陪我歌唱
歌手:苏打绿
专辑:陪我歌唱 演唱会live

夜晚的窗啊轻轻拉着梦摇晃
是你的味道掀起风浪
梦中的你啊时时抓着我分享
把心的空洞填满温光
长长的街道摊在月光下曝晒
陨落的星都装进行囊
切切的思念悬在天涯上呼喊
不睡的鱼载着我出海

像你的心脏无法那么逞强
要装着自己不痛不痒
朝你的方向能够乘着想象
让隐形的我在倾你身旁睡得多香

睡得多香

夜晚的窗啊轻轻拉着梦摇晃
是你的味道掀起风浪
梦中的你啊时时抓着我分享
把心的空洞填满温光
长长的街道摊在月光下曝晒
陨落的星都装进行囊
切切的思念悬在天涯上呼喊
不睡的鱼载着我出海
像你的心脏无法那么逞强
要装着自己不痛不痒
朝你的方向能够乘着想象
让隐形的我在倾你身旁睡得多香

像你的心脏无法那么逞强
要装着自己不痛不痒
朝你的方向能够乘着想象
让隐形的我在倾你身旁睡得多香

让隐形的你在进我梦乡
陪我歌唱

SkyDrive下载 下载2

附苏打绿成员资料,更详细的请访问苏打绿官网(www.sodagreen.com.tw)查阅:

本名 吴青峰
乐队位置:Vocal
星座 处女座
血型 B型
政治大学中文系双修广告辅修企管
喜爱音乐类型:Sodagreen,country,rock,folk,alternative,dassical,electronica
喜欢的颜色 特爱绿
喜欢吃的 常变,现在只想到玉米,讨厌吃鳖
最喜欢最想去的国家or城市 英国、荷兰、冰岛、西藏

本名 谢馨仪
艺名/英文名 壮士/Claire
乐队位置:Bass
星座 牧羊
血型 O型
体重 52~53
国立政治大学科系科技管理研究所(九月入学)
喜爱音乐类型:rock,folk,Metal,Jazz
除了音乐以外的其他喜好 游泳,看电影,去海边或山上踏青
喜欢的颜色 蓝(最爱)、绿、黑、白
最喜欢最想去的国家or城市 旧金山、纽约、威尼斯、罗马、德国

本名 刘家凯
英文名 Kay
乐队位置:Guitar
生日 71.02.05
星座 水瓶
血型 AB型
身高 175
体重 63
政治大学psychology科系大四迈入大五
喜爱音乐类型:rock,Jazz,alternative
除了音乐以外的其他喜好 游泳,看电影,跑步,看书
喜欢的颜色 黑、白、蓝、绿、橘
喜欢吃的 除了巧克力之外
喜欢喝的 可乐
最喜欢最想去的国家or城市 目前是纽约

本名 龙钰祺/阿龙/Zephyr
乐队位置:Keyboard Viola
生日 12/16/1980
星座 射手
血型 O型
身高 176
体重 66
台湾艺术大学音乐研究所
喜爱音乐类型:古典音乐,电子音乐,流行音乐 IDOLMadonna,Schmann
喜欢的颜色 红色
喜欢吃的 巧克力,烤式料理
喜欢喝的 水,红茶,奶茶
最喜欢最想去的国家or城市 美国纽约
若不做音乐也许会做什么 音乐老师

本名 史俊威/小威/Wei
乐队位置:Drums
生日 8/26/1979
星座 处女座
血型 O型
身高 165
体重 72
国立政治大学科系社会系
喜爱音乐类型:all styles except hip-hop and R&B
除了音乐以外的其他喜好 游泳,撞球,线上游戏,电影,漫画
喜欢的颜色 黑色,宝蓝色,血红色
喜欢吃的 除了吃亏之外的都喜欢
喜欢喝的 我是骆驼,连水都很少喝

本名 何景扬
乐队位置:Guitar
星座 牡羊
血型 B型
身高 184
体重 75
政治大学研究所公共行政科系
喜爱音乐类型:rock,blue,jazz,country
喜欢吃的 巧克力巧克力巧克力
喜欢喝的 巧克力奶昔
最喜欢最想去的城市 最喜欢台湾 最想去斯德哥尔摩

抱怨几句

问题一:网通老是将我访问的页面置于他们的iframe中,以此进行他们的广告投放。我向他们进行了投诉,他们给我提供了一个取消的地址……因为我使用的是上网卡,看来每个月都得去取消一次。

问题二:还是网通,干嘛要自作聪明弄个所谓的域名纠错系统呢?我喜欢输错误的不行?还不是为了多展示些广告。

问题三:继续是网通,今天发现从网通无法访问Google App Engine了。

问题四:下图是校内的“删除帐号”功能,如果你有校内的帐号,你可以具体去看看里面的选项说明。最下面说了“你可以在任何时候复活你的帐号……”,明明只是暂时暂停了帐号的展示功能,何必要欺骗我们说此操作是删除帐号。换作这点我也不能相信你不会滥用用户资料。

杂物整理

难得能够有一点时间闲下来,昨天晚上睡觉前整理了下杂乱的书桌,以及柜子里的书,今天早上7点半起床一直弄到十点才搞好,快结束的时候才想到用手机拍下当时的画面。

PS1:大量计算机及相关学科的闲置书籍处理(多数是教科书),按半价折算,运费另计。需要可与我联系,查询我手头是否有所需要的书籍。

PS2:发没发现我有很多眼药水;我的眼睛不好,有人工泪液,有止痒的,有抗疲劳的……就快成卖眼药水的了。