附件1

Transcription

1 装 山 东 大 学 青 年 学 者 未 来 计 划 申 报 书 订 所 在 单 位 计 算 机 科 学 与 技 术 学 院 申 请 人 姜 海 涛 填 表 日 期 206 年 3 月 日 线 山 东 大 学 人 事 部 制 - -

2 填 写 说 明. 申 报 书 内 容 要 逐 项 填 写, 实 际 内 容 不 发 生 的, 请 注 明 无 有 字 数 限 制 的, 应 严 格 控 制 在 限 定 字 数 以 内 2. 申 请 人 应 客 观 如 实 填 写 申 报 材 料, 所 在 单 位 应 严 格 把 关, 对 申 报 材 料 进 行 认 真 审 查 3. 研 究 领 域 请 填 写 所 在 研 究 方 向 的 关 键 词, 至 多 填 写 三 项 4. 项 目 经 费 来 源 请 填 写 项 目 的 具 体 性 质, 如 美 国 NIH 基 金 项 目 863 项 目 子 课 题 国 家 社 会 科 学 基 金 项 目 等 5. 表 中 涉 及 时 间 的, 一 律 按 格 式 填 写 6. 本 申 报 书 一 式 一 份, 用 A4 双 面 纸 打 印, 按 左 侧 装 订 线 装 订 - 2 -

3 一 申 请 人 基 本 情 况 姓 名 姜 海 涛 性 别 男 出 生 年 月 专 业 技 术 最 高 学 历 博 士 研 究 生 最 高 学 位 博 士 副 教 授 职 务 所 在 二 级 计 算 机 软 件 与 理 论 研 究 领 域 算 法 计 算 生 物 学 学 科 起 止 年 月 学 位 毕 业 院 校 专 业 教 育 经 历 ( 从 大 学 起 填 写 ) 学 士 博 士 山 东 大 学 计 算 机 科 学 与 技 术 学 院 山 东 大 学 计 算 机 科 学 与 技 术 学 院 计 算 机 科 学 与 技 术 计 算 机 软 件 与 理 论 示 例 学 士 山 东 大 学 信 息 科 学 与 工 程 学 院 集 成 电 路 设 计 与 集 成 系 统 起 止 年 月 就 职 单 位 从 事 工 作 及 职 位 工 作 经 历 ( 含 海 外 研 修 至 今 美 国 蒙 大 拿 州 立 大 学 计 算 机 科 学 系 山 东 大 学 计 算 机 科 学 与 技 术 学 院 联 合 培 养 博 士 生 讲 师 / 副 教 授 情 况 ) 国 际 国 内 学 术 组 织 兼 职 在 国 际 国 内 学 术 会 议 做 重 要 报 告 等 情 况 : 中 国 计 算 机 学 会 会 员 其 它 所 在 学 术 团 队 情 况 现 在 山 东 大 学 计 算 机 科 学 与 技 术 学 院 智 能 算 法 与 软 件 学 科 组 学 科 组 带 头 人 是 算 法 领 域 内 著 名 学 者 朱 大 铭 教 授 及 泰 山 学 者 郭 炅 教 授, 另 有 教 授 人, 副 教 授 4 人 学 科 组 成 员 近 五 年 承 担 国 家 自 然 科 学 基 金 项 目 4 项, 省 部 级 项 目 5 项, 人 才 类 项 目 项 ; 发 表 在 CCF 推 荐 期 刊 / 会 议 论 文 40 余 篇 是 否 入 选 国 家 省 部 级 人 才 支 持 计 划 : 是 否 人 才 支 持 计 划 项 目 名 称 : 入 选 时 间 : 年 月 - 3 -

