Diff for "Python/Summer2017"

Примерный распорядок дня

• 10:00-10:30 — повторение и ответы на вопросы
• 10:30-13:30 — лекции+семинары
• 13:30-14:00 — обед
• 14:00-16:00 — практика

Предполагается последовательно проходить этот план, расставляя пометки, сколько удалось сделать за день.

• — лабораторные работы / семинары (воспроизведение доски или тривиальные упражнения)

• — практические задания (решения выкладываются сюда)

Рекомендации по самостоятельному изучению

• Д/З: установить Python и Geany (можно другие IDE) дома, если есть цель научиться чему-то ненулевому

• Д/З: Щёлкать tutorial (определяем, кому интересно)

День 1 (3 июля)

Знакомство

• Знакомство, определение уровня знаний и глубины изложения (утро)
• Орг: конспекты (c двух сторон: Linux+Python), практика обязательна
• FOSS: сообщество и ПО, Linux, Python

Linux и командная строка

• «цветочек»+
  • Ядро, программный интерфейс
  • Утилиты, командный интерфейс
  • ФС, пространство имён, файловые объекты
• ⇒ командная строка (введение)
  • КС как диалог
  • shell: интерпретатор командной строки, ЯП, оболочка надо другими программами
  • договорённости о командной строке (ключи)
  • переменные, где лежат команды (пространство имён), PATH
  • Примеры команд: - ls, cp, rm, mv, mkdir, echo, перенаправление В/В
  • имена файлов, ln, ls -i
  • Встроенная помощь man

• 

  • посмотреть содержимое корня
  • посмотреть все файлы в текущем каталоге
  • посмотреть документацию к известным командам
  • создать файл, переименовать
  • создать каталог, скопировать туда файл, удалить каталог

Python и командная строка

• объекты, их типы
• действия над объектами
• неявная динамическая типизация
• преобразование типов, type() (в т. ч. type(a)(b)) и простейший ввод-вывод
• пространства имён, связывание объектов именами, dir()
• множественное связывание, id()
• help()

• 

  • вычисление формул
  • поэтапное вычисление формул с использованием имён
  • online python tutor: демонстрация связывания

Сценарии

• Текстовый редактор vs IDE
• Linux, shebang
• программа на Python

• 

  • Использование geany
  • примитивный сценарий на shell

  • сделать сценарий исполняемым и переместить в каталог $HOME/bin/

  • примитивный сценарий на Python

День 2 (4 июля)

• понятие о модулях, from math import *

• 

  • ручное развёртывание бинарного возведения в степень (например, как получить 3²¹?)

  • вычисление формул

Условные операторы и выражения

• логический тип, операции сравнения
• условное выражение a if b else c
• базовый if
• форматирование отступами
• if / elif* / else

• 

  • ввести два числа, вывести наибольшее
    • условным выражением
    • условным оператором
  • ввести два числа, вывести, больше, меньше или равно первое второму
  • ввести три числа, проверить неравенство треугольника (вложенный if)

• 

  • ввести три числа, найти наибольшее (вложенный if)
    • условным выражением
    • условным оператором

Алгебра логики

• пустой объект, примеры

• ⇒ любое выражение в условии

• таблицы истинности
• логические операции Python, их таблицы истинности
• примеры

• 

  • ввести три числа, проверить неравенство треугольника (с помощью or)

• 

  • квадратное уравнение с ненулевым a

  • условные формулы №57

Цикл while

• каноническая схема цикла: инициализация, проверка условия, тело, изменение
  • пример: цикл по вводу

• 

  • подсчёт произведения (ввод до 0)
  • сумма N элементов арифметической прогрессии (циклом)
  • факториал

• 

  • с какого элемента сумма арифметической прогрессии превысит N?
  • таблица умножения на N (в столбик)
  • подсчёт среднего (ввод до 0)

Циклы (более сложные случаи)

• условия внутри циклов, break, continue
• поиск первого, else
• вложенные циклы

