Конспект курса по Python на Coursera

Конспект лекций по изучению Python от МФТИ и Mail.ru

Ссылка на курс: //www.coursera.org/learn/programming-in-python/

Интерпретатор python3.6.x

 

Начало работы

IDE и редактор

IDE: pyCharm Community Edition (free)

или Sublime Text 3

Правила стиля кода

//www.python.org/dev/peps/pep-0008/

Утилита автостиля

//pypi.python.org/pypi/autopep8

Коллекция модулей python

//github.com/vinta/awesome-python

Базовые типы

Целочисленные

Способ указания больших чисел для читаемости (Python 3)

num = 1_000_000
>>> 1000000

Python поддерживает целые числа неограниченной длины.

Экспоненциальная запись числа

# 1.5 умножить на 10 в степени 2
num = 1.5e2
>>> 150.0

Конвертация типов

int(num) — теряется дробная часть

float(num)

Комплексные числа (complex)

Комплексное число — это выражение вида a + bi, где ab — действительные числа, а i — так называемая мнимая единица, символ, квадрат которого равен –1, то есть i2 = –1. Число aназывается действительной частью, а число b — мнимой частьюкомплексного числа z = a + bi. Если b = 0, то вместо a + 0i пишут просто a. Видно, что действительные числа — это частный случай комплексных чисел.

elementy.ru/posters/fractals/complex_numbers

num = 14 + 1j
print(type(num))
>>><class 'complex'>
print(num.real)
>>>14.0
print(num.imag)
>>>1.0

Модули decimal и fractions

Модуль decimal для работы с вещественными числами с фиксированной точностью

Модуль fractions для работы с рациональными числами (дроби)

Математические операции

Результат деления всегда вещественный

10 / 2
>>> 5.0

ZeroDivizionError

На 0 делить нельзя

