To English Page

教授紹介






浅野 孝夫(1949年1月7日生)
中央大学理工学部情報工学科教授
学位:
工学博士(東北大学大学院電気及通信工学専攻),1977年3月
論文題目 組合せ問題の計算の複雑さに関する研究

学歴:
1972年3月 東北大学工学部通信工学科卒業
1974年3月 東北大学大学院工学研究科修士課程(電気及通信工学専攻)修了
1977年3月 東北大学大学院工学研究科博士課程(電気及通信工学専攻)修了

職歴:
1977年 4月〜1980年10月 東北大学工学部(通信工学科)  助手
1980年10月〜1985年 3月 東京大学工学部(計数工学科)  講師
1985年 4月〜1992年 3月 上智大学理工学部(機械工学科) 助教授
1992年 4月〜        中央大学理工学部(情報工学科) 教授
海外留学:
1989年 3月〜1990年 2月 西ドイツBonn大学離散数学研究所 客員研究員
                           (Humboldt Research Fellowship)
2001年 3月〜2002年 3月 ドイツBonn大学離散数学研究所  客員研究員

受賞歴:
1987年12月 第1回日本IBM科学賞(情報科学部門)
2000年10月 情報処理学会平成12年度山下記念研究賞
2006年 3月 情報処理学会フェロー

所属学会:
電子情報通信学会、情報処理学会、日本オペレーションズ・リサーチ学会、
日本応用数理学会、地理情報システム学会、
ACM (Association of Computing Machinery),
IEEE (Institute of Electrical and Electronics Engineers),
SIAM (Society of Industrial Engineering and Applied Mathematics)

担当科目:
(学部) 離散システム基礎、データ構造とアルゴリズム、ネットワークアルゴリズム、
      アルゴリズム設計、科学技術英語、卒業研究
(大学院博士前期課程) 離散アルゴリズム、近似アルゴリズム、
                情報工学論文研修(第一、第二)
(大学院博士後期課程) 情報工学特殊研究(I, II)、離散アルゴリズム研究

研究テーマ:
情報科学、離散アルゴリズム、組合せ最適化、近似アルゴリズム、
グラフ理論、計算の複雑さ、データ構造、計算幾何学

論文・著書の紹介 (PDF File)

<出版書籍> <翻訳> <主要研究論文> <主要国際会議論文>