• 

  • Сумма только положительных (ввод до 0)
  • одновременный подсчёт суммы и произведения положительных чисел (используется continue для отрицательных)
  • ввести ненулевые числа, проверить, есть ли среди них отрицательные
    • без else (с break)
    • с else
  • большая таблица умножения в столбик

• 

  • таблица умножения в виде матрицы по столбцам (без форматирования)

День 3 (5 июля)

Последовательности (введение)

Хранимые последовательности

• (строки, кортежи, списки)
  • индексирование, в т. ч. отрицательное
  • операции поэлементного сравнения

    • операция is на примере списков

  • операции + и *

  • секционирование
    • обычное
    • с шагом
    • умолчания

  • 

    • какая последовательность больше и почему?
    • начальный, средний и конечный элемент
    • элементы, стоящие на 1,4,7, и т. д. местах (NB off by 1)

  • 

    • сначала элементы, стоящие на нечётных местах, затем — на чётных, задом наперёд
• цикл прохода по последовательности for

  • break, continue, else

  • 

    • выбор максимума
    • поиск 0

Вычисляемые последовательности

• (range(), enumerate())

• типичный for

• 

  • переписать на for кое-какие примеры с while

• 

  • ввести последовательность чисел, вывести второй максимум, то есть элемент, больше которого в последоватнльности только одно значение, например, для 1,1,2,2,7,7,3,3,5,5 второй максимум — это 5

Циклические конструкторы

• Конструктор списка
• Конструктор генератора, работа генератора, цикл for и генераторы
• Как работает множественное связывание
  • распаковка последовательностей при связывании
  • в цикле for (последовательность последовательностей)

  • a,b,*c,d = "Qwertyuiop"

Кратко о строках

• +, *

• "".format()

• 

  • Вывести все стороны и площади треугольников, стороны которых — однозначные положительные целые числа (не надо использовать конструктор, это жесть!)
    • использовать формулу Герона
    • не забыть, что 1 2 3, 1 3 2 и прочие перестановки — один и тот же треугольник, выводить один раз1

  • вывести таблицу умножения от 1 до 12 (сначала без "".format(), потом (если успеете) с ним):

    •     1*1 = 1   2*1 = 2   3*1 = 3
          1*2 = 2   2*2 = 4   3*2 = 6
          ...
          1*12 = 12 2*12 = 24 3*12 = 36
          4*1 = 4   5*1 = 5   6*1 = 6
          4*2 = 8   5*2 = 10  6*2 = 12
          ...
          4*12 = 48 5*12 = 60 6*12 = 72
          7*1 = 7   8*1 = 8   9*1 = 9
          7*2 = 14  8*2 = 16  9*2 = 18
          ...

  • Ввести строку, вывести, сколько в ней гласных (подсказка: c in "aeoiu" ), методами не пользоваться

  • Ввести список запрещённых слов в формате "слово1","слово2",..., затем вводить строки до тех пор пока последняя не окажется пустой (это так же, как ввод до 0). Вывести, сколько строк содержали запрещённые слова

День 4 (6 июля)

Функции (введение)

• Задача повторного использования кода — макросы и подпрограммы
• Функции в Python
  • Функция — это запись алгоритма обработки данных, а не преобразование

  • duck typing

  • вызов функции — выражение, всегда есть возвращаемое значение — любой объект (например, None)
  • возвращаемое значение можно не использовать
  • Определение функции, формальные параметры

    • простые примеры

  • Локальное пространство имён функции

    • просто вывод dir()

    • независимость имён

    • locals() и globals()

      • просто вывод

    • порядок просмотра пространств
    • автоопределение локальных имён; global

      • 

  • 

    • с этого момента и до конца курса каждые модуль/функция/класс в заданиях должны содержать docstring с пояснением, что они делают

    • (задания в этом -блоке оформить в виде интерактивной программы и в виде модуля)

    • Функция — сумма цифр
      • Ввести последовательность, вывести элемент с минимальной суммой цифр

        • можно с помощью min() — как?

    • функция — расстояние между точками ( на самом деле есть )

      • Ввести список пар вида (1,2), (3,4), (100,100) …, найти самый удалённые точки

