著者

土屋 雅稔 中村 純哉

雑誌

情報処理学会論文誌 (ISSN:18827764)

巻号頁・発行日

vol.63, no.3, pp.879-894, 2022-03-15

---

大学を含む公的機関にとって, 各種の異常事態に対する事業継続性の確保は, 重要な課題の1つである. 本論文では, 2つの観点から認証基盤システムの事業継続性について検討する. 第1に, 大規模災害に対する事業継続性について検討する. 大規模災害に対する事業継続性を確保するには, 情報システムを安全な遠隔地に設置するだけでなく, 異常時の挙動について十分に検証する必要がある. 本論文では, 認証基盤システムを遠隔地に設置する場合の設計上の留意点と, 平常時の停電を利用して異常時の挙動を定期的に検証する運用経験について述べる. 第2は, 感染症によるロックダウンに対する事業継続性である. キャンパスがロックダウンされた場合, 従来は対面形式で行われていた各種手続きをオンライン化する必要がある. しかし, 安全な認証という前提を保ちつつ, 各種手続きをオンライン化することは, 決して容易なことではない. 本論文では, 複数の多要素認証手段を組み合わせることにより, できるだけ安全に各種手続きをオンライン化する方法と, COVID-19パンデミックにおける対処経験について述べる.

著者

石川 淑 田中 飛鳥 宮崎 敏明

雑誌

情報処理学会論文誌 (ISSN:18827764)

巻号頁・発行日

vol.55, no.3, pp.1167-1176, 2014-03-15

---

Basic Local Alignment Search Tool(BLAST)は最も有名なシーケンスアライメントツールの1つである.シーケンスアライメントとはタンパク質(またはDNA)データベースから検索対象となるタンパク質(またはDNA)配列を列挙することであり,配列どうしの類似部分検索のために使用される.シーケンスアライメントは,生物学上の進化や遺伝子系図を調べるうえで重要であることから,バイオインフォマティクス分野では欠かせない情報である.そのため,従来からハードウェアを用いて,BLASTを高速化する試みがなされてきた.BLASTは前処理,seeding,ungapped extension,gapped extension,traceback処理から構成される.従来のハードウェア化は,gapped extension処理が中心であり,他の部分は,ホストマシン上で処理される形態であった.本論文では,前処理,traceback処理を含むすべてのBLAST処理をハードウェア化し,ホストマシン上のソフトウェア処理との処理速度のアンバランスを解消することによりBLAST全体の高速化を行う.提案回路を廉価なFPGA(Field Programmable Gate Array)に実装した結果,ソフトウェア実装に比べ約790倍の高速化を達成した.また,gapped extension処理とtraceback処理に対してさらなる高速化手法を提案し,840倍以上の高速化を実現した.

著者

槇原 絵里奈 池田 太郎 小野 景子 新濱 遼大

雑誌

情報処理学会論文誌 (ISSN:18827764)

巻号頁・発行日

vol.63, no.3, pp.742-751, 2022-03-15

---

オンラインジャッジシステムには多くの問題が収録されており,これらをプログラミング学習におけるアルゴリズムの自学自習支援として活用することで,教員の問題作成コストをへらすことができる.一方,学生が主体的に自身のプログラミング能力に適した問題を選択することは困難であり,最適な問題自動選択手法が望まれている.本論文では,オンラインジャッジシステムにおけるユーザの解答履歴に着目し,解答履歴,解答の正誤を深層学習モデルあるLong Short Term Memory(LSTM)により学習し,問題間の関係に基づいた問題推薦が可能な手法を提案する.オンラインジャッジシステムであるCodeforcesの実データを対象に提案法の性能を検証し,ユーザの解答履歴の高い推定性能を確認した.また,遷移の可視化により,難易度の高い問題へ遷移するための最短な問題経路や,様々な種類の問題へ着手できる核となる問題を明らかにした.

著者

市川 至 蓬莱尚幸 佐伯 元司 米崎 直樹 榎本 肇

出版者

一般社団法人情報処理学会

雑誌

情報処理学会論文誌 (ISSN:18827764)

巻号頁・発行日

vol.27, no.11, pp.1112-1128, 1986-11-15

被引用文献数

1

---

