Примерный распорядок дня
- 10:00-10:30 — повторение и ответы на вопросы
- 10:30-13:30 — лекции+семинары
- 13:30-14:00 — обед
- 14:00-16:00 — практика
Предполагается последовательно проходить этот план, расставляя пометки, сколько удалось сделать за день.
— лабораторные работы / семинары (воспроизведение доски или тривиальные упражнения) 
— практические задания (решения выкладываются сюда)
Рекомендации по самостоятельному изучению
Д/З: установить Python и Geany (можно другие IDE) дома, если есть цель научиться чему-то ненулевому
Д/З: Щёлкать tutorial (определяем, кому интересно)
Contents
День 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 *
-
ручное развёртывание бинарного возведения в степень (например, как получить 321?)
Условные операторы и выражения
- логический тип, операции сравнения
- условное выражение a if b else c
- базовый if
- форматирование отступами
- if / elif* / else
-
- ввести два числа, вывести наибольшее
- условным выражением
- условным оператором
- ввести два числа, вывести, больше, меньше или равно первое второму
- ввести три числа, проверить неравенство треугольника (вложенный if)
- ввести два числа, вывести наибольшее
-
- ввести три числа, найти наибольшее (вложенный if)
- условным выражением
- условным оператором
- ввести три числа, найти наибольшее (вложенный if)
Алгебра логики
- пустой объект, примеры
⇒ любое выражение в условии
- таблицы истинности
- логические операции Python, их таблицы истинности
- примеры
-
ввести три числа, проверить неравенство треугольника (с помощью or)
-
квадратное уравнение с ненулевым a
Цикл 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 (транспонирование матрицы)
- Случайное число на отрезке A…B
-
в каждой функции, которую пишете, краткий 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) параметров, то это:
- имя выходного файла
- имя,
- фамилия
- возраст (целое число
- средний балл (вещественное)
- сериализовать эти данные в файл;
- То же, что и выше, но с помощью 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>
- в Linux (как и в любой разумной системе) устанавливать что-то прямо в систему может только администратор
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 уместить график в прямоугольник заданных размеров
-
К зачёту: Поправить пример:
- добавить возможность таскать график мышью
- добавить масштабирование колесом
- нарисовать оси координат
- оси координат должны всегда быть видны
- подписать оси координат и формулу сверху
TODO
Построение графиков черепахой (решили не черепахой, а PyGame)
-
Попробовать нарисовать черепахой график функции y=sin(x) в диапазоне -4<=x<=5 (использовать абсолютные координаты, то есть функцию goto(x,y))
- Осознать, что:
- График — это не кривая, а ломаная (передвижение черепашки от точки к точке по прямой)
- Чем больше точек в этой ломаной, тем более она похожа на график, пускай точек будет N=100
- Если рисовать синус, как он есть, получается еле заметный червячок
- Чтобы график было хорошо видно, y-координаты надо как-то увеличивать, например, умножать на 100, а x-коордмнаты — на 50
-
Нарисовать черепахой график функции y=sin(x) из ста точек в диапазоне A<=x<=B, где A и B вводятся и поначалу равны, как и раньше, -4 и 5
- Осознать, что
- У забора 100 досок и 99 щелей (N и N-1). У графика N точек и N-1 отрезок. Это значит, что в цикле, который генерирует очередное X для того, чтобы вычислить sin(x), самое первое значение должно быть A, а самое последнее — B, и всего таких значений должно быть N
- Написать для этого функцию diap(N,i,A,B):
- A и B — диапазон
- N — общее количество точек, включая первую и последнюю.
- i — номер очередной точки
- возвращать функция должна число в диапазоне от A до B, причём при i==0 — A, а при i==N-1 (да-да, не N же!) — B
Нарисовать черепахой график функции y=sin(x) из ста точек в диапазоне A<=x<=B, где A и B вводятся, и график получается разумный при abs(B-A)<200 (дальше частокол выйдет)
Немного про eval()
Осознать природу функции eval() https://docs.python.org/3/library/functions.html?highlight=eval#eval
- Упражнение: ввести *в виде строки* произвольную формулу от x (в ней могут встречаться функции из math), ввести x, вывести (с помощью eval()) результат её вычисления
- Решить предыдущее упражнение, написав *функцию* f(x): , при этом сама программа должна выглядеть примерно так:
formulae = input() x = float(input()) print(f(x))
(очевидно, в этой функции будет использовано глобальное имя formulae и eval())
Рисуем график дальше
- Вспомнить про аффинные преобразования координат. Из них нам нужно движение и перенос, а поворот не нужен. Если не вспоминается — не страшно. Общая идея
- Есть вещественное число X на отрезке A…B. Нам нужно получить число P на отрезке Q…R, которое делит это отрезок в той же пропорции
- Записать пропорцию и вывести из неё формулу P=что-то-там-от-X
- Написать функцию scale(L,M,X,Q,R), которая по числу X на отрезке L…M вычисляет число P на отрезке Q…R, делящее этот отрезок в той же пропорции
- scale(L,M,L,Q,R) == Q, scale(L,M,M,Q,R) == R, (подсказка) scale(L,M,(L+M)/2,Q,R) == (Q+R)/2
- (спойлер!) вычесть начало старого отрезка (получится что-то от 0), поделить на длину отрезка (получится что-то от 0 до 10), умножить на длину нового отрезка, прибавить его начало
- Осознать, что это более общий вариант функции diap()
- Переписать «график синуса» с использованием scale() вместо diap()
- Переписать его далее, с использованием scale() вместо тупого умножения X и Y кооринат (размер экрана мы, допустим, знаем, что-то типа -400,400/-300,300 или как-то так, проверить)
- график наконец-то будет располагаться по центру
- Попробовать вводить не только диапазон, но и саму формулу (см. выше упражнение про функцию f()), поначалу эта формула == "f(x)", с ней должно работать хорошо
- Осознать, что
Область значений sin(x) — -1…1, а других формул — нет
- Для того, чтобы нарисовать график произвольной функции на отрезке, надо знать диапазон её значений на этом отрезке
- этот диапазон использовать в scale() при вычислении y-координаты очередной точки на экране
- Можно, например, запустить цикл с вычислением функции на всех точках, но не рисовать ничего, а только искать минимум и максимум значений (Q и R), а потом уже запустить его ещё раз и рисовать, зная Q и R
- Переписать программу так, чтобы
- В цикле создавался список значений функции на отрезке (назовём его g[])
- Тогда минимум и максимум — это просто min(g) и max(g) (спасибо, Питон!)
- Можно и список x-ов тоже генерировать, чобы два раза не вычислять
- Украсить
- Нарисовать оси координат
- Написать, где X, где Y
- Написать, что за функция
О рекурсии
- Определение рекурсии
- прямая и непрямая
- рекурсия — это цикл, но
- своё пространство имён
рост пространств имён
- Почему не факториал
-
TODO
Здесь пока не разобрано
Неподшитое
- Исключения
- Декораторы, зачем нужны
- Модули как пространства имён
- Классы, …, перегрузка операций
- Ещё классы, объектное планирование и ООП
Понятие оценки сложности алгоритма
- Оценка сложности: количество операция на единицу обрабатываемых данных
- насколько замедляется алгоритм при количестве данных
- +1
- *2
- → производная!
- насколько замедляется алгоритм при количестве данных
- Индексирование
- Поиск
- все возможные сочетания
Бинарный поиск и сортировка
- Бинарный поиск и оценка его сложности
- Примитивная сортировка и оценка её сложности
- Сортировка слиянием
- «Быстрая» сортировка, худший случай
- Сортировка кучей
-
- бинарный поиск строк в файле
- сортировка файла слиянием