256: конспект лекции для первокурсников, посвященной дню программиста

13 сентября
Александр Хижа
256: конспект лекции для первокурсников, посвященной дню программиста

Об авторе: Александр Хижа — президент DataArt Dnipro и доцент кафедры компьютерных технологий факультета прикладной математики ДНУ. Александр профессионально интересуется тенденциями в IT-образовании, организацией олимпиад по программированию, сотрудничеством IT-индустрии и университетов.

Кто такие программисты и как ими становятся? В чем заключается загадочная сила программирования, за что программистам сегодня присваивают научные степени и как будут строиться наши отношения с компьютерами в далеком будущем?

Когда программистов стало невозможно игнорировать, человечество учредило День программиста.

Программистов становится все больше, и они все шире и громче празднуют свой День. Это вызывает естественное желание разобраться хотя бы в элементарных вопросах:

  • Откуда они, программисты, берутся?
  • В чем их сила?
  • Как стать программистом?

Спрашивать программистов бесполезно. Во-первых, они похожи на обычных людей, и потому на прямой вопрос «Вы программист?» обычно отвечает что-то вроде: «Ну, в принципе, да».

Во-вторых, программисты живут в ими же придуманных мирах и настолько погружены в себя, что не могут осознать, что в этих вопросах непонятного. Возможно, иной раз до такой степени, что сами забывают ответы.

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

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

256 (конспект лекции)

Мир Программирования

Вселенная состоит из объектов, которые взаимодействуют друг с другом при помощи алгоритмов.

Фактически объекты — это все видимые, невидимые и даже виртуальные сущности, которые нас окружают. В том числе, атомы, планеты, мы сами и любые наши фантазии.

Алгоритмы — это описания действий, которые необходимо выполнить, чтобы осуществить взаимодействие объектов.

Несмотря на очевидную пропасть между объектами и алгоритмами, мир един и потому невообразимо сложен. Общепринятый способ описания фрагментов мира — программы.

Что такое программы? Классическое объяснение — сумма объектов и алгоритмов.

Кто «главнее» — алгоритм или объект? Сравним этот вопрос с вопросом из мира физики: кто «главнее» — волна или корпускула? Или из мира философии: «что было раньше – курица или яйцо?». В любом случае ответа нет. Но это не мешает нам наслаждаться красотой нашего мира и мечтать сделать его еще красивее.

Ключи от Мира Программирования

Мир очень прост — в деталях. При этом создать что-то истинно новое в мире или хотя бы понять уже созданное чрезвычайно сложно!

Ключ — понимание, основанное на теории и практике.

Теория

Учит абстрактному пониманию алгоритмов и сущностей.

Базовые теории:

  1. Дискретная математика (теория множеств, алгебра логики, конечные автоматы, лямбда-исчисление и рекурсивные функции).
  2. Математическая логика (понятие «правильного» алгоритма и методы [математического] доказательства правильности алгоритмов).
  3. Алгоритмы и структуры данных.
  4. Принципы языков программирования.

Практика

Учит создавать новые алгоритмы и сущности, а также разбираться, как были созданы прежние алгоритмы и сущности.

Базовые практики:

  1. Написание алгоритмов как последовательностей действий.
  2. Методы построения программ.
  3. Методы проверки правильности программ, или «тестирования».
  4. Методы организации (коллективной) работы для создания программ.

Наука

Объединяет теорию и практику в единое целое.

Главная наука в Мире программирования — это “Computer science” (так она называется в Америке) или “Informatics” (так ее называют в Европе).

По определению, это наука, которая изучает теоретические основы и практические методы приема, передачи, хранения и преобразования информации при помощи компьютеров.

Компьютеры

В недалеком прошлом — механические вспомогательные устройства для выполнения операций над числами — «вычислений» (или “computing”).

В настоящем — самые сложные из устройств, которые изобрело человечество. В современном компьютере различают две составляющие — аппаратную (т. н. «железо», “hardware”), и программную (т. н. «софт», от англ. “software”). Современные компьютеры вездесущи и, по большей части, невидимы. Они работают везде:

  • в мобильном телефоне;
  • в автомобиле;
  • в космическом телескопе;
  • в кардиостимуляторе;
  • в пылесосе, холодильнике, стиральной машине и  т. д.