本論文では 自然言語ベースの仕様記述言語TELL/NSLにおけるシステムの静的な仕様記述から 変換により実行可能なPrologプログラムを得てテストデータによる試験を行うラピッドプロトタイピング手法について述べる.TELL/NSLの仕様記述は まずその意味となる1階述語論理式へ変換され 次にホーン節型式に変換される.さらに 述語の入出力モードを入出力依存グラフを利用して決定し その入出力モードに基づき正しい動作をするようにPrologの実行制御を考慮してリテラルや節の並べ換えを行い 実行可能なPrologプログラムに変換する.これらの変換は 段階的に適応される部分変換からなり それぞれの変換では健全性が保証され 全体の変換により得られるプログラムは元の仕様記述を満たし部分正当であることが保証される.得られたプログラムを実行しデータ試験を行うことにより 元の仕様記述において不明確な点を発見することが可能となった.

著者

甲斐 俊文 佐々木 良一

出版者

情報処理学会

雑誌

情報処理学会論文誌 (ISSN:18827764)

巻号頁・発行日

vol.52, no.3, pp.1136-1143, 2011-03-15

---

ボットネットの被害が増大してきており,ボットマスタ(ハーダ)まで追跡することが重要な課題となっている.ボットネットごとに通信経路は異なるが,経路上に防弾業者や一般ユーザの端末がある場合には追跡は困難になる.そこで我々は防弾業者や一般ユーザの端末を使用しているボットネットの割合を推定するために,統計調査を実施した.その結果,ユーザ端末を使用しているボットネットの割合は1割から3割程度,防弾業者サーバ端末については少なくとも2割以上,専門のサーバ管理者に管理されている端末は4割から5割程度と見積もられることを示す.また,ボットネットに使用されている端末の国別の傾向について調査した結果も示し,これらの調査に基づいてボットネット追跡の方針を検討する.The damage of botnet is increasing, and it is an important problem to track bot masters. We analyzed tracing paths of botnet and classified these under 5 patterns. And if there are terminals of bulletproof providers or end users on a path, tracing on the path is difficult. Now we are examining a ratio of botnet using a terminal of bulletproof providers and end users. We have examined a ratio of botnet using a terminal of bulletproof providers and end users. As a result, we estimated the ratio of the botnet which used terminals of end users at around 30% from 10%, bulletproof providers at least 20%, and normal server managers at around 50% from 40%. And we argue about a policy of botnet traceback.

著者

坂元 哲平 小林 佑輔 中川 慶一郎 生田目 崇 後藤 正幸

雑誌

情報処理学会論文誌 (ISSN:18827764)

巻号頁・発行日

vol.62, no.1, pp.346-356, 2021-01-15

---

近年,消費者の嗜好の多様化にともない,テレビ業界においても視聴者の嗜好に寄り添った魅力的な番組戦略や広告戦略を編成する必要性が増している.このような問題意識と,デジタル化によるデータの蓄積を背景にテレビ視聴データの分析事例が報告されている.一方で,従来研究では視聴履歴を用いて視聴者と番組の関係性を表現することを目的としたモデル化事例についての議論は盛んではない.そこで本研究では,両者の関係性をトピックモデルに基づくクラスタリングによってモデル化するデータ分析手法を提案する.一般に視聴者の嗜好は時間的に変化することが考えられるため,時系列を考慮したトレンドの分析を可能とするような分析法が必要である.ここで,ドラマ番組のように3カ月を1クールとして放送される番組がいっせいに変わるというテレビ特有の事象に対して,単純なクラスタリング法ではクラスタの継続性が保たれないという問題があるため,その問題に対応するトレンド分析法を提案する.さらに,得られた結果を用いた分析を直感的に行うために,サンキーダイアグラムを用いた可視化を施す.また,多様な視聴者の視聴傾向を1つのクラスタへ一意に所属させる場合と,複数クラスタへの所属を許容する場合の2つの分析法を提案し,比較を行う.最後に,提案分析法を実際のテレビ視聴データに適用し,提案法の有効性を示すとともに,結果の分析を行い視聴者のテレビ視聴行動を明らかにする.

著者

上條浩一 上條 昇 阪本 正治

出版者

一般社団法人情報処理学会

雑誌

情報処理学会論文誌 (ISSN:18827764)

巻号頁・発行日

vol.47, no.7, pp.2168-2181, 2006-07-15

参考文献数

19

被引用文献数

1

---