• Распаковка и запаковка параметров функций
  • ничего и нет, только списки
  • Функции с переменным количеством параметров

    • 

  • Распаковка последовательности при вызове

    • {*}, в т. ч. print(*seq)

• 

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

• Всё остальное про функции — потом, не сегодня

Методы объектов; модули

• Поля объектов, инкапсуляция

  • dir(объект)

  • объект.имя_поля

  • методы и … поля

• Модули, sys.path

  • программа на Python как модуль
  • встроенная и в среду Python, и в язык Python документация

    • help()

    • документирование собственного кода
      • docstring

      • object.__doc__

  • 

Строки и их методы

• Строковые методы

  • все (в т. ч. in)

  • replace()

    • 

  • split() и join()

    • 

• 

  • Ввести строку, заменить в ней последовательности "-" на один минус
  • Ввести запрещённое сочетание букв и строку. Вывести строку, в которой запрещённое сочетание букв не встречается (например, "ab" и "aabbcaabbb" → "cb")

Списки и их методы

• все методы
• стек, суть pop()/push(), эффективность
• очередь и deque()

• Функция: список -> список

  • Список всех делителей числа
  • Убрать из списка подряд идущие одинаковые элементы

    • Для уверенных в себе: То же, но повторять, пока таких групп не останется.

День 5 (7 июля)

Ещё немного обо всём

• zip(последовательность, последовательность, ...)

  • удобнее всего одинаковой длины

  • столько же элементов, сколько в аргументе наименьшей длины, остальные отбрасываются

  • 

    • (07.02) Ввести матрицу N*M, выдать транспонированную матрицу

  • 

    • Ввести N строк, проделать то же самое

• lambda arguments: returnexpr

• python3 matrix_generator.py | python3 another_program.py

  • работает везде: Linux, Windows, OS X, any other Unix
  • в т. ч. возможность писать самые настоящие автоматические тесты для своих программ!

Про random

• Случайное и неслучайное, зачем нужно
• Датчик случайных чисел
  • неслучайность
  • воспроизводимость, seed()

• Модуль random

  • random() , randint(), randrange()

  • choice(), shuffle(), sample()

  • seed()

• 

  • Случайное число на отрезке A…B
    • Гистограмма (список частот для возможных значений)
  • Перемешать строку
  • Случайные слова случайной длины
  • Генератор значений для 07.02 (транспонирование матрицы)

• 

  • в каждой функции, которую пишете, краткий docstring, к хорошему тону надо привыкать

  • Функция, с вероятностью 1/3 выдающая "yes", с 2/3 "no". (без модуля random, кроме random.random)

    • Программа, выводящая выборку из N вызовов такой функции и гистограмму (кол-во "yes" и кол-во "no")

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

    • if __name__ == "__main__": краткое демо

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

    • можно не слово, а букву или комбинацию букв, с точки зрения Python одно и то же

  • В первой программе сгенерировать двумерный список чисел случайно и вывести на экран
    • в другой: среди всех минимумов в строчках полученной матрицы найти максимум

    • тестируем при помощи конвейера (что-то сродни python3 gen.py | python3 program.py)

    • обратите внимание, что по pipe между программами проходит текст, т. е. строчки символов

Про черепаху

• Модуль turtle

• Основные команды
• Как закрасить область

• 

  • Функция, рисующая домик размера N пикселей.
  • Функция, рисующая ёлочку из n треугольников размера от k до l
  • лес с разными ёлочками

    • немного не параллельными

• дальше не успеем

День 6 (10 июля)

• Q: был вопрос о разнице между " и ' в Python.

  • A: Разницы нет никакой, кроме стилистической: хорошим тоном считается использовать для docstring двойные кавычки.

  • см. PEP 257 на эту тему

Работа с файлами

• Текстовые файлы
  • open(), read() / write() / close()
  • readlines() он же сам файл, print(.. file=)
  • "b/t" — str или bytes

  • with