出版書籍:
  1. 浅野孝夫:情報数学:組合せと整数およびアルゴリズム解析の数学
  2. 計測自動制御学会 編
    コロナ社 2009年4月出版予定
    
    概要
    コンピューターによる情報の高速処理とインターネットによる高速情報通信に基づく高度
    情報化の社会システムでは,本質的には,離散的な情報のみが扱われている。したがって,
    連続数を扱う従来の伝統的な数学では対応できず,離散数を扱う数学の重要性が認識され
    てきている。すなわち,基盤情報技術の基礎数学として,従来の連続数を扱う解析学以上
    に,離散数を扱う離散数学が重要になってきている。そして現在,大学の情報科学科・情
    報工学科の標準的なカリキュラムでは,離散数学が情報の数学と見なされて,必修科目と
    して指定されている。
    
    本書は,コンピューターを用いて情報の高速高品質処理を行うためのアルゴリズムデザイ
    ンおよびインターネットを介して高速にかつ安全に通信を行うためのネットワークセキュ
    リティの基礎となる情報数学を系統的に解説する。
    
    特に,情報数学の原点で名著であるD.E. Knuthの本 The Art of Computer Programming, 
    Vol.1: Fundamental Algorithms, Addison-Wesley (1968)で取り上げられ,後に, 
    R.L. Graham, D.E. Knuth, and O. Patashnikの本 Concrete Mathematics: A Foundation
     for Computer Science, Addison-Wesley (1989)に集大成されている内容から題材を選ん
    で,情報数学におけるアルゴリズムデザインとその解析の数学を,高度な概念まで段階的
    に学びやすくなるように,具体的な例題を挙げながら系統的に解説する。
    
    具体的には,組合せ理論の基礎概念と基本的証明法,アルゴリズム解析のための和の公式
    と不等式,母関数,漸化式とその解法,セキュリティの基礎となる素数と中国の剰余定理,
    漸近評価のための基礎概念などを取り上げている。
    
    特に心がけた点は以下のとおりである。ウォーミングアップ問題を10章まで配置して,そ
    の章で取り上げる新しい概念がイメージしやすくなるようにしてある。これらの問題は,
    基本的には,少し考えればわかる問題にしてあるので,できるだけ読者が考えて解答を出
    すようにと,解答は,基本的には,裏のページに配置している。さらに,章の中でも例題
    を多く取り上げて,その章の概念が自然に理解できるように努めている。また,その章で
    学んだことを確認するための問題を章末の問題で取り上げ,その解答を巻末に与えている。
    
    最後の3章では,10章までに取り上げた基本的な概念がどのように他の概念に展開され応
    用されていくのかがわかるように,発展内容を取り上げている。具体的には,組合せ理論
    の二項係数や母関数などの概念を利用して,m乗和の公式の導出,オイラーの定数とス
    ターリングの公式の導出,素数定理の証明へのアプローチを取り上げている。
    このように踏み込んだ試みは,離散数学や組合せ理論の日本語の書籍では,これまでほと
    んど見られなかった新鮮なものである。もちろん,証明は,基本的には飛躍のないものに
    しているので,十分時間をかけて考えれば,誰もが理解できるものになっている。さらに,
    読者が現れる定理の美しさやその証明の簡潔さを堪能できるように,表現には工夫を施し
    ている。
    
    したがって,情報や数学の分野に興味をもつ学生や研究者および教育や企業の現場で情報
    と数学関係の仕事に従事している人々には,本書が情報数学を楽しく学べる新鮮なテキス
    トであると信じている。
    
    目次
    
    第1章 和の公式と数学的帰納法
      1.1 本章の目標
      1.2 数学的帰納法
      1.3 和の公式の図による説明
      1.4 等差級数と等比級数
      1.5 発展トピック
          問題
    第2章 鳩の巣原理と背理法
      2.1 本章の目標
      2.2 鳩の巣原理と背理法
          問題
          問題16
    第3章 不等式
     3.1 本章の目標
     3.2 算術平均と幾何平均
     3.3 コーシー-シュワルツの不等式
     3.4 指数関数と対数関数に関する不等式
         問題
    第4章 包除原理
     4.1 本章の目標
     4.2 包除原理
     4.3 オイラー関数
     4.4 包除原理とオイラー関数の適用例と注意
         問題
    第5章 順列と組合せ
     5.1 本章の目標
     5.2 順列と関数の個数
     5.3 組合せの個数
     5.4 二項定理
     5.5 多項係数と多項展開
     5.6 一般化二項係数(組合せの個数の一般化)
     5.7 乱列と全射関数の個数
         問題
    第6章 分割:集合と整数の分割
     6.1 本章の目標
     6.2 集合の分割
     6.3 正整数の分割
     6.4 カタラン数
         問題
    第7章 最大公約数と中国の剰余定理
     7.1 本章の目標
     7.2 最大公約数
     7.3 剰余系と有限群
     7.4 体
     7.5 中国の剰余定理
     7.6 RSA公開キー暗号系
     7.7 素数の個数
     7.8 半順序集合
     7.9 反転公式
         問題
    第8章 母関数
     8.1 本章の目標
     8.2 数列と母関数
     8.3 二項係数と代表的な数列の母関数
     8.4 分割数の母関数
     8.5 発展トピック
         問題
    第9章 漸化式
     9.1 本章の目標
     9.2 漸化式と差分方程式
     9.3 定数係数の線形の差分方程式の解法
     9.4 母関数による定数係数の線形の差分方程式の解法
         問題
    第10章 漸近評価とスターリングの近似式
     10.1 本章の目標
     10.2 漸近評価のための表記法
     10.3 漸近近似評価の誤差:絶対誤差と相対誤差
     10.4 整数の階乗の粗い漸近評価
     10.5 二項係数の近似式
     10.6 発展:階乗と特別な二項係数のより精密な近似不等式
     10.7 発展:ウォリスの公式
     10.8 漸化式の解の漸近評価と分類定理
          問題
    第11章 発展:ベルヌーイ数と整数のm乗和
     11.1 本章の目標
     11.2 ベルヌーイ数と二項係数によるm乗和の公式の導出
     11.3 ベルヌーイ数の指数母関数によるm乗和の公式の導出
    第12章 発展:オイラーの和公式
     12.1 本章の目標
     12.2 有限級数の和の近似公式
     12.3 ベルヌーイ多項式とオイラーの和公式
     12.4 オイラーの和公式の応用1:調和数H_nの漸近近似
     12.5 オイラーの和公式の応用2:n!の漸近近似
    第13章 発展:素数定理へのアプローチ
     13.1 本章の目標
     13.2 記法
     13.3 素数定理の近似版2の証明
     13.4 素数定理の近似版3の証明
     13.5 素数定理の証明へのアプローチ
          問題
    付録 微分積分学の基礎事項
    引用・参考文献
    問題解答
    
    (PDF File)

  3. 杉原, 茨木, 浅野孝夫, 山下(編):アルゴリズム工学 --- 計算困難問題への挑戦, 共立出版, 2001


  4.   (PDF File)

  5. 浅野孝夫, 田村, 加藤, 櫻井, 中野(藤重悟(編)):離散構造とアルゴリズムVII, 近代科学社, 2000

  6. 浅野孝夫, 今井浩: 計算とアルゴリズム, オーム社, 2000 


  7.   (PDF File)

  8. 浅野孝夫: 情報の構造(データ構造とグラフアルゴリズム(上),ネットワークアルゴリズムとデータ構造(下)),日本評論社, 1994


  9.      目次 (PDF File)

  10. 佐々木,今井浩,浅野孝夫,杉原:計算代数と計算幾何(岩波講座応用数学5),岩波書店,1993


  11.   (PDF File)

  12. 浅野孝夫, 今井浩: 計算とアルゴリズム---計算機の科学, オーム社, 1986.

  13. 伊理正夫,腰塚武志,浅野孝夫,他: 計算幾何学と地理情報処理, ビット別冊,共立出版,1986(計算幾何学と地理情報処理(第2版), 共立出版,1993)


  14.      目次 (PDF File)

  15. 伊理正夫, 白川功, 篠田庄司, 浅野孝夫, 他:演習グラフ理論: 基礎と応用, コロナ社, 1983


  16.    目次 (PDF File)