4 二 教 学 及 人 才 培 养 情 况 ( 近 五 年 ) 教 育 教 学 情 况 简 介 ( 限 500 字, 包 括 主 要 授 课 课 程 授 课 对 象 以 及 指 导 研 究 生 等 情 况 ) 主 要 承 担 三 年 级 本 科 生 的 算 法 设 计 与 分 析 运 筹 学 两 门 主 干 课 程 目 前 指 导 研 究 生 人, 协 助 指 导 博 士 生 人 ( 已 毕 业 ), 研 究 生 2 人 ( 即 将 毕 业 ) 三 主 要 研 究 成 绩 及 代 表 性 成 果 ( 填 写 近 五 年 情 况 ) ( 一 ) 主 要 学 术 成 绩 创 新 点 及 其 科 学 意 义 ( 字 数 限 本 页 ) 自 攻 读 博 士 学 位 的 近 十 年 来, 一 直 坚 持 从 事 基 因 组 分 析 中 组 合 问 题 的 算 法 与 计 算 复 杂 性 研 究 工 作, 相 关 研 究 工 作 受 到 国 内 外 同 行 的 关 注 已 积 累 的 相 关 代 表 性 成 果 为 : () 设 计 了 无 向 基 因 组 二 次 切 割 并 连 接 排 序 问 题 的.5- 近 似 算 法, 第 一 次 提 出 亚 核 心 化 的 思 想, 并 证 明 该 类 题 存 在 线 性 亚 核, 设 计 出 第 一 个 参 数 化 求 解 算 法 成 果 发 表 在 生 物 信 息 学 领 域 的 顶 级 刊 物 Bioinformatics (2) 发 现 一 类 特 殊 排 列 短 块 移 动 排 序 是 多 项 式 时 间 可 求 得 最 优 解 的, 成 果 发 表 在 Theoretical Computer Science ; 在 此 基 础 上, 设 计 了 基 因 组 短 块 移 动 排 序 问 题 的 4/- 近 似 算 法, 成 果 发 表 在 中 国 科 学 信 息 科 学 ; 最 近, 改 进 了 一 般 排 列 短 块 移 动 排 序 问 题 的 最 优 解 的 下 界, 并 据 此 将 近 似 性 能 比 改 进 至 5/4, 成 果 发 表 在 著 名 国 际 会 议 ISAAC204 上 (3) 设 计 了 无 重 复 基 因 组 片 段 填 充 问 题 的 多 项 式 时 间 精 确 算 法, 并 证 明 了 有 重 复 基 因 组 片 段 填 充 问 题 是 NP-Hard 的, 成 果 发 表 在 生 物 信 息 学 领 域 的 顶 级 刊 物 IEEE/ACM Transactions on Computational Biology and Bioinformatics ; 设 计 了 有 重 复 基 因 组 单 面 片 段 填 充 问 题 的 5/4- 近 似 算 法, 成 果 的 简 化 版 本 发 表 在 著 名 国 际 会 议 COCOON203 上, 完 整 版 本 发 表 在 IEEE/ACM Transactions on Computational Biology and Bioinformatics ;205 年 又 将 单 面 片 段 填 充 问 题 的 近 似 算 法 改 进 至 6/5, 结 果 发 表 在 著 名 国 际 会 议 COCOON205 上 ; 参 与 设 计 了 有 重 复 基 因 组 单 面 片 段 填 充 问 题 的 3/2- 近 似 算 法, 该 成 果 发 表 在 计 算 机 算 法 领 域 的 顶 级 刊 物 Algorithmica (4) 设 计 基 因 组 最 长 带 恢 复 补 问 题 的 近 似 性 能 比 为 3 的 多 项 式 算 法, 该 结 果 发 表 在 理 论 计 算 机 领 域 的 主 流 刊 物 Journal of Combinatorial Optimization ; 最 近, 从 参 数 化 计 算 的 角 度, 证 明 最 长 带 恢 复 补 问 题 存 在 大 小 为 78K 的 核, 该 成 果 发 表 在 计 算 机 理 论 领 域 的 顶 级 刊 物 Journal of Computer and System Sciences (5) 对 于 用 PQ- 树 存 储 的 基 因 组 的 比 较 问 题, 第 一 次 正 面 两 棵 PQ- 树 版 本 及 一 个 PQ- 树 的 版 本 都 是 NP- 完 全 的, 该 成 果 目 前 已 投 稿 到 A 类 杂 志 Information and Computation 近 两 年 设 计 求 解 问 题 的 新 算 法, 改 进 算 法 的 性 能 指 标, 一 直 是 算 法 研 究 领 域 追 求 的 目 标 对 NP- 困 难 问 题 算 法 的 每 一 小 步 改 进, 都 意 味 着 对 问 题 更 深 入 的 探 索, 发 现 了 更 朴 素 的 内 在 规 律 - 4 -