カメラ,電話,テレビ放送等あらゆる分野でデジタル化が進んでいるが,新聞,書籍等,紙媒体は依然多く流通しており,今のところデジタル化の波に 完全にのみこまれてしまう兆候は見えない.しかし,これら紙媒体とデジタルの世界とを結びつける需要は増えており,それを実現する手段の例として,バーコードや電子透かしがある. しかし,バーコードの場合は場所をとり,見栄えが悪く,電子透かしは埋め込める情報量が少ない,という問題がある. 本論文では,これらの問題を解決しつつ紙媒体とデジタルの世界を結びつける電子スクラップシステムを紹介する. 本システムでは,不可視インクを用いて新聞等の記事に重畳して印刷された2次元バーコードを,そのインクに反応する特殊な発光装置を搭載した携帯電話等で撮影し,その撮影画像から画像処理を組み合わせた抽出アルゴリズムによって情報を抽出する. 我々は,この抽出アルゴリズムと特殊LEDを実際に搭載した携帯電話の試作機を作り,正しく動作することを確認した.Digitalization has been pervading in various areas, including camera, telephone,TV, and so on. On the other hand, paper media forms, such as newspapers and magazines, still have large market shares, and we see no sign they will be completely digitized. However, demands to connect between these analog and digital worlds are increasing. Barcodes and watermarking are examples of the technologies used to connect them. However, the problem is that a barcode occupies space and disrupts the layout of the article, and watermarking has limited capacity for embedding data. In this paper, we propose an "Electronic Scrap System", which connects the analog and digital world, solving these problems. In this system, we superimpose invisible barcodes on printed articles using invisible ink, then take pictures of them using a special camera equipped with a special LED (Light Emitting Diode) that is sensitive to the invisible ink, decode the encoded data after the image is processed, and extract the information. We made a prototype cell phone which includes the code extraction algorithm and the LED attached outside the device, and confirmed that we can correctly extract the information from the photo image taken by the cell phone.

著者

福本 淳文 山内 利宏

雑誌

情報処理学会論文誌 (ISSN:18827764)

巻号頁・発行日

vol.61, no.9, pp.1507-1518, 2020-09-15

---

権限昇格攻撃はシステムの改ざんや情報漏えいにつながる可能性がある.これに対処するために,我々はシステムコールによる権限の変更に着目した権限昇格攻撃防止手法(以降,先行研究の手法)を提案した.しかし,先行研究の手法はOS内で実現されており,導入するために,カーネルソースコードを変更する必要がある.また,先行研究の手法では,変更の検証のために保存したカーネル空間内の権限情報を,攻撃者に改ざんされる可能性がある.本論文では,これらの課題に対処するために,仮想マシンモニタであるKVMを用いて権限昇格攻撃を防止する手法を提案する.提案手法は,ゲストOS上のシステムコール発行をフックし,システムコール処理による権限の変更を検証する.提案手法の実現により,手法の導入にともなうカーネルソースコードの変更が不要となる.また,権限情報をホストOSのメモリ領域に保存することで,権限情報の改ざんが困難となる.本論文では,先行研究の手法の課題を示し,提案手法や評価の結果について述べる.

著者

位守 弘充 中村 宏 朴 泰祐 中澤 喜三郎

出版者

一般社団法人情報処理学会

雑誌

情報処理学会論文誌 (ISSN:18827764)

巻号頁・発行日

vol.34, no.12, pp.2612-2623, 1993-12-15

参考文献数

16

被引用文献数

16

---

大規模科学技術計算では、データ領域が非常に大きくデータの局所性が少ないため、キャッシュメモリが有効に働かない、そのためスカラプロセッサの実効性能はキャッシュミス時の主記億アクセスペナルティーにより低下する。本諭文では、主記憶のスループットを十分強化した上で、浮動小数点レジスタの構成としてスライドウィンドウ方式を採用し、既存のスカラアーキテクチャとの上位互換性を保ちながらレジスタ数を増やすことでこの問題を解決した新しいプロセッサを提案する。提案するスライドウィンドウ方式は、われわれが以前提案したレジスタウィンドウ方式と比較して、ウィンドウ構成をソフトウェアで制御できるという長所がある。本諭文ではスライドウィンドゥを用いた擬似ベクトルプロセッサのアーキテクチャと処理原理、ならびにベンチマークプログラムを用いた評価緒果を示す。主記億アクセスレーテンシーが20マシンサイクルの場合、擾案するプロセッサは通常のスカラプロセッサに対し約8借の性能向上が得られた。レジスタウィンドウ方式のプロセッサと比ぺても、レジスタ数が同じ場合、2倍の主記億アクセスレーテンシーを隠蔽でき、総レジスタ数が88のと妻、提案するプロセッサは60マシンサイクルの主記憶アクセスレーテンシーを隠蔽することができた。これらの評価結果より、提案するプロセッサは高速にベクトル計算を処理することができると結論できた。