翻訳:
  1. 浅野孝夫,浅野泰仁,小野孝男,平田富夫:組合せ最適化---理論とアルゴリズム(第2版)
    (原著: B. Korte and J. Vygen: Combinatorial Optimization: Theory and Algorithms 4th edition, Springer, 2007)
  2. 組合せ最適化 第2版
    理論とアルゴリズム(シュプリンガージャパン)
    改訂新版
    B. コルテ/J. フィーゲン 著 
    浅野 孝夫/浅野 泰仁/小野 孝男/平田 富夫 訳 
    2009年3月 出版予定
    B5変 716頁
    
    概要
    組合せ最適化とは,対立する複数の制約を満たす有限個の解から最良の解を探し出すこと
    である.その際,扱う数はn個でも,解の個数はn!というように膨大な数の組合せを考慮
    せねばならないので,高速に最良の解を求めるには数理的な理論と手法が不可欠である.
    これが組合せ最適化の主題である.
    
    インターネットに代表される情報ネットワークやロジスティクスに代表される輸送ネット
    ワークでは,高速・高信頼・高性能・低コストを実現するための最適化が必要である.本
    書は,現代社会で生じるネットワーク上の様々な問題を,組合せ理論・グラフ理論を用い
    てモデル化して解決する,最適化の数理的な理論と手法(アルゴリズム)を,系統的に分
    かりやすく解説している.
    
    本書は,ほぼすべての定理に簡潔な証明をつけた,組合せ最適化の集大成といえる教科書
    である.検索しやすい記法一覧,問題一覧,アルゴリズム一覧,見出し語3,000超の索引
    を収載. 
    
    この邦訳第2版は,原著最新版に対応した完全アップデート版であり,次の節が新たに増
    補されるなど,より一層充実した内容となっている.
    3.3節:単体法の実装,
    9.6節:ネットワーク単体法
    16.2節:最大カット問題
    
    
    目次
    第1章はじめに
      列挙
      アルゴリズムの計算時間
      線形の最適化問題
      ソーティング
      演習問題
      参考文献
    第2章グラフ
      基礎的な定義
      木,閉路,カット
      連結性
      オイラーグラフと2 部グラフ
      平面性
      平面的双対性
      演習問題
      参考文献
    第3章線形計画法
      多面体
      単体法
      単体法の実装
      双対性
      凸包と有界多面体
      演習問題
      参考文献
    第4章線形計画アルゴリズム
      頂点と面のサイズ
      連分数
      ガウスの消去法
      楕円体法
      Khachiyan の定理
      分離問題と最適化
      演習問題
      参考文献
    第5章整数計画法
      多面体の整数包
      ユニモジュラー変換
      完全双対整数性
      完全ユニモジュラー行列
      切除平面法
      ラグランジュ緩和
      演習問題
      参考文献
    第6章全点木と有向木
      最小全点木問題
      最小重み有向木
      多面体的表現
      全点木と有向木のパッキング
      演習問題
      参考文献
    第7章最短パス
      1 点からの最短パス
      全点間の最短パス
      最小平均長閉路
      演習問題
      参考文献
    第8章ネットワークフロー
      最大フロー最小カット定理
      Menger の定理
      Edmonds-Karp アルゴリズム
      ブロックフローと藤重(Fujishige)のアルゴリズム
      Goldberg-Tarjan アルゴリズム
      Gomory-Hu 木
      無向グラフの最小カット
      演習問題
      参考文献
    第9章最小費用フロー
      問題の定式化
      最適性基準
      最小平均長閉路解消アルゴリズム
      最短パス反復アルゴリズム
      Orlin のアルゴリズム
      ネットワーク単体法
      時変フロー
      演習問題
      参考文献
    第10章最大マッチング
      2 部グラフのマッチング
      Tutte 行列
      Tutte の定理
      因子臨界的グラフの耳分解
      Edmonds のマッチングアルゴリズム
      演習問題
      参考文献
    第11章重み付きマッチング
      割当問題
      重み付きマッチングアルゴリズムの概略
      重み付きマッチングアルゴリズムの実装
      事後最適性
      マッチング多面体
      演習問題
      参考文献
    第12章b-マッチングとT-ジョイン
      b-マッチング
      最小重みT-ジョイン
      T-ジョインとT-カット
      Padberg-Rao の定理
      演習問題
      参考文献
    第13章マトロイド
      独立性システムとマトロイド
      他のマトロイド公理系
      双対性
      グリーディ法
      マトロイドの共通独立集合
      マトロイド分割
      重み付きマトロイド交差
      演習問題
      参考文献
    第14章マトロイドの一般化
      グリードイド
      ポリマトロイド
      劣モジュラー関数の最小化
      Schrijver のアルゴリズム
      対称劣モジュラー関数
      演習問題
      参考文献
    第15章NP-完全性
      チューリング機械
      Church の提唱
      P とNP 
      Cook の定理
      いくつかの基本的なNP-完全問題
      クラスcoNP 
      NP-困難問題
      演習問題
      参考文献
    第16章近似アルゴリズム
      集合カバー
      最大カット問題
      彩色
      近似スキーム
      最大充足化問題
      PCP 定理
      L-帰着
      演習問題
      参考文献
    第17章ナップサック問題
      小数ナップサック問題と重み付き中央値問題
      擬似多項式時間アルゴリズム
      完全多項式近似スキーム
      演習問題
      参考文献
    第18章ビンパッキング問題
      グリーディ法
      漸近的近似スキーム
      Karmarkar-Karp アルゴリズム
      演習問題
      参考文献
    第19章多品種フローと辺素パス
      多品種フロー
      多品種フローのアルゴリズム
      有向辺素パス問題
      無向辺素パス問題
      演習問題
      参考文献
    第20章ネットワーク設計問題
      シュタイナー木
      Robins-Zelikovsky アルゴリズム
      サバイバルネットワーク設計
      主双対近似アルゴリズム
      Jain のアルゴリズム
      演習問題
      参考文献
    第21章巡回セールスマン問題
      TSP の近似アルゴリズム
      ユークリッドTSP 
      局所探索
      巡回セールスマン多面体
      下界
      分枝限定法
      演習問題
      参考文献
    第22章施設配置問題
      容量制約なし施設配置問題
      線形計画問題の解のラウンディング
      主双対アルゴリズム
      スケール変換とグリーディ増加操作
      開設施設数の制約
      局所探索
      容量制約付き施設配置問題
      普遍的施設配置問題
      演習問題
      参考文献 
    

  3. 浅野孝夫,浅野泰仁,平田,小野:アルゴリズムデザイン,共立出版,2008(原著: J. Kleinberg and E. Tardos: Algorithm Design, Addison-Wesley, 2005)

       (PDF File)

  4. 浅野孝夫,平田,小野,浅野泰仁:組合せ最適化---理論とアルゴリズム, シュプリンガー・フェアラーク東京,2005 (原著: B. Korte and J. Vygen: Combinatorial Optimization: Theory and Algorithms 3rd edition, Springer, 2005)


  5.    目次 (PDF File)

  6. 浅野孝夫:近似アルゴリズム, シュプリンガー・フェアラーク東京,2002 (原著: V.V. Vazirani, Approximation Algorithms, Springer, 2001)


  7.    目次 (PDF File)

  8. 浅野孝夫:アルゴリズムと複雑さ(第4章データ構造), 丸善,1994, pp.305--346 (原著: K. Mehlhorn and A. Tsakalidis: Data Structures, J. van Leeuwen, ed.: Handbook of Theoretical Computer Science Vol.A, 1990, pp.301--341)

  9. 浅野孝夫,浅野哲夫:計算幾何学入門,総研出版, 1992 (原著: F.P. Preparata and M.I. Shamos, Computational Geometry, Springer, 1988)


  10.   (PDF File)


