imported>Bauwens: Migrated current public revision from wiki.cs.hse.ru

2024-12-25T20:48:26Z

Migrated current public revision from wiki.cs.hse.ru

Новая страница

= Classes =

Lectures + seminar: Friday 18h10 -- 21h00 in Pokrovkaya room G405 ([https://docs.google.com/spreadsheets/d/1ldM3vgMHX9YFC695JfL1ImtkYgVuO1mAiEHjC_6y72E/edit?gid=0#gid=0 electives-shedule]) and in [https://us02web.zoom.us/j/82300259484?pwd=NWxXekxBeE5yMm9UTmwvLzNNNGlnUT09 zoom]. The teacher is [https://www.hse.ru/en/org/persons/160550073 Bruno Bauwens].

Telegram group for announcements and discussions [https://t.me/+inFR7m-mzzphZDU0 invite link.]

= Course Materials =

{| class="wikitable"
|-
! Rec !! Summary !! Notes !! Problem list !! Solutions
|-
|| [https://www.youtube.com/watch?v=0m7RXtisu5w 04.10] || Course overview, (universal) Turing machines, computable and non-computable sets and functions. [https://www.dropbox.com/scl/fi/0fxjeu8h1ekawcueto4yn/01slides.pdf?rlkey=ww3ec2ngtoysexwoc6wahcfg4&st=7t55t5bi&dl=0 slides.pdf] || [https://www.dropbox.com/scl/fi/n1vhfvtfagv2ji6x30exn/00notes.pdf?rlkey=pvd79gi91567mut35n87j1vfo&st=ypsaw36s&dl=0 ch00] [https://www.dropbox.com/scl/fi/cm2xfnegccktu3s7h00wy/01notes.pdf?rlkey=87ctjsio681ee821tzlomufqp&st=jvdlwdnn&dl=0 ch01]|| [https://www.dropbox.com/scl/fi/2alcydgfglcxs8rst99kk/01sem.pdf?rlkey=pe1xwmex19wi32bppr5s4bmdz&st=mzww1qix&dl=0 sem01] ''update 11.10''|| [https://www.dropbox.com/scl/fi/9y5fzpuvawpdcvrupj9zi/01sol.pdf?rlkey=5lni39fv1c7xpgufhtpl6typu&st=vutbaar2&dl=0 sol01]
|-
|| [https://www.youtube.com/watch?v=p6vKnnPfVOM 11.10] || Optimality of Solomonoff induction. See Vitanyi chapter 5.1--5.2 for background. [https://www.dropbox.com/scl/fi/rgdv6lhsjyauupmi319pw/02slides.pdf?rlkey=86etkg0bnbxx7debnvo5d8i2q&st=etj740r0&dl=0 slides.pdf]|| [https://www.dropbox.com/scl/fi/hhkk87q66ebx54vtswkge/02notes.pdf?rlkey=argdpb3l8ky75lj1g7n94175e&st=rqfszhit&dl=0 ch02] [https://www.dropbox.com/scl/fi/wjihhy6iuoxjuh9gje6b7/03notes.pdf?rlkey=03s29gprfjej7qwrvju8icaus&st=hlhvwri5&dl=0 ch03]|| [https://www.dropbox.com/scl/fi/otz8g8vjhovpllkkahrts/02sem.pdf?rlkey=o36rg87pbjh2jkywngtt3yctn&st=75is03yf&dl=0 sem02] ''update 26.10'' (Huawei [https://www.dropbox.com/scl/fi/nwp13nmrzyji1cqt4uds5/02hsem.pdf?rlkey=f8cys0wr4n8hqho22pd9lvcoi&st=bmzxl4l5&dl=0 sem02])|| [https://www.dropbox.com/scl/fi/6zusok315o3rk5v1osoow/02sol.pdf?rlkey=zpsgur7dv4llkycelbi2lfuc2&st=73oaxtir&dl=0 sol02]
|-
|| 25.10 || Minimizing loss according to unknown computable measure (non-responsive systems). Merhav-Feder and Helinger bounds for Bayesian mixtures. (The recording failed.) || [https://www.dropbox.com/scl/fi/isxpy6t5v9remzwlvt5e2/04notes.pdf?rlkey=gxhs69b00tcye4y8mmv4x5qyx&st=xalcy9a4&dl=0 ch04] || see notes ch04 ||
|-
|| [https://youtube.com/live/crwRCkXsEVw 01.11] || Minimizing loss in responsive systems. Self-optimizing strategies in sets of environments. If there exists a self-optimizing strategy, then a Bayesian mixture over all environments in a countable set is self optimizing. A variant with algorithmic probability. [https://youtube.com/live/NDsCxduHjgU recording 2nd part] || [https://www.dropbox.com/scl/fi/i97a1auk5x10aqomx6its/05notes.pdf?rlkey=kcmufbn1w70m48n4lvbp5yp54&st=rswmru4w&dl=0 ch05] || [https://www.dropbox.com/scl/fi/7ovfpljxe5p59vfhthzrk/04sem.pdf?rlkey=18urcicegj875oiu7x21sj2gi&st=p8nergg7&dl=0 sem04]
|-
|| [https://youtube.com/live/gxtqX9ZhJfQ 08.11] || Plain Kolmogorov complexity, simple properties, Godel-incompleteness, upper bounds, symmetry of information (see also [https://arxiv.org/pdf/1504.04955 notes]) || [https://www.dropbox.com/scl/fi/4ujoo1ppjxyib8ehz66il/04slides.pdf?rlkey=gz6npiztww9fcui2pgktxp6pz&st=09bw895o&dl=0 05sl] || [https://www.dropbox.com/scl/fi/u4gvojf9rqwxa6mz7tdbv/05sem.pdf?rlkey=f2l1j0p82zo4obier22uazizo&st=6m1u3elp&dl=0 sem05] || [https://www.dropbox.com/scl/fi/ebf53st4m2v1a3xa0ujl3/05sol.pdf?rlkey=s0ghwgwlptpqqxgst9mr2oxnl&st=tziuvgwr&dl=0 sol05]
|-
|| [https://youtube.com/live/ZegYzw8LLdI 15.11] || Prefix Kolmogorov complexity 3 definitions, upper bounds, symmetry of information. || [https://www.dropbox.com/scl/fi/zu84z1smw9m0rdns54ohr/05slides.pdf?rlkey=fakwr6sbl3fadwbydsecsz4mb&st=nyuu4wmz&dl=0 06sl] || [https://www.dropbox.com/scl/fi/8rrc8uluayw2qh4wfeqvv/06sem.pdf?rlkey=l44247q3j8g7kg3orvq0gv3lm&st=iswydrfx&dl=0 sem06] ||
|-
|| [https://youtube.com/live/Uh-hXNLegRw 22.11] || Information distance, clustering by compression, google distance. Seminar: incompressibility method || [https://www.dropbox.com/scl/fi/07vwgskncnceo5gnl3g1m/07slides.pdf?rlkey=7yuluul6anwd7vpm72tagpqek&st=nscvj3g3&dl=0 07sl] || [https://www.dropbox.com/scl/fi/m0tzh6qocbxtr4rz3ai5x/07sem.pdf?rlkey=iy7glkqwkbciax7n5ttdfkmo0&st=n8ezmv8o&dl=0 sem07] ||
|-
|| [https://youtube.com/live/o8GS-4fCACk 06.12] || Algorithmic statistics, [https://arxiv.org/pdf/1607.08077 overview paper] (notes later) || || [https://www.dropbox.com/scl/fi/gap1istjpb9xe80nfu5mb/08sem.pdf?rlkey=blefd1fodq4x0zhommsnp0h6i&st=rzaqhybe&dl=0 sem08] ||
|-
|| 13.12 || Colloquium: 17h00 room G116 (from 18h in G406). [https://www.dropbox.com/scl/fi/9pc3gsvprmwzuynxauis0/col.pdf?rlkey=rbyhl3ydyhfqjxrpmb1yyy5dg&st=vo7x6nwr&dl=0 Questions and rules]. || || ||
|}

= Homeworks =

Deadlines: every 2 weeks, before the lecture at 18h00. Submit in pdf or fotos of handwritten to brbauwens@gmail.com with the subject line starting with KOLM-HW. Link with results will be [https://www.dropbox.com/scl/fi/horrfz3kcj0r7etvu3ofw/grades.ods?rlkey=chgacqq84sfxm4tgtwdwqn57i&st=1qmn28wz&dl=0 here].

Tasks are in the problem lists from the seminar. Deadlines: problem lists 1 and 2: at the start of 3rd lecture, lists 3 and 4 at the start of the 5th lecture, etc.

Late policy: 1 homework can be submitted at most 24h late without explanations.

= References =

See notes00.pdf above.

= Grading =

Final score = 0.35 * [score homework] + 0.35 * [score colloquium] + 0.3 * [score exam] <br>

Some homework assignments contain extra problems. Each solution of an extra problem will give 1 extra points on the final exam (which is graded out of 10). There will be around 10 extra problems. Rounding is applied only when the final score is transferred to the official grade. Arithmetic rounding is used. Autogrades. If only 6/10 for the exam is needed to get a final score of 10/10, then this will be given automatically.

= Colloquium and exam =

Colloquium: in the middel of December, a list with about 10 questions will be provided.

Exam: Problems similar to the homework. You may use main references, lecture notes, and handwritten notes.

= Office hours =

Bruno Bauwens: Tuesday 12h -- 20h. Wednesday 16h -- 18h. Friday 11h -- 17h. Better send me an email in advance.

Kolmogorov complexity 24/25 - История изменений

imported>Bauwens: Migrated current public revision from wiki.cs.hse.ru