著者

梶 克彦 長尾 確

出版者

一般社団法人情報処理学会

雑誌

情報処理学会論文誌 (ISSN:18827764)

巻号頁・発行日

vol.48, no.1, pp.258-273, 2007-01-15

参考文献数

35

被引用文献数

8

---

一般にテキスト,ビデオ,音楽などのコンテンツには複数の解釈が存在し,それらのコンテンツを対象とする場合,複数の解釈の中から適切なものを扱う必要がある.そこで我々は任意のコンテンツに対する複数の解釈を扱うためのプラットフォームとしてAnnphony を構築した.Annphony では,一般的なアノテーション記述形式であるRDF を拡張し,すべてのアノテーションに識別子を付与することでそれぞれの解釈を区別して扱うことができる.解釈が多様になりやすいコンテンツの典型例として音楽があげられる.一般に音楽は必ずしも解釈を一意に決定できず,その楽曲をとらえる人によって異なる解釈を見い出すことがしばしばみられる.そこで我々はAnnphony を基盤とし,楽曲に対する多様な解釈をWeb 上のユーザから取得する音楽アノテーションシステムを構築した.本システムは1. 書誌情報などの楽曲自体に対するアノテーション,2. 連続メディアに対するアノテーション,3. 楽譜に対するアノテーションの3 種類のエディタを備える.また実際に本システムによりアノテーションを収集し,楽曲に対する多様な解釈を扱う例として,楽曲検索システムとプレイリスト作成支援システムを構築した.Generally, there are multiple interpretations of single content such as a text, a video clip, a song, and so on. Therefore we have developed an annotation platform called "Annphony" to deal with such multiple interpretations. By extending RDF, a common annotation framework, each annotation has its own identifier that enables distinction of each interpretation. Music is one typical example that apt to cause multiple interpretations. Listeners do not necessarily make the same interpretation about the tune. Therefore, to deal with various musical interpretations we have developed a musical annotation system that consists of the following annotation editors ― 1: basic information of the tunes, 2: continuous media, and 3: musical scores. We have also developed two applications based on annotations about multiple interpretations collected by the annotation system. One is a music retrieval system based on music's inner structure. The other is a playlist recommendation system that semiautomatically generates playlists that reflect listener preferences and situations.

著者

伊木 惇 亀井 清華 藤田 聡

出版者

一般社団法人情報処理学会

雑誌

情報処理学会論文誌 (ISSN:18827764)

巻号頁・発行日

vol.55, no.11, pp.2461-2475, 2014-11-15

---

ecサイトにおける商品のレビューは,商品購入の意思決定に大きく関わり,価値ある情報として注目されている.一方で,ステルスマーケティングを目的とした,レビュースパムと呼ばれる信頼性の低いレビューの投稿が問題となっている.既存研究では,レビューの文章などから,それらスパムを検知する取り組みが行われてきた.しかしながら依然として,すべてのスパムの検知は難しい.さらに,レビューを読むユーザ自身が判断するにも,信頼性を判断するための情報は十分でない.また,ユーザは,ウェブ上の情報に対して,ある程度信じやすいという報告もされている.そのため,ユーザが信頼性を意識し,判断するための機構が必要である.よって,本稿ではecサイトにおけるレビューを対象とした信頼性を判断するための支援システムを提案する.具体的には,レビューの信頼性を表す指標として,類似性,協調性,集中性,情報性という4つの信頼性指標を定義し,各指標ごとのスコアを求める.そして,レビューごとにそのスコアを可視化して提示する.それにより,ユーザ自身に信頼性を意識してレビューを読むように促すとともに,信頼性判断がしやすくなるよう支援を行うことが可能となる.本研究では,これらの指標を用いた判断支援を行うシステムを構築し,評価を行った.その結果,提案システムにより,ユーザの信頼性に対する意識を促すとともに,有効な判断支援が行えることが確認できた.Reviews of products in e-commerce sites such as Rakuten have attracted as valuable information. On the other hand, in such the sites, unreliable reviews called review spam have become a big issue. In existing works, they proposed various methods to detect the spam. However, spam detections play a cat-and-mouse game with new type of spam, and any spam detections are not enough for the issue. Therefore, for users, mechanisms to support judgments of the credibility of each review are necessary. Thus, we proposed a support system to judge the credibility for reviews in e-commerce sites. Specifically, we define four credibility indicators to represent how much each review is spammy. Then, our support system calculates scores for each indicator and provides the scores for users. In this paper, we built a prototype system and evaluated the system by questionnaires. As a result, by using our system, it was confirmed that it is possible to enhance awareness of credibility for users.