• 

  • вводить числа до 0, записывать в файл только положительные
• файлы с данными

  • если данные наши: сериализация/десериализация, pickle (json, xml, …)

    • dump[s]()/load[s]()

  • если данные готовы: struct

    • byte order

    • pack()/unpack()

• 

  • Если в командной строке программы пять (с argv[0] — 6) параметров, то это:

    1. имя выходного файла
    2. имя,
    3. фамилия
    4. возраст (целое число
    5. средний балл (вещественное)
       • сериализовать эти данные в файл;
       а если параметр только один (argv[1]), это имя входного файла, десериализовать их оттуда и вывести
  • То же, что и выше, но с помощью struct

Словари и множества

• Задача хранения и индексирования
  • сложных данных
  • просто слишком больших данных
  • +невосстановимое хеширование
• Свойства хеш-функции
  • неоднозначность
  • распределённость по ОЗ (на конкретных данных!)
    • разброс для почти похожих
  • невосстановимость объекта (сравнение без раскрытия)

⇒ Возможности

• индексирование
• сортировка и поиск

Примеры

• a % b
• int(sin(b)*1000)%100

• hash(), какие объекты хешируются

• ...

• 

  • если есть различные значения синуса, какой к ним хороший хеш?
  • идентификаторы

Множество — просто хеш-таблица

• Задание, в т. ч. циклический конструктор
• Операции над множествами, методы
• Типичное использование

• 

  • каких букв не хватает

• 

  • вводятся предложения, проверить, есть ли общее слово (регистр букв игнорировать)

Словарь — множество с атрибутами, т. е. соответствие множества хешируемых ключей множеству произвольных объектов

• Задание, в т. ч. циклический конструктор
• Операции над множествами, методы
• Типичное использование:
  • ...
  • globals()/locals()
  • именные параметры функции

• 

  • Словари и счётчики
    • ручная реализация счётчика
    • collections
    • тестирование хеш-функции: много входных данных и гистограмма

• 

  • генератор файла с N случайными словами (N задаётся из командной строки), причём 1-е слово встречается ровно 1 раз, второе — 2 раза, …, N-е — N раз
  • подсчёт слов в файле, гистограмма вида

      ########                                  word1
      #############################             word2
      ###################                       word3
      ...

    • где максимальная длина "#######" — 50 символов

  • самое популярное слово длиной >3 в файле anna.txt

День 7 (11 июля)

Генераторы

• позволяют по собственным правилам конструировать вычислимые последовательности
  • даже бесконечные!
• выглядят как самые обычные функции...

  • ...но в них есть хотя бы одно ключевое слово yield

  • Как только Python видит в теле функции yield, он понимает, что это генератор
• Отличия функции-генератора от не-генератора:

  • Функция-генератор создаёт и возвращает generator object, по которому можно ходить

    • iterable(gen) == True

    • for i in gen: blabla

    • next(gen)

      • ...кстати, не что иное, как gen.__next__()

      • алгоритм в теле функции выполняется не при её вызове, а именно в методе gen.__next__

    • справедливы все остальные свойства вычислимой последовательности

  • yield не завершает выполнение алгоритма в функции-генераторе, а лишь приостанавливает

    • их может быть сколько угодно

    • next(gen) начинает (соотв. продолжает) выполнение функции до ближайшего yield

  • return в теле функции-генератора означает мгновенный выброс StopIteration

    • как и достижение конца тела
    • TODO а что происходит с возвращаемым значением? игнорируется?

• 

  • Руками реализовать range(10,70,2)

• 

  • Вычисление π с помощью генератора (формула Лейбница для π)

PyPI

• централизованное хранилище модулей для Python

• pip3

  • кроссплатформенный!

  • pip3 install <package>

    • в Linux (как и в любой разумной системе) устанавливать что-то прямо в систему может только администратор

      • поэтому, чтобы поставить себе в домашний каталог: pip3 install --user <package>

  • pip3 search <package>

• sys.path

PyGame

• не забываем о help()

• огромный пакет, состоящий из множества модулей

• 

  • Линии, примитивные фигуры, ёлки из треугольников
  • Квадрат, который можно тащить мышью
  • Анимированный движущийся квадратик (движение растянуто во времени)

• 

  • Несколько квадратиков; иметь возможность плавно тащить мышью каждый
  • Заставить едущий квадрат отражаться от стенок окна

    • Тормоз и газ

  • К зачёту: Совместить две предыдущие.

День 8 (12 июля)

• itertools

Построение графиков в PyGame

• нарисуем ломаную

  • pygame.draw.lines()

  • например, график функции y = sqrt(x) или y = sin(x)

  • график 1:1px очень мелкий; особенно забавным получается sin(x)

    • нужно прибегать к масштабированию и смещению осей, т. е. экранных координат

• Напишем функцию scale(x,a,b,A,B), которая по числу x на отрезке a…b вычисляет число X на отрезке A…B, делящее этот отрезок в той же пропорции

  • (подсказка) scale(a,a,b,A,B) == A, scale(b,a,b,A,B) == B, scale((a+b)/2,a,b,A,B) == (A+B)/2

    • (спойлер!) вычесть начало старого отрезка (получится что-то от 0), поделить на длину отрезка (получится что-то от 0 до 10), умножить на длину нового отрезка, прибавить его начало

• 

  • Нарисовать sin(x) на отрезке a≤x≤b, 100 точек в графике, график растянут на всё окно

  • Переписать предыдущее задание с использованием масштабирующей функции scale

    • Попробовать при помощи scale уместить график в прямоугольник заданных размеров

• 

  • К зачёту: Поправить пример:

    • добавить возможность таскать график мышью
    • добавить масштабирование колесом
    • нарисовать оси координат

      • оси координат должны всегда быть видны

Классы

• Можно почитать скетч про классы в Python3

• class someclass():

• класс по имени someclass — это тоже такой объект

  • callable(someclass) == True

  • (type(some) is type) == True"

  • ...такой объект с полями

    • aka static class members в других языках

• класс можно инстанциировать — создать экземпляр класса, объект класса

  • a = someclass()

    • (type(a)) is someclass) == True

  • такой объект — не что иное, как пространство имён
    • TODO вспомним: а чем отличается от словаря?
  • к объекту можно добавлять поля, которых класс изначально не предусматривал

  • при обращении к callable-полям класса через объект мы получаем не само поле, а обёртку над ним, имеющую тип method:

    • def ff(...): ...

    • some.fn = ff

    • type(some.fn) is type(ff) == True

    • type(a.fn) is type(ff) == False

    • вызов метода a.fn(*args) аналогичен вызову функции-поля класса some.fn(a, *args)