5 ( 二 ) 发 表 ( 出 版 ) 论 著 情 况 ( 近 五 年, 共 出 版 著 作 0 册, 发 表 论 文 22 篇, 其 中 以 第 一 作 者 或 通 讯 作 者 发 表 的 论 文 被 SCI 收 录 0 篇 EI 收 录 6 篇 SSCI 收 录 篇 CSSCI 收 录 篇 以 下 限 填 0 项 ) 序 号 时 间 206 论 著 名 称 A.5-Approximation Algorithm for Two-Sided Scaffold Filling. 刊 物 名 称 / 出 版 单 位 Algorithmica 3 位 次 收 录 情 况 影 响 因 子.0 他 引 次 数 Isomorphism and similarity for 2-generation pedigrees BMC Bioinformatics SCI(C) A (.408+ε)-Approximation Algorithm for Sorting Unsigned Theoretical Computer Genomes by Reciprocal Science Translocations A linear kernel for the complementary maximal strip Journal of Computer and System Sciences. recovery problem An 5/4-Approximation Algorithm for Sorting Permutations by Short ISAAC 204 EI(C) Block Moves. 203 An Improved Approximation IEEE/ACM Trans. 6 Algorithm for Scaffold Filling to Maximize the Common Comput. Biology Bioinform. 2(*) SCI(C).6 Adjacencies Scaffold Filling under the Breakpoint and Related IEEE/ACM Trans. Comput. Biology SCI(C).6 Distances. Bioinform A (+ε)-approximation algorithm Theor. Comput. Sci. 0.4 for sorting by short block-moves Algorithms for sorting unsigned Bioinformatics 5.0 linear genomes by the DCJ operations A 4/-approximation algorithm 中 国 科 学 0.3 for sorting by short block-moves. 信 息 科 学 - 5 -

6 ( 三 ) 主 持 参 与 项 目 情 况 ( 近 五 年, 共 主 持 4 项 项 目, 其 中 省 部 级 及 以 上 项 目 4 项 以 下 限 填 0 项 ) 序 号 起 止 时 间 项 目 名 称 实 到 经 费 ( 万 元 ) 位 次 经 费 来 源 基 因 组 比 较 中 三 个 组 合 问 题 的 算 24 国 家 自 然 科 学 法 研 究 青 年 基 金 基 因 组 断 点 距 离 比 较 算 法 与 复 杂 5 山 东 省 自 然 科 性 学 青 年 基 金 基 因 组 重 组 比 较 算 法 研 究 5 中 国 博 士 后 科 学 基 金 特 别 资 助 基 因 组 比 较 问 题 的 算 法 和 复 杂 性 3 中 国 博 士 后 科 研 究 学 基 金 面 上 资 助 ( 四 ) 省 部 级 以 上 奖 励 及 授 权 专 利 情 况 ( 近 五 年, 共 获 得 项 专 利, 其 中 发 明 专 利 项, 实 用 新 型 专 利 项 ; 获 得 省 部 级 及 以 上 奖 励 项 以 下 限 填 5 项 ) 序 号 获 奖 项 目 名 称 ( 或 专 利 名 称 ) 获 奖 名 称 等 级 及 受 奖 单 位 ( 或 专 利 授 权 国 专 利 号 ) 获 奖 时 间 ( 或 公 告 日 ) 位 次 - 6 -