著者

小山 智之 串田 高幸

雑誌

情報処理学会論文誌 (ISSN:18827764)

巻号頁・発行日

vol.63, no.2, pp.504-514, 2022-02-15

---

現在,Webサービスは広く利用されており,利用者の増加とともにアクセス数が増加している.アクセス数が増えるにつれ,サーバから生成されるアクセスログの件数は大規模になる.大規模なログの管理手法の1つである分散型は,ログを複数のノードに分散配置することで検索時のディスクI/Oにともなう負荷を分散している.分散型ログ管理の課題は,検索時のログへのアクセス傾向が十分に考慮されないためディスクI/Oが一部のノードへ偏り,検索の応答時間が高速でないことである.本研究では,Webアクセスログを対象とした検索クエリを想定した分散ログ配置により,検索の応答時間を削減する手法を提案する.具体的には,検索で発行されるクエリを想定し,それをもとにログに含まれる属性(PathやMethod,ノード名,日付)から特徴量を取り出し,ログの分割と再配置を行った.これにより,検索クエリにより偏るディスクI/Oを分散させ,検索の応答時間を削減した.評価では,86,400,000件のログを13台のノード上に3種類の手法(提案配置,ノード配置,時系列配置)により配置し,発行する検索クエリを変えながら検索の応答時間を比較した.その結果,提案配置は他の配置に比べ最大32秒の短縮を行った.

著者

西ノ平 志子 松井 博和 大島 千佳 中山 功一

雑誌

情報処理学会論文誌 (ISSN:18827764)

巻号頁・発行日

vol.63, no.2, pp.388-400, 2022-02-15

---

本論文では,上肢に障害がある人でも,すぐにギターを演奏したい気持ちを叶える支援装置“F-Ready”を提案した.対象者は,脳梗塞や脳性まひなどの脳神経系疾患による上肢の動作に困難がある重度障害者である.対象者のギターを演奏したいというモチベーションを維持するために,「すぐに演奏できる」「演奏している実感がある」に通ずる演奏動作に着目した.その演奏動作を実現するために鍵となる動きは,片方の手でギターネックに沿い手を動かし弦を押す動作と,もう片方の手で弦を弾く動作の協調動作である.対象者の上肢機能を考慮して,F-Readyはギターネックに沿い手を動かし弦を押す動作を支援する.本論文では,11人の対象者がF-Readyを搭載したギターを弾くことに挑戦した.9人の対象者はすぐにギターを演奏できた.さらに「ギターを演奏している実感がある」との回答を得た.次に別の対象者1人が,F-Readyを搭載したギターで1年間練習した.練習開始から5週間後には約1分間の曲を演奏できるようになった.続けて1年後には,4分以上の曲を演奏できるようになった.理学療法士は,対象者が楽器の練習により両上肢を運動する機会が得られ,通常のリハビリテーション以外で持久力と上肢の制御が改善されることを認めた.

著者

折原 征幸 塚田 浩二

雑誌

情報処理学会論文誌 (ISSN:18827764)

巻号頁・発行日

vol.63, no.2, pp.424-436, 2022-02-15

---

デスクワーク等を行う作業机,特に電子工作では多数の電子部品や工具が机の上に配置され,それらを組み合わせて使用するために煩雑になりやすい.本研究では,電子工作等の作業机に着目し,机上の工具/部品等のさりげない移動・整理を目指すシステム「PartsSweeper」を提案する.本システムは,机の裏に設置したXYプロッタ,ヘッド部の永久磁石と昇降機構,および作業空間を入力するタブレット端末を中心に構成される.特別なセンシングを行うことなく,工具と電子部品を個別に移動/整理することを目指す.本論文では,コンセプトを整理した後,プロトタイプや応用例を制作する.さらに,性能評価とユーザテストを通してプロトタイプの基礎的な性能やその動作に対する印象等を調査する.

著者

綾塚 祐二 雅樂 隆基 安川 力 吉高 淳夫

雑誌

