The Journal, live journal

Автор книги «Теоретическая информатика» — Юрай Громкович, профессор ETH Zürich, известный пропагандист преподавания информатики в школах и вузах, публикуется в Springer.

Эта книга претендует на роль учебника для вводного курса по теоретической (фундаментальной информатике) в университетах. Автор пишет, что соответствующий курс может читаться во втором семестре первого курса. Разумеется, многие вопросы рассматриваются неглубоко, на уровне идей, но достаточно широко.

Прочитав две первые главы — «Введение» и «Алфавиты, слова, языки, алгоритмические проблемы», я попытался определить, какие знания из математики нужны для её чтения (и, соответственно, для чтения курса по этой книге). В итоге (совершенно случайно) получилась программа курса «Основы дискретной математики» для первого семестра:

1) Методы доказательства математических утверждений: логический вывод (modus ponens), доказательство от противного, метод математической индукции.

2) Множества, операции над множествами. Отображения, свойства отображений. Конечные и счётные множества.

3) Комбинаторика (интересно, что во многих зарубежных книгах вместо слова комбинаторика используют counting).

4) Теория отношений (эквивалентность, порядок — вплоть до существования неподвижной точки).

5) Алгебра высказываний, алгебра предикатов, булевы функции (с критерием Поста).

6) Общая алгебра (моноиды, полугруппы, группы).

7) Теория графов.

За наводку на книжку спасибо undesames.

Попал я на ленту.ру совершенно случайно: по ссылке с хабра. Заинтересовался комментарием про алтайскую мумию. Потом был китаец из древнеримской могилы. А там я узнал, что бывают митохондриальные ДНК. И всё бы ничего, если бы в седьмой серии третьего сезона, которую я тоже смотрел сегодня, не появились бы они. Митохондриальные ДНК.

Да, это House MD...

Сегодня ударно завершил сессию: принял два экзамена и одну пересдачу. На пересдаче народ бился с редукцией лямбда-термов: борьба шла с переменным успехом. Второй экзамен был экспериментальным: студенты восемь часов писали программы на Java. Первый — обычный письменный экзамен с двумя вопросами, одинаковыми для всех — история развития вычислительной техники, программирования и информационных технологий. Не обошлось без шедевров.

Первый вопрос: «Теоретическая информатика и её основные разделы».
Ответ:
Основные разделы теоретической информатики:
1) теория помехоустойчивого кодирования;
2) теория криптографии;
3) теория систематического кодирования;
4) теория анализа информации.

Второй вопрос: «Язык программирования Алгол».
Тут выяснилось, что «данный язык используется для алгоритмического программирования и позволяет решать сложные алгебраические задачи». А ёще он был популярен «благодаря своей эффективности и сравнительной простоте». Это Алгол-то, про который известно, что многие последующие языки получались выбрасыванием из Алгола чего-нибудь. Порадовало также перечисление «Алгол–60, Алгол–68 и т.д.».

Кстати, сегодня (или вчера, я точно не помню) исполняется десять лет с начала моей педагогической деятельности: всё началось с геометрии в 8 и 9 классах.

Есть такая эквивалентная машине Тьюринга вычислительная модель — нормальные алгорифмы Маркова, её основная операция — замена вхождения подстроки в строке на другую подстроку. Она интересна тем, что её элементарно запрограммировать: эта задача под силу любому начинающему программисту. Всё, что от него требуется — это обработка строк (ну т.е. часть B из ЕГЭ).
( Вот, например )

λx.λy.x((λx.λy.(λx.λy.x(x(x(x(x(x(xy)))))))((λx.λy.x(x(x(xy))))x)y)xy)

С точки зрения разработчика стандарта магистратуры третьего поколения по направлению «Фундаментальная информатика и информационные технологии» магистрант должен прослушать следующие курсы:

• Современная философия и методология науки
• Иностранный язык
• Математические основы защиты информации и информационной безопасности
• Алгоритмические основы мультимедийных технологий
• Анализ информационных технологий
• Объектно-ориентированные CASE-технологии
• Объектные базы данных
• Распределенные объектные технологии
• Параллельное и распределенное программирование

Какой-то странный набор, мне кажется. Впрочем, я знаю, откуда он взялся. Это читают на ВМК МГУ.

Широко известные «принципы фон Неймана» организации ЭВМ были сформулированы Джоном фон Нейманом в «First Draft of the Report on EDVAC» по итогам целого ряда обсуждений между фон Нейманом и создателями ENIAC Джоном Мокли и Джоном Преспером Эккертом. Этот документ был без ведома фон Неймана, но под его авторством разослан по крупнейшим университетам. Публикация вызвала большой скандал, в частности сам фон Нейман всегда утверждал, что все эти идеи не принадлежат лично ему: по сути, эти принципы были заложены еще Бэббиджем (АУ, УУ, внутренняя память, устройства ввода/вывода) и Тьюрингом (хранение программ в закодированном виде в памяти машины). Тем не менее, публикация доклада от имени одного только Неймана очень сильно обидела Эккерта и Мокли, они покинули проект EDVAC.

Решил убить свой курс Распределенные системы. За два года он так и не превратился во что-то цельное. Cил отнимает много, а на выходе ничего толкового не получается. Может быть, когда-нибудь.

http://en.wikipedia.org/wiki/List_of_computer_scientists

Насчитал троих: А. Н. Колмогоров, А. П. Ершов и Ю. В. Матиясевич.