• Некоторые методы и поля (вида __blabla__) имеют особенное значение

  • __init__(), aka конструктор

  • __class__ — тип объекта; класс, экземпляром которого он является

  • __str__() — преобразование в строку

  • __eq__() — операция сравнения (==)

    • 'запись на Python' a == 2 'эквивалентна записи' a.__eq__(2)

  • __add__() — операция сложения

  • тысячи их!

  • естественно, их можно переопределять (перегружать)

    • тем самым наделять различные конструкции языка смыслом

    • например, def __eq__(self, ob): ...

  • левые/правые операции

    • если a.__add__(b) возвращает NotImplemented, то Python пытается подставить b.__radd__(a)

• 

  • создать cписок из 10 экземпляров класса Square:

    • содержащего docstring, описывающий, что такое объект класса Square

    • содержащего pygame.Rect

    • с методом show(self, surface), рисующим квадрат на surface

    • с методом ID(self), выдающим строку с описанием объекта

    • содержащего информацию о цвете (pygame.Color)

    • задать каждому координаты, размер, цвет
    • нарисовать, пользуясь методами класса

• 

  • реализовать класс Rect как Square:

    • поддержка сложения, ( вычитания, умножения на число)

    • отображение на экран

  • К зачёту: программа, которая умеет рисовать такие прямоугольники, таскать их по экрану и при переносе одного прямоугольника на другой складывает их

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

    • pygame.Color при сложении довольно быстро дают белый, интереснее брать полусумму цветов (примерно так: self.color//pygame.Color(2,2,2,1)+other.color//pygame.Color(2,2,2,1))

    • при этом вместо двух старых образуется один новый, пока не останется один

День 9 (13 июля)

Классы и перегрузка операций, повторение

Класс «vector» на скорую руку

• сложение векторов и с числом
  • выяснить тип операнда
• умножение на вектор и на число

• Не забыть делать именно вектор, type(self)(...)

Декораторы

• Преобразование списков... а функций?

• Пример — отладочная выдача параметров и возвращаемого значения

  • ручная реализация обёртки
  • обёртка вида fun = wrapper(fun)
  • ⇒ @wrapper

• Пример @integer (одно значение или последовательность)

• Декораторы классов и параметрические декораторы

Вывод изображений и текста в Pygame

• surface

• загрузка изображений, .convert()

• Font, render()
• Ввод текста в Pygame — ??

  • если будет время, pyginput.py

Инкапсуляция, наследование и полиморфизм

• Инкапсуляция — иерархизация пространств имён
• Наследование

• 

  • пример теоретический

  • перепишем последнюю программу с классом Square так, чтобы он был унаследован от pygame.Rect

• Полиморфизм — в питоне сам собой по причине duck typing

• 

  • Класс «окно» — Rect + bg + show() + resize()
  • Класс «окно с рамочкой»
  • Класс «окно с заголовком»
  • Класс «окно с рамочкой и заголовкам» (двойное наследование)
  • как их таскать или ресайзить

Структура игровой программы

• Игровой мир
  • Актёры
  • События с ними и миром
  • Свои единицы измерения
  • Часы (как минимум одни), понятие такта
• Отображение мира
  • Низкоуровневые события (мышь, клавиатура, таймер и т. п.)
  • Координаты на экране
  • Отрисовка
• Один такт работы:
  • Аккумуляция низкоуровневых событий (иногда с некоторой непосредственной реакцией)
  • Превращение их в события мира (в т. ч. выбор актёров, которым они преднахначаются)
  • Обработка событий актёрами
  • Самостоятельная активность актёров и мира
  • Отрисовка результата

• Режимы работы игры (например, intro, gameplay и gameover) — такт выглядит так же, а обработчики разные, => общие названия методов

• Игра в шары,

  • минимум:
    • Несколько шаров
    • Замедление скорости
    • Разлёт при соударении (массы одинаковы, а вот углы!)
    • Бросаем любой (но не несём, т. е. несём не больше 1/5 сек, дальше отпускаем со скоростью, вычисляемой из event.rel)
    • Считаем отскоки до полного останова

    • Конец игры, когда количество бросков > количество отскоков/J

  • Дополнения
    • Крутящиеся шары
    • гравитация
    • Входной и выходной экран, задание J

---

Исключения

• Примеры

• raise

• try … except

• Зачем нужны
• Свои исключения

• TODO

TODO

О рекурсии

• Определение рекурсии
• прямая и непрямая
• рекурсия — это цикл, но
  • своё пространство имён

  • рост пространств имён

• Почему не факториал

• 

  • TODO

---

Здесь пока не разобрано

Неподшитое

• Исключения
• Декораторы, зачем нужны
• Модули как пространства имён
• Ещё классы, объектное планирование и ООП

Понятие оценки сложности алгоритма

• Оценка сложности: количество операция на единицу обрабатываемых данных
  • насколько замедляется алгоритм при количестве данных
    • +1
    • *2
    • → производная!
• Индексирование
• Поиск
• все возможные сочетания

Бинарный поиск и сортировка

• Бинарный поиск и оценка его сложности
• Примитивная сортировка и оценка её сложности
• Сортировка слиянием
• «Быстрая» сортировка, худший случай
• Сортировка кучей

• 

  • бинарный поиск строк в файле
  • сортировка файла слиянием