情報処理学会論文誌 (ISSN:18827764)

巻号頁・発行日

vol.63, no.2, pp.379-387, 2022-02-15

---

機械学習を用いた画像分類は医療を含め幅広い分野で多くの成果をあげている.しかしその分類は何を根拠としてなされているかが人間には分かりにくい場合も多く,どこを見て分類を行ったかを可視化するためのさまざまな研究が行われている.疾患の分類のような目的のためには,画像中の「それらしい」正の寄与部分(所見)だけでなく「そぐわない」,すなわち負の寄与部分となる所見も診る必要があるが,既存の研究では負に寄与する部分は可視化の対象として注目されていない.我々は,機械学習モデルに対し,画像に微小な差異を加えた画像を入力した場合の確信度の出力の大きさの変化を画像化し提示する手法,DiDAを提案する.提案手法ではグリッド単位で区切りマスクした画像を用いて出力の差異をとらえ,複数のグリッドサイズを用いることで,正負の寄与領域を的確に描出する.DiDAを光干渉断層計による眼底の断層画像からの疾患分類に適用し眼科専門医の見解と照合した結果,DiDAによる解析画像は正負の寄与を的確にとらえていることが分かった.また,眼底の断層画像の疾患分類において画像中の正負の寄与領域を既存手法よりも的確に描出することを確かめた.

著者

磯島 和樹 萩原 将文

雑誌

情報処理学会論文誌 (ISSN:18827764)

巻号頁・発行日

vol.62, no.1, pp.378-386, 2021-01-15

---

本論文では,話題語を応答に反映させる話題語Seq2Seqを用いた,共感と助言に着目した自動相談システムを提案する.相談においては相手の感情に共感する発話と,相手に対して情報を与える助言の発話が求められる.提案システムでは相談者の入力文から抽出した感性語や話題語をもとに共感と助言の2つの発話を使い分ける.共感の発話にはテンプレート文を用い,助言の発話には話題語を応答に反映させる話題語Seq2Seqを提案する.話題語Seq2Seqにより,ありきたりな応答を生成しやすい従来のSeq2Seqを改善し,相談内容に関する多様な応答を生成できるようになった.評価実験では,従来のSeq2Seqを用いた相談システムと比較する主観評価実験を行った.その結果,従来システムよりも多様でユーザに寄り添う応答を生成できることが示された.

著者

住吉 英樹 相沢 輝昭

雑誌

情報処理学会論文誌 (ISSN:18827764)

巻号頁・発行日

vol.35, no.1, pp.35-45, 1994-01-15

---

英日機械翻訳システムの翻訳結果の出力形熊の一つとして、日本語音声合成装置による読み上げが考えられる。翻訳結果には、辞書に登録されていない英語固有名詞(人名、地名など)が、未知語として英語のまま含まれることがある。このような文章を目本語音声合成装置で読み上げさせると、英語部分の綴りをアルファベットのまま読み止げるため、非常に違和感を与えるだけでなく、文章の意昧を容易に把握できない。この問題を解決するために、簡易な手法により英語固有名詞を片カナ読みに変換するプログラムを開発した。このプログラムは変換対象となる英語文字列中の、4文字の母音字子音字のパターンに注目した簡単なルールと、小規模な片カナ読みへの変換テーブルにより変換を行う。英語固有名詞(人名、地名)約1、500語のうち、80%以上が正しく変換でき、簡単な手法にしては高い変換精度を得ることができた。

著者

遠山 宏明 足立 暁生

出版者

一般社団法人情報処理学会

雑誌

情報処理学会論文誌 (ISSN:18827764)

巻号頁・発行日

vol.37, no.11, pp.1886-1896, 1996-11-15

参考文献数

8

---

