プログラミング課題とLLM
東京大学情報基盤センター 田中哲朗

背景(自己紹介)-

田中哲朗 東京大学情報基盤センター情報メディア教育研究部門
プログラミング教育--

1年生を主な対象にした「アルゴリズム入門」 (関連授業も含めて 1997年から)，教養学部学際科学科 3年生 「情報数理科学 2」という名前 「データ構 」 授業 (2013年から)．
ACM-ICPC審判委員 (2003 - 2016, うち2010, 2014 審判長)

研究-

プログラミング言語処理系 (UtiLisp/C)
漢字フォント(和田研フォント由来 フォントが今でも amazonで発行する明細書ている)
ゲーム情報学 (どうぶつしょうぎ， GPS将棋など)- openai 強化学習 フレームワーク openai gym で馴染み

PDFなどで使われ

LLMでプログラミング課題が解ける
●

LLM
○
○
○

●

○

●

プログラミングと相性が良い?
自然言語よりも予測しやすい ?
LLMを作る人たちも自分が使えると便利な対象として選んでいる ?
プログラミングコンテストサイト 問題を解かせる課題もある程度対応

LLMで多様性○ある解答を作成可能

同一性 判定 みで 判定できない (自分が手元で LLMで作成した解答といつも同じ解答が出るわ
けで ない)．
「プログラム 説明を書かせる」ことで，プログラムを理解しているどうかをチェックさせる もことも可能

田中が担当した実際○○

か?

アルゴリズム入門
情報数理科学 2

講義

プログラミング課題で例をみていく．

「アルゴリズム入門」●●●●

プログラミング経験がない受講者も対象にした情報科学入門講義
受講者 100名(全教員で1000名程度?)程度，1年生が主，一部2年生，クラス指定で基本
容教科書 森畑 明昌著「Pythonによるプログラミング入門東京大学教養学部テキスト」
2018年からPython言語を用いる
○

●
●

授業概要

プログラミング環境
Google Colab2018-2019

教育用計算機システム

iMac環境で同じ内

Jupyter Notebookがメイン，2020から

対面試験を実施
評価 一部に課題を用いる．
○

絵やアニメーションを描くプログラム (2次元画像 配列あるい ，画像フレーム 配列を作成する )を除くと，決まりきった課題．
■
教科書 練習問題から 出題が多い．
■
2018年から課題チェックプログラムを使って提出前にチェック可能 (提出自体 ITC-LMS 掲示板機能で)■2020年から東京大学MIセンター 佐藤先生作成 PLAGS UTを使って提出

2022年度アルゴリズム入門で田中が用いた課題
●

11回
○
○

●

プログラミング課題を出題．

うち1回 ，画像あるい 動画を作成するプログラムを ITC-LMSで提出させるも ．
残り10回 PLAGS UT 練習問題を提出するも (難易度が低いも を中心に全 12題)．

13題を ChatGPT (GPT-4使用)で解かせてみる．
○○○○

GPT-4 課金が必要 (研究目的で登録 )GPT-4 コーディング能力が低下したということだが，試した
2023年7月
プロンプト 「 以下 問題にPython言語で解答しなさい．」
問題文 数式 ， $$ \frac{a(r^n-1)}{(r - 1)} $$ ように，LaTeX 数式で与える．

○

英語で入力した方が解答 精度が良いこともあると ことだが，日本人学生が使用することを想定して，プロンプトも含めて日本語で問題文を与える．
1回 試行 み(統計的に意味 ある結果を得ているわけでない)，毎回リセットせず続けて問題を入力(他 問題
入力が解答に影響することも)

○

結果
問題

結果

ex03_1○ex03_2○ex03_4○ex04_2△ex04_3○ex04_7○ex04_8△○ex05_2✕△○ex06_2○ex07_2○ex07_4△ex08_4

○

画像あるい

動画

△

追加指示後結果

○

○

出力例

正解例
入力
以下 問題にPython言語で解答しなさい．
Ex08_4(難易度☆☆☆) リスト xと整数n（$1 \le n \le(x 長さ)$）が与えられたとき、x中 小さい方からn個（ $n \ge 1$) 要素を抽出する再帰関数ex08_4を定義せよ。 こ 関数 、併合整列法を参考にして、リストを再帰的に分割し、それぞれ 部分 小さ
い方からn個 要素を抽出し、それを併合してゆくことで最終的な結果を得るも とせよ。なお、x中に同じ大きさ 値が複数あったとしても、それら 別 も としてよい。例え 、[2,1,2,1,3]から3個抽出する場合、結果 [1,1,2]となる。なお、結果として出力される要素 値 小さい順に整列すること。（教科書練習問題
8.5）
import ita
def ex08_4(x, n):...