Целочисленное деление (//)

10 // 3
>>> 3

Остаток от деления (%)

10 % 3
>>> 1

Побитовые операции

Подробное разъяснение

server.179.ru/tasks/python/2014b1/22-bits.html

 

 

 

 

Битовые операции

Переменные типа int хранятся в двоичной системе счисления
в виде последовательности бит. Биты нумеруются от 0, биты будем
записывать справа налево (то есть бит с номером 0 будет
записан самым правым, а самый старший бит — самым левым).

a = 0   # 0b0
a = 1   # 0b1
a = 2   # 0b10
a = 10  # 0b1010
a = 255 # 0b11111111

Например, если a = 10, то в битовой записи
a биты с номерами 1 и 3 равны 1,
а остальные биты равны 0.

В программах на языке Питон числа в двоичной системе счисления можно записывать
в виде последовательностей из 0 и 1, предваряя их префиксом 0b.
Например, допустимо присваивание a = 0b101.

Для двух переменных одинакового скалярного типа
определены битовые операции:
& битовое И (AND)
| битовое ИЛИ (OR)
^ битовое ИСКЛЮЧАЮЩЕЕ ИЛИ (XOR)
~ битовое ОТРИЦАНИЕ (NOT) — унарная операция.

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

a = 5     # 0b101
b = 6     # 0b110
c = a & b # 0b100 == 4
d = a | b # 0b111 == 7
e = a ^ b # 0b11 == 3
f =  ~ a  # 0b1...11111010 == -6

Битовое отрицание числа (величина f
в последнем примере) — это число, полученное
из исходного заменой всех нулей на единицы и наоборот.

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

Есть еще две операции, работающие с битами: это битовые сдвиги.
Их два: сдвиг влево и вправо.
Оператор a >> n возвращает число,
которое получается из a сдвигом всех бит на
n позиций вправо, при этом самые правые
n бит отбрасываются.
Например:

a = 43      # 0b101011
b = a >> 1  # 0b10101 == 21
c = a >> 2  # 0b1010 == 10
d = a >> 3  # 0b101 == 5
e = a >> 5  # 0b1 == 1

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

Аналогично, битовый сдвиг влево на n
бит равносилен (для положительных чисел) умножению на
2n и осуществляется при помощи оператора <<:

a = 5       # 0b101
b = a << 1  # 0b1010 == 10
c = a << 2  # 0b10100 == 20
d = 2 << 3  # 0b101000 == 40

Упражнения

Во всех упражнениях (если не оговорено иное) нельзя использовать
арифметические операторы сложения, умножения, вычитания,
деления, взятия остатка.
Вместо них используем побитовые операторы &, |,
~, ^, <<, >>.

A: 2k

Дано число k, 0≤k≤31. Запишите число 2k,
то есть число, у которого k-й бит равен 1, а остальные — нули.

ВводВывод
8
256

B: 2k+2n
Даны два неравных целых неотрицательных числа: k и n.
Вычислите 2k+2n.

ВводВывод
0 1
3

C: Обнулить последние биты
Дано целое число A и целое неотрицательное число число k. Обнулите у числа A его последние k бит и выведите результат.

ВводВывод
3 1
2

D: Установить бит
Дано целое число A и целое неотрицательное число k.
Выведите число, которое получается из числа A установкой значения
k-го бита равному 1.

ВводВывод
12 1
14

E: Инвертировать бит
Дано целое число A и целое неотрицательное число k.
Выведите число, которое получается из числа A инвертированием
k-го бита.

ВводВывод
15 2
11

F: Значение бита
Дано целое число A и целое неотрицательное число k.
Выведите значение k-го бита числа A, то есть 0 или 1.

ВводВывод
179 0
1

G: Обнулить бит
Дано целое число A и целое неотрицательное число k.
Выведите число, которое получается из числа A установкой значения
k-го бита равному 0.

ВводВывод
14 1
12

H: Обрезать старшие биты
Дано целое число A и натуральное число k.
Выведите число, которое состоит только из k последних бит числа A
(то есть обнулите все биты числа A, кроме последних k).

В этой задаче можно использовать сложение и вычитание.

ВводВывод
126 3
6

I: Битовое представление
Дано натуральное число. Выведите его
битовое представление.

ВводВывод
179
10110011

J: Быстрое вычисление
Даны числа \(a\) и \(b\). Используя только битовые операции
и операции сложения и вычитания вычислите число
\(x = (36a + [\frac{b}{16}]) \bmod 32\). Выведите результат на экран.

ВводВывод
1 2
4
2 16
9

K: Быстрое умножение
Даны числа \(a\) и \(b\). Не используя операции *, /, %
вычислите их произведение.

ВводВывод
2 3
6

L: Заменить 1 на 0
Дано число, замените первую справа единицу его двоичной записи на ноль.

Разрешается использовать битовые и арифметические операции.
Запрещается использовать ветвления и циклы.

ВводВывод
1
0
6
4

M: Замените 0 на 1
Дано число, замените первый справа ноль его двоичной записи на единицу.

Разрешается использовать битовые и арифметические операции.
Запрещается использовать ветвления и циклы.

ВводВывод
0
1
5
7

N: Шифрование перемешиванием
Дано число, переставьте его соседние биты
(то есть поменяйте местами биты с номерами 0 и 1, 2 и 3, 4 и 5 и т.д.).
Разрешается использовать битовые операции. Запрещается использовать
арифметические операции, ветвления, циклы.

Общее число бит в числе не превосходит 32.

ВводВывод
78
141

O: Контрольная сумма BSD
В операционной системе BSD используется следующий алгоритм вычисления контрольных сумм.

Контрольная сумма хранится в двубайтовой целочисленной переменной \(h\)
(то есть хранятся только два байта числа, все вычисления выполняются
в кольце вычетов по модулю \(2^{16}\). С самого начала эта переменная
равна 0.

Далее с каждым считанным байтом \(c\) выполняются следующие операции.

Значение \(h\) циклически сдвигается вправо (то есть последний бит
становится первым, не забываем, что число \(h\) является 16-битным.
К значению \(h\) прибавляется значение считанного байта (то есть
ASCII-кода его), от результата берется последние 16 бит.

Вот пример вычисления контрольной суммы для строки “AND“

h = 0b0000000000000000 - начальная инициализация
h = 0b0000000000000000 - циклический сдвиг вправо
h = 0b0000000001000001 - добавили 65 - ASCII-код A
h = 0b1000000000100000 - циклический сдвиг вправо
h = 0b1000000001101110 - добавили 78 - ASCII-код N
h = 0b0100000000110111 - циклический сдвиг вправо
h = 0b0100000001111011 - добавили 68 - ASCII-код D

Результат равен 16507. Обратите внимание, что после сложения результат
может оказаться более чем 16-битным, и требуется оставить только последние 16 бит.

В системе Linux можно проверить результат работы при помощи
консольной команды sum:

$ echo -n "AND" | sum
ВводВывод
AND
16507

P: Adler-32
В алгоритме Adler-32 вычисляются две 16-битные суммы: A — сумма всех байт входных данных и
B — сумма всех промежуточных
значений суммы A. При этом начальное значение A инициализируется числом 1,
а начальное значение B — числом 0. Все вычисления проводятся по модулю
65521 (максимальное простое, меньшее \(2^{16}\)).

Таким образом, если файл состоит из байт \(d_1\), \(d_2\), …, \(d_n\), то
\(A = 1 + d_1 + d_2 + … + d_n \bmod 65521\),
\(B = (1 + d_1) + (1 + d_1 + d_2) + … + (1 + d_1 + … + d_n) \bmod 65521\).

Итоговым значением контрольной суммы является одно 32-битное число, в котором в старших 16 битах записано значение B, в младших 16 битах — значение A.

Вычислите контрольную сумму Adler-32 для данной строки.

ВводВывод
AND
27656404

Q: FNV-1 хеш-функция
Алгоритм хеширования FNV-1 устроен следующим образом.
Используется 64-битная арифметика. Переменная \(h\)
хранит текущее значение хеш-функции. Начальное значение \(h\) равно
14695981039346656037. На каждом шаге значение \(h\) домножается на
1099511628211, затем делается побитовое исключающее ИЛИ с очередным
байтом входных данных. Все вычисления проводятся с 64-битными целыми
числами, поэтому после выполнения всех операций нужно брать младшие
64 бита результата.

Вычислите значение хеш-функции FNV-1 для данной строки.

ВводВывод
AND
15595937027161525016

R: PJW-32 хеш-функция
Алгоритм хеширования PJW-32 устроен следующим образом.
Используется 32-битная арифметика.
Переменная \(h\) хранит текущее значение хеш-функции.
Далее для каждого считанного байта \(с\) сообщения выполняются следующие операции:

1. Значение \(h\) сдвигается на 4 бита влево, к нему прибавляется (арифметическим суммированием)
значение \(c\).

2. Если хотя бы один из 4 старших битов \(h\) равен 1, то старшие 4 бита сдвигаются
на 24 бита вправо, и выполняется операция побитового исключающего ИЛИ со значением \(h\).
После чего обнуляются старшие 4 бита значения \(h\).

Все операции проводятся с 32-битными числами, то есть берутся 32 младших бита
результата.

ВводВывод
AND
17956


Z*: SHA-1
SHA-1 — алгоритм, вычисляющий криптографические контрольные суммы
от произвольной битовой последовательности. Результатом вычисления функции
SHA-1 является 160-битный хэш, который как правило записывается в виде
40 16-ричных цифр. Хэш-функция является односторонней, то есть по значению
хэш-функции тяжело подобрать какую-либо исходную последовательность, имеющую
такое значение хэш-функции.

Изучите описание алгоритма вычисления контрольной суммы SHA-1 по
материалам википедии
и реализуйте данный алгоритм.

Программа получает на вход одну строку и должна вывести значение SHA-1 суммы
для этой строки. Исходная последовательность байт для вычисления SHA-1 суммы
состоит только из символов этой строки, так в примере ниже входная строка
имеет длину 3 байта = 24 бита. Добавлять к строке символ \n и иные спецсимволы не нужно.

Программа должна вывести 40 16-ричных цифр, цифры af
записываются в строчном регистре.

ВводВывод
sha
d8f4590320e1343a915b6394170650a8f35d6926

Обратите внимание, вам достаточно реализовать чуть более простой вариант
SHA-1, который работает только в случае, когда исходное сообщение состоит из целого
числа байт, в то время как спецификация SHA-1 описывает алгоритм, который получает
на вход последовательность бит произвольной длины, не обязательно кратной 8.

Для тестирования можно использовать стандартную команду sha1sum
из дистрибутива Linux. Например, ответ на тест из условия получен при помощи
команды echo -n "sha" | sha1sum.

 

 

 

 

побитовые операции python

Степень и корень

** — возведение

** 0.5  — Корень

Перестановка (сравнение двух числе)

a, b = b, a

Двойное присваивание x = y = 0 (или [])

x = y = 0
x+=1
>>>x
1
>>>y
0

Если список

x = y = []
x.append(1)
y.appedn(2)
>>>x
(1,2)
>>>y
(1,2)

Множественное сравнение

x = 2
print(1 < x < 3)
>>>True

Строки

Экранирование спецсимволов в Python

strint_is = "Курс про \"Python\" на \"Coursera\""
>>>string_is
Курс по "Python" на "Coursera"

Сырые строки

string_is = r"Файл на диске c:\\"
>>>string_is
Файл на диске c:\\

Форматирование строк

tpl = "%s - главное достоинство программиста. (%s)"
tpl % ("Лень", "Larry Wall")

docs.python.org/3/library/string.html#format-specification-mini-language

"{} не лгут, но {} пользуются формулами. ({}).format("Цифры", "лжецы", "Robert A. Heinlein"

f-строки, Python >=3.6

subject = "оптимизация
author = "Donald Knuth"
f"Преждевременная {subject} - корень всех зол. ({author})

Модификаторы форматирования

num = 8
f"Binary: {num:#b}"
>>>'Binary: 0b1000'

Ограничение периода дробных чисел

num = 2 / 3
print(f"{num:.3f}")

Байтовые строки

b_string = b"Hello"

Байтовые строки, кодирование кириллических символов, utf-8

encode python utf-8

Декодирование байтов в строку

decoding_string = encoded_string.decode()

Условный оператор if, elif, else

Аналог тернарного оператор

one = 5
two = 0
what = "Argentina" if one > two else "Jamaica"