先生方が若手だった頃に出した論文リンク集
先生方が若手だった頃に出した論文リンク集
最近ISerの中で進路の悩みが噴出しているのを感じます。かく言う私もヤバいです。先生方が修士/博士でどんなことをしていたかを調べるとイメージもつくかなぁと思い、リンク集をつくりました。
まぁ、強すぎて参考にならない説もあります。コンピューター科学専攻の修士論文が全体的に載っていそうなここも参考になるかもしれません。
本当は修士論文を中心に調べようと思ったのですが、東大の修士論文が載っているサイトへのリンクが切れているため博士論文が中心です。修士論文or博士論文を見つけられてなかった先生に関しては、強そうな論文を載せておきました。
修士論文等を実際に読みたい人は、理7号館の図書館に行くのが一番良さそう。
相澤彰子先生と高前田伸也先生の()は旧姓。横に付いてる年度は基本的には学位授与日だが、出版日のものもある。
高野明彦先生
2000 関数プログラムの融合変換
http://gakui.dl.itc.u-tokyo.ac.jp/cgi-bin/gazo.cgi?no=214832
相澤(中原)彰子先生
1990 プロトコルの形式記述によるネットワークの実現と評価に関する研究
http://gakui.dl.itc.u-tokyo.ac.jp/cgi-bin/gazo.cgi?no=108554
佐藤いまり先生
2005 写実的な画像生成のための光源環境推定と物体表面の見えの標本化
http://gakui.dl.itc.u-tokyo.ac.jp/cgi-bin/gazo.cgi?no=120547
今井浩先生
1983 ネットワ-ク算法による組合せ最適化問題の効率的解法
http://www.orsj.or.jp/~archive/pdf/bul/Vol.28_11_571.pdf
須田礼仁先生
1996 並列回路シミュレーションのための新しい反復線形解法の研究
http://gakui.dl.itc.u-tokyo.ac.jp/cgi-bin/gazo.cgi?no=212955
小林直樹先生
1996 並行線形論理プログラミング
http://gakui.dl.itc.u-tokyo.ac.jp/cgi-bin/gazo.cgi?no=212843
五十嵐健夫先生
2000 視覚的情報処理のための手書きインタフェースに関する研究
http://gakui.dl.itc.u-tokyo.ac.jp/cgi-bin/gazo.cgi?no=115222
杉山将先生
修士論文 1999 Incremental Active Learning for Optimal Generalization in Neural Networks
https://t2r2.star.titech.ac.jp/cgi-bin/publicationinfo.cgi?q_publication_content_number=CTT100596022
宮尾祐介先生
2006 言語理論から統語解析へ : コーパス指向の文法開発と素性森モデル
http://gakui.dl.itc.u-tokyo.ac.jp/cgi-bin/gazo.cgi?no=216489
吉本芳英先生
2000 Si(001),Ge(001)およびGe/Si(001)表面の温度と被覆度に依存する構造の第一原理計算による研究
http://gakui.dl.itc.u-tokyo.ac.jp/cgi-bin/gazo.cgi?no=114986
加藤真平先生
2008 マルチプロセッサシステム上の周期および非周期タスクの実時間スケジューリング
https://ndlonline.ndl.go.jp/#!/detail/R300000001-I000009361742-00
高前田(山崎)伸也先生
2014 Multi-FPGA based Prototyping Framework for Emerging Manycores
https://ndlonline.ndl.go.jp/#!/detail/R300000003-I9424758-00
佐藤一誠先生
2011 統計的機械学習における量子アニーリング http://gakui.dl.itc.u-tokyo.ac.jp/cgi-bin/gazo.cgi?no=127272
横矢直人先生
2013 ミクセル分解に基づくハイパースペクトルデータ融合
https://ndlonline.ndl.go.jp/#!/detail/R300000001-I025105855-00
2013年はデータベースの更新時期だったせいか、論文が載ってない。
東京大学学術機関リポジトリ(UTokyo Repository)(2013年度(平成25年度)-) 東京大学学位論文データベース(1957年度(昭和32年度)-2012年度(平成24年度))
石田隆先生
2017 補ラベルからの学習
https://repository.dl.itc.u-tokyo.ac.jp/records/49081
谷中瞳先生
博士論文がデータベースに登録されていない。
Yanaka, H., Mineshima, K., Bekki, D., & Inui, K. (2020). Do neural models learn systematicity of monotonicity inference in natural language?. arXiv preprint arXiv:2004.14839.
https://arxiv.org/abs/1906.06448
福里司先生
2016 デジタルコンテンツ作品におけるデザイナの技法再現及びインタラクティブな設計手法
https://ndlonline.ndl.go.jp/#!/detail/R300000003-I10952159-00
佐藤亮介先生
2013 高階関数型プログラムのソフトウェアモデル検査
https://ndlonline.ndl.go.jp/#!/detail/R300000001-I024934458-00
小野寺拓先生
2015 多様なポストゲノムデータのためのアラインメントフリーなアルゴリズムの構造
https://ndlonline.ndl.go.jp/#!/detail/R300000003-I10982068-00
黒木祐子先生
博士論文がデータベースに登録されていない。
Kuroki, Y., Miyauchi, A., Honda, J., & Sugiyama, M. (2020, November). Online dense subgraph discovery via blurred-graph feedback. In International Conference on Machine Learning (pp. 5522-5532). PMLR.
https://arxiv.org/abs/2006.13642
若桑江友里先生
2015 Information Theoretical Analysis of Distributed Quantum Computation
https://ndlonline.ndl.go.jp/#!/detail/R300000003-I10192063-00
検索につかったサイト集
https://repository.dl.itc.u-tokyo.ac.jp/?page=1&size=100&sort=controlnumber&search_type=0&q=0
博士論文は東京大学学位論文データベース(古い方)
http://gakui.dl.itc.u-tokyo.ac.jp/index.html?
一番安定して動く国立国会図書館オンライン←神
https://ndlonline.ndl.go.jp/#!/
使いにくい...
東大の新しい学位論文データベース、めちゃくちゃ使いにくくてつらい。つらい...
サイトが重くて固まりまくり。
windowのサイズのせいか、indexを選択できないバグ
cpu実験完動してません...
microUSBのケーブルやPCを弄ってcpu実験の通信速度を上げることは可能か
目次
- USBの仕様と今回の実験の器具
- PCの限界
- ケーブルの限界
- fpgaの限界
USBとは
- ユニバーサルシリアルバス通信
- ユニバーサル
- 全世界的!!! 汎!!!!
- シリアル
- シリアル通信。1ビットずつ送る。今回は通信線は2本
- バス
- 1つの信号線・通信線に複数のデバイスがぶら下がる構造のことらしい
microUSBについて
microUSBは5ピンあり、2本の差分でデータ、VCC,GND、そして周辺機器同士の通信用の線、で構成されている。
master/slave
USBには親子関係のようなものが強く存在しており、常にどちかであると定まらなければいけないようだ。周辺機器同士の通信用の線も、その子同士で通信するために儲けられたとのこと
器具
surface pro 6
ボードに付いてきたケーブル
ボード(nexys A7 100T)
https://www.xilinx.com/products/boards-and-kits/1-6olhwl.html
PC側のUART通信の限界
わからん。まじで。
USB controller
USB controllerなるものが存在し、cpuから命令を受け取ってコイツから通信線が出ているようだ。(https://www.itf.co.jp/tech/road-to-usb-master/devicecont)
windowsなので、デバイスマネージャーからUSB controllerの情報を漁って見る。すると、下の画像のような感じだった。
とりあえずベンダーID等でpcilookup.comを調べてみると出てきた。Intel製らしい。ここから仕様書とかに飛べるのかと思ったが、リンクはなく仕様書をググる。
仕様書はこれっぽいが、baud rateについての記述が特に無さそうだし、長いので諦めた。
あんま世の中の人が気にして無さそうだし無限の速度を出せるのでは。
ケーブルの通信速度の限界
ただの線でしょ?違いとかでるのか?と思い家にあったコードを付け替えてみると、通信が帰ってこない線があった。
そのようなケーブルは5本のピンのうち通信線2本をショートさせている。
https://direct.sanwa.co.jp/contents/sp/howtouse/how-usbcbl.html
fpgaボードの通信速度の限界
dmesgコマンドを叩いてみて、起動時のUSBに関する通信を見てみると、下のように出た。
[13325.509509] usb 7-2: new high-speed USB device number 6 using xhci_hcd [13325.663710] usb 7-2: New USB device found, idVendor=0403, idProduct=6010, bcdDevice= 7.00 [13325.663717] usb 7-2: New USB device strings: Mfr=1, Product=2, SerialNumber=3 [13325.663719] usb 7-2: Product: Digilent USB Device [13325.663721] usb 7-2: Manufacturer: Digilent [13325.663723] usb 7-2: SerialNumber: 210292B17F9A [13325.690118] usbcore: registered new interface driver usbserial_generic [13325.690128] usbserial: USB Serial support registered for generic [13325.693089] usbcore: registered new interface driver ftdi_sio [13325.693100] usbserial: USB Serial support registered for FTDI USB Serial Device [13325.693265] ftdi_sio 7-2:1.0: FTDI USB Serial Device converter detected [13325.693304] usb 7-2: Detected FT2232H [13325.693889] usb 7-2: FTDI USB Serial Device converter now attached to ttyUSB0 [13325.693909] ftdi_sio 7-2:1.1: FTDI USB Serial Device converter detected [13325.693918] usb 7-2: Detected FT2232H [13325.694459] usb 7-2: FTDI USB Serial Device converter now attached to ttyUSB1
上のFT2332HというICがfpgaボードに積まれているようだ。 これのdatasheet によるとFT2232Hの通信速度は12M baud rateが限界とのこと。
https://misoji-engineer.com/archives/usb-serial.html
結論
PCを変えても変わら無さそう。 ケーブルは充電専用のもの以外を使えば同じ。 ICまでなら12Mまで出る。
Pythonのint入門の入門
はじめにのはじめに
この記事は2020年ISアドベントカレンダーの7日目として書かれました。明日はハードウェア構成法の鬼テストななまる君の記事です。楽しみですね!
はじめに
書いた人
概要
目標と注意
- 目標はintを読むことですが、全体としてあまり筋道立っていない散漫な記事になりました。
流れ
- cpythonについて
- pyobjectたちについて
- intについて
pythonとcpython
pythonはいくつかの処理系を持ちますが、その殆どがcpythonです。
他の処理系も(pypy等)色々あります。下の記事によくまとまっていました。
「pypyはJITコンパイラを持ち、javaっぽくなって速い(??)」という話がありますが、Cで書かれたモジュールなどとの互換性を考えるとcpythonを使っておくのが丸そうです。
cpythonのデータ構造
では、実際にcpythonの中身を読んでみましょう!実装はここ(https://github.com/python/cpython )にころがっています。 intに行く前に、それの母体となるPyobjectから見ていきましょう。
Pyobject
この中の/include/object.hにすべてのオブジェクトの基となるPyobjectが書かれています。
#define _PyObject_HEAD_EXTRA \ struct _object *_ob_next; \ struct _object *_ob_prev; ...中略 typedef struct _object { _PyObject_HEAD_EXTRA Py_ssize_t ob_refcnt; PyTypeObject *ob_type; } PyObject;
構造体のメンバ変数を一つずつ見ていきましょう。
_ob_nextと_ob_prev
公式ドキュメントによると、
These fields are only present when the macro Py_TRACE_REFS is defined. Their initialization to NULL is taken care of by the PyObject_HEAD_INIT macro. For statically allocated objects, these fields always remain NULL. For dynamically allocated objects, these two fields are used to link the object into a doubly-linked list of all live objects on the heap. This could be used for various debugging purposes; currently the only use is to print the objects that are still alive at the end of a run when the environment variable PYTHONDUMPREFS is set. https://docs.python.org/3/c-api/typeobj.html
Py_TRACE_REFS が指定されているときかつオブジェクトのサイズが動的に変わる時に使われるということなので、debug時に何か働いてくれてるんでしょう。ちなみに僕はどう使われるか理解してません。ガハハ https://www.oreilly.com/library/view/python-cookbook/0596001673/ch16s09.html
ob_refcnt
参照カウンタ(このobjectが何回参照されているか)。pythonなら普通これが0になれば自動でオブジェクトが破壊されます。
ob_type
型が入っている。「こいつ(ob_type)の型」がPyTypeObjectなので、こいつの説明に入ります。
PyTypeObject
型に対応する関数とかモリモリ
定義
まずは、定義を見ると/include/obejct.hには
/* PyTypeObject structure is defined in cpython/object.h. In Py_LIMITED_API, PyTypeObject is an opaque structure. */ typedef struct _typeobject PyTypeObject;
とある。特にインクルードしてるファイルもないし_typeobjectについて上で書かれているわけでもないのでよく分からなかったが、/Include/cpython/object.hにそれっぽい実装があるのでそれを読むと
struct _typeobject { PyObject_VAR_HEAD const char *tp_name; /* For printing, in format "<module>.<name>" */ Py_ssize_t tp_basicsize, tp_itemsize; /* For allocation */ /* Methods to implement standard operations */ destructor tp_dealloc; Py_ssize_t tp_vectorcall_offset; getattrfunc tp_getattr; setattrfunc tp_setattr; PyAsyncMethods *tp_as_async; /* formerly known as tp_compare (Python 2) or tp_reserved (Python 3) */ reprfunc tp_repr; /* Method suites for standard classes */ PyNumberMethods *tp_as_number; PySequenceMethods *tp_as_sequence; PyMappingMethods *tp_as_mapping; /* More standard operations (here for binary compatibility) */ hashfunc tp_hash; ternaryfunc tp_call; reprfunc tp_str; getattrofunc tp_getattro; setattrofunc tp_setattro; /* Functions to access object as input/output buffer */ PyBufferProcs *tp_as_buffer; /* Flags to define presence of optional/expanded features */ unsigned long tp_flags; const char *tp_doc; /* Documentation string */ /* Assigned meaning in release 2.0 */ /* call function for all accessible objects */ traverseproc tp_traverse; ...略
100行を超えて居たのでこれのすべてを理解をするのは諦めるとして、分かるところだけをさらって分かった風に振る舞います
PyObject_VAR_HEAD
- pyvarobjectに必要なものを固めてるもの
- tp_name
- 型の名前でしょう
- getattrfunc
- get attribute functionの略っぽいので、属性(それに付随するメンバ関数やメンバ変数)をgetできるんでしょう
- ソース https://docs.python.org/ja/3/c-api/typeobj.html#c.getattrfunc
あまり慣習がわかっていなくて、cpython/Include/object.hをcpython/Include/cpython/object.hで使っていそうなのが自分には少し気持ち悪いです。
customな型の実装例
定義は上のような形でしたが、実際にcustomな型の実装例を見るのも良い気がしていて以下から引っ張ってきました。 https://docs.python.org/ja/3/extending/newtypes_tutorial.html#defining-new-types
少しだけ説明を加えます
PyObject_HEADは素のPy_objectである。
PyModule_Createで、引数に従ってモジュールを作ってる。
PyModule_Createのドキュメントも置いておきます。 https://docs.python.org/ja/3/c-api/module.html
#define PY_SSIZE_T_CLEAN #include <Python.h> typedef struct { PyObject_HEAD /* Type-specific fields go here. */ } CustomObject; static PyTypeObject CustomType = { PyVarObject_HEAD_INIT(NULL, 0) .tp_name = "custom.Custom", .tp_doc = "Custom objects", .tp_basicsize = sizeof(CustomObject), .tp_itemsize = 0, .tp_flags = Py_TPFLAGS_DEFAULT, .tp_new = PyType_GenericNew, }; static PyModuleDef custommodule = { PyModuleDef_HEAD_INIT, .m_name = "custom", .m_doc = "Example module that creates an extension type.", .m_size = -1, }; PyMODINIT_FUNC PyInit_custom(void) { PyObject *m; if (PyType_Ready(&CustomType) < 0) return NULL; m = PyModule_Create(&custommodule); if (m == NULL) return NULL; Py_INCREF(&CustomType); if (PyModule_AddObject(m, "Custom", (PyObject *) &CustomType) < 0) { Py_DECREF(&CustomType); Py_DECREF(m); return NULL; } return m; }
PyVarObject
既に何回か登場しているのですが、PyVarObjectの下位存在的な形でPyVarObjectというものが存在します。これをひな形にしてintやfloatなどが作られています。まずこの定義を見ましょう。
typedef struct { PyObject ob_base; Py_ssize_t ob_size; /* Number of items in variable part */ } PyVarObject;
PyObjectに一つ変数が追加された形になっています。 変数(variable)の構造体なのにob_size?それもNumber of itemsと言い始めるところが怖いですね。
intの実装
本題に入ります。まずはintのヘッダファイルから見てみましょう。 https://github.com/python/cpython/blob/master/Include/longintrepr.h
定義をみると
typedef uint32_t digit; struct _longobject { PyObject_VAR_HEAD digit ob_digit[1]; };
となっています。 「上から一つの桁に一つの数字が入る」というデータ構造をしている事がわかります。pythonのintは配列なんですね。
満を持してlongintrepr.cをみると、5740行あって泣く。あれ、というかcpythonを読もうとするたび毎回ここでやめていませんか?
アドベントカレンダー書く時ぐらいしか読まないと思うので少しだけ読むと、まずメモリの確保が出てきます。
_PyLong_New(Py_ssize_t size) { PyLongObject *result; /* Number of bytes needed is: offsetof(PyLongObject, ob_digit) + sizeof(digit)*size. Previous incarnations of this code used sizeof(PyVarObject) instead of the offsetof, but this risks being incorrect in the presence of padding between the PyVarObject header and the digits. */ if (size > (Py_ssize_t)MAX_LONG_DIGITS) { PyErr_SetString(PyExc_OverflowError, "too many digits in integer"); return NULL; } result = PyObject_Malloc(offsetof(PyLongObject, ob_digit) + size*sizeof(digit)); if (!result) { PyErr_NoMemory(); return NULL; } _PyObject_InitVar((PyVarObject*)result, &PyLong_Type, size); return result; }
MAX_LONG_DIGITSというのが環境に用意されていて、それでobjectを作るか決めたり、これはmallocで確保して、足りないときは云々...という処理に見える。
次に、longからpythonのlongを作る関数っぽいものがある。
PyLong_FromLong(long ival) { PyLongObject *v; unsigned long abs_ival; unsigned long t; /* unsigned so >> doesn't propagate sign bit */ int ndigits = 0; int sign; if (IS_SMALL_INT(ival)) { return get_small_int((sdigit)ival); } if (ival < 0) { /* negate: can't write this as abs_ival = -ival since that invokes undefined behaviour when ival is LONG_MIN */ abs_ival = 0U-(unsigned long)ival; sign = -1; } else { abs_ival = (unsigned long)ival; sign = ival == 0 ? 0 : 1; } /* Fast path for single-digit ints */ if (!(abs_ival >> PyLong_SHIFT)) { v = _PyLong_New(1); if (v) { Py_SET_SIZE(v, sign); v->ob_digit[0] = Py_SAFE_DOWNCAST( abs_ival, unsigned long, digit); } return (PyObject*)v; } #if PyLong_SHIFT==15 /* 2 digits */ if (!(abs_ival >> 2*PyLong_SHIFT)) { v = _PyLong_New(2); if (v) { Py_SET_SIZE(v, 2 * sign); v->ob_digit[0] = Py_SAFE_DOWNCAST( abs_ival & PyLong_MASK, unsigned long, digit); v->ob_digit[1] = Py_SAFE_DOWNCAST( abs_ival >> PyLong_SHIFT, unsigned long, digit); } return (PyObject*)v; } #endif /* Larger numbers: loop to determine number of digits */ t = abs_ival; while (t) { ++ndigits; t >>= PyLong_SHIFT; } v = _PyLong_New(ndigits); if (v != NULL) { digit *p = v->ob_digit; Py_SET_SIZE(v, ndigits * sign); t = abs_ival; while (t) { *p++ = Py_SAFE_DOWNCAST( t & PyLong_MASK, unsigned long, digit); t >>= PyLong_SHIFT; } } return (PyObject *)v; }
これがpythonのintの作り方として結構わかりやすそうですね。まず最初にabs_ival >> PyLong_SHIFT というif文でpylong_shift(一般に30桁)に収まるものはそれに収めて返しています。v->ob_digit[0]ということで、0桁目しか使っていないことが見て取れますね。次に、それにおさまらないものを桁数を増やしたりなどして収めて返している事がわかります。
いくつか飛ばして、doubleからpythonのlongを作るものが出て来ました。これは面白そうなので読むと
PyLong_FromDouble(double dval) { /* Try to get out cheap if this fits in a long. When a finite value of real * floating type is converted to an integer type, the value is truncated * toward zero. If the value of the integral part cannot be represented by * the integer type, the behavior is undefined. Thus, we must check that * value is in range (LONG_MIN - 1, LONG_MAX + 1). If a long has more bits * of precision than a double, casting LONG_MIN - 1 to double may yield an * approximation, but LONG_MAX + 1 is a power of two and can be represented * as double exactly (assuming FLT_RADIX is 2 or 16), so for simplicity * check against [-(LONG_MAX + 1), LONG_MAX + 1). */ const double int_max = (unsigned long)LONG_MAX + 1; if (-int_max < dval && dval < int_max) { return PyLong_FromLong((long)dval); } PyLongObject *v; double frac; int i, ndig, expo, neg; neg = 0; if (Py_IS_INFINITY(dval)) { PyErr_SetString(PyExc_OverflowError, "cannot convert float infinity to integer"); return NULL; } if (Py_IS_NAN(dval)) { PyErr_SetString(PyExc_ValueError, "cannot convert float NaN to integer"); return NULL; } if (dval < 0.0) { neg = 1; dval = -dval; } frac = frexp(dval, &expo); /* dval = frac*2**expo; 0.0 <= frac < 1.0 */ assert(expo > 0); ndig = (expo-1) / PyLong_SHIFT + 1; /* Number of 'digits' in result */ v = _PyLong_New(ndig); if (v == NULL) return NULL; frac = ldexp(frac, (expo-1) % PyLong_SHIFT + 1); for (i = ndig; --i >= 0; ) { digit bits = (digit)frac; v->ob_digit[i] = bits; frac = frac - (double)bits; frac = ldexp(frac, PyLong_SHIFT); } if (neg) { Py_SET_SIZE(v, -(Py_SIZE(v))); } return (PyObject *)v; }
値がある程度小さければCのlongに直してから、pythonのlongになおしていますね。 次に無限大の判定等をしていますが、これはC由来ののisinfを使っているようです。(cpython/Include/pymath.h) 計算機システムやパタヘネでやった事が出てきて嬉しいですね。 frexpはC++とかにあるやつと同じで浮動小数点をx * 2**nの形に分解していそうです。 そう考えると、pylong_shift(一桁あたりのbit数)乗で区切って、これをob_digitに一桁ずつ入れていくところが見て取れます。 https://cpprefjp.github.io/reference/cmath/frexp.html#:~:text=frexp%20%E9%96%A2%E6%95%B0%20
PyLong_SHIFT
これは自分が誤解をしているかもしれないのですが、こいつがpythonのintのそれぞれの桁に入りうるbit数を司っていると思って自分は生きています。最初の方のifdefを見ると一般にこれが30であることが推測され、此の時「30bitずつが一桁」になります。 colaboratoryでの実験結果を置いておきます。
floatの実装
typedef struct { PyObject_HEAD double ob_fval; } PyFloatObject;
doubleです。特になし。 https://github.com/python/cpython/blob/ae00a5a88534fd45939f86c12e038da9fa6f9ed6/Include/floatobject.h
終わりに
いかがでしたか?C++もpythonも無知なので、どこか間違っていたらすいません。よく考えたら自分は去年のこれぐらいの時期も同じことをしていました。去年からほんの少ししか理解が進んでい無さそう... 来年も同じことしてるかもしれません。来年の自分さん、来年のadvenr calenderはpythonのlistの実装あたりでどうですか。