1989年、テキサス大学オースティン校のRobert Holte氏たちは、ある実務上の困りごとを数学の問題として定式化した。複数の人工衛星がそれぞれ決まった間隔でデータを送信してくる。地上局のアンテナは一度に一つの衛星しか受信できない。各衛星について「連続する日間に必ず1回は受信する」という条件を満たしつつ、無限に続く受信スケジュールを組めるか。この問いが輪番割当問題(pinwheel scheduling problem)の始まりだった。
問題の構造は単純だ。$k$個の仕事があり、仕事$i$は日ごとに必ず1回実行しなければならない。1日に実行できる仕事はちょうど1つ。スケジュールが存在するか否かを判定したい。
密度という量がこの問題の核心を握る。各仕事の「1日あたりの実行頻度」の合計であり、これが1を超えれば物理的にスケジュール不可能である。1日に1つしか仕事をこなせないのに、要求される総仕事量が1日あたり1を超えるのだから当然だ。
ところが密度1以下という条件は、スケジュール可能性を保証しない。最も有名な反例は$(2, 3, m)$()である。密度はであり、$m$を大きくすれば1にいくらでも近づけられるが、この組はどんな$m$を選んでもスケジュール不可能だ。2日周期の仕事と3日周期の仕事が互いに干渉し、3番目の仕事を割り込む隙間が永遠に残らない。
33年未解決の「6分の5予想」を京都大学が証明、周期タスク設計に理論的上限 [すらいむ★]
5名無しのひみつ
2026/08/22(土) 06:47:40.49ID:0d7J2bIjレスを投稿する
ニュース
- 「執行猶予つかないんか」元ジャンポケ斉藤慎二被告に“一発実刑” 判決でネット騒然「初犯で実刑4年!?」Xでもワード急上昇 [muffin★]
- GDP速報値は年率0.1%マイナス 4期ぶりのマイナス成長 個人消費は低調 ★2 [首都圏の虎★]
- 東京が「世界で最も魅力的な都市」1位に! 日本は国別で世界2位 北海道は「魅力的な地域」10位に [首都圏の虎★]
- 【速報】元ジャンポケ斉藤慎二被告に懲役4年の実刑判決 ★6 [Anonymous★]
- 【後だしジャンケン】インド高速鉄道は「日本の新幹線」を選んだはずが…「車両はインド製、信号はドイツ製」のワケ [煮卵★]
- 【テレビ】 ブラジル撃破 サッカー日本代表戦は高視聴率 18・0%! 瞬間最高23・6% 久保建英が結婚公表後初ゴール ★2 [阿弥陀ヶ峰★]
- 「検便」の時思わず出るセリフ
- 🤥ア...ア...
👕
👖
💩ポロッ
🏡
- 【悲報】日本の消費「コロナ前」を下回る [256556981]
- 【悲報】米中露「我々はファシズムジャップを倒すため共に戦った!」 [431136663]
- お前らの夜飯当てます!!!!
- かぼちゃって過小評価されすぎてると思うんやが...