Папа Сильвестр II, он же Герберт Аврилакский, он же архиепископ Реймсский и Равеннский, для разбора рукописей которого в Москву прибыл консультант Воланд, известен как популяризатор вычислений на абаке в Средневековой Европе (X век), его перу принадлежит учебник с описанием методов сложения, вычитания, умножения и деления. Он был известнейшим педагогом, уделявшим большое внимание visual aids. Слыл большим ценителем Цицерона, Вергилия и Марциала, но не слишком часто цитировал Священное Писание и Св. Августина с другими отцами церкви, что в то время было довольно необычно. Занимался политикой, страдал имперским синдромом, работал на благо Священной Римской империи Германской нации, способствовал падению династии Каролингов и воцарению Капетингов. Многими считался чернокнижником из-за умения быстро вычислять. Признан одним из прототипов доктора Фауста.

Абак как основной прибор для вычислений господствовал до XIII века, когда его потеснил «алгоритмический» метод — вычисления на бумаге с помощью арабских цифр. «Абакисты» и «алгоритмики» долгое время спорили между собой, пытаясь доказать, что их способ лучший. Основателем движения «алгоритмиков» был Леонардо Пизанский, более известный как Фибоначчи.

А calculus — «галька», «голыш» — это камешек, используемый для вычислений на абаке.

На прошедшей неделе дочитал «Ярмарку тщеславия» Теккерея. Чрезвычайно приятное чтение: автор не просто рассказывает долгую историю, он общается с читателем, задаёт вопросы, много рассуждает. Запросто может выдать что-то вроде:
Дездемона не сердилась на Кассио, хотя весьма сомнительно, чтобы она не замечала нежного расположения лейтенанта (что касается меня, то я уверен, что в этой грустной истории были кое-какие подробности, о которых не подозревал достойный мавр).

Или вот:
Хотя письмам школьных наставниц можно доверять не больше, чем
надгробным эпитафиям, однако случается, что почивший и на самом деле
заслуживает всех тех похвал, которые каменотес высек над его останками: он
действительно был примерным христианином, преданным родителем, любящим
чадом, супругой или супругом и воистину оставил безутешную семью,
оплакивающую его. Так и в училищах, мужских и женских, иной раз бывает, что
питомец вполне достоин похвал, расточаемых ему беспристрастным наставником.

Я как раз перед тем, как это прочитал, рассуждал тут на тему разговоров с родителями учеников.

Для получения наибольшего удовольствия Теккерея нужно читать в оригинале, изучив предварительно английский, немецкий и французский языки, историю британии с норманнского завоевания, уделяя особое внимание колониальной политике, и историю наполеоновских войн, экономческую географию Великобритании, правила английского этикета, генеалогию английской аристократии, а также всю мировую литературу, начиная с древнегреческих мифов и библии и заканчивая Диккенсом, Шекспира нужно знать вообще наизусть.

19 июля я писал, что изучение функционального программирования на первом курсе может решить проблему разного уровня  программистской подготовки абитуриентов. А негодяй Саймон Пейтон-Джонс нагло украл эту идею и высказал ее в своем интервью!

Наконец-то понял, как должен выглядеть мой курс по ФП (17 часов лекций + 17 часов лабораторных занятий) для четверокурсников ИТ. Базовый язык — Haskell.

( Программа курса )

А еще я составил checklist для изучающего Haskell:

( Этапы изучения )

P.S. В первом выпуске журнала «Практика функционального программирования» отличный обзор литературы по ФП (с удовлетворением отметил, что я уже все знал и почти все нашел, кстати, книжка Bird'а в электронном виде существует?); несколько притянутые за уши рассуждения о «ленивости» условного оператора в императивных языках в статье «Лень бояться» Сергея Зефирова, дурацкая псевдофилософская статья Романа Душкина «Функции и функциональный подход» и еще три довольно интересные статьи практического характера. Задание на реализацию игры в шашки можно из списка индивидуальных заданий вычеркивать.

С этого года наши абитуриенты сдают ЕГЭ по информатике. Это означает, что они гарантированно изучают программирование (в школе или на подкурсах). Традиционная проблема первого семестра в курсах по программированию всегда была в том, что кто-то не знает ничего,  кто-то знает слишком много (причем зачастую научен плохому!).  Сейчас проблема, скорее всего, немного сгладится, но вряд ли сильно. 

Так вот, самое время перейти на функциональное программирование в первом семестре! Это уравнивает новых студентов на начальных этапах. А кроме того, снимает проблему «слишком умных» студентов, которые думают, что знают все, забивают на программирование, а потом неожиданно для себя оказываются в лучшем случае в середнячках (бывало и хуже). 

Конечно, экспериментировать на людях нехорошо, но и почивать на прокрустовом ложе императивщины тоже печально. 

Итого:

• первый семестр — функциональное программирование;
• второй семестр — язык C (как последний флагман императивного программирования);
• третий семестр — россыпь промышленных ОО-языков (C++, C#, Java).

Вот.

Согласно википедии Ноам Хомский is influenced by Рассел, Декарт, Маркс, Оруэлл, Кант, Смит, Гумбольдт, Квайн, Бакунин, Тьюринг. Он тоже стоит на плечах гигантов, дай ему бог здоровья.

В комитете по созданию языка Haskell была переходящая должность — Syntax Czar. В его обязанности входило принятие окончательного решения по синтаксису той или иной конструкции:
Everyone always says that far too much time is devoted to discussing syntax—but many of the same people will fight to the death for their preferred symbol for lambda. The Syntax Czar was our mechanism for bringing such debates to an end.

А когда комитет выбрал имя для нового языка, они обратились к вдове Карри за ее согласием. Она не возражала, но заметила: «Вы знаете, Хаскель на самом деле никогда не любил имя Хаскель». 

History of Haskell