Скоро они объединятся. Поэтому следует их хорошенько изучить, пока не поздно.

Уникальность программирования

Это единственный (научно обоснованный) вид человеческой деятельности, позволяющий создавать активно действующих («живых») квазиразумных существ. К таковым можно отнести:

  • роботов;
  • искусственный интеллект;
  • любые другие устройства, в основе которых «тело» — компьютер — и внутреннее содержание, «душа» — программа.

Пока что компьютер — (придуманный нами) исполнитель (придуманных нами) алгоритмов.

В будущем произойдет одно из двух:

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

Пока что программист создает модель мира в памяти компьютера. Внутри этой модели, в свою очередь, существуют компьютеры, моделирующие другие миры. А в тех мирах, в свою очередь, есть компьютеры, моделирующие . . .

Ваш стек еще не переполнился? Спокойствие! Выход из рекурсии происходит в тех мирах, где еще нет компьютеров. Если только вы не пытаетесь моделировать миры будущего. В этих случаях следует соблюдать особую осторожность, чтобы не спровоцировать Всеобщий Конец Стека.

Как стать программистом

Короткий ответ

Набирать на компьютере примеры кода из лекций по программированию и пытаться их «оживить» (т. е. заставить эти примеры работать).

Длинный ответ

Начинать с детства.

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

Ключевая проблема в развитии таланта — выбор языка. И эта проблема человечеством до сих пор не решена.

Автоформализация (профессиональных) знаний и умений

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

Например:

  • ребенок учится ходить — в языке программирования должна быть возможность описать это действие и применить его к исполнителю;
  • учится лепить, рисовать, говорить и т. д. — аналогично.

Кого же мы называем «исполнителем»? Это объект, который более или менее напоминает самого обучаемого. Например, дети играют в стихийную обучающую ролевую игру «Семья»: «Ты будешь папа, а я буду мама».

Еще пример: ребенок учится рисовать на компьютере. Тогда исполнитель — это виртуальный персонаж внутри компьютера, которого ребенок «обучает» рисованию при помощи языка программирования (слыхали про язык LOGO и Черепашку?).

Все сказанное в равной мере применимо и к взрослым, т. е. к  будущим профессионалам.

Если взрослый человек хочет научиться программировать, отправная точка для него — автоформализация уже приобретенных знаний и умений: бухгалтерских, медицинских, строительных, конструкторских, математических, химических и т. д.

Иными словами, все начинается с того, чтобы описать свою предметную область в терминах алгоритмов и объектов. Кто лучше домохозяйки знает как автоматизировать ведение домашнего хозяйства? Она большинство действий уже выполняет автоматически. Так же обстоит дело и в других профессиональных областях.

Где этому учат

Программированию учат там, где теория программирования доступна пониманию учителей.

Кто учит программированию? Те, кто программирует.

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

Но разделение программирования на теоретическое и прикладное все же существует. Причем не только в головах программистов, но и в их профессиональной деятельности.

Как стать прикладным программистом

Учебный план университета предусматривает «производственную практику». Это дает студенту возможность  завязать контакты с IT-компаниями еще во время учебы в университете.

Но только работа в индустрии делает студента прикладным программистом.

Как стать программистом-ученым

Для этого нужно получить в университете ученую степень бакалавра, затем — магистра, продолжить обучение в аспирантуре и защитить после ее окончания диссертацию на соискание ученой степени «кандидат наук» (ее общепринятое в мире название — PhD, дословно: «доктор философии»).

Но какой такой «теорией программирования» занимаются ученые? Что конкретно они делают?

Ученые создают новые высокоэффективные алгоритмы. Например: «наибольший общий делитель» (500 г. до н.э.), «кратчайший путь в графе» (1959 г.), «быстрая сортировка» (1962 г.), «дерево отрезков» (1979-1981 г.г.), «дерево Фенвика» (1994 г.).