主要研究論文:
  1. ACM論文誌(Association on Computing Machinery, 情報科学の代表的な世界的学会)

    1. Takao Asano, Tetsuo Asano and Hiroshi Imai: Partitioning a polygonal region into trapezoids, Journal of ACM, 33 (1986), pp.290--312

    2. M. Edahiro, I. Kokubo and Takao Asano: A new point-location algorithm and its practical efficiency - comparison with existing algorithms, ACM Transactions on Graphics, 3 (1984), pp.86--109


  2. SIAM論文誌(Society of Industrial and Applied Mathematics, 応用数理の代表的な世界的学会)

    1. Takao Asano, M. Shibui and I. Takanami: General results on tour lengths in machines and digraphs, SIAM Journal on Computing, 5 (1976), pp.629--645

    2. Hiroshi Imai and Takao Asano: Efficient algorithms for geometric graph search problems, SIAM Journal on Computing, 15 (1986), pp.478--494

    3. Takao Asano: An application of duality to edge-deletion problems, SIAM Journal on Computing, 16 (1987), pp.312--331


  3. IEEE論文誌 (Institute of Electrical and Electronics Engineers, 電子工学の代表的な世界的学会)

    1. Takao Asano, K. Yoshikawa and S. Suzuki: The design of a precompensator for multivariable adaptive control --- A network-theoretic approach, IEEE Transactions on Automatic Control, AC-35 (1990), pp.706--710


  4. アルゴリズムの世界的学術専門誌

    1. Takao Asano and T. Hirata:Edge-contraction problems, Journal of Computer and Systems Science, 26 (1983), pp.197--208

    2. Hiroshi Imai and Takao Asano: Finding the connected components and a maximal clique of an intersection graph of rectangles in the plane, Journal of Algorithms, 4 (1983), pp.310--323

    3. Takao Asano: An approach to the subgraph homeomorphism problem, Theoretical Computer Science, 38 (1985), pp.249--267

    4. Takao Asano, Tetsuo Asano and R.Y. Pinter: Polygon triangulation: efficiency and minimality, Journal of Algorithms, 7 (1986), pp.221--231

    5. Takao Asano, Tetsuo Asano, L. Guibas, J. Hershberger and Hiroshi Imai: Visibility of disjoint polygons, Algorithmica, 1 (1986), pp.49--63

    6. Hiroshi Imai and Takao Asano: Dynamic orthogonal segment intersection search,Journal of Algorithms, 8 (1987), pp.1--18

    7. M. Edahiro, K. Tanaka, T. Hoshino and Takao Asano: A bucketing algorithm for the orthogonalsegment intersection search problem and its practical efficiency, Algorithmica, 4 (1989), pp.61--76

    8. Takao Asano: Dynamic programming on intervals, International Journal of Computational Geometry and Applications, 3 (1993), pp.323--330

    9. Takao Asano, An O(n log log n) time algorithm for constructing a graph of maximum connectivity with prescribed degrees, Journal of Computer and System Sciences, 51 (1995), pp.503--511

    10. Takao Asano and D.P. Williamson, Improved approximation algorithms for MAX SAT, Journal of Algorithms, 42 (2002), pp.173--202

    11. Takao Asano: An Improved Analysis of Goemans and Williamson's LP-relaxation for MAX SAT, Theoretical Computer Science, 354 (2006), pp.339--353


  5. グラフ理論・離散数学の世界的学術専門誌

    1. Takao Asano, T. Nishizeki and T. Watanabe: An upper bound on the length of a hamiltonian walk of a maximal planar graph, Journal of Graph Theory, 4 (1980), pp.315--336

    2. T. Nishizeki, Takao Asano and T. Watanabe: An algorithm with a constant worst-case bound for the hamiltonian walk problem on maximal planar graphs, Discrete Applied Mathematics, 5 (1983), pp.211--222

    3. Takao Asano: Properties of matroids characterizable in terms of excluded matroids,Journal of Combinatorial Theory, Series B, 34 (1983), pp.233--236

    4. Takao Asano, S. Kikuchi and N. Saito: A linear algorithm for finding Hamiltonian cycles in 4-connected maximal planar graphs, Discrete Applied Mathematics, 7 (1984), pp.1--15

    5. Takao Asano, T. Nishizeki, J. Oxley and N. Saito: A note on the critical problem for matroids, European Journal of Combinatorics, 5 (1984), pp.93--97

    6. T. Asano, T. Nishizeki and P.D. Seymour: A note on nongraphic matroids, Journal of Combinatorial Theory, Series B, 37 (1984), pp.290--293

    7. Takao Asano: Constructing a bipartite graph of maximum connectivity with prescribed degrees, Networks, 29 (1997), pp.245--263