混合グラフのもとでのチャイニーズ・ポストマン問題(CPP)はNP完全であることが示されている. すべての辺の長さが等しい混合グラフ 平面混合グラフ 最大次数を3に制限した混合グラフのもとでさえNP完全である. 一方 グラフを全有向 または全無向に制限したCPPは多項式時間アルゴリズムを持つ. 本論文では 各辺の通行回数をたかだか2回に制限したCPP (2-CPP)がNP完全であり ちょうど1回に制限したCPP(1-CPP)はPに属することを示した. また CPP に関連する2つの興味ある関数の計算量も示した: (i)2-CPPにおいて 配達路の数を計算する関数は#P完全である (ii)CPPにおいて コスト k 以下で配達するためには 同一辺を少なくとも何回通行しなければならないかを計算する関数は多項式時間階層のクラスΔ^P_2に属する.The Chinese Postman Problem (CPP) on the mixed graphs is shown to be NP-complete. It remains NP-complete even if restricted to those whose edges all have equal length, or to the one on the mixed planner graphs, or to the one on the mixed graphs with nodes of degree three. CPP can be solved in polynomial time if the graph is either directed or undirected. In this paper, we show that even if the number of traverses for each edge is restricted to at most twice, CPP on the mixed graphs (called 2-CPP) is NP-complete, and if the number of traverses for each edge is restricted to exactly once, CPP on the mixed graphs (called 1-CPP)is in P. We also show complexity of two related functions: (i) in 2-CPP the function that calculates the number of delivery paths is #P-complete, oh the other band, (ii) in CPP the function that calculates the minimum of the maximum traverse numbers for each delivery path of cost k or less belongs to the class AZ in the polynomial time hierarchy.

著者

香田徹 柿本 厚志

雑誌

情報処理学会論文誌 (ISSN:18827764)

巻号頁・発行日

vol.27, no.3, pp.289-296, 1986-03-15

---

擬似乱数発生器として非線形写像で生成されるカオスを利用しようとする試みが行われている.この際 カオスが従来の擬似乱数と比較して 乱雑さに関する性質の良い乱数であるか否かがまず問題とされなければならないが これに関する検討は十分ではない.性質の良い乱数を定義することは容易ではなく また 実数値系列の乱雑さの度合いの測定も容易ではない与えられた実数値系列を闇値関数により2値系列に変換し 2値系列の乱雑さから実数値系列のそれを検討する方法が最近提案されている.本稿では 性質の良い乱数に関する一つの考え方を提案する.すなわち 変換して得られる2値系列がb閾値とは無関係に常にベルヌイ試行に十分近いとき もとの実数値系列を性質の良い乱数とみなすものである.このような考え方にたつと 従来の擬似乱数の検定法では 任意の閾値に対して得られる2値系列とベルヌイ試行との近さを議論していないので従来の検定法は十分ではない.本稿では ロジスティック写像で生成されるカオスの乱雑さと従来の擬似乱数発生法としての線形合同法 M系列 平方採中法による数列のそれとを比較検討した.なお 与えられた2値系列とベルヌイ試行との近さは連テストと組合せテストのχ^2検定により測った.その結果 従来の擬似乱数の方がカオスより性質の良い乱数であるとの結論を得た.

著者

千代 浩之 武田 瑛 船岡 健司 山崎 信行

雑誌

情報処理学会論文誌 (ISSN:18827764)

巻号頁・発行日

vol.52, no.8, pp.2365-2377, 2011-08-15

---

本論文では,低ジッタと高スケジュール可能性を達成するために,準固定優先度スケジューリングを提案する.準固定優先度スケジューリングは,終端部分という第2の必須部分を有する拡張インプリサイスタスクの各々の部分を固定優先度でスケジュールする.また,本論文では,Rate Monotonic(RM)を基調とした準固定優先度スケジューリングアルゴリズムRate Monotonic with Wind-upPart(RMWP)とRMWP++を提案する.スケジュール可能性解析では,RMWPはRMでスケジュール可能なタスクセットは必ずスケジュール可能であることを証明する.さらに,RMWP++は,タスクの実際実行時間に依存せず,最短周期タスクのジッタを0に抑制可能であることを証明する.シミュレーションによる評価結果では,準固定優先度スケジューリングは固定優先度スケジューリングと同程度のスケジュール成功率を発揮するだけでなく,従来のスケジューリングよりジッタを抑制したことを示した.This paper proposes semi-fixed-priority scheduling to achieve both low-jitter and high schedulability. Semi-fixed-priority scheduling schedules the part of each extended imprecise task, which has a wind-up part as a second mandatory part, by fixed-priority. This paper also proposes two novel semi-fixed-priority scheduling algorithms based on Rate Monotonic (RM), called Rate Monotonic with Wind-up Part (RMWP) and RMWP++. The schedulability analysis proves that one task set is feasible by RMWP if the task set is feasible by RM. In addition, we prove that the shortest period task in RMWP++ has zero-jitter, regardless of its actual case execution time. Simulation results show that semi-fixed-priority scheduling has approximately the same success ratio as fixed-priority scheduling and lower jitter than existing scheduling.