Создают новые абстракции для более адекватного описания более сложных объектов. Например: «классы» (1967), «реляционные базы данных» (1970), «контейнеры» и «итераторы» (1970-1990 г.г.).

Закладывают фундаментальные основы  для понимания устройства Мира: «лямбда-исчисление» (1936), «машина Тьюринга» (1936), «конечные автоматы, формальные языки и грамматики, теория синтаксического анализа, перевода и компиляции» (1950-1970 г.г.), «программные логики» (1970-1980 г.г.), «формальная семантика» (1969-1980 г.г.), «темпоральные логики» (1950-2000 г.г.).

Каждое из упомянутых понятий связано с именами величайших ученых в области программирования. Изобретенные ими теории продолжают развиваться и со временем приобретают прикладной характер. Например, один из подходов к формальному доказательству правильности программ сводит правильность любой программы P, которая стартует в состоянии Q и завершается в состоянии R, к вопросу истинности предиката Q=>WP(P,R), где WP — «предикат слабейшего предусловия».

В соответствии с этим подходом доказательство программы «while(a≠b){a:=a-b; swap(a,b);}» сводится, в частности, к формуле вида: (a=b)^(gcd(a,b)=gcd(A,B))=>(a=gcd(A,B)), которая, очевидно, истинна (согласны?).

Знать подобные приемы должны все программисты — выпускники университетов, даже если они будут работать в индустрии. То есть если они в своей производственной деятельности не будут формально (т. е. при помощи формул) доказывать правильность программ. Это нужно и для того, чтобы писать более правильные программы.

Чтобы стать PhD, необходимо получить (доказать, изобрести) новые элементы Теории программирования. Примеры исследований, завершенных в рамках PhD в 2018 году:

  • «Улучшение проверок на этапе выполнения в динамических языках программирования»;
  • «Доказательство достаточных условий постоянства транзакционной памяти и структур данных в многопроцессорных системах»;
  • «Искусственный интеллект: когда машины научатся забывать»;
  • «Инструментальные средства программирования: сообщения об ошибках с точки зрения рациональной реконструкции»;
  • «Эффективные подходы к оценке затрат и тестированию систем с сервис-ориентированной архитектурой»;
  • "Asynchronous Adventures: Formal Approaches to Querying Big Data in Shared-Nothing Systems";
  • «Поиск сходства и построения набросков в многомерном случае: алгоритмы и сложность».

Олимпиады по программированию

Качество университетского ИТ-образования можно измерить достижениями выпускников университета:

  • объемом прибыли, которую с их помощью получил ИТ-бизнес;
  • количеством их изобретений, обогативших науку.

Но такие оценки работают постфактум: должно пройти много лет, чтобы можно было оценить университет по достоинству.

Как оценить качество образования молодого университета (или немолодого, но преподающего программирование недавно)? Не измерять же его баллами, полученными студентами на экзаменах!

Объективную оценку знаниям основ программирования дают международные студенческие олимпиады по программированию. Например, ACM ICPC.

Ведущие ИТ-компании мира гоняются за победителями (и участниками) этих олимпиад.

Победы студентов повышают мировые рейтинги университетов. Участвуя в олимпиадах вы убиваете двух зайцев:

  • повышаете уровень своих знаний;
  • ускоряете свою карьеру в ИТ.

Искусственный интеллект и будущее

Мы учимся, обучая других.

Явно — других людей и себя. Неявно — искусственных «исполнителей», компьютеры.

Наш интеллект развивается. Но развивается и их интеллект.

И если интеллект — это способность быстро решать определенные проблемы (эмоциональные, финансовые, математические, социальные и т. д.), то почему бы не сделать ставку на искусственный интеллект?

Например, в обществе, где действует принцип распределения материальных благ «от каждого по способностям, каждому по труду», социальный искусственный интеллект помогает быстро и беспристрастно (без коррупции) решить главную проблему: кто сколько потрудился.

На сегодня лекция окончена. Найдите ответы на скрытые вопросы и открыто задайте новые вопросы — в рамках самостоятельной домашней работы. В ней залог успешного образования.

Спасибо за внимание.