3 0 0 0 OA 変わりつつある情報教育 : 7.大学での情報入試
1 0 0 0 OA 各種浮動小数点表現法の評価方式の実現
- 著者
- 森 岳志 中川 正樹 高橋 延匡 中森 眞理雄
- 雑誌
- 情報処理学会論文誌 (ISSN:18827764)
- 巻号頁・発行日
- vol.29, no.8, pp.807-814, 1988-08-15
本論文は 新しい浮動小数点表現法の比較・評価を行う環境を提供することを目的とし OS用言語CコンパイラCATに複数通りの浮動小数点表現法を実現したことについての報告である.本研究では (1)URR (2)IEEE表現法(3)MIL-STD-1750A表現法の3種類の表現法をサポートしている.さらに 表現法の選択を (ア)コンパイル時に行う方法 (イ)実行時に行う方法の両者を用いて実現した.後者の方法は 効率の良い評価環境を与えることを目的として考案された方式で 評価の際のコンパイルとリンクの手間を軽減し 新たに表現法を追加したとしても浮動小数点演算ライブラリの再編成だけを行えばよく プログラムの再コンパイルを必要としないことなどの特徴を有している.定数の扱いに問題が生じたが 現時点では実行時に内部表現に変換することによって解決している.
1 0 0 0 OA 平成18 年度入試に向けての「情報」試行試験の実施報告(1)
1 0 0 0 巡回トーナメント問題に対するタブーサーチ・アルゴリズム
- 著者
- 住川 裕岳 宮代 隆平 中森 眞理雄
- 出版者
- 一般社団法人情報処理学会
- 雑誌
- 情報処理学会研究報告数理モデル化と問題解決(MPS) (ISSN:09196072)
- 巻号頁・発行日
- vol.2007, no.64, pp.5-8, 2007-06-25
- 参考文献数
- 9
本研究では、スポーツスケジューリング問題の一種である巡回トーナメント問題を扱う。巡回トーナメント問題とは、ホーム&アウェイ形式の二重総当りリーグ戦を行うスポーツにおいて、各チームの移動距離の総和を最小化した試合日程を構築する問題である。この問題では、巡回セールスマン問題の難しさに加え、あるチームの対戦順序が他チームの対戦順序に影響を与えており、問題の難易度を増している。これまでの研究により、巡回トーナメント問題に対してはシミュレーテッド・アニーリングが有効であることが示されていたが、本研究ではタブーサーチを用いて最適化を行った。計算機実験の結果、既存のアルゴリズムによる結果に匹敵する質の良い解が得られた。The traveling tournament problem is a well known benchmark problem in sports scheduling. This problem has both an optimization aspect like the traveling salesman problem and a feasibility aspect as in many scheduling/timetabling problems. Since the traveling tournament problem was established, a number of researchers have tackled the problem with various optimization techniques. Recent researches indicated that simulated annealing algorithms are effective for the traveling tournament problem, and few results by tabu search are reported so far. In this manuscript, we propose a tabu search algorithm for the traveling tournament problem. Our computational experiments show that the proposed algorithm generates good solutions, which are competitive with solutions by simulated annealing algorithms.
1 0 0 0 各種浮動小数点表現法の評価方式の実現
- 著者
- 森 岳志 中川 正樹 高橋 延匡 中森 眞理雄
- 出版者
- 一般社団法人情報処理学会
- 雑誌
- 情報処理学会論文誌 (ISSN:18827764)
- 巻号頁・発行日
- vol.29, no.8, pp.807-814, 1988-08-15
- 被引用文献数
- 1
本論文は 新しい浮動小数点表現法の比較・評価を行う環境を提供することを目的とし OS用言語CコンパイラCATに複数通りの浮動小数点表現法を実現したことについての報告である.本研究では (1)URR (2)IEEE表現法(3)MIL-STD-1750A表現法の3種類の表現法をサポートしている.さらに 表現法の選択を (ア)コンパイル時に行う方法 (イ)実行時に行う方法の両者を用いて実現した.後者の方法は 効率の良い評価環境を与えることを目的として考案された方式で 評価の際のコンパイルとリンクの手間を軽減し 新たに表現法を追加したとしても浮動小数点演算ライブラリの再編成だけを行えばよく プログラムの再コンパイルを必要としないことなどの特徴を有している.定数の扱いに問題が生じたが 現時点では実行時に内部表現に変換することによって解決している.
1 0 0 0 OA 大学等における情報処理教育の諸問題:平成元年度の調査研究を中心として
1 0 0 0 メモリ領域が小さい確率的なグラフ連結性判定アルゴリズムについて
- 著者
- 池田 諭 品野 勇治 中森 眞理雄
- 出版者
- 一般社団法人情報処理学会
- 雑誌
- 情報処理学会研究報告数理モデル化と問題解決(MPS) (ISSN:09196072)
- 巻号頁・発行日
- vol.2002, no.19, pp.17-20, 2002-03-04
与えられたグラフG=(V E)が連結か否かを判定することを考える.O(|V|+|E|)のメモリ領域を用いることが出来るならば,O(|V|+|E|)の手間で連結性が判定できることがR.E.Tarjanによって示されている.本論文の目的は,分散システム上で動作する連結性判定分散アルゴリズムを求めることである.本論文では,R.Aleliunas R.M.Karp R.J.Lipton L.Lovaaszおよび C.Rackoff による?RW を用いる手法を取り上げている.そして,簡単な前処理をすることが可能な状況ならば,O(|V|^2 ?log|V|)の手間でほぼ確実に無向グラフの連結性が判定出来ることを示した.また,有向グラフの場合もグラフの直径と次数の上界が分かっているならば同様にして多項式オーダーで判定できることを示した.We consider the reachability problem for directed and undirected graphs. Let G=(V,E) be a directed graph. In [1], R. E. Tarjan has showed the algorithm of O(|V|+|E|) sapce and time complexity. We show a probablistic distributed algorithm for this problem in space O(1) and time O(|V|^2 \log |V|). In this paper,\ we discuss a variant of the algorithm which based on random walk, due to R.Aleliunas, R.M.Karp, R.J.Lipton, L.Lovaasz, and C.Rackoff. We show an improvement of their algorithm from O(|V|^3 log |V|) to O(|V|^2 log |V|) in time helped with a simple preprocessing. In a directed graph,\ we also show their original algorithm run in time O(|V|^2log|V|),\ if the diameter and the degree of the graph is bounded.
- 著者
- 高橋 延匡 SHAPIRO Stua RALSTON Anth KERSHNER Hel SELMAN Alan 中森 眞理雄 大岩 元 都倉 信樹 牛島 和夫 野口 正一
- 出版者
- 東京農工大学
- 雑誌
- 国際学術研究
- 巻号頁・発行日
- 1992
わが国の大学の情報処理教育のカリキュラムは米国に比べると著しく遅れているというのが通説であった。本研究代表者および分担者は情報処理学会の「大学等における情報処理教育の改善のための調査研究」で中心的な役割を果たし,コンピュータサイエンスのモデルカリキュラムJ90の作成に貢献した。しかし,J90を各大学で具体化して実現するには,授業時間配分や担当教員の割り振りなど多くの問題を解決しなければならないことが明らかになった。そこで,本年度は,米国で,過去にコンピュータサイエンスのモデルカリキュラムを各大学で具体化して実現する際にどのようにしたかを調査することにした。まず,予備調査として,ACM(米国計算機学会)が1988年に発表したコンピュータサイエンスの見取図である9行3列のマトリクス(以下では「デニング図」と呼)をカリキュラムの評価に使うことが可能かどうかを検討した。デニング図の各行は1アルゴリズムとデータ構造,2計算機アーキテクチャ,3人工知能とロボティックス,4データベースと情報検索,5人間と計算機のコミュニケーション,6数値的計算と記号的計算,7オペレーティングシステム,8プログラミング言語,9ソフトウェアの方法論とソフトウェア工学に対応する。デニング図の各列は(1)理論,(2)抽象化,(3)設計に対応する。個々の大学のコンピュータサイエンスのカリキュラムについて,その各授業科目をデニング図の27(=9×3)の枠にあてはめてみることにより,そのカリキュラムの特徴が明らかとなる。さらに,もう一つの予備調査として,ACMが1991年に発表したコンピュータサイエンスの頻出概念について,カリキュラム評価の手法として使うことが可能かどうかを検討した。ACMの頻出概念は(A)バインディング,(B)大規模問題の複雑,(C)概念的および形式的モデル,(D)一貫性と完全性,(E)効率,(F)進化とその影響,(G)抽象化の諸レベル,(H)空間における順序,(I)時間における順序,(J)再利用,(K)安全性,(L)トレードオフとその結果,の12から成る。検討した結果,ACMの頻出概念はきわめて重要なものを含んでいるが,(a)これら12個の概念は互いに独立であるか,(b)これら12個の概念はコンピューサイエンスを完全に覆っているか,についてさらに詳しく検討する必要があることがわかった。以上の予備調査を行った上で,米国ニューヨーク州立大学バッファロー大学計算機科学科を訪問し,共同研究を行った。研究の方法は,デニング図を含むカリキュラム評価方法やコンピュータサイエンスの頻出概念について,日米双方の研究代表者・分担者が見解を述べ,互いに賛否の意見を出し合う,という形で行った。この過程で,バッファロー大学ではデニング図を用いて自己点検・評価を行っていることが示された。ACMの1991年報告書では「広がり優先方式」(以下,「BF方式」と呼ぶ)によるカリキュラム編成方式が紹介され,それを実現するために多数の「知識ユニット」が提案されている(もちろん,それらの知識ユニットを組み合わせて,学問体系に沿って教える伝統的なカリキュラムを編成することも可能である)。このBF方式カリキュラムについても議論した。米国分担者達はBF方式カリキュラムを試みたが,現在は伝統的なカリキュラムに復帰しつつあるという見解であった。ACMのSIGCSE研究会の研究発表の内容を調べた結果,非BF方式カリキュラムに対する支持が強いことが確かめられた。もっとも,教育は必然的にBF的面を有するものであり,BF方式カリキュラムが妥当であるか否かという問題は,知識ユニットをどの程度の大きさにするのが適切であるかという問題に帰着され,今後の検討課題となった。本研究の期間中に,ACMのSIGCHI研究会から人間と計算機のコミュニケーションを主題とするカリキュラム案が発表された。このカリキュラム案に伴って紹介されている演習課題についても検討した。この分野は日本が大きな貢献をすることが可能な分野であり,今後の研究課題とすることにした。
1 0 0 0 作業領域が小さいマージソート
- 著者
- 萩原 洋一 池田 論 中森 眞理雄
- 出版者
- 一般社団法人電子情報通信学会
- 雑誌
- 電子情報通信学会技術研究報告. COMP, コンピュテーション
- 巻号頁・発行日
- vol.98, no.442, pp.57-64, 1998-12-04
- 被引用文献数
- 1 1
マージソートは時間計算量が0(n log n)(nはソートされるレコードの個数)であり高速であるが, 内部ソートとして実行する場合, 作業場所として大きさnの配列を要するのが欠点であるとされている.本論文では, 作業場所として数語だけを要するマージソートを提案する.新しいマージソートの時間計算量は0(n log^2 n)であり, 従来のアルゴリズムより悪いが, これは作業場所とのトレードオフの結果である.
1 0 0 0 タイムラグ付き RCPSP/t に対するヒューリスティックな解法
- 著者
- 草部 博輝 中森 眞理雄
- 出版者
- 一般社団法人情報処理学会
- 雑誌
- 情報処理学会論文誌数理モデル化と応用(TOM) (ISSN:18827780)
- 巻号頁・発行日
- vol.48, no.15, pp.34-46, 2007-10-15
資源制約付きプロジェクトスケジューリング問題(Resource Constrained Project Scheduling Problem: RCPSP)は,多くの古典的スケジューリング問題の一般化されたモデルである.本稿は,利用可能な再生型資源量の時刻による変化と,各アクティビティが要求する再生型資源量の時間による変化を取り入れた,RCPSP/t モデルに,タイムラグの概念を追加した拡張モデル,RCPSP/t+ モデルを取り扱う.本稿において,我々はRCPSP/t+ モデルの解法として,タブーサーチアルゴリズムを提案し,ILOG CPLEX から得られた最適解と比較することにより,解の精度を評価する.Resource-constrained project-scheduling problem (RCPSP) is a general model of several classical scheduling models. In this paper, we suggest the scheduling model RCPSP/t+, which is added the time windows to the model of RCPSP/t having the changing of limit of renewable resources in project term and of requirement of renewable resources in each activity's processing time. We present a tabu search algorithm for the RCPSP/t+ and evaluate the solution accuracy comparing the oplitmal solution of ILOG CPLEX.
- 著者
- 草部 博輝 中森 眞理雄
- 出版者
- 一般社団法人情報処理学会
- 雑誌
- 情報処理学会研究報告バイオ情報学(BIO) (ISSN:09196072)
- 巻号頁・発行日
- vol.2007, no.128, pp.41-43, 2007-12-20
資源制約付プロジェクトスケジューリング問題(Resource Constrained Project Scheduling Problem : RCPSP)は,job-shop のようなモデルの一般形としてよく知られるモデルである.本稿は,RCPSP の先行制約と資源制約を変化させた RCPSP/τ+ モデルを取り扱い,その下界値の計算法を提案する.評価は比較的小規模のインスタンスを用い,最適解との比較を行うことにより行う.Resource-constrained project-scheduling problem (RCPSP) is a general model of several classical scheduling models like a job-shop. In this paper, we suggest the scheduling model RCPSP/${\tau}+$, which is added the time windows to the model of RCPSP/${\tau}$ having the changing of limit of renewable resources in project term and of requirement of renewable resources in each activity's processing time. We present a lower bounding method for the RCPSP/${\tau}+$ and evaluate the lower bound accuracy comparing the oplitmal solution.
1 0 0 0 作業場所が小さいマージソートと計算量の評価
- 著者
- 萩原 洋一 池田 諭 中森 眞理雄
- 出版者
- 一般社団法人情報処理学会
- 雑誌
- 情報処理学会研究報告アルゴリズム(AL) (ISSN:09196072)
- 巻号頁・発行日
- vol.1999, no.33, pp.33-40, 1999-05-10
マージソートは時間計算量がO(n log n)(nはソートされるレコードの個数)であり高速であるが,内部ソートとして実行する場合,作業場所として大きさnの配列を要するのが欠点であるとされている.本論文では,作業場所として数語だけを要するマージソートを提案する.新しいマージソートの時間計算量はO(n log^2 n)であり,従来のアルゴリズムより悪いが,これは作業場所とのトレードオフの結果である.Mergesort is one of the fastest sorting algorithm, since it requires only O (n log n) of computing time. Mergesort, however, requires an array of size n as working area, when executed as an internal sort. In the present paper, we propose an algorithm which is a modified version of mergesort. The space complexity of the proposed algorithm is only O. The time complexity is O (n log^2 n), which is worse than the existing merge sort and is the result of the tradeoffs between time and space complexities.