主要国際会議論文:
  1. 情報科学の代表的な世界的学会の著名な国際会議:ACM STOC (Symposium on Theory of Computing), ACM SCG (Symposium on Computational Geometry), IEEE FOCS (Foundations of Computer Science), SIAM SODA (Symposium on Discrete Algorithms)での発表論文

    1. Takao Asano and T. Hirata: Edge-deletion and edge-contraction problems, Proceedings of the 14th Annual ACM Symposium on Theory of Computing, San Francisco, 1982, pp.245--254

    2. Tetsuo Asano and Takao Asano: Minimum partition of polygonal regions into trapezoids, Proceedings of the 24th Annual IEEE Symposium on the Foundations of Computer Science, Tucson, 1983, pp.233--241

    3. Hiroshi Imai and Takao Asano: Dynamic segment intersection search with applications, Proceedings of the 25th Annual IEEE Symposium on the Foundations of Computer Science, Singer Island, 1984, pp.393--402

    4. Takao Asano, Tetsuo Asano, L. Guibas, J. Hershberger and Hiroshi Imai: Visibility polygon search and Euclidean shortest paths, Proceedings of the 26th Annual IEEE Symposium on the Foundations of Computer Science, Portland, 1985, pp.155--164

    5. M. Edahiro, K. Tanaka, T. Hoshino and Takao Asano: A bucketing algorithm for the orthogonal segment intersection search problem and its practical efficiency, Proceedings of the 3rd Annual ACM Symposium on Computational Geometry, Waterloo, 1987, pp.258--267.

    6. Takao Asano and D.P. Williamson: Improved Approximation Algorithms for MAX SAT, Proceedings of the 11th ACM-SIAM Symposium on Discrete Algorithms, San Francisco, 2000, pp.96--105.

    7. Takao Asano: Approximation algorithms for MAX SAT: Yannakakis vs. Goemans-Williamson, Proceedings of the 5th Israel Symposium on Theory of Computing and Systems, Ramat Gan, 1997, pp.24--37.