こ 問題 ため 関数 併合整列法を使用する で、まず、リストを 2つ リストに分割します。それから、再帰的に分割したリスト それぞれに対して同じ操作を行います。それぞれ 再帰呼び出しから返された結果をマージしますが、各マージ操作で 最小 n個 要素だけを維持します。
以下に、そ ため Pythonコードを示します。
def ex08_4(x, n):if len(x) <= 1:
return xelse:
mid = len(x) // 2
left = ex08_4(x[:mid], n)right = ex08_4(x[mid:], n)return merge_min_n(left, right, n)
def merge_min_n(left, right, n):result = []i=j=0while i < len(left) and j < len(right) and len(result) < n:if left[i] <= right[j]:result.append(left[i])i += 1else:
result.append(right[j])j += 1
while i < len(left) and len(result) < n:result.append(left[i])i += 1
while j < len(right) and len(result) < n:result.append(right[j])j += 1
return result
こ コードで 、 ex08_4関数がリスト xを分割してそれぞれ 部分に対して再帰的に同じ関数を適用します。結果として得られる 2つ リスト merge_min_n関数に渡され、そこで最小 n個 要素を持つリストが作られます。マージ操 作
リスト 要素が尽きるか、 n個 要素がマージされるまで続きます。

追加指示で正しい説明を誘導した問題(1)出力例

入力以下に求めるプログラムを提供します。また、こ アルゴリズム 計算量についても説明します。

以下

問題にPython言語で解答しなさい．

Ex07_2 (難易度☆☆)$a^n$ 以下 漸化式を満たす。
$$ a^0 = 1 $$$$ a^{2n} = (a^n)^2 $$$$ a^{2n+1} = a \cdot (a^h)^2 $$こ 漸化式に基づき、数aと正整数nをこ 順に入力にとり、$a^n$を求める再帰関数ex07_2を定義せよ。（教科書練習問
題7.4）
プログラムを作成するだけでなく，「計算量を見積もる過程と，そ 結果をO記法」で表して解答セル コメント（#で始まる行）で表してください．整数同士 乗算 結果 ビット数がある程度よりも大きくなると時間がかかる で，計算量 見積
もり 際に aを小数と仮定して解答してください．