7 四 可 行 性 及 预 期 目 标 工 作 计 划 : 入 选 本 计 划 后 工 作 设 想 研 究 工 作 主 要 内 容, 工 作 目 标, 预 期 贡 献 及 现 有 基 础 团 队 情 况 等 ( 本 栏 限 页 ) 算 法 研 究 都 是 针 对 一 个 个 具 体 的 小 问 题 而 进 行 的 计 划 在 今 后 的 几 年 时 间 里, 综 合 应 用 随 机 算 法 线 性 规 划 局 部 搜 素 半 正 定 规 划 等 最 新 的 和 传 统 的 算 法 设 计 技 术, 针 对 计 算 生 物 领 域 的 几 个 经 典 问 题 和 公 开 未 解 问 题, 改 进 算 法 的 近 似 性 能 比 参 数 时 间 复 杂 度, 证 明 公 开 未 解 问 题 的 计 算 复 杂 性 具 体 的 研 究 问 题 如 下 : ( 一 ) 无 向 基 因 组 全 局 排 序 问 题 基 因 组 全 局 排 序 问 题 基 于 不 同 的 全 局 性 操 作, 包 含 翻 转 排 序, 移 位 排 序, 二 次 切 割 并 连 接 排 序 等, 近 20 来, 有 不 下 200 篇 文 章 对 这 些 问 题 进 行 了 研 究, 取 得 了 若 干 显 著 性 成 果 但 是, 无 向 基 因 组 的 全 局 性 排 序 研 究 进 入 了 瓶 颈, 近 似 算 法 最 好 能 达 到.375 的 性 能 比, 改 进 的 关 键 在 于 对 其 断 点 图 进 行 更 好 的 圈 分 解, 然 而 目 前 的 圈 分 解 策 略 在 细 节 上 已 极 尽 完 美 因 此, 欲 要 突 破.375 的 瓶 颈, 必 须 从 更 高 的 角 度 俯 视 这 个 问 题 降 低 多 项 式 时 间 的 要 求, 设 计 参 数 时 间 (f(k)poly(n),k 为 参 数,f 为 可 计 算 函 数 ) 的 近 似 算 法, 是 当 前 很 受 关 注 的 研 究 点 ( 二 ) 基 因 组 局 部 排 序 问 题 基 因 组 局 部 排 序 操 作 主 要 有 短 块 移 动 和 短 翻 转 两 种, 这 两 个 问 题 已 经 公 开 了 5 年, 其 复 杂 性 至 今 未 知 学 者 们 对 这 两 个 问 题 做 了 一 系 列 求 解 算 法, 目 前 最 好 的 近 似 性 能 比 分 别 是 5/4( 申 请 人 的 成 果 ) 和 2 无 论 是 证 明 这 两 个 问 题 是 NP- 困 难 的, 还 是 给 出 更 好 的 求 解 算 法, 都 需 要 建 立 更 好 的 求 解 模 型, 并 发 现 问 题 本 身 的 潜 在 规 律 短 块 移 动 排 序 问 题 目 前 已 发 现 关 联 伞 结 构 排 列 的 求 解 算 法, 基 于 此 有 望 改 进 近 似 性 能 比 至 6/5 发 现 了 双 递 增 排 列 的 关 键 性 质, 据 此 有 望 证 明 该 问 题 是 NP- 困 难 的 短 翻 转 排 序 问 题 需 要 建 立 排 列 图 作 为 新 的 求 解 模 型 一 旦 这 两 个 问 题 被 证 明 是 NP- 困 难 的, 必 然 能 吸 引 更 多 的 研 究 者 进 来 从 事 更 深 入 的 研 究 ( 三 ) 基 于 插 入 / 删 除 的 基 因 组 比 较 问 题 为 充 分 利 用 新 一 代 基 因 测 序 的 数 据 成 果, 人 们 建 立 了 以 基 因 组 相 似 性 的 量 化 距 离 为 优 化 目 标 的 基 因 组 比 较 问 题 模 型, 采 用 组 合 优 化 方 法 对 数 据 进 行 修 正 和 分 析, 片 段 填 充 问 题 和 带 恢 复 问 题 就 是 典 型 代 表 学 者 们 对 这 些 问 题 进 行 了 广 泛 的 研 究, 取 得 了 一 些 成 果, 但 性 能 不 够 理 想 要 大 幅 度 改 进 当 前 算 法 的 性 能, 必 须 更 先 进 的 算 法 设 计 技 术, 最 近, 申 请 人 提 出 了 非 直 接 局 部 搜 索 的 算 法 设 计 方 法, 并 将 之 应 用 到 片 段 填 充 问 题, 改 进 了 近 似 性 能 比, 此 方 法 已 初 见 成 效 ; 将 其 应 用 到 最 长 带 恢 复 问 题, 也 能 改 进 近 似 性 能 两 个 成 功 实 例 证 明 该 方 法 确 实 有 其 优 势 和 推 广 性, 必 将 引 起 更 多 的 关 注 和 应 用 预 期 目 标 : () 无 向 基 因 组 DCJ 排 序 问 题 的 多 项 式 近 似 算 法 的 近 似 比 改 进 至.375, 参 数 近 似 算 法 的 近 似 性 能 比 改 进 至 4/3 ( 2) 证 明 短 块 移 动 排 序 是 NP- 难 的, 并 设 计 6/5 近 似 算 法 (3) 将 最 长 带 恢 复 原 始 问 题 和 补 问 题 的 近 似 比 分 别 改 进 至 3 和 2 累 计 发 表 CCF 推 荐 B 类 期 刊 / 会 议 论 文 5 篇 现 有 基 础 : 针 对 上 述 研 究 问 题 已 发 表 9 篇 相 关 论 文, 积 累 的 丰 富 的 研 究 成 果 团 队 情 况 : 所 在 课 题 组 中 的 朱 大 铭 教 授 是 该 领 域 国 内 外 的 知 名 专 家, 也 是 申 请 人 的 博 士 导 师, 一 直 从 事 相 关 的 研 究 工 作, 有 丰 富 的 经 验 和 深 厚 的 研 究 功 底, 能 给 申 请 人 提 供 很 好 的 发 展 平 台 并 从 学 术 上 给 予 提 点 帮 助 课 题 组 中 的 泰 山 学 者 郭 炅 教 授, 是 新 引 进 的 算 法 领 域 的 国 外 著 名 专 家, 申 请 人 能 学 习 到 很 多 知 识, 而 且 学 术 上 可 以 互 相 交 流, 事 半 功 倍 团 队 内 其 他 老 师 也 都 是 从 事 算 法 研 究 很 多 年, 大 家 可 针 对 很 多 学 术 问 题 讨 论, 群 策 群 力, 共 同 进 步 - 7 -