プログラム 正しいが， aが実数でdef ex07_2(a, n):
if n == 0:
return 1
elif n % 2 == 0:
return ex07_2(a, n//2) ** 2
else:
return a * (ex07_2(a, n//2) ** 2)
上記 関数 再帰関数であり、入力値 n が0でない限り、自分自身を呼び出しています。そ 際に、 n を2で割った商を新たな n 値として再帰呼び出しを行っています。こ ため、こ 関数 計算量 、入力 大きさ n
を2で何回割ることができるか、つまり、 n 2進表現 桁数に比例します。そ ため、こ 関数 時間計算量$O(\log n)$ となります。
乗算について 、一般に二つ 整数 乗算 それら ビット数に比例する時間がかかります。そ ため、こ関数で 、 a ビット数と n ビット数 積に比例する時間がかかる乗算を行っています。したがって、こ 関
数 時間計算量 $O((\log a) \cdot (\log n))$ となると言えます。
ただし、こ 見積もり 最悪ケース 時間計算量を見積もるも であり、平均ケースや最良ケース 時間計算量を見積もるも で ありません。また、こ 見積もり 漸近的な計算量を見積もるも であり、具体的な入力
値 サイズに対する正確な実行時間を予測するも で ありません。

なく整数だと思っている．また， aが整数だとしても，正しくない．

追加指示で正しい説明を誘導した問題(2)入力

出力例
おっしゃる通り、入力 aが実数である場合にありません。再考します。

、ビット数に基づく考察が適切で再帰的に計算を行うときに、 nが偶数か奇数かによって二つす。

こ 問題で ，入力 aを小数(実数)と仮定している で，結果も実数であり，a ビット数が時間計算量に影響する
おかしい で ないでしょうか?

計算パスがありまnが偶数 場合、 nを半分にして同じ計算を繰り返します。こ たび 計算
a べき乗 計算（一回 乗算）です。
nが奇数 場合、 nを半分にした後に同じ計算を行い、そ 後に aを掛けます。こ 計算パスで 乗算が二回行われます。
こ アルゴリズム 、 nを半分にして計算を進めていくため、計算回数（再帰 深さ） おおよそ log(n)となります。各ステップで行われる乗算 回数 一定（最大で2回）であるため、全体としてこ アルゴリズム 時間計算量
O(log(n))と評価されます。

正しい説明になっている．

不正解だが追加指示で正解した問題(1)入力
以下問題にPython言語で解答しなさい．

正 整数 nが与えられたとき n行 n列 市松模様を生成する関数ex05_2を定義せよ。左上隅が白（つまり1）、それに隣接するマスが黒（つまり0）となるようにせよ。画像を表示
する で なく、画像に対応する2次元配列を作る関数とせよ。（教科書練習問題5.3）
import ita
def ex05_2(n):...

説明 前半で 行番号と列番号 和が偶数 場合明していて，プログラムもそ ようになっている．

出力例
こ 問題で 、与えられた正 整数n 値に基づいて市松模様を生成する2次
元配列を作成する必要があります。ここで 、Python 内包表記を使用して、配列を生成します。
各セル 、そ 行番号と列番号が偶数また 奇数であるかによってそ 値が決まります。具体的に 、行番号と列番号 和が偶数 場合 値が1、奇数
場合 値が0となります。
こ ロジックを用いて、問題 関数を次 ように定義します。
def ex05_2(n):return [[(i + j) % 2 for j in range(n)] for i in range(n)]こ 関数で 、内側 リスト内包表記(i + j) % 2 for j in range(n) が各行を生成し、外側 リスト内包表記[(i + j) % 2 for j in range(n)] for i in range(n) が全体配列を生成します。
ここで、 (i + j) % 2 行番号 i と列番号 j 和を2で割った余りを計算します。こ値 、 i と j 両方が偶数また 奇数である場合（つまり、i と j 和が偶数である場合） 0、一方が偶数で一方が奇数である場合（つまり、i と j 和が奇数である場合） 1になります。これにより、市松模様が生成されます。

値が 1になることを理解しているが，後半で0になると説不正解だが追加指示で正解した問題(2)
追加指示

行番号と列番号 和が偶数 時に0でなく1になるようにプログラムを修正してください．

出力例
了解しました。行番号と列番号 和が偶数 時に1になるように、条件を逆にします。具体的に 、 (i + j) % 2 結果を1から引くことで、0と1が反転します。修正した関数 以下 ようになります。
def ex05_2(n):return [[1 - (i + j) % 2 for j in range(n)] for i in range(n)]こ 関数で 、 (i + j) % 2 が0なら 1 - 0 となり1に、 (i + j) % 2 が1なら 1 - 1 とな
り0になります。したがって、行番号と列番号 和が偶数 場合 1、奇数場合 0となります。

指示に従って，正しいプログラムを出力している．
なお，これに更に「 2次元配列を作成する に，リスト 内包表記を用いずに関数 ita.array.make2dを用いたもに修正してください．」という指示を加えると，リスト 内包表記を用いない想定解を出力する．

自由に画像を出力させる問題
入力
第1-6章まとめ課題 自分 好きな図あるい アニメーションを描くプログラムを書
いて，NotebookファイルをITC-LMSで 第1-6章まとめ課題に投稿して下さい． 第5章 練習問題にある図でも良いし，自分で工夫して考えた図でも良いです． なるべく ita.plot.image_show また
ita.plot.animation_show で画像，動画を表示するプログラムを作成してください(ヒントとして，簡単な静止画像を作成するプログラム，簡単なアニメーションを作成するプログラムを提示するが省略 )出力例

以下に、画像を生成するシンプルな関数を作成しました。
こ 関数 、ピクセル RGB値を座標に基づいて計算します。これにより、縦方向に グリーンからブルーへ、横方向に レッドからマゼンタへ変化するグラデーション画像が作成されます。さらに、経過時間によってグラデーション 色調が変化するアニメーションを作成します。
まず、静止画像を生成する関数を作ります。
def show_color_picture(t):a = ita.array.make3d(50, 50, 3)
for y in range(50):for x in range(50):a[y][x] = [x / 49, 1 - y / 49 + t / 10, t / 10]
return a
ita.plot.image_show(show_color_picture(0)) # t = 0で画像を表示

こ 関数 、画像 各ピクセルについて
RGB値を計算します。R値 x座標に基づいているため、画像 左から右へとレッドからマゼンタに変化します。
G値 y座標に基づいており、画像 上から下へとグリーンからブルーに変化します。
B値 時間に基づいており、t値によって色調が変わります。
次に、こ 関数を使ってアニメーションを作ります。
def show_animation():images = ita.array.make1d(10)for t in range(10):images[t] = show_color_picture(t)return images
ita.plot.animation_show(show_animation())
こ 関数 、show_color_picture(t)を呼び出して時間ごとに画像を生成し、それら 画像を配列に格納します。そ 結果 配列を
ita.plot.animation_show()に渡すことでアニメーションを表示します。アニメーションで 、時間 経過とともに色調が変化します。
ご指定 itaライブラリ 関数 私が模擬的に説明しており、実際にると、同様 結果を得ることが可能です。

サンプル 数値を変更しただけ，面白くないプログラム．

実行できないことをご了承ください。ですが、Python PILやmatplotlibなど ライブラリを用い

「アルゴリズム入門」
●
●
●
●
●

13題 プログラミング課題 うち12題に最低限 プロンプトで正しいプログラムを出力する．
残り 1題も誤り 指摘に対応して正解．
プログラムが正しいだけでなく，プログラム 説明も概 適切だが，計算量 オーダーを解答させる問題 ，誘導が必要な場合がある．
想定解と異なる出力が出たときも，追加 指示を出せ 想定解に誘導可能．
自由に画像を出力させる問題で ，ヒントとして出したサンプルとほぼ同じ内容だった で，評価 低い(授業で ，「相互評価」として受講者同士 評価を点数 一部に用いた)．
○

●
●

課題まとめ

「サンプル」が「制約」と解釈された?

もともと，課題 評価で大きな差 つけないが，受講者 平均レベル 達成．
プログラムだけを見て，LLM 出力をそ まま出したも かどうかを判定すること ，困難「情報数理科学2」 授業 概要●●

受講者 教養学部学際科学科総合情報コース3年生が主，一部4年生や他コース，他学科，他学部
教科書 Pat Morin著 「Open Data Structures」○○○

Creative Commonsで公開されており， Java版，C++版，擬似コード (ほぼPython)版
内容 一般的な「アルゴリズムとデータ構 」■ ただし，Skiplistを扱う，binary treeでparentを持つ，red black treeを扱う(特にleft leaned red
black tree), singly linked listでFIFO queueを実現することなどが特徴的■ Java版をもとにC++版が作成されたため，通常 C++プログラミング的に 不自然な点もあり，
授業で C++版をベースに独自に修正したも (本家でPRが採用されなかったも )を使用
英語を読んでもらうという意図もあったが，過去 受講者が 日本語訳を作成，出版．

「情報数理科学2」 課題概要
●

6回

課題を出題

○

教科書 章末 練習問題 数題 うちから選択して解答■ 2023年度 計18題からプログラミング課題と説明課題 (図を用いて説明させるも を含む )プログラミング課題 プログラミング言語を問わず (教科書 派生版が公開されているも に限る )■ 2022年度 Rust で解答した受講者もいた． 2023年度 半数近くが Pythonで解答○○●

チェック用プログラムを配布
○

●

提出
○

tar.gz (C++版)および，Google Colabで実行可能な Notebook (C++版，Python版)を配布．

LMSを用いてファイルで提出
Notebook, pdf, テキストファイル， zipファイルなど

ChatGPT (GPT-4使用)を使って解かせてみる
●

プロンプト

以下 Exercise ??にC++言語で解答しなさい．なお，ファイル入力をおこなうときにを定義する際 ，要素 型をテンプレート引数で与えること．

，入力 標準入力から与えられると仮定せよ．データ構

なお，出題者から 以下 ヒントが与えられている．
(問題ごとに受講者に与えるヒント，サンプルプログラムなど )また，(データ構

名)

以下(教科書や配布プログラム中
Exercise ??
(教科書 練習問題●

ように実装されている．
データ構

英文．数式

C++クラス定義 )LaTeX形式で)図を参照しているときも，与えることができないで，「 Figure ?.? 」などをそ まま残す．

結果

Exercise

結果

1.1

○

2.2

○

2.3

△

2.7

○

3.4

○

3.7

○

3.14

○

4.5

✕

4.11

○

4.12

✕

5.5

✕

説明問題

5.7

△

説明問題

6.4

✕

✕

6.5

✕

✕

6.14

○

7.1

✕

図を入力，図を出力

7.3✕

図を入力，図を出力

7.4○

追加指示後結果

備考

○

図

入力が必要

○

正解例

入力

以下 Exercise 3.4にC++言語で解答しなさい．なお，ファイル入力をおこなうときに ，入力 標準入力から与えられると仮定せよ．データ構 を定義する際，要素 型をテンプレート引数で与えること．
なお，出題者から 以下 ヒントが与えられている．
Exercise 3.4ヒント
Exercise 3.4 "should not use any secondary data structures, and should not create any new nodes." という条件を満たす必要がありますが，report3.tgz
中に含まれるSLList.h 中からincludeされているex3_4.h ，void reverse(){...
} //Ex3_4
ように，こ 条件を満たしていませんが(temp というsecondary data structureを使っている，new Nodeと 動きます．

ところで，create new nodesを実行している)，動くこ

また，SLList.h 以下 ように実装されている．
....
Exercise 3..4 Design and implement an $ \mathtt{SLList}$ method, $ \mathtt{reverse()}$ that reverses the order of elements in an $ \mathtt{SLList}$. Thismethod should run in $ O(\ensuremath{\mathtt{n}})$ time, should not use recursion, should not use any secondary data structures, and should not create
any new nodes.

「...」部分 省略

正解例(出力)以下に、SLList メソッドであるreverse()を実装します。こ 実装 O(n)時間で動作し、再帰を使わず、補助的なデータ構 を使わず、新しいノードを作成せずにリスト 要
素 順序を逆にします。
template<class T>
void SLList<T>::reverse() {if (n == 0) return;Node *prev = NULL;
Node *current = head;
Node *next;
while (current != NULL) {next = current->next; // temporarily store the next nodecurrent->next = prev; // reverse the link
prev = current;// move pointers one position ahead
current = next;}// Swap head and tailNode* temp = head;
head = tail;tail = temp;}
こ reverse()メソッド 、現在 ノード(current)とそ 前 ノード(prev)、そしてそ 次 ノード(next) 三つ ポインタを使用します。各反復で 、現在 ノード nextポイン
タを前 ノードを指すように更新します。そして、すべて ポインタを一つ前に進めます。こ 処理をリスト 終端(NULL)まで続けると、リンク 向きが逆になります。
最後に、headとtail

ポインタを交換します。これでリスト

Singly Linked List reverseというる．

順序が反転します。

よく知られた問題だが，FIFO queueとするために，tailも持つというこ 教科書独自

仕様に従って，正しく書き換えていプログラミング問題

不正解例(入力)

以下 質問に回答してください．
また，教科書 以下 プログラムを参考にすること．
int size2() {Node *u = r, *prev = nil, *next;
int n = 0;
while (u != nil) {if (prev == u->parent) {n++;if (u->left != nil) next = u->left;
else if (u->right != nil) next = u->right;
else next = u->parent;} else if (prev == u->left) {if (u->right != nil) next = u->right;
else next = u->parent;} else {next = u->parent;}
prev = u;u = next;}
return n;}
Exercise 6..4 Implement a non-recursive method, $ \mathtt{size2(u)}$, that computes the size of the subtree rooted at node $ \mathtt{u}$.

入力として，rootから non recursive traversal

サンプルみを与えた．

プログラミング問題

不正解例(出力)

上記 size2()メソッド 、二分木 サイズ（ノード 数）を非再帰的に計算します。これ ルートノードから開始し、子ノード（左また 右）が存在する場合 そ 方向に進み、子ノードがない場合 親ノードに戻ります。そして各ノードを一度だけ訪問し、訪問する度にカウンタ nを増加させます。
こ 関数を用いて特定 ノード uから始まる部分木 サイズを計算する size2(u)メソッドを実装します。こ 方法で 、開始ノードを uに変更し、終了条件を u != nilからu != u->parentに変更します。これにより、関数 u 部分木を訪問し、そ サイズを計算します。
以下に該当 コードを示します。
int size2(Node* u) {Node *prev = nil, *next;
int n = 0;
while (u != nil && (prev == nil || u != prev->parent)) {if (prev == u->parent) {n++;if (u->left != nil) next = u->left;
else if (u->right != nil) next = u->right;
else next = u->parent;} else if (prev == u->left) {if (u->right != nil) next = u->right;
else next = u->parent;} else {next = u->parent;}
prev = u;u = next;}
return n;}
ここで、 nil 通常NULLまた nullptrを指し、 Node 適切な型と仮定します。また、こ コード
uが有効なノードポインタであると仮定します。そ ため、無効な値を渡さないように注意が必要です。

受講者にもよくあることだが，while 終了条件を間違えている．こ あと，どう指示を与えても正解できなかった．ただし，最初にrootから non recursive
traversal サンプルを与えないと，△ 解答を出すことがある．

図を入出力とする不正解例(入力)Exercise 7..1 Illustrate the addition of 4.5 (with priority 7) and then 7.5(with priority 20) on the $ \mathtt{Treap}$ in Figure 7.5.

図

与えない

図を入出力とする不正解例(出力)Figure 7.5に対応するTreap（優先度付き二分探索木）を描画できない で、私 テキストを用いて操作 進行を説明します。
最初に4.5（優先度7）を追加します。これ 現在 Treapにおいて、値が4と5 間に位置します。4.5を追加した後、こ ノード
親（値が4、優先度5）よりも高い優先度を持つため、右回転を行います。これにより、4.5（優先度7）が親ノードとなり、元親であった4（優先度5）がそ 左 子ノードとなります。
次に7.5（優先度20）を追加します。こ 値 Treap 最大値よりも大きいため、最右部に位置するノードになります。しかし、7.5（優先度20） 全て ノードよりも高い優先度を持つため、ルートノードになるまで左回転を続けます。
以上 操作により、4.5と7.5がTreapに追加され、優先度 順序が保たれます。ノード 追加と回転により、Treap 二分探索木 性
質（左 子 親より小さく、右 子 親より大きい）とヒープ 性質（親 子より優先度が高い）を維持します。
なお、具体的なTreap 状態 問題 内容やFigure 7.5 状態に依存します で、正確な状態を理解するに それら 情報が必要となります。

図 7.5を適当に仮定して，解答を生成している．

説明問題 不正解例(入力)以下 質問に日本語で回答してください．なお，出題者から 以下 ヒントが与えられている．
Exercise 5.5 ヒント「giving an example of a sequence of 𝑂(𝚗) 𝚊𝚍𝚍(𝚡) , 𝚛𝚎𝚖𝚘𝚟𝚎(𝚡) , and 𝚏𝚒𝚗𝚍(𝚡) operations 」にあるようなadd, remove, find 列 パターンを与えた上で，「take on the order of n2 time to execute.」であることを説明する．そ 際に，教科書中 プログラム add で ，そ ような問題が起きないことも確認すること．
また，教科書 プログラムadd, find 以下 コードである．
...
Exercise 5..5 Consider the following simplified version of the code for adding an element $ \mathtt{x}$ to a $ \mathtt{LinearHashTable}$, which simply stores$ \mathtt{x}$ in the first $ \mathtt{null}$ array entry it finds. Explain why this could be very slow by giving an example of a sequence of $O(\ensuremath{\mathtt{n}})$ $ \mathtt{add(x)}$, $ \mathtt{remove(x)}$, and $ \mathtt{find(x)}$ operations that would take on the order of $\ensuremath{\mathtt{n}}^2$ time to execute.
bool addSlow(T x) {if (2*(q+1) > t.length) resize(); // max 50% occupancy
int i = hash(x);while (t[i] != null) {if (t[i] != del && x.equals(t[i])) return false;i = (i == t.length-1) ? 0 : i + 1; // increment i}t[i] = x;n++; q++;return true;}説明問題 不正解例(出力)
ここで 問題 、addSlow(T x)メソッドがハッシュテーブル ある範囲が満杯になる状況を引き起こし得ることにあります。
addSlow(T x)メソッド 、与えられた要素xをハッシュテーブル 最初 nullエントリに格納します。しかし、これ ハッシュ値が衝突した場合、ハッシュテーブル内
連続するセグメントがすぐに満杯になる可能性があることを意味します。
具体的な操作 シーケンスとして 以下 ようなも が考えられます：
n回 addSlow(x)操作を行い、特定 ハッシュ値 周辺にn個 アイテムが集まります。こ ステップで 、ハッシュ値が衝突するため、各
addSlow(x)操作 ハッシュテーブル 一部が既に満杯であるためO(n) 時間がかかります。
次に、上記で追加したn個 アイテムをすべて削除（remove(x)）します。こ とき、ハッシュテーブルで 実際に nullに置き換えられずにdelマーカーに置き換えられます。
最後に、上記で削除したアイテムを探す（find(x)）操作をn回行います。各検索操作 、ハッシュテーブル 該当するセグメントがdelマーカーで満たされているため、O(n) 時間がかかります。
以上から、全体 操作 O(n^2) 時間がかかることがわかります。n回 addSlow(x)、remove(x)、そしてfind(x) 各操作がそれぞれO(n) 時間を必要とします。
これ addSlow(T x)が最初 nullエントリを使用するために、特定 ハッシュ値周辺が満杯になる可能性があるためです。
一方、教科書 add(x)メソッドで こ 問題 生じません。なぜなら、こ メソッドで 新たな要素が追加される際に、最初に見つかった
nullエントリで なく、ハッシュ関数によって計算された位置か、そ 位置が既に占有されている場合 そ 次 nullエントリを使用します。これにより、特定 ハッシュ値 周辺が急 に満杯になるという事態 避けられます。したがって、
add(x)メソッドで O(1) 時間で操作を完了することができます。
また、find(x)関数もadd(x)関数と同様に、ハッシュ関数によって計算された位置から検索を開始し、nullエントリに達するまで順次探索を進めます。こ ため、特定ハッシュ値周辺が満杯になるという事態が発生したとしても、
O(n) 時間複雑度を保証できます。

受講者 レポートにもよくある誤り．別々場合 addも同様にO(n^2)かかる．

オブジェクトがハッシュ値 衝突を起こすことが前提となるが，こ受講者へ LLM
●

出題時
○
○

●

指示

LLM 利用 禁止しない
LLMを利用した時に 使用した ダイアログを提出すると評価する

解答者○

使用について

LLMへ

言及「アルゴリズム 仕組みとコード ChatGPTを参考にした。」という が1件．ダイアログ 提供されず．
■

プログラム 少なめ

プロンプトでChatGPTが解答する内容と一致．コメント

独自．

「情報数理科学2」●●●

18題 課題 うち9題に追加 指示なしに一応正解する．
図 入力，図 出力 現在 非対応(3題)
教科書 データ構 について ，与えなくても解答できることもあるが，与えた方が解答しやすい．
○

●
●

課題まとめ

一般的でないデータ構について，追加で指示を出しても正解に至らないこともある．

説明問題もあまり一般的でない設問で 正解できないことも．
学習に教科書 「Open Data Structures」が使われている可能性もある．
○○

CC by CAな でLLM学習 入力に使える ず．
ChatGPTに著者が誰かを英語で聞いてみると答えてくれる．

○

不正解 プログラム 断片に， Open Data Structures部を参考にしていると思われるも が出ることが．

別 データ構 で使われたコード

一プログラミング課題とLLM●

好ましくないLLM○●●

内容を理解しなくても課題

好ましい(あるい
○
○

利用
今後

説明を LLMに入れて，出力をそ まま提出避けられない)LLM

利用

自分 作成したプログラム 修正を LLMと対話してデバッグ
関連資料をどこで探すか LLMにアドバイスを求める．

プログラミングで何が重要かが変わってきた と同様に，今後も変わること 避けられない か．
○○○○

機械語 -> アセンブリ言語
アセンブリ言語 -> 高級言語
型チェック，IDE等々
github copilotを入れると def fib(n): まで入れるとフィボナッチ数を求める関数 補完を提案する．

LLMに対応したプログラミング課題
●

図 入出力
○
○

●

自分で例を作らせて説明する．
○●

設問自体がありふれている場合もあり，そ 場合 無効，学習データ 中に同じように例を作って説明させる文が含まれている場合

一般的な課題とずらした内容○●

2023年7月現在 多く 対話式LLM 図 入出力をサポートしていない で，図 入出力をおこなう課題に対応できない．
あくまで現在 話，そ うち，「人間が見て分かる図 だいたい理解できる」ようになっても不思議 ない．

「フィボナッチ数列」以外 漸化式，通常と 変わった関数名，引数等，対応可能な場合も，どれを入力に含めるかなどが難しいLLMに正解を出させるため○入力を作成させる課題

問題を解かせるために，ど ような前提を与えなけれ「好ましくないLLM

いけないかを考えさせることも勉強になる?

利用」を受講者がしようと思わないような授業をすることが必要