8 五 培 养 期 内 所 需 研 究 经 费 预 算 序 号 科 目 名 称 预 算 经 费 ( 万 元 ) 备 注 ( 计 算 依 据 及 说 明 ) 设 备 购 置 费 5 小 型 仪 器 等 2 材 料 费 2 试 验 材 料 耗 材 办 公 费 3 测 试 化 验 加 工 费 0 检 验 测 试 化 验 加 工 费 4 差 旅 费 20 调 研 旅 费 交 通 费 参 加 学 术 会 议 费 5 会 议 费 3 项 目 负 责 人 组 织 召 开 的 研 讨 会 验 收 会 等 ( 报 销 时 须 附 会 议 通 知 ) 6 国 际 合 作 与 交 流 费 5 短 期 出 国 及 外 请 专 家 在 国 内 费 用 7 出 版 / 文 献 / 信 息 传 播 / 知 识 产 权 事 务 费 4 资 料 出 版 复 印 邮 电 软 件 专 利 等 ( 个 人 电 话 费 除 外 ) 8 劳 务 费 0 助 研 津 贴 计 算 分 析 费 数 据 采 集 劳 务 费 9 专 家 咨 询 费 咨 询 鉴 定 评 审 费 等 ( 校 外 专 家, 需 提 供 身 份 证 号 码 ) 0 其 他 支 出 0 以 上 0 项 以 外 的 支 出, 需 详 细 列 明 支 出 内 容 年 度 经 费 划 拨 情 况 合 计 50 第 一 年 第 二 年 第 三 年 第 四 年 第 五 年 说 明 : 本 计 划 资 助 经 费 按 山 东 大 学 基 本 科 研 业 务 费 有 关 规 定 执 行, 预 算 一 经 批 复, 需 严 格 执 行 不 得 随 意 变 更 ; 当 年 拨 付 经 费 需 当 年 执 行 完 成 六 申 请 人 承 诺 本 人 郑 重 承 诺, 以 上 所 填 内 容 完 全 属 实, 并 严 格 遵 守 资 助 经 费 相 关 管 理 规 定, 切 实 保 证 研 究 工 作 时 间, 认 真 开 展 研 究 工 作 申 请 人 签 字 : 年 月 日 - 8 -

9 七 院 级 学 术 委 员 会 意 见 ( 一 ) 推 荐 意 见 ( 对 申 请 人 的 综 合 评 价 ) 应 到 人 数 实 到 人 数 同 意 票 不 同 意 票 弃 权 主 任 签 字 : 年 月 日 ( 二 ) 申 请 人 入 选 未 来 计 划, 单 位 拟 采 取 的 保 障 措 施 ( 资 金 投 入 工 作 条 件 等 ) 资 助 申 请 人 参 加 高 水 平 国 际 会 议 每 年 至 少 一 次, 邀 请 国 外 高 水 平 专 家 与 申 请 人 进 行 学 术 交 流 当 申 请 人 科 研 经 费 不 足 时, 学 院 酌 情 给 予 支 持 适 当 降 低 申 请 人 的 课 堂 教 学 任 务, 保 证 申 请 人 的 研 究 生 和 科 研 助 手 人 数 单 位 盖 章 : 单 位 负 责 人 签 字 : 年 月 日 八 学 校 组 织 专 家 评 审 意 见 参 与 评 审 专 家 人 数 同 意 票 不 同 意 票 弃 权 经 综 合 评 价, 同 意 ( 不 同 意 ) 确 定 同 志 为 山 东 大 学 青 年 学 者 未 来 计 划 拟 培 养 人 选, 并 给 予 万 元 科 研 支 持 经 费 九 学 校 意 见 组 长 签 字 : 年 月 日 经 公 示 无 异 议, 同 意 同 志 入 选 年 度 山 东 大 学 青 年 学 者 未 来 计 划 盖 章 : 签 字 : 年 月 日 - 9 -